The Banach Fixed-Point Theorem and Why Value Iteration Converges

If you have ever run iterative policy evaluation and watched the value estimates settle down to a fixed answer no matter how you initialized them, you have seen the Banach fixed-point theorem at work. The whole story rests on one structural fact: the Bellman policy-evaluation operator shrinks distances. Apply it, and any two value functions move strictly closer together. Apply it forever, and everything collapses onto a single point: the true value function.

This post builds that argument carefully, the way I worked through it from scratch. We start with the right norm to measure value functions, show the Bellman operator stays inside our space and contracts, prove the Banach fixed-point theorem in full, and then collect the payoff as a corollary that justifies the policy-evaluation algorithm line by line.

The right way to measure value functions: the sup norm

Before we can say "the iterates get closer," we need a notion of distance. For value functions the natural choice is the worst-case-over-states norm.

Let $x = (x_1,\dots,x_n) \in \mathbb{R}^n$. The infinity norm (or sup norm) is

Intuitively:

• It measures the largest absolute component of the vector.
• Its unit ball is a cube in $\mathbb{R}^n$, not a sphere.
• It captures worst-case coordinate magnitude, which is exactly what we care about when we want a value estimate to be good at every state, not just on average.

The operator norm it induces

A linear map $A : \mathbb{R}^n \to \mathbb{R}^m$ is represented by a matrix $A = (a_{ij}) \in \mathbb{R}^{m \times n}$. The operator norm induced by the infinity vector norm asks: how much can $A$ amplify a vector, in the worst case?

This is the largest possible blow-up factor. The reason it matters here is that the Bellman operator involves a transition matrix, and we will need to know that transition matrices never amplify the sup norm. That fact follows from a clean formula.

Theorem: the induced infinity norm is the max absolute row sum

Let $A \in \mathbb{R}^{m\times n}$. Then

In words, the induced infinity operator norm equals the largest absolute row sum. Here is why.

Step 1: Upper bound. For any $x \neq 0$, each output coordinate is

so by the triangle inequality and the definition of the sup norm,

Taking the supremum over $i$,

Dividing by $\|x\|_\infty$ and taking the supremum over $x$ gives $\|A\|_\infty \le \sup_i \sum_j |a_{ij}|$. So the row-sum quantity is at least the operator norm.

Step 2: Lower bound. We show the bound is actually achieved by exhibiting a vector that nearly saturates it. Let

For any $\varepsilon > 0$ pick a row $i_\varepsilon$ whose absolute sum almost realizes the supremum,

The trick is to choose the input that aligns perfectly with the signs of that row, turning every term positive:

Then $\|x^{(\varepsilon)}\|_\infty = 1$, and in coordinate $i_\varepsilon$ the products $a_{i_\varepsilon j}\,x^{(\varepsilon)}_j = |a_{i_\varepsilon j}|$, so

Since $\varepsilon$ was arbitrary, $\|A\|_\infty \ge R(A)$. Combining the two inequalities gives $\|A\|_\infty = R(A)$. $\blacksquare$

The immediate consequence we will use: a row-stochastic matrix (each row a probability distribution, nonnegative entries summing to one) has every absolute row sum equal to exactly $1$, so its induced infinity norm is $1$. It can rotate and average a vector, but it can never make the worst-case coordinate larger.

The Bellman policy-evaluation operator

The space $V$ of bounded value functions

Let $S$ be the state space, finite or countable, and define

This is the space of bounded value functions, and under the sup norm it is a Banach space: a complete normed space, meaning every Cauchy sequence has its limit sitting inside $V$. Completeness is the unsung hero of the whole argument; it is what guarantees the limit of our iterates is itself a legitimate value function.

Induced reward and transition kernel

Fix a stationary randomized decision rule $d$, which assigns to each state $s$ a distribution $q_d(s,\cdot)$ over actions. Averaging the reward and the transition kernel over that action distribution collapses the MDP into a Markov reward process:

Let $P_d$ be the corresponding transition operator. Because each $p_d(\cdot|s)$ is a probability distribution, $P_d$ is row-stochastic, and by the row-sum formula above, $\|P_d\|_\infty = 1$.

Lemma: the Bellman map stays inside $V$

Before we can talk about contraction or fixed points, we must check the operator does not throw us out of our space. Assume rewards are bounded, $|r(s,a)| \le M$, and the discount satisfies $0 \le \lambda < 1$. Define

Then $L_d : V \to V$. Here is the proof in three small steps.

Step 1: $r_d \in V$. Since $q_d(s,\cdot)$ is a probability distribution,

so $\|r_d\|_\infty \le M$.

Step 2: $P_d$ does not increase the norm. Because $p_d(\cdot|s)$ is a probability distribution, the next-state value is an average of values, and an average never exceeds the worst case:

Equivalently, $\|P_d\|_\infty = 1$, so $\|P_d v\|_\infty \le \|P_d\|_\infty \|v\|_\infty = \|v\|_\infty$.

Step 3: Combine.

Therefore $L_d v \in V$. $\blacksquare$

Remark. $L_d$ is affine, not linear, because $L_d(0) = r_d \neq 0$ unless rewards vanish everywhere. That additive reward term is why the fixed point is not simply zero; it pins the value function to a nontrivial location. Closure $L_d : V \to V$ is the prerequisite for everything that follows: only a map that sends $V$ into itself can be iterated and can have a fixed point in $V$.

The Banach fixed-point theorem

Now the centerpiece. This is the abstract engine; in the next section we just plug $L_d$ into it.

Theorem (Banach Fixed-Point Theorem). Suppose $V$ is a Banach space and $T:V \to V$ is a contraction mapping, meaning there exists $\lambda$ with $0 \le \lambda < 1$ such that

Then:

• (a) There exists a unique $v^* \in V$ with $Tv^* = v^*$.
• (b) For any starting point $v^0 \in V$, the iteration $v^{n+1} = Tv^n = T^{\,n+1} v^0$ converges to $v^*$.

Why the proof has the shape it does

A Banach space is complete: every Cauchy sequence converges to a limit inside $V$. That dictates the entire strategy. We cannot point at the fixed point directly, so instead we manufacture it as the limit of the iteration. The argument has four forced moves:

• Show the iteration $\{v^n\}$ is Cauchy.
• Use completeness to conclude it converges to some $v^* \in V$.
• Show that limit satisfies $Tv^* = v^*$.
• Show there cannot be two distinct fixed points.

A contraction is precisely the property that makes successive iterates close the gap by a uniform factor $\lambda < 1$. That uniform factor is what powers the geometric series in the Cauchy estimate.

Step 1: the iterates form a Cauchy sequence

Step 1(a): consecutive steps shrink geometrically. From $v^{n+1} = T v^n$ and the contraction property applied to the previous step,

Peeling this off repeatedly all the way down to the first step,

Each application of $T$ shrinks distances by at least $\lambda$, so the step sizes decay geometrically like $\lambda^n$. The iteration brakes hard.

Step 1(b): control any gap, not just consecutive ones. Being Cauchy requires that distant iterates also be close, so fix $m \ge 1$ and chain the steps with the triangle inequality:

The geometric sum is bounded uniformly in $m$ by its infinite tail:

Hence

Since $0 \le \lambda < 1$ we have $\lambda^n \to 0$, so for any $\varepsilon > 0$ there is an $N$ with $\|v^{n+m} - v^n\| < \varepsilon$ for all $n \ge N$ and all $m \ge 1$. The sequence is Cauchy. The intuition: far out in the sequence, the total remaining travel is bounded by the tail of a geometric series, which is arbitrarily small.

Step 2: completeness hands us a limit

Because $V$ is Banach, every Cauchy sequence converges in $V$. So there exists $v^* \in V$ with

The contraction makes the iterates bunch up ever tighter; completeness guarantees there is an actual point in $V$ where they land. Without completeness they could "converge" toward a hole not in the space, and the theorem would fail.

Step 3: the limit is a fixed point

Two routes to $Tv^* = v^*$; pick whichever you find cleaner.

Step 3(a): limit interchange via continuity. A contraction is Lipschitz, hence continuous, so it commutes with limits:

But $T v^n = v^{n+1}$, and the shifted sequence has the same limit,

Therefore $Tv^* = v^*$.

Step 3(b): the norm trick, no interchange needed. Estimate the residual directly by inserting $Tv^n$:

Apply contraction to the first term and use $Tv^n = v^{n+1}$ on the second:

Let $n \to \infty$. Both terms vanish since $v^n \to v^*$, so $\|Tv^* - v^*\| = 0$ and thus $Tv^* = v^*$. Intuitively: once $v^n$ is near $v^*$, applying $T$ cannot pull them apart (contraction), and $Tv^n = v^{n+1}$ is itself near $v^*$, so $Tv^*$ is squeezed onto $v^*$.

Step 4: the fixed point is unique

Suppose $u^* \in V$ is another fixed point, $Tu^* = u^*$. Then

Rearranging,

Since $1 - \lambda > 0$ and norms are nonnegative, this forces $\|v^* - u^*\| = 0$, so $v^* = u^*$. A contraction must strictly shrink the distance between two distinct points, but two fixed points do not move at all, so their distance cannot shrink unless it is already zero. This completes the proof. $\blacksquare$

Iterative policy evaluation as a fixed-point method

We have shown that for a stationary Markov decision rule $d \in D^{MR}$, the discounted value function $v_\lambda^{d^\infty}$ satisfies the fixed-point equation

Everything is now in place to compute that fixed point by simple iteration, because $L_d$ is a contraction on the Banach space $(V, \|\cdot\|_\infty)$.

Lemma: the Bellman operator is a contraction

Let $0 \le \lambda < 1$. Then for all $v, w \in V$,

so $L_d$ is a contraction with modulus $\lambda$. The proof is short because the affine reward term cancels. For any $s \in S$,

The shared $r_d(s)$ disappears, which is exactly why an affine map can still contract. Taking the sup norm,

Since $P_d$ is row-stochastic it does not increase the infinity norm, $\|P_d u\|_\infty \le \|u\|_\infty$, so

The discount factor $\lambda$ is the contraction modulus. This is the deep reason discounting matters: it is not just a modeling convenience for valuing the future, it is the mathematical lever that makes the infinite-horizon problem well-posed and solvable by iteration. As $\lambda \to 1$ the contraction weakens and convergence slows, which you feel directly in practice as longer-running evaluation.

Corollary: existence, uniqueness, and convergence

Because $(V, \|\cdot\|_\infty)$ is Banach and $L_d$ is a contraction, the Banach fixed-point theorem immediately gives:

• there exists a unique $v^* \in V$ with $L_d v^* = v^*$;
• for any initialization $v^{(0)} \in V$, the iteration $$v^{(k+1)} = L_d v^{(k)} = r_d + \lambda P_d v^{(k)}$$ converges to $v^*$.

Moreover, that unique fixed point is exactly the policy value function,

Read that twice: the answer does not depend on $v^{(0)}$. You can start from all zeros, from random noise, from a wild guess, and the iteration funnels you to the same value function. The Banach theorem promised exactly that.

The algorithm

The corollary is a recipe. Iterate the operator until consecutive estimates stop moving, and the sup-norm gap between them upper-bounds how far you are from the true fixed point.

• Inputs: stationary rule $d$, induced reward $r_d$, induced transition matrix $P_d$, discount $\lambda \in (0,1)$, tolerance $\varepsilon > 0$.
• Output: an approximation $v$ to $v_\lambda^{d^\infty}$.

1. Initialize $v^{(0)} \in V$, for example $v^{(0)} \equiv 0$.
2. For $k = 0, 1, 2, \dots$:
   • Update $v^{(k+1)} \leftarrow r_d + \lambda P_d v^{(k)}$.
   • If $\|v^{(k+1)} - v^{(k)}\|_\infty < \varepsilon$, return $v^{(k+1)}$.

That single update line is the contraction in code. Every pass closes the remaining gap by at least a factor of $\lambda$, so the number of iterations to reach tolerance scales like $\log \varepsilon / \log \lambda$.

From policy evaluation to value iteration

Everything so far was for a fixed decision rule $d$. The optimality operator replaces that fixed rule with a maximization over actions,

and both structural facts survive the max. Closure holds by the same bounded-reward argument. Contraction holds because a maximum can never amplify a difference: using $|\max_a f(a) - \max_a g(a)| \le \max_a |f(a)-g(a)|$, for any $v, w$ and any state $s$,

where the last step is the row-stochastic bound once more. Taking the supremum over states gives $\|T^\star v - T^\star w\|_\infty \le \lambda \|v-w\|_\infty$, so $T^\star$ is a contraction on the same Banach space $(V, \|\cdot\|_\infty)$.

The Banach fixed-point theorem then delivers the same three gifts: a unique $v^\star$ with $T^\star v^\star = v^\star$, which the Bellman optimality equation identifies as the optimal value function; convergence of $v^{(k+1)} = T^\star v^{(k)}$ from any initialization; and the same geometric rate $\lambda$. That iteration is exactly value iteration. One theorem, two operators, and the two workhorse algorithms of dynamic programming both come out convergent. This structure is the backbone of nearly every dynamic-programming method in reinforcement learning.