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

Convergence Guarantees for Policy Iteration

Understand why policy iteration converges to the optimal policy in finite steps for finite MDPs.

Convergence Guarantees for Policy Iteration

What You'll Learn

You'll understand why policy iteration is guaranteed to find the optimal policy in a finite number of steps for finite MDPs.

Why Policy Iteration Always Converges

Policy iteration alternates between two steps: policy evaluation (computing state values for the current policy) and policy improvement (making the policy greedy with respect to those values). But does this process always reach the optimal policy?

The answer is yes, and here's why:

Finite Improvement Steps

In a finite MDP with a finite number of states and actions, there are only finitely many possible deterministic policies. Each policy improvement step either:

  1. Finds a strictly better policy (higher value in at least one state), or
  2. Cannot improve further (we've reached optimality)

Since the Policy Improvement Theorem guarantees that we never worsen a policy, and we can't improve indefinitely in a finite space, we must reach the optimal policy in finite steps.

The Monotonic Progress Guarantee

Think of it like climbing a staircase with a fixed number of steps. Each policy improvement moves you up at least one step (if improvement is possible), and you can't go down. Eventually, you reach the top.

Mathematically, the sequence of values is monotonically increasing:

  • V^π₀ ≤ V^π₁ ≤ V^π₂ ≤ ... ≤ V*

Since there are finitely many policies and we strictly improve until reaching optimality, convergence happens in at most as many iterations as there are distinct policies.

Practical Implication

In practice, policy iteration typically converges in far fewer iterations than the theoretical maximum, often finding the optimal policy in just a handful of steps for small to medium MDPs.

Key Takeaway: Policy iteration is guaranteed to converge to the optimal policy in finite steps for finite MDPs because it monotonically improves through a finite policy space, making it a reliable algorithm with strong theoretical foundations.