Foundations T17 / 27 · Convergence and fixed points
Norms and fixed points: where «it always converges» comes from
«Value iteration always converges» is not an empirical fact; it is a corollary of Banach's fixed point theorem. The Bellman optimality operator is a γ-contraction in the sup norm — γ<1 is the entire premise, and at γ=1 every guarantee vanishes.
One-line takeaway
The contraction mapping principle in one sentence: on a complete space, a map that compresses the distance between any two points to γ<1 times has exactly one fixed point, and iteration from any starting point reaches it at rate γ^k. The convergence speed of value iteration, the error bound, and the stopping condition are all mechanical applications of this theorem.
Does TD converge? Does value iteration? Q-learning? The first common source of these questions is here. After this piece you will know what the proof structure of «convergence» looks like, what role γ plays, and where the gap is at γ=1 — T10 later supplies the final piece for the stochastic version.
Why this tool exists
First set the target: given the Bellman optimality operator (TV)(s) = max_a Σs' p(s'|s,a)[r + γV(s')], «value iteration converges» means V, TV, T²V, … tend to the unique solution V* satisfying TV* = V*.
Why does T²V settle down rather than oscillate back and forth or diverge? Convergence analysis of iterative methods has one universal path: find a distance on the space, and prove the map compresses the distance between any two points to at most γ<1 times. Then the iteration sequence is a Cauchy sequence, the limit exists, and the limit is necessarily a fixed point.
Take the tools one at a time: what a distance between two points means (norm), what completeness means in the distance sense (every Cauchy sequence converges), what a contraction means (Lipschitz constant <1).
Definitions
Definition 5.1 Norm and completeness
A norm ‖·‖ is a function on a vector space satisfying positive definiteness, homogeneity, and the triangle inequality. A metric space is complete: every Cauchy sequence (pairwise distances tending to 0) converges within the space. ℝⁿ with any norm is complete.
Why define it this wayCompleteness is the guarantee that «the limit exists». Without it, a Cauchy sequence may «converge to a point outside the space» — the iteration runs for nothing. The value function space ℝ|S| with the sup norm is complete; in the finite-state case this comes for free.
Definition 5.2 Contraction mapping
A map T on (X, ‖·‖) is a γ-contraction (γ<1) if for all x, y∈X: ‖Tx − Ty‖ ≤ γ‖x−y‖. γ is called the contraction factor.
Why define it this wayNote that ≤ γ‖x−y‖ holds uniformly for every pair of points — not on average, not locally. The Bellman operator happens to satisfy this strong condition (with factor exactly γ), which is the luckiest thing about reinforcement learning.
Theorems and proofs
Theorem 5.1 Banach fixed point theorem (full proof)
A γ-contraction T on a complete space X has a unique fixed point x*, and from any x₀, ‖x_k − x*‖ ≤ γ^k/(1−γ)·‖x₁−x₀‖.
Proof
Step 1 (the iterates form a Cauchy sequence). For m>n, apply the contraction repeatedly: ‖xn+1−x_n‖ ≤ γ‖x_n−xn−1‖ ≤ … ≤ γ^n‖x₁−x₀‖. Sum the triangle inequality:
γ^n → 0, so for m,n large enough the right side is arbitrarily small — Cauchy. By completeness, x_n → x* ∈ X.
Step 2 (the limit is a fixed point). A contraction is continuous (let y→x in ‖Tx−Ty‖≤γ‖x−y‖). Hence Tx* = T(lim x_n) = lim T x_n = lim xn+1 = x*.
Step 3 (uniqueness). If Tx*=x* and Ty*=y*: ‖x*−y*‖ = ‖Tx*−Ty*‖ ≤ γ‖x*−y*‖. For γ<1 the only possibility is ‖x*−y*‖=0, i.e. x*=y*.
Step 4 (the rate). ‖xn+1−x*‖ = ‖Tx_n − Tx*‖ ≤ γ‖x_n−x*‖, so by induction ‖x_n−x*‖ ≤ γ^n‖x₀−x*‖. Combine this bound with the Cauchy control of Step 1 (substitute x_m → x* into ‖x_m−x_n‖ ≤ γ^n/(1−γ)·‖x₁−x₀‖ and let m→∞) to get the error bound ‖x_n−x*‖ ≤ γ^n/(1−γ)·‖x₁−x₀‖. ∎
NoteThe proof structure is the standard template of iterative-method analysis: Cauchy → limit exists → limit is a fixed point → unique → rate. Every proof that «such-and-such iteration converges» is a variant of this template, including stochastic approximation in T10 (where extra noise requires extra tools).
Theorem 5.2 The Bellman optimality operator is a γ-contraction
On (ℝ|S|, ‖·‖_∞), the Bellman optimality operator T (and the Bellman expectation operator T^π of any fixed policy) satisfies ‖TV − TW‖_∞ ≤ γ‖V−W‖_∞.
Proof
Expand state by state. For each s, the contraction property of max: |max_a f(a) − max_a g(a)| ≤ max_a |f(a)−g(a)| (max is 1-Lipschitz: some term realizing max_a f satisfies f(a) ≥ g(a) ≥ max_a g; compare pointwise).
The second inequality substitutes |V(s')−W(s')| ≤ ‖V−W‖_∞ pointwise; the third uses that the probabilities sum to 1. Taking the max over s gives the operator-norm inequality. ∎
NoteWhere γ enters: the discount term γV(s') scales the next level's value by γ, and both max and expectation are 1-Lipschitz, so γ passes through every operation straight into the conclusion. At γ=1 the chain snaps — the T7 experiments will show that V* itself may not exist.
Work it by hand
γ=0.9, initial value V₀=0, and the final value function error must be ≤0.01. Using the bound of Theorem 5.1, estimate how many iterations value iteration needs? (measured for this problem: ‖V₁−V₀‖_∞ = 1)
- Theorem 5.1 error bound: ‖V_k − V*‖_∞ ≤ γ^k/(1−γ)·‖V₁−V₀‖ = 0.9^k/0.1 × 1.
- Require 0.9^k/0.1 ≤ 0.01, i.e. 0.9^k ≤ 0.001.
- [object Object]
- Compare with the other bound (the γ^n form of Step 4 of Theorem 5.1 needs ‖x₀−x*‖, which is unusable while x* is unknown) — in practice use the Cauchy stopping rule: you may stop when ‖V_k − Vk−1‖ ≤ (1−γ)/γ · tolerance.
k = 66 steps guarantee error ≤0.01. Note this is a «guarantee»; the measured error (below) falls faster than the bound — the bound must cover the worst case. The stopping-rule conversion (1−γ)/γ·tolerance comes from combining ‖V_k−Vk−1‖ ≤ γ^k/(1−γ)‖V₁−V₀‖ with ‖V_k−V*‖ ≤ γ/(1−γ)·‖V_k−Vk−1‖.
Run the numbers
Where the numbers come from
4-state chain (state 3 absorbing, reward 1 per step), γ=0.9, value iteration from V₀=0. Measured adjacent-iteration differences against the theoretical bound:
- k=2: ‖ΔV‖=0.900, contraction ratio 0.9000 (theoretical bound 9.000)
- k=5: ‖ΔV‖=0.656, contraction ratio 0.9000 (theoretical bound 6.561)
- k=10: ‖ΔV‖=0.387, contraction ratio 0.9000 (theoretical bound 3.874)
- k=20: ‖ΔV‖=0.135, contraction ratio 0.9000 (theoretical bound 1.351)
- k=39: ‖ΔV‖=0.018 — the contraction ratio equals exactly γ=0.9000 at every step, while the theoretical bound is about 10× looser
Where this shows up
| The object here | The counterpart in RL | Used in |
|---|---|---|
| Contraction factor γ | The discount factor: it both defines the problem (weight on long-term reward) and guarantees the algorithm converges | used in → |
| Uniqueness of the fixed point | V* exists uniquely — the precondition for the very phrase «optimal value function» to be legitimate | used in → |
| Error bound | Value iteration's stopping condition: ‖V_k−Vk−1‖ ≤ (1−γ)/γ · tolerance | used in → |
| The γ=1 breakdown | Without discounting, T may fail to be a contraction and V* may not exist — the mathematical root of divergence | used in → |
Boundaries: where this article stops
Where this piece stops: fixed point theorems on incomplete spaces, weighted-norm contractions (a trick that speeds up convergence), and convergence conditions for asynchronous value iteration — none covered. Sufficiency criterion: finite state space + γ<1, and the theorems of this piece apply directly.
Self-test: 4 questions
All hand-computation and «find the flaw in this proof» questions — nothing to memorize. Stuck? Go back to the section.
01What problem does each of the four proof steps of Banach's theorem solve?
① Cauchy sequence: guarantees the sequence «qualifies to converge»; ② the limit is a fixed point: the iteration is meaningful; ③ uniqueness: the word «fixed point» can be used in the singular; ④ the rate: gives a stopping criterion and an iteration budget. All four are indispensable; «numerically stable» without ②③ is not convergence.
02Why is the contraction factor of the Bellman operator exactly γ? Do max and expectation not amplify error?
max is 1-Lipschitz (no amplification), and expectation is also 1-Lipschitz over convex combinations of probabilities (no amplification). The only source of a coefficient is the discount γ multiplying the next level's value. For γ<1 the whole chain contracts; at γ=1 the chain is 1-Lipschitz — no amplification but no contraction either, and convergence may fail.
03Why is value iteration's stopping condition ‖V_k−Vk−1‖ ≤ (1−γ)/γ·tolerance instead of directly ≤ tolerance?
Because a small ‖V_k−Vk−1‖ does not directly mean a small ‖V_k−V*‖: ‖V_k−V*‖ ≤ γ/(1−γ)·‖V_k−Vk−1‖. At γ=0.9 the true error is about 9× the iteration difference, so the difference must first be scaled down by (1−γ)/γ. Using the iteration difference as the error directly stops 9× too early in precision.
04If γ=1 and there is a state with a self-loop of reward 1 per step, what happens to value iteration?
V at that state gains 1 each step and diverges to infinity (measured in T7: V=30 after 30 iterations). The contraction property fails (γ=1 is not a contraction) and V* does not exist. This is not a numerical problem — the problem itself has no finite answer: you must add discounting, add a termination, or switch to the average-reward criterion.