The Bellman Equations

Recall that for a policy $\pi$, the state-value function is defined as the expected return starting from state $s$ and following $\pi$ thereafter:

The return $G_t$ satisfies an immediate recursive identity purely from its definition as an infinite sum:

Substituting this into the definition of $V^\pi$, and using the Markov Decision Process property that transitions depend only on the current state and action, gives the Bellman equation for $V^\pi$:

In words: to evaluate a state, average over the policy's action choice, then average over the environment's stochastic transition, the sum of the immediate reward and the discounted value of the successor state. This is a one-step lookahead identity — it relates $V^\pi(s)$ to $V^\pi(s')$ for states $s'$ reachable in a single transition, rather than to the entire future trajectory. The same idea gives the Bellman equation for the action-value function $Q^\pi(s,a) = \mathbb{E}_\pi[G_t \mid S_t=s, A_t=a]$:

The two functions are mutual expectations of one another: $V^\pi(s) = \sum_a \pi(a\mid s)\, Q^\pi(s,a)$, and $Q^\pi(s,a) = \mathbb{E}[R_{t+1} + \gamma V^\pi(S_{t+1}) \mid S_t=s, A_t=a]$. Substituting one definition into the other reproduces both Bellman equations above — they are two views of the same recursive consistency requirement, connected via State-Value and Action-Value Functions. Crucially, the Bellman equation is not an algorithm. It is a system of equations — one equation per state — that the true value function $V^\pi$ is guaranteed to satisfy. Whether we solve that system by matrix algebra, by iterative sweeps (Iterative Policy Evaluation), or by sampling (temporal-difference learning), is a separate question addressed elsewhere. Here the goal is to understand why the equation is true and what structure it reveals.

Deriving the equation. Start from the definition of $V^\pi(s)$ and unroll one step of the expectation using the law of total expectation, conditioning first on the action $A_t$ chosen by $\pi$, then on the resulting next state $S_{t+1}$ and reward $R_{t+1}$ given by the environment's dynamics $p(s', r \mid s, a)$. Because $G_{t+1}$'s expectation given $S_{t+1}=s'$ (and future policy behavior) is exactly $V^\pi(s')$ by definition, this substitution closes the recursion — no term involving the raw return remains.

Solving it exactly (finite MDPs). For a finite MDP with $n$ states, write the Bellman equation in matrix form. Define the policy-induced reward vector $\mathbf{r}^\pi \in \mathbb{R}^n$ with entries $r^\pi(s) = \sum_a \pi(a\mid s)\sum_{s',r} p(s',r\mid s,a)\, r$, and the policy-induced transition matrix $P^\pi \in \mathbb{R}^{n\times n}$ with entries $P^\pi(s,s') = \sum_a \pi(a\mid s) \sum_r p(s',r\mid s,a)$. Then:

This closed form is exact, but inverting an $n \times n$ matrix costs $O(n^3)$ — often impractical for large state spaces, which is precisely why iterative methods dominate practice.

Iterative view. Treat the Bellman equation as a fixed-point condition for an operator $T^\pi$ acting on value functions:

$V^\pi$ is the unique fixed point: $T^\pi V^\pi = V^\pi$. Repeatedly applying $T^\pi$ to any starting guess converges to $V^\pi$ — this is the basis of iterative policy evaluation, foreshadowed here and developed as its own topic. ```

# Computing one application of the Bellman operator T^pi

# Inputs: policy pi, dynamics p(s', r | s, a), discount gamma, current estimate V

# Output: updated value estimate V_new (one Bellman "backup" per state) function BELLMAN_BACKUP(pi, p, gamma, V): V_new = array of size |S|, initialized to 0 for each state s in S: total = 0 for each action a with pi(a | s) > 0: action_value = 0 for each (s_next, r) with p(s_next, r | s, a) > 0: action_value += p(s_next, r | s, a) (r + gamma V[s_next]) total += pi(a | s) * action_value V_new[s] = total return V_new

# Checking the Bellman equation holds (a consistency test, not a solver) function CHECK_CONSISTENCY(V, pi, p, gamma, tolerance): V_updated = BELLMAN_BACKUP(pi, p, gamma, V) return max over s of |V_updated[s] - V[s]| < tolerance ``` The pseudocode above is deliberately not an optimization loop — it computes a single right-hand side evaluation of the Bellman equation for every state. Running it repeatedly to convergence is the subject of iterative policy evaluation; here it illustrates that the Bellman equation's right-hand side is a well-defined, computable quantity given $V$, $\pi$, and the model.

Cost of one backup. For a single state, the backup sums over all actions with nonzero policy probability, and for each action over all possible $(s', r)$ pairs. If there are $|A|$ actions and at most $|S|$ possible successor states, one backup costs $O(|A|\cdot|S|)$. Doing this for every state costs $O(|S|^2 |A|)$ per full sweep — this is the per-iteration cost inherited by iterative policy evaluation, and it is why the Bellman equation itself, while exact, is expensive to evaluate exhaustively on large state spaces.

Cost of exact solution. Solving $\mathbf{V}^\pi = (I - \gamma P^\pi)^{-1}\mathbf{r}^\pi$ directly requires forming and inverting an $|S|\times|S|$ matrix, costing $O(|S|^3)$ via Gaussian elimination. This is exact and non-iterative but scales poorly; it is rarely used beyond small MDPs or as a ground-truth check for iterative methods.

Correctness: existence and uniqueness of $V^\pi$. Why does the Bellman equation have a solution, and why is it exactly the true value function? Two arguments: 1. Derivation argument. The equation is derived directly from the definition of $V^\pi(s) = \mathbb{E}_\pi[G_t \mid S_t=s]$ using only the recursive structure of the return and the Markov property. So $V^\pi$ trivially satisfies its own Bellman equation — existence of a solution is immediate because we constructed the equation from a function we already know exists. 2. Uniqueness via contraction. Define the Bellman operator $T^\pi$ as above, acting on the space of bounded value functions with the supremum norm $\|V\|_\infty = \max_s |V(s)|$. For any two value functions $U, V$:

using that $\sum_a \pi(a\mid s)\sum_{s'} P^\pi(s,s') = 1$ (a proper probability distribution) so the inner expression is a convex combination, bounded by $\max_{s'}|U(s')-V(s')|$. Since $\gamma < 1$, $T^\pi$ is a contraction mapping with modulus $\gamma$. By the Banach fixed-point theorem, $T^\pi$ has a unique fixed point, and iterating $T^\pi$ from any starting $V_0$ converges to it geometrically fast:

This is the mathematical guarantee underlying iterative policy evaluation, and it confirms that the Bellman equation pins down $V^\pi$ uniquely (assuming $\gamma < 1$, or $\gamma = 1$ with guaranteed termination in episodic tasks).

Honest tradeoffs. The linear-algebra solution is exact but cubic in state count and requires full knowledge of the model $p(s',r\mid s,a)$. The Bellman equation itself says nothing about how to find an optimal policy — that requires the closely related but distinct Bellman Optimality Equation, which replaces the policy average with a max over actions and is nonlinear. Also, everything here assumes a known, tabular model; when the model is unknown or the state space is continuous, the Bellman equation still holds in principle but must be estimated from samples (temporal-difference methods) or approximated with function approximators — introducing bias and variance tradeoffs not present in the exact tabular case.

Consider a tiny 3-state MDP: Study, Break, Done (terminal), with $\gamma = 0.9$. The agent follows a fixed policy $\pi$: from Study, it takes action "continue" with probability 0.7 (reward $+2$, stays in Study) and "rest" with probability 0.3 (reward $+0$, moves to Break). From Break, it always takes "resume" (reward $-1$, moves back to Study) — for simplicity assume no path to Done to keep the example a clean two-state recursion (a self-loop system), which still exercises the full Bellman machinery. The Bellman equations for this policy are:

Let $x = V^\pi(\text{Study})$, $y = V^\pi(\text{Break})$. Expanding:

Substitute the second into the first:

Then $y = -1 + 0.9(8.898) \approx 7.008$. Check by plugging back into the original equation for Study:

The equation is self-consistent, as required. The table below traces a few iterations of the Bellman backup starting from $V_0 = (0,0)$, illustrating the contraction toward this exact solution:

Each row is one call to `BELLMAN_BACKUP`; the error shrinks geometrically at rate approximately $\gamma = 0.9$ per full sweep here (the effective contraction on this particular chain), matching the theoretical bound.

The Bellman equation is the theoretical foundation beneath essentially every value-based reinforcement learning method used in practice. Dynamic programming methods — policy evaluation and policy iteration — directly implement its fixed-point structure on tabular MDPs, and remain the standard teaching tool and a component of planning modules in model-based systems. Temporal-difference learning methods (TD(0), SARSA, Q-learning) are best understood as sampling-based approximations to the Bellman backup, replacing the exact expectation over the model with a single observed transition — this is the bridge to model-free RL. Deep reinforcement learning systems, including Deep Q-Networks used in Atari-playing agents and value-based components of modern policy-gradient methods, train neural networks to approximately satisfy a Bellman equation via a squared "Bellman error" loss, minimizing the discrepancy between a network's current prediction and a bootstrapped target built from the same recursive identity. Large-scale industrial recommender systems and resource-allocation controllers that use RL for sequential decisions — ad placement, inventory control, robotic control — all rely on some approximate solution to a Bellman equation, whether solved exactly, iteratively, or via sampled gradient updates. The concept also underlies model-predictive control and classical operations-research techniques for inventory and scheduling problems that predate modern RL by decades, showing the equation's reach well beyond machine learning.

Ask the tutor: How does replacing the policy-weighted average with a max over actions transform this into the Bellman optimality equation, and why does that change break the linearity of the system?