The Bellman Equations: Value as a Self-Consistent Recursion

The recursive insight

We defined value as an expected return — a sum stretching to the horizon. Computing that sum directly looks hopeless. The Bellman equations rescue us with one observation we already met in return decomposition: the return is this step's reward plus the discounted return of the next state. Apply the expectation and value inherits the same shape — today's value is one reward plus the discounted value of where you land. Value becomes self-referential, and that recursion is something we can actually solve.

The Bellman expectation equation

The Bellman expectation equation writes the value of a policy in terms of itself. For the state-value function: V_π(s) equals the expected immediate reward plus γ times the expected V_π of the next state, where the expectation is over the policy's action and the environment's transition dynamics. The same holds for Q_π. These equations are consistency conditions: a correct value function must satisfy them everywhere.

The Bellman expectation equation: a policy's value written in terms of itself — reward now plus the discounted value of the next state.

Read the other direction, they give an algorithm. Start with any guess for V, repeatedly replace each V(s) with 'reward + γ · (current estimate of next V),' and the estimates converge to the true V_π. That is policy evaluation, the foundation of dynamic programming.

Bootstrapping: learning a guess from a guess

Bootstrapping is what makes Bellman updates so efficient and so distinctive. Instead of waiting for an entire episode to finish and summing the actual return (as Monte Carlo methods do), we update a value using our current estimate of the next state's value. We learn a guess from a guess. It introduces some bias early on but lets the agent learn from incomplete episodes and propagate information quickly — the central idea behind temporal-difference learning.

The Bellman optimality equation

The expectation equation describes a policy. The Bellman optimality equation describes the best one. It replaces 'average over the policy's actions' with 'take the maximum over actions': the optimal value of a state is the best action's immediate reward plus γ times the optimal value of the next state. That single max is the difference between evaluating what you do and finding what you should do.

The Bellman optimality equation: swap 'average over the policy' for 'take the best action,' defining the optimal value V*.

This equation defines the optimal value function V* and Q*: they are its unique solution. Once you have Q*, the best policy is simply to act greedily with respect to it — no further planning required.

Why this matters: fixed points and operators

Both Bellman equations can be viewed as an operator that takes a value function and returns an improved one — the Bellman backup operator. Applying it repeatedly is a contraction: estimates get steadily closer to the true value and converge to a unique fixed point. That guarantee is why so many algorithms — value iteration, Q-learning, DQN — are 'just' the Bellman optimality equation turned into an update rule.

1. Write value as reward-now plus discounted value-next (the recursion).
2. For evaluation, average over the policy's actions → Bellman expectation equation.
3. For optimality, take the max over actions → Bellman optimality equation.
4. Turn either into a repeated update; it converges to the true (or optimal) value.

# One sweep of the Bellman expectation backup for V (tabular policy evaluation)
def bellman_backup(V, states, actions, P, R, pi, gamma=0.99):
    newV = {}
    for s in states:
        newV[s] = sum(
            pi[s][a] * sum(P[s][a][s2] * (R[s][a][s2] + gamma * V[s2])
                           for s2 in states)
            for a in actions)
    return newV   # repeat until V stops changing

Recap