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

Convergence of Iterative Policy Evaluation

Understand why iterative policy evaluation converges and how to set termination criteria based on value function changes.

Convergence of Iterative Policy Evaluation

You'll learn why iterative policy evaluation is guaranteed to converge and how to decide when to stop iterating.

Why Convergence Happens

When performing iterative policy evaluation (computing state values for a given policy), you repeatedly apply Bellman backup operations to update your value function estimates. The magical fact is: this process always converges to the true value function under standard MDP assumptions.

Here's why: The Bellman expectation equation acts as a contraction mapping. Each iteration brings all state values closer together toward their true values. Think of it like squeezing a sponge—no matter where you start, repeated squeezes eventually compress it to a predictable size. The discount factor γ (gamma < 1) ensures this "squeezing" property: errors shrink by at least a factor of γ with each iteration.

Setting Termination Criteria

Since you can't iterate forever, you need practical stopping conditions. The most common approach is monitoring maximum value change between iterations:

Δ = max |V_{k+1}(s) - V_k(s)| for all states s

When Δ drops below a small threshold θ (like 0.001), you've converged "close enough." Your value function won't be perfectly exact, but it's practically accurate.

Why This Works

Because of the contraction property, if the maximum change across all states is tiny, you know all values have stabilized near their true values. You're essentially measuring how much your estimates are still shifting—when they barely move, you're done.

Key Takeaway: Iterative policy evaluation converges to the true value function because Bellman updates are contractions; terminate when the maximum value change between iterations falls below your chosen threshold θ.