Bellman Operators and Value Iteration

Reinforcement learning and dynamic programming both rest on a single idea: apply one operator to a value function over and over, and the iterates converge. The reason they converge is not luck. The operator is a contraction, and its contraction rate is exactly the discount factor $\gamma$. That one fact powers value iteration, policy iteration, and every temporal-difference method that approximates a Bellman backup.

The Bellman optimality operator

Fix a finite Markov decision process $(\mathcal{S}, \mathcal{A}, P, r, \gamma)$ with $\gamma \in [0, 1)$. A value function $V : \mathcal{S} \to \mathbb{R}$ is just a vector in $\mathbb{R}^{\lvert \mathcal{S} \rvert}$. The Bellman optimality operator $T^{\ast}$ maps a value function to a new one by taking the best one-step lookahead:

$$(T^{\ast} V)(s) = \max_{a \in \mathcal{A}} \ \sum_{s'} P(s' \mid s, a)\,\bigl[\, r(s, a, s') + \gamma\, V(s') \,\bigr].$$

The optimal value function $V^{\ast}$ is characterized as the fixed point of this operator, the Bellman optimality equation $V^{\ast} = T^{\ast} V^{\ast}$.¹ Value iteration simply applies the operator repeatedly from any start, $V_{k+1} = T^{\ast} V_k$, and hopes to land on $V^{\ast}$.

A gamma-contraction in the sup-norm

Measure value functions in the sup-norm $\lVert V \rVert_{\infty} = \max_s \lvert V(s) \rvert$. The claim is that $T^{\ast}$ shrinks distances by at least $\gamma$:

$$\lVert T^{\ast} V - T^{\ast} W \rVert_{\infty} \ \le \ \gamma\, \lVert V - W \rVert_{\infty}.$$

The proof is two lines. Start from the elementary inequality $\max_a f(a) - \max_a g(a) \le \max_a \bigl(f(a) - g(a)\bigr)$. Applying it at a fixed state $s$ and cancelling the reward and transition-probability terms, which do not depend on the value function,

$$(T^{\ast} V)(s) - (T^{\ast} W)(s) \ \le \ \max_a\, \gamma \sum_{s'} P(s' \mid s, a)\,\bigl( V(s') - W(s') \bigr).$$

Each inner sum is a convex combination of the differences $V(s') - W(s')$, so it is bounded by $\lVert V - W \rVert_{\infty}$. The same bound holds with $V$ and $W$ swapped, giving $\lvert (T^{\ast} V)(s) - (T^{\ast} W)(s) \rvert \le \gamma \lVert V - W \rVert_{\infty}$ for every $s$, and taking the max over $s$ finishes it.² The discount factor is the entire budget for how much the operator can fail to contract.

Banach gives geometric convergence

The space $\bigl( \mathbb{R}^{\lvert \mathcal{S} \rvert}, \lVert \cdot \rVert_{\infty} \bigr)$ is complete, and $T^{\ast}$ is a contraction with modulus $\gamma < 1$. The Banach fixed-point theorem then delivers three facts at once: $T^{\ast}$ has a unique fixed point $V^{\ast}$, the iterates $V_{k+1} = T^{\ast} V_k$ converge to it from any starting $V_0$, and the convergence is geometric,

$$\lVert V_k - V^{\ast} \rVert_{\infty} \ \le \ \gamma^{k}\, \lVert V_0 - V^{\ast} \rVert_{\infty}.$$

To reach accuracy $\varepsilon$ takes on the order of $\log(1/\varepsilon) / \log(1/\gamma)$ iterations, which blows up as $\gamma \to 1$: long-horizon problems are genuinely harder to solve, and the contraction rate says exactly how much.

A two-state worked example

Take two states $\{A, B\}$ and $\gamma = 0.9$. In $B$ the only move pays reward $1$ and stays in $B$; in $A$ the agent chooses between waiting (reward $0$, stay in $A$) and going (reward $0$, move to $B$). Both transitions are deterministic, so the operator is

$$(T^{\ast} V)(A) = \max\bigl( \gamma V(A),\ \gamma V(B) \bigr), \qquad (T^{\ast} V)(B) = 1 + \gamma V(B).$$

Apply $T^{\ast}$ to two different value functions,

$$V = \begin{bmatrix} 0 \\ 0 \end{bmatrix}, \qquad W = \begin{bmatrix} 5 \\ 10 \end{bmatrix}, \qquad \lVert V - W \rVert_{\infty} = 10.$$

Then $T^{\ast} V = (\,\max(0, 0),\ 1 + 0\,) = (0, 1)$ and $T^{\ast} W = (\,\max(4.5, 9),\ 1 + 9\,) = (9, 10)$, so

$$\lVert T^{\ast} V - T^{\ast} W \rVert_{\infty} = \max\bigl(\lvert 0 - 9 \rvert,\ \lvert 1 - 10 \rvert\bigr) = 9 = 0.9 \times 10 = \gamma\, \lVert V - W \rVert_{\infty}.$$

The bound is met with equality, so $\gamma$ is the tightest possible constant. The fixed point solves $V^{\ast}(B) = 1 + 0.9\,V^{\ast}(B)$, giving $V^{\ast}(B) = 10$ and $V^{\ast}(A) = 0.9 \times 10 = 9$. Running value iteration from $V_0 = 0$ makes the geometric law exact rather than merely an upper bound:

$$\lVert V_k - V^{\ast} \rVert_{\infty} = 10\,(0.9)^{k} = 10,\ 9,\ 8.1,\ 7.29,\ \dots$$

Each sweep multiplies the error by precisely $\gamma$, so on a log axis the error falls along a straight line of slope $\log \gamma$.

Value iteration in a gridworld

The demo runs the same operator on a stochastic gridworld. An action succeeds with probability $1 - \text{slip}$ and otherwise slips to a perpendicular cell; the goal pays $+1$ and the pit pays $-1$. Stepping $V_{k+1} = T^{\ast} V_k$ fills in the value heatmap and the greedy policy arrows converge. The second panel plots $\lVert V_k - V^{\ast} \rVert_{\infty}$ against $k$ on a log axis, with the bound $\gamma^{k} \lVert V_0 - V^{\ast} \rVert_{\infty}$ overlaid.

Value iteration on a stochastic gridworldinteractive

discount γ = 0.90slip = 0.20

PlayStepReset

iteration k

0

‖V_k − V*‖∞

8.81e+0

measured rate

n/a

contraction γ

0.90

‖V_k − V*‖∞ (measured)

γ^k ‖V_0 − V*‖∞ (bound)

The measured decay rate equals $\gamma$ no matter how large the grid is, how much noise the slip injects, or where the rewards sit. That invariance is the practical payoff of the contraction: the same geometric guarantee that makes this tiny gridworld converge is what lets approximate value iteration scale to problems with billions of states.

Footnotes

1. Sutton & Barto, Reinforcement Learning: An Introduction (2018). ↩

2. Bertsekas, Dynamic Programming and Optimal Control. ↩