Course contentsShow
← Machine Learning and Deep Learning
Lesson 2162 of 3,53846. Reinforcement Learning: FundamentalsFree lesson

Policy Iteration Algorithm

Combine policy evaluation and policy improvement in an alternating scheme to find optimal policies iteratively.

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:

  1. Evaluate the current policy to get accurate state values V
  2. Improve the policy by acting greedily with respect to those values
  3. 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.