D-DL4CV-Lec21d-Value_Iteration_Convergence

Value Iteration Convergence

The Core Insight: Growing Optimality Horizon

Each $Q_i$ is optimal for exactly $i$ steps, then reverts to the initial random policy $Q_0$

What Each Q_i Represents

• $Q_0$ : Random actions at every step
• $Q_1$ : Optimal for 1 step, then random
• $Q_2$ : Optimal for 2 steps, then random
• $Q_3$ : Optimal for $i$ steps, then random

The Update Mechanism

$Q_{i+1}(s,a)={\mathbb{E}}_{r,s^{\prime }}\left[r+\gamma {\max }_{a^{\prime }}{Q}_i(s^{\prime },a^{\prime })\right]$

The nesting creates “telescoping optimality”:

• $Q_{i+1}$ = optimal for 1 step + $\gamma$ × (optimal for $i$ steps) = optimal for $i+1$ steps

Why Convergence Happens

Since $\gamma <1$, rewards far in the future matter exponentially less. Eventually $Q_i$ becomes optimal for so many steps that the remaining “random tail” contributes negligibly.

Result: As $i\to \infty$, the optimality horizon grows without bound while the random part vanishes, so $Q_i\to Q^{\star }$.