The Bellman Equation

From the previous topics: an MDP (the board game, topic 196) hands out rewards as you play, and the value of a state (topic 198) is the expected discounted sum of all rewards from there on:

G_t = R_{t+1} + γR_{t+2} + γ²R_{t+3} + …

That definition is honest but painful: the horizon is infinite, the die of the world is random, and the policy rolls its own dice too.

Richard Bellman's answer: no. You never need the whole sum at once. Value obeys a one-step recursion — and that recursion is the hinge on which all of reinforcement learning swings.

This topic is that recursion, in two flavors (with a policy, and best-case), plus the mathematical promise that repeatedly applying it converges.

Bellman's insight (the principle of optimality) is that an optimal plan contains optimal sub-plans: if the best road trip from Los Angeles to New York passes through Denver, then the part of the route beyond Denver must itself be the best route from Denver to New York. Otherwise you would just swap in something better and have a better LA→NY trip — contradiction.

In RL, this turns the intimidating infinite sum into a one-step recursion:

v_π(s) = Σ_a π(a|s) Σ_{s',r} P(s',r|s,a) [ r + γ v_π(s') ]

That is the Bellman expectation equation. Read it out loud, slowly:

Unpack the pieces (each one you have already met):

• π(a|s) — the policy's dice: how often you play each action here (topic 197).
• P(s',r|s,a) — the world's dice: the chance that action a in state s yields reward r and lands you in s' (topic 196).
• r — the cash you collect this step.
• γ v_π(s') — the whole rest of your future, compressed into one number: the value of where you land, taxed by the discount.

The magic is the self-reference: v_π appears on both sides. The value of here is defined in terms of the value of there — by the exact same rule. An infinite horizon, handled by one step of arithmetic at a time.

Carry one analogy through the topic: a hiking trail where every junction has a signpost.

Each signpost states its own value the same way:

code
Copy
  you ──2 km──► post A ──3 km──► post B ──1 km──► summit (0 km)
              "5 + B says"     "1 + 0"

  B is known directly: B = 1.
  A = 3 + B  =  3 + 1 = 4.
  You = 2 + A = 2 + 4 = 6 km.

Nobody walked the whole mountain. Each sign just looked one step at the next sign — and the answers chained backward into a complete distance map.

• The recursion terminates because the trail ends (a terminal state with value 0 — like the summit).
• With a discount γ, each signpost says "miles to next sign + 0.9 × what the next sign says" — the future gets gently shrunk as it propagates back.
• Replace "miles" with "expected reward-to-come" and you have Bellman exactly.

Every algorithm later in this phase (TD, Q-learning, DQN) is some way of building the signpost network from real walks, even when nobody drew the map of the mountain.

Tiny numbers, matching the code block below. A corridor of states 0, 1, 2, terminal 3 (value 0 by definition — the trail ends). Moving right from state 2 pays +10 and ends the episode. γ = 0.9.

Solve it forward-looking but backward-computing, like the signposts:

• State 2: go right → 10 + 0.9 × V(3) = 10 + 0 = 10. Go left → −1 + 0.9 × 10 = 8. Take the max: V*(2) = 10.
• State 1: go right → 2 + 0.9 × V*(2) = 2 + 9 = 11. Go left (stay put, zero reward) → 0 + 0.9 × 11 = 9.9. So V*(1) = 11.
• State 0: go right → 1 + 0.9 × V*(1) = 1 + 9.9 = 10.9. Go left (stay put, losing 1) → −1 + 0.9 × 10.9 ≈ 8.8. So V*(0) = 10.9.

Result: V* = [10.9, 11.0, 10.0, 0.0]. One formula, applied at every state, produced the entire price list — no infinite sums written anywhere.

Notice the interesting bit: state 1 is worth more than state 2 (11 vs 10), because it collects its +2 on the way — being slightly further from a big reward can still be better if the tolls going there pay. Bellman arithmetic catches that automatically.

The code performs this exact computation: initialize every value to 0, then repeatedly sweep a max backup over all states (that is the Bellman optimality operator, next section) until the numbers stop moving.

# states 0..3, terminal state 3 has V=0; deterministic example
rewards = {(0,'r'):1, (0,'l'):-1, (1,'r'):2, (1,'l'):0, (2,'r'):10, (2,'l'):-1}
nxt     = {(0,'r'):1, (0,'l'):0, (1,'r'):2, (1,'l'):1, (2,'r'):3, (2,'l'):2}
gamma   = 0.9
V = [0.0, 0.0, 0.0, 0.0]

for _ in range(50):                      # Bellman backups to convergence
    newV = V[:]
    for s in range(3):                   # state 3 is terminal
        best = -1e9
        for a in ('r','l'):
            s2 = nxt[(s,a)]
            q  = rewards[(s,a)] + gamma * V[s2]   # BOE max backup
            best = max(best, q)
        newV[s] = best
    V = newV
print("V* =", [round(v,3) for v in V])

There are two Bellman equations, and confusing them is the most common beginner error.

1. Bellman Expectation Equation (BEE) — holds for a given policy π. It averages over actions with weights π(a|s):

v_π(s) = Σ_a π(a|s) Σ_{s',r} P(s',r|s,a) [r + γ v_π(s')]

Use it to evaluate: "how good is this specific policy?"

2. Bellman Optimality Equation (BOE) — holds for the best achievable value. Replace the policy-weighted average with a max:

v_*(s) = max_a Σ_{s',r} P(s',r|s,a) [r + γ v_*(s')]

q_*(s,a) = E_{s'}[ r + γ max_{a'} q_*(s',a') ]

The max is the pivot of the whole field:

• Policy iteration (topic 197's evaluate-and-rewrite loop) uses the expectation form.
• Value iteration and Q-learning use the optimality (max) form — which is exactly why Q-learning is off-policy: backing up through the max never requires knowing which policy generated the data.

The action-value version is the one algorithms actually implement:

q_π(s,a) = Σ_{s',r} P(s',r|s,a) [ r + γ Σ_{a'} π(a'|s') q_π(s',a') ]

Look only at the bracket: one step of reward, then how the next state's value is chosen. That single choice generates the whole value-based family:

• Policy evaluation: plug in a fixed π, average over a' with π(a'|s'), and iterate.
• SARSA (on-policy TD control): use the action π will actually take at s'.
• Q-learning (off-policy TD control): use max_{a'} at s' — topic 201.

That is the entire difference between famous algorithms: the same equation, differing only in the next-state term. Keep it as your mental index card for this phase.

Two more pieces make this topic complete.

The Bellman error. For a candidate value function, define the one-step inconsistency:

δ = r + γV(s') − V(s)

If V were the true value, every signpost would agree with the next one and δ would be 0 everywhere. TD learning (topic 200) literally is estimating this error from samples and stepping to reduce it. δ doubles as the TD residual and the gradient signal that trains most critic networks.

Why iterating is guaranteed to work. Mathematically, the Bellman operator is a γ-contraction in the max-norm: apply it once, and the distance between any two value guesses shrinks by at least a factor γ < 1. Two signposts that disagree can only disagree less after each sweep. Banach's fixed-point theorem then guarantees:

• A unique solution v_π exists.
• Iterating the backup converges to it from any initialization — even the all-zeros guess in the code above.

This is the formal reason value iteration and policy iteration are guaranteed to work on finite MDPs.

Open the source of any value-based agent and you will find this equation wearing a trench coat:

• DQN's loss (topic 202) is [r + γ max_{a'} Q(s',a') − Q(s,a)]² — the squared Bellman error for Q, minimized by SGD.
• AlphaZero's MCTS backups (real-world example below) mix immediate evaluation with bootstrapped subtree value — Bellman-style propagation through a search tree, iterated across self-play.
• Actor-critic critics (topic 204) regress on TD targets r + γV(s') — again one Bellman step.
• The n-step and GAE estimators inside PPO (topics 203–205) are just longer signpost chains: two steps, three steps, λ-blends — all built from the same backup.

So: Bellman is not history-book elegance. It is the arithmetic primitive every modern RL loop runs on, and the contraction property is why the loops settle instead of spinning forever.