The value of a state is a promise about the future: the expected total discounted reward from here on. The Bellman equation says that promise can be split into two pieces, what you get right now and a discounted promise about the state you land in next. That is it. Every value based algorithm in reinforcement learning is a way of making both sides of that equation agree.

The reason this is powerful rather than merely true is that it turns an infinite sum over trajectories into a local consistency condition between a state and its neighbors. You never have to enumerate futures. You only have to make each state consistent with the states one step away, and the Markov property guarantees that local consistency everywhere implies global correctness.

The Bellman expectation equations

Fix a policy $\pi$. Start from the definition $V^\pi(s) = \mathbb{E}_\pi[G_t \mid s_t = s]$ and the return recursion $G_t = r_{t+1} + \gamma G_{t+1}$:

For the second term, condition on the next state and use the tower property of conditional expectation:

By the Markov property, once $s_{t+1}$ is known, the earlier state $s_t$ carries no further information about $G_{t+1}$, so the inner expectation is $V^\pi(s_{t+1})$. Expanding the outer expectation over the action and the transition gives the Bellman expectation equation:

The same argument on action values, conditioning on $(s_{t+1}, a_{t+1})$ instead, gives

Both are systems of $|\mathcal{S}|$ (or $|\mathcal{S}| \cdot |\mathcal{A}|$) linear equations in as many unknowns. In matrix form, $v_\pi = r_\pi + \gamma P_\pi v_\pi$, with the unique solution $v_\pi = (I - \gamma P_\pi)^{-1} r_\pi$ as shown in the previous note. Linearity is the important feature: for a fixed policy, evaluation is a linear solve.

The Bellman optimality equations

Now consider the optimal value functions $V^*(s) = \sup_\pi V^\pi(s)$ and $Q^*(s, a) = \sup_\pi Q^\pi(s, a)$. They satisfy the Bellman optimality equations:

The sum over actions weighted by the policy has become a max over actions. The optimal agent, at every state, picks whichever action has the highest one step lookahead value. Intuitively that must be right: if $V^*$ really is the best achievable from every state, then the best thing to do now is whatever leads to the best combination of immediate reward and best achievable continuation.

That intuition is not a proof, and it is worth being clear about what needs proving. Two separate claims are hiding here:

1. The optimality equation has a solution, and only one.
2. That solution is $V^*$, the supremum over policies, and a policy achieving it exists.

The max makes the equation nonlinear, so the matrix inverse that solved the expectation equation is unavailable. The route to both claims is through operators and contraction.

The Bellman operators

Value functions on a finite state space are vectors in $\mathbb{R}^{|\mathcal{S}|}$. Define the Bellman expectation operator for a policy $\pi$ and the Bellman optimality operator as maps from value vectors to value vectors:

In this language the Bellman expectation equation says $V^\pi$ is a fixed point of $\mathcal{T}^\pi$, and the optimality equation says $V^*$ is a fixed point of $\mathcal{T}^*$. The question of existence and uniqueness of solutions becomes the question of whether these operators have unique fixed points.

Two elementary properties of the operators will be used repeatedly.

Monotonicity. If $u \le v$ componentwise, then $\mathcal{T}^\pi u \le \mathcal{T}^\pi v$ and $\mathcal{T}^* u \le \mathcal{T}^* v$. This is immediate, since each operator is a nonnegative combination of the entries of its input plus a constant, and a max of larger things is larger.

Constant shift. For a constant $c$ and the all ones vector $\mathbf{1}$, $\mathcal{T}^\pi(v + c\mathbf{1}) = \mathcal{T}^\pi v + \gamma c \mathbf{1}$, and likewise for $\mathcal{T}^*$. Adding $c$ to every value adds $\gamma c$ to every backed up value, because the probabilities sum to one.

Theorem: the Bellman operators are contractions

The norm that makes this work is the sup norm, $\|v\|_\infty = \max_s |v(s)|$.

Theorem. For any policy $\pi$, $\mathcal{T}^\pi$ is a $\gamma$ contraction in $\|\cdot\|_\infty$, and so is $\mathcal{T}^*$. That is, for all $u, v \in \mathbb{R}^{|\mathcal{S}|}$,

Proof for $\mathcal{T}^\pi$. Fix a state $s$. The immediate reward terms cancel in the difference, leaving

The double sum is a convex combination of the entries of $u - v$, since $\pi(\cdot \mid s)$ and $P(\cdot \mid s, a)$ are probability distributions. A convex combination of numbers is bounded in absolute value by the largest absolute value among them, so

This holds for every $s$, so it holds for the max over $s$. $\square$

Proof for $\mathcal{T}^*$. The max requires one extra lemma.

Lemma. For any two functions $f, g$ on a finite set, $|\max_a f(a) - \max_a g(a)| \le \max_a |f(a) - g(a)|$.

Proof of lemma. Let $a^\star$ attain $\max_a f(a)$. Then $\max_a f(a) - \max_a g(a) = f(a^\star) - \max_a g(a) \le f(a^\star) - g(a^\star) \le \max_a |f(a) - g(a)|$. Swapping the roles of $f$ and $g$ gives the same bound on the negative, hence on the absolute value. $\square$

Now fix $s$ and set $f(a) = R(s, a) + \gamma \sum_{s'} P(s' \mid s, a) u(s')$ and $g(a)$ the same with $v$. By the lemma,

by the same convex combination argument as before. Taking the max over $s$ finishes the proof. $\square$

The content of the proof is small: every Bellman backup is an average of neighboring values scaled by $\gamma$, and averaging cannot increase the largest gap between two vectors, while $\gamma$ strictly shrinks it. The max in $\mathcal{T}^*$ does not change this because a max of averages is still no worse than the largest average.

The Banach fixed point theorem

Theorem (Banach). Let $(X, d)$ be a nonempty complete metric space and $T : X \to X$ a contraction with constant $k \in [0, 1)$. Then $T$ has exactly one fixed point $x^*$, and for any starting point $x_0$ the iterates $x_{n+1} = T x_n$ converge to $x^*$ with

Proof. The iterates are Cauchy. Applying the contraction $n$ times, $d(x_{n+1}, x_n) \le k^n d(x_1, x_0)$. For $m > n$, the triangle inequality and the geometric series give

which goes to zero as $n \to \infty$.

The limit is a fixed point. By completeness the sequence converges to some $x^* \in X$. A contraction is Lipschitz and therefore continuous, so $T x^* = T(\lim x_n) = \lim T x_n = \lim x_{n+1} = x^*$.

Uniqueness. If $Tx = x$ and $Ty = y$, then $d(x, y) = d(Tx, Ty) \le k\, d(x, y)$, which with $k < 1$ forces $d(x, y) = 0$.

Rates. Letting $m \to \infty$ in the Cauchy estimate gives the second bound. For the first, $d(x_n, x^*) = d(T x_{n-1}, T x^*) \le k\, d(x_{n-1}, x^*)$, and iterate. $\square$

$\mathbb{R}^{|\mathcal{S}|}$ with the sup norm is complete (it is finite dimensional, and all norms on a finite dimensional space are equivalent), so the theorem applies to both Bellman operators.

Consequences

Put the two theorems together and the first of the two claims above is settled, with a convergence rate as a bonus.

Corollary 1 (existence and uniqueness). $\mathcal{T}^\pi$ has a unique fixed point, which must therefore be $V^\pi$. $\mathcal{T}^*$ has a unique fixed point; call it $v^*$ for now.

Corollary 2 (value iteration converges). From any $v_0$, the sequence $v_{k+1} = \mathcal{T}^* v_k$ satisfies

Convergence is geometric with ratio $\gamma$, from any initialization. The same holds for $v_{k+1} = \mathcal{T}^\pi v_k$ converging to $V^\pi$, which is iterative policy evaluation.

Corollary 3 (a computable error bound). From the second Banach bound, after observing consecutive iterates,

This is what turns value iteration into an algorithm with a stopping rule. You do not need to know $v^*$ to bound your distance from it; the size of the last step is enough.

The fixed point is the optimal value, and a greedy policy achieves it

Corollary 1 gave a unique solution $v^*$ to the optimality equation. It remains to show that $v^* = V^*$, the supremum over policies, and that an optimal policy exists. This is the second claim, and it is the one that makes the whole thing worth anything.

Define a greedy policy with respect to a value vector $v$ as any deterministic policy $\pi_v$ with

By construction, $\mathcal{T}^{\pi_v} v = \mathcal{T}^* v$: for the greedy policy, the expectation backup of $v$ equals the max backup of $v$.

Theorem. Let $v^*$ be the fixed point of $\mathcal{T}^*$ and $\pi^*$ a greedy policy with respect to $v^*$. Then $V^{\pi^*} = v^*$, and $v^* \ge V^\pi$ for every policy $\pi$. Hence $v^* = V^*$ and $\pi^*$ is an optimal policy, deterministic and stationary.

Proof. The greedy policy achieves $v^*$. Since $\pi^*$ is greedy for $v^*$ and $v^*$ is a fixed point of $\mathcal{T}^*$,

So $v^*$ is a fixed point of $\mathcal{T}^{\pi^*}$. But $\mathcal{T}^{\pi^*}$ has a unique fixed point, namely $V^{\pi^*}$. Therefore $V^{\pi^*} = v^*$.

No policy does better. Take any policy $\pi$. For any vector $v$, $\mathcal{T}^\pi v \le \mathcal{T}^* v$ componentwise, because an average over actions is at most the max over actions. Apply this to $v^*$ and use monotonicity of $\mathcal{T}^\pi$ repeatedly:

The first equality is Corollary 2 applied to $\mathcal{T}^\pi$ started from $v^*$. The inequality is by induction: $(\mathcal{T}^\pi)^{k} v^* \le (\mathcal{T}^\pi)^{k-1}\mathcal{T}^* v^* = (\mathcal{T}^\pi)^{k-1} v^* \le \cdots \le v^*$, using $\mathcal{T}^* v^* = v^*$ at each step. The last equality is because $v^*$ is fixed.

So $V^\pi \le v^* = V^{\pi^*}$ for every $\pi$, which says $v^* = \sup_\pi V^\pi = V^*$ and that $\pi^*$ attains the supremum in every state simultaneously. $\square$

This is the theorem that was promised in the previous note: every finite discounted MDP has an optimal policy, and a deterministic stationary one at that. The proof also shows something practical. If you can compute $V^*$, or $Q^*$, then acting optimally is just taking the argmax. All the difficulty of the problem lives in the value function.

The same statements hold for $Q^*$, with the operator

which is a $\gamma$ contraction on $\mathbb{R}^{|\mathcal{S}| \cdot |\mathcal{A}|}$ by the identical argument. The $Q$ form matters because a greedy policy with respect to $Q^*$ needs no model: $\pi^*(s) = \arg\max_a Q^*(s, a)$ with no $P$ in sight. That is the reason model free methods learn $Q$ rather than $V$.

What the theory buys you

• A target. $V^*$ and $Q^*$ exist and are unique, so "learn the optimal value function" is a well posed goal.
• An algorithm. Iterating $\mathcal{T}^*$ converges geometrically from anywhere. Dynamic programming is that algorithm and its relatives, for when the model is known.
• A stopping rule. The distance to the optimum is bounded by the size of the last update.
• A template for the model free case. Temporal difference learning replaces the expectation in $\mathcal{T}^*$ with a single sampled transition. The contraction is what makes those noisy iterations converge too.

Where this breaks

The contraction constant is $\gamma$, so as $\gamma \to 1$ the guarantees weaken and the number of iterations to a given accuracy grows like $1 / (1 - \gamma)$. At $\gamma = 1$ the operator is only nonexpansive and the theorem says nothing; convergence then needs a separate argument about termination.

More seriously, everything above is for a tabular value function, a vector with one entry per state. Once the value function is approximated by a parametric model, the projection back onto the model class need not be a contraction in the sup norm, and the combination of bootstrapping, off policy sampling and function approximation can diverge. The theory in this note is exact for small problems and a guide, not a guarantee, for large ones.

References

• Bellman. Dynamic Programming. Princeton University Press, 1957.
• Puterman. Markov Decision Processes. Wiley, 1994, chapter 6.
• Sutton, Barto. Reinforcement Learning: An Introduction, 2nd ed. MIT Press, 2018, chapters 3 and 4.
• Bertsekas. Dynamic Programming and Optimal Control, vol. 2. Athena Scientific.