RobotGuide
Math foundations/Norms and fixed points: where «it always converges» comes from

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.

55 min2 theorems10 proof steps4 self-test questions

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:

‖x_m − x_n‖ ≤ Σk=nm−1 ‖xk+1−x_k‖ ≤ ‖x₁−x₀‖·Σk=nm−1 γ^k ≤ ‖x₁−x₀‖·γ^n/(1−γ)

γ^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).

|(TV)(s)−(TW)(s)| = |max_a Σs' p(s'|s,a)[r+γV(s')] − max_a Σs' p(s'|s,a)[r+γW(s')]|
≤ max_a |γ Σs' p(s'|s,a)(V(s')−W(s'))| ≤ γ max_a Σs' p(s'|s,a)·‖V−W‖_∞ = γ‖V−W‖_∞

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)

  1. Theorem 5.1 error bound: ‖V_k − V*‖_∞ ≤ γ^k/(1−γ)·‖V₁−V₀‖ = 0.9^k/0.1 × 1.
  2. Require 0.9^k/0.1 ≤ 0.01, i.e. 0.9^k ≤ 0.001.
  3. [object Object]
  4. 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.
Answer

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 hereThe counterpart in RLUsed in
Contraction factor γThe discount factor: it both defines the problem (weight on long-term reward) and guarantees the algorithm convergesused in →
Uniqueness of the fixed pointV* exists uniquely — the precondition for the very phrase «optimal value function» to be legitimateused in →
Error boundValue iteration's stopping condition: ‖V_k−Vk−1‖ ≤ (1−γ)/γ · toleranceused in →
The γ=1 breakdownWithout discounting, T may fail to be a contraction and V* may not exist — the mathematical root of divergenceused 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.

Up next

The full series · 27 articles

T1The Matrix Is a Ledger for Rotation≈ 25 minT2From Slope to Gradient: The First Line of Every Robot Learning Algorithm≈ 25 minT3Vectors and forces: the physical reading of the dot productAbout 20 minT4Two Rulers and a Better Rulerabout 25 minT5The Ledger of One Motor Revolution: Radians, Speed, and Powerabout 20 minT6Complex multiplication is rotation: the one-dimensional version of quaternionsAbout 20 minT7Bases and coordinates: why robots put everything in matrices45 minT8Matrix Multiplication: Chaining Transformations, Not a Table OperationAbout 40 minT9The Jacobian: Rotate a Joint One Degree — How Far Does the End Effector Move?About 45 minT10Eigenvectors: The Directions a Matrix Dare Not Touchabout 45 minT11SVD and the Pseudoinverse: When There Is No Exact Solution, Find the Nearest Oneabout 50 minT12Taylor expansion: putting a straight line to work in place of a curveAbout 40 minT13Probability spaces: why «random» needs axioms50 minT14Expectation: A Rigorous Construction of «Average»About 55 minT15Conditional Expectation: What the Vertical Bar Really Means≈ 60 minT16Four inequalities: the quantitative answer to «how many samples are enough»45 minT17Norms and fixed points: where «it always converges» comes from55 minT18Markov Chains: When the Time Average Equals the Ensemble Averageabout 55 minT19The Mathematical Construction of the MDP: What One Axiom Is Worthabout 50 minT20Dynamic Programming: The Accounting for Two Iterations≈ 50 minT21Optimization: why constraints cannot rely on penalties aloneAbout 55 minT22Stochastic Approximation: Every Term in the Learning-Rate Formulaabout 55 minT23The Mathematics of Contact: Hertz Theoryabout 45 minT24Friction and the Friction Cone: The Geometry of Constraintsabout 40 minT25Force Closure and Grasp Metrics: ε Is a Linear ProgramAbout 50 minT26Contact Kinematics: Why Rolling Is Not «Sliding Along»≈ 45 minT27Slip detection: from «I felt it» to «I computed it»About 50 min