7 Ā· Value iteration
The Bellman OPTIMALITY equation replaces 'average over actions' with 'take the best action'. Sweeping it is value iteration ā it finds the optimal value function in a handful of passes, and a greedy read-off gives the optimal policy.
The Bellman OPTIMALITY equation is V*(s) = max_a Ī£_s' P(s'|s,a)[R + Ī³ V*(s')]: the value of acting optimally is the value of the single best action. Sweeping this max-backup until convergence is value iteration; the optimal policy is then 'be greedy with respect to V*'.
Without this:
Policy evaluation only tells you how good a FIXED policy is. Without the optimality equation you have no way to compute the BEST achievable value or extract the optimal policy directly.
Evaluating a fixed policy is useful, but the real goal is the optimal policy. The trick is one change to the Bellman equation: instead of averaging over the actions the policy might take, take the maximum over actions. This is the Bellman optimality equation for the optimal value function V*:
V*(s) = max_a Ī£_s' P(s'|s,a) Ā· [ R(s,a,s') + Ī³ Ā· V*(s') ]
In words: the value of acting optimally from s is the value of the single best action available there. (The action-value form is Q*(s,a) = Ī£_s' P[R + Ī³ max_a' Q*(s',a')].) There is no policy in this equation ā it directly describes optimal behaviour.
Value iteration turns this into an algorithm: initialise V to zero and repeatedly apply the max-backup to every state until the values stop changing. Each sweep is one application of the optimality operator, and that operator is a contraction (it shrinks the error by a factor of Ī³ every sweep), so it provably converges to the unique V*.
Once we have V*, the optimal policy falls out for free: in each state, pick the action whose backup is largest ā be greedy with respect to V*. Below we run value iteration on the gridworld, print the optimal value grid, and render the greedy optimal policy as arrows. Watch how it threads around the trap.
Python (in browser)
Value iteration: a few max-backup sweeps yield V*, and reading off the greedy action per cell gives the optimal policy. The arrows form a clean flow toward the goal, around the trap.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
What is the ONLY difference between the Bellman expectation backup (policy evaluation) and the Bellman optimality backup (value iteration)?
- The Bellman optimality equation uses max_a instead of averaging: V*(s) = max_a (reward + Ī³ Ć value of next state).
- Value iteration sweeps the max-backup until convergence; the operator is a contraction, so it provably converges to the unique V*.
- The optimal policy is obtained by acting greedily with respect to V* ā pick the best action in each state.
Q-learning and DQN are sampled, model-free versions of the same optimality backup; the 'max over next actions' in the DQN target is exactly the Bellman optimality operator.
If you remove it: Without the optimality equation you can only evaluate fixed policies, never compute the best achievable value or derive an optimal controller.