Discounted dynamic programming works because Bellman operators are contractions. This fixed-point geometry supplies existence, uniqueness, convergence of iteration, and perturbation bounds.
Banach fixed-point theorem
The contraction theorem is the basic analytic tool behind value iteration.
Theorem. Let \((X,d)\) be complete and \(T:X\to X\) satisfy \(d(Tx,Ty)\le\gamma d(x,y)\) for some \(0\le\gamma<1\). Then \(T\) has a unique fixed point \(x^*\), and \(T^nx\to x^*\) for every \(x\).
Proof. The iterates satisfy \(d(x_{n+1},x_n)\le\gamma^nd(x_1,x_0)\), so \((x_n)\) is Cauchy and converges to some \(x^*\). Continuity of \(T\) gives \(Tx^*=x^*\). If \(y^*\) is another fixed point, \(d(x^*,y^*)\le\gamma d(x^*,y^*)\), hence \(x^*=y^*\).
Bellman contractions
Bellman operators inherit contraction from discounting and Markov averaging.
Proposition. For bounded value functions, \[ \|T_\pi u-T_\pi v\|_\infty\le\gamma\|u-v\|_\infty, \qquad \|T_*u-T_*v\|_\infty\le\gamma\|u-v\|_\infty. \]
Proof. For \(T_\pi\), Markov averaging cannot increase the sup norm and the discount contributes \(\gamma\). For \(T_*\), use the inequality \(|\sup_a f_a-\sup_a g_a|\le\sup_a|f_a-g_a|\), then apply the same Markov averaging bound.
Residual bounds
A small Bellman residual implies closeness to the fixed point.
Proposition. If \(T\) is a \(\gamma\)-contraction with fixed point \(v^*\), then \[ \|v-v^*\|\le\frac{1}{1-\gamma}\|v-Tv\|. \]
Proof. Use \[ \|v-v^*\|\le\|v-Tv\|+\|Tv-Tv^*\| \le\|v-Tv\|+\gamma\|v-v^*\|. \] Move the last term to the left.
Perturbed fixed points
Approximate dynamic programming repeatedly applies operators with error; perturbation bounds quantify error accumulation.
Corollary. If \(Tv^*=v^*\), \(\tilde T\tilde v=\tilde v\), and \(\|Tv-\tilde Tv\|\le\varepsilon\) for all \(v\), then \[ \|v^*-\tilde v\|\le\frac{\varepsilon}{1-\gamma}. \]
Proof. Apply the residual bound for \(T\) at \(v=\tilde v\). Since \(T\tilde v-\tilde v=T\tilde v-\tilde T\tilde v\), the residual is at most \(\varepsilon\).
Banach's theorem with quantitative bounds
Theorem (Banach). If \((\mathcal X,d)\) is complete and \(F\) satisfies \(d(Fx,Fy)\le\gamma d(x,y)\), \(0\le\gamma<1\), then \(F\) has a unique fixed point \(x^*\), and \[ d(F^nx,x^*)\le\gamma^nd(x,x^*), \] \[ d(F^nx,x^*)\le\frac{\gamma^n}{1-\gamma}d(Fx,x). \]
Proof. Consecutive iterates satisfy \(d(F^{k+1}x,F^kx)\le\gamma^kd(Fx,x)\). Summing the geometric tail makes \((F^nx)\) Cauchy. Completeness gives a limit \(x^*\), continuity gives \(Fx^*=x^*\), and contraction gives uniqueness. Applying contraction to \(F^nx\) and \(x^*\) proves the first rate; summing consecutive increments from \(n\) onward proves the second.
Bellman contraction and residual certificates
Proposition. For every bounded \(V,W\), \[ \|T^\pi V-T^\pi W\|_\infty\le\gamma\|V-W\|_\infty, \qquad \|TV-TW\|_\infty\le\gamma\|V-W\|_\infty. \] Consequently, \[ \|V-V^\pi\|_\infty \le\frac{\|V-T^\pi V\|_\infty}{1-\gamma}, \qquad \|V-V^*\|_\infty \le\frac{\|V-TV\|_\infty}{1-\gamma}. \]
Proof. Markov averaging cannot increase sup norm, and the maximum operator is one-Lipschitz in sup norm. For the residual, \[ \|V-V^*\|_\infty \le\|V-TV\|_\infty+\|TV-TV^*\|_\infty \le\|V-TV\|_\infty+\gamma\|V-V^*\|_\infty. \]
Perturbed fixed points
Theorem. If \(F,\widetilde F\) are \(\gamma\)-contractions with fixed points \(x^*,\tilde x^*\), then \[ d(x^*,\tilde x^*) \le\frac{\sup_x d(Fx,\widetilde Fx)}{1-\gamma}. \] If an inexact iteration satisfies \(d(x_{k+1},Fx_k)\le\varepsilon_k\), then \[ d(x_k,x^*)\le\gamma^kd(x_0,x^*) +\sum_{j=0}^{k-1}\gamma^{k-1-j}\varepsilon_j. \]
The geometric convolution shows why recent approximation errors matter more than old ones and why a persistent one-step error is amplified by \((1-\gamma)^{-1}\).
Beyond sup-norm contraction
Average-reward Bellman operators are translation equivariant rather than strict contractions in sup norm. Under communicating assumptions they can contract the span seminorm \(\operatorname{sp}(V)=\max_sV(s)-\min_sV(s)\). With function approximation, projected Bellman maps may contract in a policy-weighted \(L_2\) norm on-policy but fail off-policy. The norm and invariant subspace are therefore part of the theorem, not cosmetic details.