RobotGuide
Foundations/The Bellman Equation: Why V Is a Fixed Point and Why Iteration Must Converge

Foundations 03 / 11 · Value functions

The Bellman Equation: Why V Is a Fixed Point and Why Iteration Must Converge

From the closed-form solution of a linear system, to the convergence guarantee of a contraction mapping, to the one spot of nonlinearity that max introduces - and the systematic overestimation it causes

60 minFoundational6 derivation steps4 self-test questions

One-line conclusion

The Bellman equation is a system of linear equations whose solution is the value function; because γ<1 makes it a contraction mapping, any initialization iterated repeatedly must converge to the unique solution. The moment you replace ∑_a π with max_a, linearity is gone - and that is the real reason approximation methods become necessary later on.

This article is the proof of 'why this is computable at all'. After reading it you will understand three things: why value iteration always converges, why γ=1 goes wrong, and why every Q-learning-style algorithm overestimates - the last of which directly decides why SAC takes the minimum of two Q values.

Symbol table

SymbolMeaning
P^πThe state transition matrix under policy π; row s holds 'the probabilities of reaching everywhere from s'
R^πThe expected immediate reward under policy π, a vector
TThe Bellman operator: takes in a value vector, outputs a new value vector
||·||_∞The max-norm - 'how far apart the worst-differing states are'
A w = bThe fixed-point equation under linear approximation, where A is the feature covariance matrix

Derivation

  1. Matrix form: the Bellman equation is really a linear system
  2. Contraction mapping: why iteration must converge
  3. The moment you swap in max, linearity is gone
  4. Policy iteration and value iteration are the same thing
  5. The systematic overestimation caused by max (this item decides how SAC is written)
  6. Why γ=1 is trouble, not merely 'no convergence'

1. Matrix form: the Bellman equation is really a linear system

Line up each state's equation as one row and you get an n-equation linear system, where n is the number of states. Since it is linear, you can just solve it.

V^π = R^π + γ P^π V^π ⟹ V^π = (I - γP^π)-1 R^π

Why this holdsWhen the state count is small this is the optimal solution - one shot, no iteration error. Deep RL cannot use it because n is uncountable (continuous states) and (I-γP)^{-1} costs O(n³). Note also what this says: as long as γ<1, (I-γP) is guaranteed invertible.

2. Contraction mapping: why iteration must converge

Define the Bellman operator T: give it a value vector and it computes a new vector from the Bellman right-hand side. What needs proving is that T shrinks the distance between any two vectors to within a factor of γ.

||T V - T V'||_∞ = γ||P(V - V')||_∞ ≤ γ||V - V'||_∞

Why this holdsThe second inequality is allowed because P is a stochastic matrix (each row sums to 1), so it cannot amplify any vector's max absolute value. For γ<1, T is a contraction mapping, and by the Banach fixed-point theorem a unique fixed point exists and iteration from any initial value converges to it. That is the legitimacy proof for value iteration, and it is not one line longer than it needs to be.

3. The moment you swap in max, linearity is gone

The optimality equation replaces 'weight by the policy' with 'take the best action'. This step changes the equation from linear to piecewise linear.

V*(s) = max_a ∑s' P(s'|s,a)[ r + γ V*(s') ]

Why this holdsThree consequences: (1) you can no longer write (I-γP)^{-1} and invert; (2) but T is still a contraction (max does not amplify distances either), so value iteration still converges; (3) the solution is no longer 'a linear function of V' but 'the upper envelope of a family of linear functions' - which is why the optimal value function has kinks, and why approximating it with smooth functions carries systematic error.

4. Policy iteration and value iteration are the same thing

Policy iteration is 'evaluate fully → improve once'; value iteration is 'evaluate one step → improve once'. The latter works because of the policy improvement theorem: picking actions greedily with respect to Q gives a new policy that is never worse.

π'(s) = argmax_a Q^π(s,a) ⟹ Vπ' ≥ V^π (state by state)

Why this holdsProof sketch: V^π(s) ≤ max_a Q^π(s,a) = Q^π(s,π'(s)) ≤ V^{π'}(s). The first step is the definition of max; the second is one Bellman expansion with respect to π', applied recursively. So the 'improve' step never regresses, and the loop must stop at the optimum.

5. The systematic overestimation caused by max (this item decides how SAC is written)

When the Q estimates carry noise, max picks the action that was most overestimated. So the expectation of the estimate is not the max of the true values; it is larger.

E[ max_a Q̂_a ] ≥ max_a E[ Q̂_a ]

Why this holdsJensen's inequality: max is convex, and the expectation of a convex function is no smaller than the function of the expectation. How big the bias is depends on the action count and the noise: with true values all 0, 10 actions and noise σ=1, the measured E[max]=1.539 (0.769 for σ=0.5, 3.087 for σ=2 - essentially linear). This is the motivation for double Q: use two independent estimates and take the smaller one to push the positive bias back down.

6. Why γ=1 is trouble, not merely 'no convergence'

At γ=1, T is only 'non-expansive', not 'contractive'; the fixed point may not be unique and the iteration can wander back and forth on a plateau.

γ=1: ||TV - TV'||_∞ ≤ ||V - V'||_∞ (equality possible)

Why this holdsSome tasks are solvable at γ=1 (finite return when there is an absorbing terminal state), but there is no convergence rate guarantee, and the value function's scale can shift arbitrarily. Practical advice: default to γ=0.99 for continuous control; raise it to 0.995~0.999 when episodes are long or rewards sparse, and check in parallel that the effective horizon still covers one complete action.

Work it by hand

A three-state chain: s0 →(r=0)→ s1 →(r=0)→ s2, where s2 is terminal and pays 1 on arrival. γ=0.9. Compute V(s0), V(s1), V(s2) by hand from the Bellman equation.

  1. Work back from the end: V(s2) = 1 (terminal state, only the immediate reward, nothing after)
  2. V(s1) = 0 + 0.9 × V(s2) = 0.9
  3. V(s0) = 0 + 0.9 × V(s1) = 0.81
Answer

V = [0.81, 0.90, 1.00]. This kind of "single chain" MDP is the standard test piece for a Bellman implementation: the answer is unique, computable in your head, and it instantly exposes the classic bug of counting the terminal state one extra time (the wrong V(s2)=1+0.9×1=1.9 makes every entry wrong). Value iteration in practice converges after 200 rounds to [0.81, 0.9, 1.0] with error 1e-12

Run it

A complete policy iteration implementation in 25 lines. The key knob is the inner 'how many sweeps to evaluate' - set it to 1 and it becomes value iteration, with identical results; verify that yourself.

python · numpy only
import numpy as np
n, G = 3, 0.9
P = np.zeros((n, n)); R = np.zeros(n)
P[0,1] = 1.0; P[1,2] = 1.0; P[2,2] = 1.0; R[2] = 1.0

def eval_pi(pi, iters=100):
    V = np.zeros(n)
    for _ in range(iters):
        V = R + G * P.dot(V)
    return V

pi = np.zeros(n, dtype=int)
for k in range(20):
    V = eval_pi(pi)
    Q = np.stack([R + G * P.dot(V)] * 1, 0)  # single-action environment, Q is V
    new = Q.argmax(0)
    if (new == pi).all():
        break
    pi = new
print('V =', V, ' outer rounds =', k+1)
print('analytic solution =', np.linalg.solve(np.eye(n) - G*P, R))

You pass when you see this

The two printed lines agree: V = [0.81 0.9 1.0], identical digit for digit to the np.linalg.solve result. If they differ, some row of your P is not normalized (row sums are not 1), and the premise of the contraction mapping fails.

Self-test · 4 questions

Answer first, then expand. Each question traces back to a specific derivation section.

01Why can the optimality equation not be written in the form (I-γP)-1R?

Because it contains max_a, which is not a linear combination of P - different states pick different actions, so the effective 'transition matrix' depends on V itself. The solution is the upper envelope of a family of linear functions and can only be found by iteration.

02Does value iteration necessarily diverge at γ=1?

It need not diverge, but there is guaranteed to be no convergence rate guarantee, and the fixed point may not be unique (values can shift as a whole). With terminal states the return is bounded and convergence is still possible; but do not gamble on this in practice.

03Why does the direction of the inequality E[max_a Q̂] ≥ max_a E[Q̂] lead to 'the longer you train, the worse it gets'?

Because the target is systematically overestimated, and the overestimate is fed back into the next step through bootstrap, forming positive feedback. More actions and more noise mean more bias, until the policy chases rewards that do not exist at all.

04What does the policy improvement theorem guarantee? Why does it also make 'improve after evaluating only one step' valid?

It guarantees that the greedy-with-respect-to-Q policy is no worse than the old one, state by state. Because the improvement proof uses only one Bellman expansion and does not need evaluation to converge, improving after one evaluation step still works - it just improves a little less, and that is exactly value iteration.

Keep reading

Previous: MDP and returnNext: MC and TDReinforcement learning knowledge page
PreviousMDP and Return: Writing 'What To Do' as Something Computable NextModel-Free: The Bias-Variance Ledger of MC vs TD

The whole series · 11 articles

01The Only Four Math Tools You Need40 min02MDP and Return: Writing 'What To Do' as Something Computable45 min03The Bellman Equation: Why V Is a Fixed Point and Why Iteration Must Converge60 min04Model-Free: The Bias-Variance Ledger of MC vs TD60 min05Function approximation: the three ingredients that take you from 'guaranteed convergence' to 'blowing up'55 min06Policy gradient: deriving REINFORCE line by line70 min07Actor–critic and GAE: turning the variance knob to λ60 min08PPO: what does clip actually clip70 min09SAC: entropy, reparameterization, double Q - three parts, each solving one problem75 min10HER: why goal relabeling is mathematically legitimate50 min11How to debug non-convergence: map symptoms back to formulas45 min