Policy Iteration Algorithm
What you'll learn: How to find optimal policies in MDPs by alternating between evaluating a policy and improving it until no further improvement is possible.
The Core Idea
Policy iteration is the complete algorithm that puts together the two pieces you've just learned: policy evaluation and policy improvement. Instead of running each once, you cycle between them repeatedly:
- Evaluate the current policy to get accurate state values V
- Improve the policy by acting greedily with respect to those values
- Repeat until the policy stops changing
Think of it like tuning a recipe: you taste the dish (evaluate), adjust the seasoning (improve), taste again, adjust again, and keep going until no adjustment makes it better.
The Algorithm Flow
Initialize policy π arbitrarily
Loop:
1. Policy Evaluation:
Compute V^π using iterative evaluation until convergence
2. Policy Improvement:
For each state s:
π'(s) = argmax_a Σ P(s'|s,a)[R + γV^π(s')]
3. Check if π' = π
If yes: stop (optimal policy found)
If no: set π = π', continue loop
Why It Works
Each improvement step is guaranteed to make the policy at least as good (by the policy improvement theorem you just learned). Since there are finitely many deterministic policies in finite MDPs, and we can't cycle back to a worse policy, the algorithm must converge to the optimal policy π*.
Policy iteration is remarkably efficient in practice—often converging in just a few iterations, even though each evaluation step itself requires multiple iterations.
Key Takeaway: Policy iteration finds optimal policies by alternating policy evaluation and greedy policy improvement until convergence, guaranteed to reach π* in finite iterations.