The Bellman Equations: Recursive Structure of Value

The single most important equation in reinforcement learning expresses a simple idea: the value of where you are equals the reward you get now plus the (discounted) value of where you end up. Richard Bellman's recursive equations underpin dynamic programming, temporal-difference learning, Q-learning and deep RL alike.

From returns to recursion#

The return satisfies $G_t = R_{t+1} + \gamma G_{t+1}$. Taking expectations under a policy $\pi$ gives the Bellman expectation equation for $V^\pi$:

and for $Q^\pi$:

They are linked by $V^\pi(s) = \sum_a\pi(a \mid s)Q^\pi(s, a)$.

Backup diagram intuition: from a state, branch over actions (weighted by the policy), then over next states and rewards (weighted by the dynamics), and "back up" the values from the leaves to the root.

Solving the expectation equation exactly#

For a finite MDP with $n$ states, the Bellman expectation equation is a linear system. Writing $\mathbf{P}^\pi$ for the state-transition matrix under $\pi$ and $\mathbf{r}^\pi$ for expected immediate rewards:

The matrix is invertible for $\gamma < 1$. Direct solution costs $O(n^3)$ — fine for small problems.

import numpy as np

# A 3-state chain: 0 -> 1 -> 2 (terminal). Policy moves right with prob 0.9, stays with 0.1.
P = np.array([[0.1, 0.9, 0.0],
              [0.0, 0.1, 0.9],
              [0.0, 0.0, 1.0]])
r = np.array([-1.0, -1.0, 0.0])        # expected reward per step from each state
gamma = 0.95
v = np.linalg.solve(np.eye(3) - gamma * P, r)
print("V^pi:", v.round(3))

# Check the Bellman equation holds
print(np.allclose(v, r + gamma * P @ v))

The Bellman optimality equations#

The optimal value functions $V^*(s) = \max_\pi V^\pi(s)$ and $Q^*(s, a) = \max_\pi Q^\pi(s, a)$ satisfy

The expectation over actions is replaced by a maximum: an optimal agent picks the best action. These equations are non-linear (because of the max), so we solve them iteratively — value iteration, policy iteration, Q-learning.

Once $Q^*$ is known, the optimal policy is greedy: $\pi^*(s) = \arg\max_aQ^*(s, a)$. This is why so many algorithms focus on estimating $Q^*$.

Why iteration converges: contraction#

Define the Bellman optimality operator $(\mathcal{T}V)(s) = \max_a\sum p(s', r \mid s, a)[r + \gamma V(s')]$. For $\gamma < 1$, $\mathcal{T}$ is a $\gamma$-contraction in the max norm:

By the Banach fixed-point theorem, repeatedly applying $\mathcal{T}$ from any starting point converges to the unique fixed point $V^*$, with error shrinking by a factor $\gamma$ each iteration. This is the theoretical foundation of value iteration.

Bootstrapping#

The Bellman equations define values in terms of other values — estimates built on estimates. This is called bootstrapping. Dynamic programming and temporal-difference methods bootstrap; Monte Carlo methods do not (they wait for actual returns). Bootstrapping reduces variance and allows learning before an episode ends, but introduces bias when estimates are wrong — a trade-off at the heart of RL algorithm design.