Value Iteration & Q-Learning

Interview-grade notes for the technical (it-ml) track.

Value iteration is a contraction. The Bellman optimality backup is an operator T that maps a value function to a new one. Its key property is that it is a γ-contraction in the max-norm: for any two value functions U and V,

max_s | (T U)(s) − (T V)(s) |  ≤  γ · max_s | U(s) − V(s) |

Every sweep shrinks the worst-case error by at least a factor of γ. By the Banach fixed-point theorem a contraction has exactly one fixed point, and repeated application converges to it geometrically — so value iteration converges to the unique optimal V* from any starting values, and the error after k sweeps is bounded by γ^k times the initial error. This is why γ < 1 is not a mere modelling preference but a requirement for the guarantee: at γ = 1 the contraction becomes non-strict and convergence needs extra structure (a proper policy reaching a terminal with probability 1). It also explains the corridor's behaviour — with the goal one and two steps away, the error hits zero after two informative sweeps, and the third only confirms it.

Q-learning's guarantee is stochastic and stricter. Watkins & Dayan (1992) proved tabular Q-learning converges to the optimal Q* with probability 1, but under two conditions the planner never needed:

• Infinite exploration — every state–action pair must be visited infinitely often. If exploration ever abandons a pair (e.g. ε decayed to 0 too soon, or a purely greedy behaviour policy), its Q-value can freeze at a wrong estimate and the proof breaks. This is the deep reason the bandit module's explore–exploit lesson never goes away: coverage is a convergence requirement, not a nicety.
• A decaying learning rate — the step sizes α_t for each pair must satisfy the Robbins–Monro conditions, Σ α_t = ∞ and Σ α_t² < ∞ (sum to infinity so the estimate can travel any distance, but square-sum finite so the noise is eventually averaged out). A constant α, common in practice, does not strictly satisfy this — it keeps Q(s, a) bouncing in a neighbourhood of the truth rather than settling exactly, which is usually a fine engineering trade for faster tracking of a changing environment.

Function approximation forfeits the guarantee. Both proofs assume an exact table. Swap in a function approximator (deep RL) and the contraction argument no longer holds — the projection onto the approximator's representable functions can expand rather than contract error, and the notorious "deadly triad" (function approximation + bootstrapping + off-policy updates) can diverge outright. The stabilising tricks of modern deep RL (target networks, experience replay, clipped updates) exist precisely to claw back the stability the tabular theory gave for free.