Expected Free Energy Action Selection

When to Use

• An agent must choose among candidate next-states without a fixed reward function, where exploration and exploitation must both emerge naturally from the agent's own uncertainty.
• You are replacing epsilon-greedy, UCB, or Thompson-sampling heuristics with a principled Bayesian alternative whose exploration drive vanishes automatically as knowledge accumulates.
• Agents operate in a shared environment (stigmergic medium, graph, map) and can incorporate social signals (pheromone, shared traces) as a second belief-update channel.

NOT for:

• Bandit problems with i.i.d. rewards and no spatial structure — simpler Thompson sampling is sufficient there.
• Environments where the state space is continuous and high-dimensional; this formulation assumes discrete nodes with tractable per-node Beta posteriors.
• Settings requiring hard guarantees on regret bounds; EFE is principled but does not come with PAC or UCB-style worst-case guarantees.

Core Concepts

Beta distribution belief per node. Each node n carries a belief NodeBelief(alpha, beta) initialised to Beta(1, 1) (maximum ignorance). After visiting n and observing a binary outcome (found something / found nothing), the posterior updates:

• found: alpha += learning_rate
• nothing: beta += learning_rate

This gives E[p_n] = alpha / (alpha + beta) and Var[p_n] = alpha*beta / ((alpha+beta)^2 * (alpha+beta+1)).

Expected Free Energy G(n). The scalar the agent minimises when choosing where to go next:

G(n) = w_prag * pragmatic(n) + w_epist * epistemic(n)

pragmatic(n)  = -E[p_n] * max(0, 1 - resolution_damping * res_n)
epistemic(n)  = -Var[p_n] * novelty(n)

Lower (more negative) G means more attractive. The pragmatic term rewards going where the agent believes something rewarding will be found, damped by a resolution signal that prevents pile-on. The epistemic term rewards going where uncertainty is highest and the node is undervisited.

Softmax action selection with inverse temperature gamma. Candidates are ranked by softmax(-gamma * G(n)). Higher gamma sharpens the distribution toward the EFE minimum; lower gamma makes selection nearly uniform. This is not epsilon-greedy: the exploration probability is a smooth function of the belief state, not a hyperparameter.

Precision adaptation. After each observation the agent records surprise S = -log p(outcome | belief). A sliding window mean of recent surprise is compared to the neutral threshold ln(2) ≈ 0.693 (surprise of a uniform Beta observing either outcome). High mean surprise increases w_epist (explore more); low mean surprise increases w_prag (exploit more). The weights therefore track whether the model is currently well-calibrated.

Epistemic scan and epistemic teleportation. Two mechanisms that prevent local optima from hiding globally unseen nodes:

• Epistemic scan (step > 3): with probability len(unseen) / total_nodes, jump to the highest-uncertainty unseen node. Probability decays to zero once all nodes have been visited at least once.
• Epistemic teleportation (triggered when max |EFE| of all local neighbors < teleport_threshold): jump globally to the node with the highest Var[p] * novelty score, but only if it is 1.5x more informative than the best local neighbor.

Implementation Pattern

The following pseudocode maps directly onto the SOMA implementation in soma/generative_model.py and soma/active_inference_agent.py.

# ---- Per-agent initialisation ----
model = GenerativeModel(
    w_pragmatic=1.0,          # exploit weight (self-adapting)
    w_epistemic=1.5,          # explore weight (self-adapting)
    gamma=4.0,                # softmax inverse temperature
    learning_rate=1.0,        # Beta update step size
    social_learning_rate=0.1, # pheromone → belief transfer rate
    precision_adapt_rate=0.05,
    rng_seed=seed,
)

# ---- Per step ----
def step(agent, medium):
    # 1. Social learning: pheromone updates beliefs before deciding
    neighborhood = medium.sense(agent.position, radius=receptive_radius)
    model.update_from_pheromone(neighborhood, max_pheromone=max(neighborhood.values()))

    # 2. Compute EFE for each neighbor
    neighbors = list(graph.neighbors(agent.position))
    resolution_map = {n: medium.resolution.get(n, 0.0) for n in neighbors}

    efe_scores = {
        n: model.compute_efe(n, resolution_map[n], resolution_damping)
        for n in neighbors
    }

    # 3. Softmax selection
    #    select_action() returns (selected_node, action_type, efe_scores)
    selected, action_type, _ = model.select_action(
        neighbors=neighbors,
        resolution_map=resolution_map,
        resolution_damping=medium.resolution_damping,
    )

    # 4. Epistemic scan: stochastic jump to unseen nodes
    #    Implemented inside _decide_move() in ActiveInferenceAgent:
    #    scan_prob = len(unseen) / len(all_nodes)
    #    if rng.random() < scan_prob: target = highest-uncertainty unseen node

    # 5. Move, do work, observe
    agent.position = selected
    outcome = do_work(selected)     # returns {found_something: bool, quality: float}

    # 6. Bayesian belief update
    surprise = model.update_belief(selected, outcome["found_something"])
    # found_something=True  → alpha += 1
    # found_something=False → beta  += 1

    # 7. Precision adaptation (after each step)
    model.adapt_precision()
    # High recent surprise → w_epist up, w_prag down
    # Low  recent surprise → w_prag up, w_epist down

# ---- EFE formula (from GenerativeModel.compute_efe) ----
def compute_efe(node_id, resolution_level, resolution_damping):
    belief = model.get_belief(node_id)
    damping  = max(0.0, 1.0 - resolution_damping * resolution_level)
    pragmatic = -belief.expected_value * damping          # exploit
    epistemic = -belief.uncertainty * model.novelty(node_id)  # explore
    return w_pragmatic * pragmatic + w_epistemic * epistemic

# ---- Novelty (inverse visit count) ----
def novelty(node_id):
    visits = visit_counts.get(node_id, 0)
    return 1.0 / (1.0 + visits)     # 1.0 for unvisited, decays toward 0

# ---- Softmax (from GenerativeModel.select_action) ----
values = np.array([-gamma * efe_scores[n] for n in neighbors])
values -= values.max()              # numerical stability
probs  = np.exp(values) / np.exp(values).sum()
selected = rng.choice(neighbors, p=probs)

# ---- Cloning with mutation (immune selection hook) ----
child_model = model.clone(mutation_scale=0.1, rng_seed=seed)
# Inherits beliefs and visit_counts; mutates w_pragmatic, w_epistemic, gamma

Default hyperparameters (SOMA Week 2, validated on 20-trial benchmark):

Parameter	Default	Effect of increasing
w_pragmatic	1.0	More exploitation of known-good nodes
w_epistemic	1.5	More exploration of uncertain nodes
gamma	4.0	Sharper selection toward EFE minimum
learning_rate	1.0	Faster belief update per observation
social_learning_rate	0.1	More influence from neighbors' pheromone
teleport_threshold	0.01	Fewer epistemic teleports
precision_adapt_rate	0.05	Faster precision weight drift

Benchmark result: switching from epsilon-greedy (Week 1) to EFE action selection (Week 2) raised task-completion rate from 50% to 100% across 20 trials and closed the isolated-node coverage gap entirely via the epistemic scan mechanism.

Key References

• Friston, K. (2010). "The free-energy principle: a unified brain theory?" Nature Reviews Neuroscience, 11(2), 127–138. — Foundational derivation of EFE from variational inference; establishes the pragmatic/epistemic decomposition.
• Parr, T., & Friston, K. (2019). "Generalised free energy and active inference." Biological Cybernetics, 113(5–6), 495–513. — Extends EFE to policy selection; shows how precision-weighting implements attention.
• Da Costa, L., Parr, T., Sajid, N., Veselic, S., Neacsu, V., & Friston, K. (2020). "Active inference on discrete state-spaces: A synthesis." Journal of Mathematical Psychology, 99, 102447. — Practical discrete-state formulation closest to this implementation.
• SOMA soma/generative_model.py + soma/active_inference_agent.py — Reference implementation: GenerativeModel, NodeBelief, ActiveInferenceAgent. Key entry-points: compute_efe(), select_action(), update_belief(), adapt_precision(), highest_uncertainty_node().