If you know the rules of the world perfectly — every transition probability, every reward — you can solve any MDP exactly with two short loops. That is dynamic programming. Real problems rarely give you that gift, but DP is the gold-standard baseline every later RL algorithm tries to approximate. Q-learning is sampled DP. DQN is approximated DP. AlphaZero is DP over a learned model. Master this and the rest of RL is variations.
Learning Objectives
After this lesson, you will be able to:
Write down both Bellman equations — expectation (for evaluating a fixed policy) and optimality (for finding the best policy) — and explain why one looks like 'average over actions' and the other like 'take the max'
Run Policy Iteration on a small MDP: alternate evaluation (compute v_π) and improvement (greedy w.r.t. v_π) until the policy stops changing
Run Value Iteration on the same MDP: combine evaluation and improvement into one update with a max, iterate until the values converge
Recognize that almost every later RL algorithm is a noisy, partial, or sampled version of Generalized Policy Iteration — DP is the limit case the rest of the field approximates
Don't worry if "iterate until convergence" sounds vague — once you implement it on a 4-by-4 grid in 30 lines of Python, it stops being abstract and starts being mechanical.
In an MDP we have transitions P(s'|s,a) and rewards R(s,a) — both fully specified. The Bellman equations connect the value of a state to the values of its successors:
vπ(s)=a∑π(a∣s)s′,r∑P(s′,r∣s,a)[r+γvπ(s′)]
v∗(s)=amaxs′,r∑P(s′,r∣s,a)[r+γv∗(s′)]
Two equations. Two algorithms. Both converge to the right answer.
#Deriving the Bellman equation from first principles
So far we have stated the Bellman equations. We have not yet derived them, nor have we proven that iterating them converges. Both gaps matter: the proof is what tells you value iteration is guaranteed to work, why policy iteration terminates, and how fast convergence happens. The derivation comes from the linearity of expectation and the tower law; the convergence comes from the Banach fixed-point theorem applied to a γ-contraction.
Setup. Fix a discounted infinite-horizon Markov decision process (S, A, P, R, γ) with γ ∈ [0, 1), where P(s' | s, a) is the transition kernel, R(s, a, s') is the (possibly random) reward, and π(a | s) is a stationary policy. The state-value function under π is defined as
Vπ(s):=Eπ[t≥0∑γtrts0=s]
Step 1: one-step decomposition via the tower law. Split the infinite sum into the first reward and everything after:
Step 2: expand the outer expectation over action and next-state. The expectation under π marginalizes over the action a ~ π(· | s) and the next state s' ~ P(· | s, a):
Vπ(s)=a∑π(a∣s)s′∑P(s′∣s,a)[R(s,a,s′)+γVπ(s′)]
Step 3: action-value version. Applying the same one-step decomposition to Q^π(s, a) := E_π[Σ γ^t r_t | s_0=s, a_0=a] (where the first action is forced to be a) gives the Bellman expectation equation for Q:
Step 4: optimality equations. Define V*(s) := max_π V^π(s) and Q*(s,a) := max_π Q^π(s,a). Because the optimal policy is greedy w.r.t. its own Q-function (this is the Policy Improvement Theorem applied at convergence), the average over actions becomes a max:
V∗(s)=amaxs′∑P(s′∣s,a)[R(s,a,s′)+γV∗(s′)]
Step 5: the Bellman operator and contraction. Treat the Bellman expectation update as a function T^π : R^|S| → R^|S| mapping value functions to value functions:
Step 6: Banach fixed-point theorem.R^|S| with the sup-norm is a complete metric space (every Cauchy sequence converges). A γ-contraction on a complete metric space has a unique fixed point, and iterating the contraction from any starting point converges to that fixed point at geometric rate γ. Concretely:
||T^k V - V*||_∞ ≤ γ^k · ||V - V*||_∞
The unique fixed point of T^π is V^π; the unique fixed point of T* is V*. This is why value iteration works. Iterate T* from any initial V_0; after k steps the error is bounded by γ^k · ||V_0 - V*||_∞. To achieve error ε, run k ≥ log(ε / ||V_0 - V*||) / log(γ) iterations.
Step 7: policy iteration justification. Policy iteration alternates two operations: (1) policy evaluation — solve V^π = T^π V^π for the current π, which the contraction argument shows is the unique fixed point reachable by iterating T^π; (2) policy improvement — set π'(s) = argmax_a Σ_{s'} P(s'|s,a)[R + γ V^π(s')]. The Policy Improvement Theorem guarantees V^{π'}(s) ≥ V^π(s) for all s, with strict inequality somewhere unless π was already optimal. Since there are only finitely many deterministic policies on a finite MDP (at most |A|^|S|), and the value function is monotonically non-decreasing across outer iterations, policy iteration terminates in finitely many steps — typically <10 in practice.
What Do You Think?
With γ = 0.99, how many value-iteration sweeps does the contraction argument guarantee are needed to drive the error from 1.0 down to 0.01 (a 100x reduction)?
References. Bellman 1957, Dynamic Programming (originated the equation and the principle of optimality). Puterman 1994, Markov Decision Processes: Discrete Stochastic Dynamic Programming (the canonical proof reference; contraction arguments in Chapters 6–7). Sutton & Barto 2018, Reinforcement Learning: An Introduction, Chapter 4 (the modern pedagogical treatment, including Generalized Policy Iteration). Bertsekas & Tsitsiklis 1996, Neuro-Dynamic Programming (function-approximation extensions).
def policy_iteration(P, R, gamma=0.9):
pi = {s: 0 for s in range(num_states)} # arbitrary start
while True:
V = policy_evaluation(pi, P, R, gamma)
new_pi = policy_improvement(V, P, R, gamma)
if new_pi == pi:
return V, pi # converged
pi = new_pi
In small MDPs, PI typically converges in 3–10 outer iterations. The catch is that each outer iteration runs the full policy-evaluation loop to convergence, which is expensive.
On a small grid with γ = 0.9 and exact tabular updates, which converges faster in wall-clock time — Policy Iteration or Value Iteration?
The honest answer is (c): it depends. On classic textbook GridWorlds, VI usually wins because each sweep is cheap. On large MDPs with informative initial policies and sparse transitions, PI can win because few outer iterations suffice and modified PI (truncated evaluation) becomes near-optimal.
Tests · Verify both PI and VI produce identical V (within tolerance). Verify the optimal V values are negative integers reflecting step counts to nearest corner. Check that the extracted policy points toward the closest corner from each state.
Two Bellman equations, two algorithms. Bellman expectation gives you policy evaluation. Bellman optimality gives you value iteration and policy improvement. Every later RL method is one of these in disguise.
Policy Iteration alternates two loops; Value Iteration smashes them together. PI does fewer outer iterations but each is expensive. VI does many cheap sweeps. Both converge to the same v* and the same optimal policy.
Generalized Policy Iteration is the unifying meta-pattern. Q-learning, SARSA, A2C, PPO, MuZero — every one of them is GPI with different choices for how to evaluate (sample vs sum) and how to improve (greedy vs gradient).
DP requires perfect knowledge of the MDP. That's why we don't actually use it on real problems — we use sampled, model-free approximations. But understanding the exact case is the only way to know what those approximations are converging to.
Tabular DP doesn't scale. Function approximation (DQN, AlphaZero, etc.) is the answer. The tradeoff is convergence guarantees: tabular DP has them, neural approximators usually don't, and the field is largely about managing that gap.
Interactive Lab
Run Value Iteration on a 4×4 gridworld one sweep at a time — watch the value function ripple outward from the goal cell and the optimal policy crystallize in 3–5 iterations.
After running Policy Iteration to convergence, the policy stops changing. What does this prove?
Now you understand the gold-standard solution to a fully-known MDP. Next: what changes when we have to learn from experience instead of knowing the dynamics — the Monte Carlo and Temporal Difference methods that brought RL out of the textbook and into the real world.