8 · Policy iteration
Instead of one giant max-sweep, alternate two cheaper steps: fully evaluate the current policy, then make it greedy. Each round can only improve the policy, and it converges to the same optimum as value iteration — usually in very few rounds.
Policy iteration alternates two steps until the policy stops changing: (1) policy evaluation — compute V^π for the current policy; (2) policy improvement — make the policy greedy w.r.t. that V^π. The policy-improvement theorem guarantees each round is no worse, and the loop converges to the optimal policy — the same one value iteration finds.
Without this:
Without the evaluate-then-improve loop you'd lack the cleanest proof that greedy improvement actually works, and you'd miss the template (generalised policy iteration) that nearly every RL algorithm — including actor-critic — instantiates.
Value iteration folds evaluation and improvement into a single max-sweep. Policy iteration keeps them as two distinct, alternating steps — and this separation reveals why greedy improvement works.
Start from any policy π (even a random one) and repeat:
- Policy evaluation — compute
V^πfor the current policy (the Bellman expectation sweep from Lesson 6, run to convergence). - Policy improvement — build a new policy that is greedy with respect to
V^π: in each state pick the action with the largestreward + γ·V^π(next state).
The policy-improvement theorem guarantees the new policy is at least as good as the old one in every state. So each round either strictly improves the policy or leaves it unchanged — and when a round leaves it unchanged, the policy is greedy with respect to its own value, which is precisely the Bellman optimality condition. So we have converged to the optimal policy.
Because there are only finitely many deterministic policies and each round strictly improves (until the end), policy iteration converges in a small number of rounds — often just a handful, even though each round does a full evaluation internally. Below we run it on the gridworld starting from a random policy, count the rounds, print the final policy, and confirm it matches the value-iteration answer from the previous lesson.
Python (in browser)
Policy iteration: alternate full evaluation with greedy improvement. It converges in a handful of rounds and reaches the EXACT same optimal policy value iteration found.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
Policy iteration starts from a random policy yet converges in only a few rounds. What guarantees it never gets worse and stops at the optimum?
- Policy iteration alternates policy evaluation (compute V^π) and policy improvement (make the policy greedy w.r.t. V^π) until the policy is stable.
- The policy-improvement theorem guarantees each round is no worse, so the loop converges — usually in very few rounds — to the optimal policy.
- It reaches the SAME optimal policy as value iteration; both are instances of generalised policy iteration (GPI).
GPI — alternating evaluation and improvement — is the skeleton of nearly every control algorithm: SARSA, Q-learning, and actor-critic all evaluate a value estimate and improve a policy against it.
If you remove it: Without the policy-improvement theorem we'd have no guarantee that acting greedily on a value estimate improves behaviour — the assumption underpinning every value-based controller.