contraction mapping

A contraction mapping is an operator that always pulls two points closer together: apply it to any pair of value functions and the distance between them shrinks by at least a constant factor. This single geometric fact is the engine behind almost every convergence proof in dynamic programming. If repeatedly applying an operator keeps squeezing space, the iterates must funnel toward one and only one resting point.

In RL the operator is the Bellman operator, and the constant factor is the discount γ < 1. Measured in the max-norm (a sup over states), both the policy-evaluation operator and the Bellman optimality operator are γ-contractions. Banach's fixed-point theorem then guarantees a unique fixed point — the value function V^π or the optimal V* — and that value iteration converges to it geometrically, with error shrinking like γ to the k after k sweeps.

The contraction lives in the max-norm. Once you approximate values in a different norm (least-squares fitting works in an L2 norm), the operator may no longer be a contraction in that norm, which is exactly where approximate dynamic programming loses its clean guarantees.