Core idea. Bellman equations are first-step decompositions of long-run reward. They turn sequential decision problems into fixed-point equations. For a fixed policy, the Bellman equation is a linear equation. For optimal control, the Bellman equation is nonlinear because of the maximization over actions.
The first equation evaluates a policy. The second equation characterizes an optimal policy.
8.1 Learning goals
After reading this chapter, students should be able to:
derive the Bellman expectation equation from the return decomposition;
distinguish value functions \(V^\pi\), action-value functions \(Q^\pi\), optimal values \(V^*\), and optimal action-values \(Q^*\);
write Bellman equations in scalar, vector, and operator form;
explain why the Bellman expectation equation is linear while the Bellman optimality equation is nonlinear;
prove that discounted Bellman operators are contractions under the sup norm;
interpret value iteration and policy evaluation as fixed-point iterations;
compute Bellman backups in finite MDPs using Python;
use Bellman residuals as diagnostics for approximate solutions;
connect Bellman equations to conditional expectation, dynamic programming, optimization, and AI-assisted reasoning.
8.2 5.1 First-step analysis
The mathematical source of Bellman equations is the identity
\[
G_t=R_{t+1}+\gamma G_{t+1},
\]
where
\[
G_t=\sum_{k=0}^{\infty}\gamma^k R_{t+k+1}
\]
is the discounted return from time \(t\). This identity is simple but powerful: the infinite future can be decomposed into one immediate reward plus the discounted future value after one transition.
For a fixed policy \(\pi\), the state-value function is
This equation is the Bellman expectation equation.
Bellman equations are conditional expectation identities. They are not originally algorithms. Algorithms arise by solving or approximating these fixed-point equations.
For a deterministic policy \(\pi\), the policy-induced transition matrix chooses one row from either \(P^C\) or \(P^H\) for each state. For a randomized policy, the rows are convex combinations.
Since \(P_\pi\) is a stochastic matrix and \(0\leq\gamma<1\), the matrix \(I-\gamma P_\pi\) is invertible. Hence
\[
V^\pi=(I-\gamma P_\pi)^{-1}r_\pi.
\]
This is the clean linear-algebraic solution. It is exact for small finite models. For large models, forming and inverting the matrix is usually impossible, so iterative or approximate methods are used.
8.4.1 Python example: solving a Bellman expectation equation
The operator \(T^\pi\) is affine. The operator \(T\) is nonlinear because it takes a maximum over actions. However, both are contractions when \(0\leq\gamma<1\).
Bellman operators as maps. The expectation operator \(T^\pi\) evaluates a fixed policy. The optimality operator \(T\) evaluates the best one-step action followed by optimal future behavior.
8.6 5.5 Interactive demonstration: a Bellman backup
A Bellman backup takes a candidate future value vector and produces a new value estimate. In a two-action state, each action gives an affine score:
The optimal Bellman backup chooses the larger score.
In the graph, each action score is affine in a simplified one-dimensional future-value parameter. The optimal backup is the upper envelope of the two action scores. This is why the optimal Bellman equation is piecewise linear in finite discounted MDPs when viewed locally as a function of a value vector.
8.7 5.6 Action-value Bellman equations
The state-value function \(V^\pi\) asks: starting from state \(s\), what is the expected return if the agent follows \(\pi\)?
The action-value function \(Q^\pi\) asks: starting from state \(s\), taking action \(a\) first, and then following \(\pi\), what is the expected return?
8.7.1 Python example: computing \(Q^\pi\) from \(V^\pi\)
Q_pi = np.zeros((len(states), 2))for i inrange(len(states)): Q_pi[i, 0] = r_C[i] + gamma * P_C[i] @ V_pi Q_pi[i, 1] = r_H[i] + gamma * P_H[i] @ V_piprint("Rows are states; columns are C and H.")print(np.round(Q_pi, 4))V_from_Q = (1- p_H) * Q_pi[:, 0] + p_H * Q_pi[:, 1]print("Recovered V from policy-weighted Q:")print(np.round(V_from_Q, 4))
Rows are states; columns are C and H.
[[30.4705 31.1146]
[35.0457 37.8045]
[41.548 41.6335]]
Recovered V from policy-weighted Q:
[30.5993 36.9769 41.6249]
The equality \(V^\pi(s)=\sum_a\pi(a\mid s)Q^\pi(s,a)\) is not an approximation. It is the law of total expectation applied to the first action.
8.8 5.7 Bellman optimality equations
The optimal state-value function is
\[
V^*(s)=\sup_\pi V^\pi(s).
\]
For finite discounted MDPs, an optimal stationary deterministic policy exists under standard assumptions. The Bellman optimality equation is
def bellman_optimality_backup(V, gamma=0.90):"""One Bellman optimality backup for the study-planning MDP.""" backup_C = r_C + gamma * P_C @ V backup_H = r_H + gamma * P_H @ V V_new = np.maximum(backup_C, backup_H) greedy_actions = np.where(backup_H > backup_C, "H", "C")return V_new, greedy_actions, backup_C, backup_HV0 = np.zeros(len(states))V1, greedy, backup_C, backup_H = bellman_optimality_backup(V0, gamma)print("One-step backup from V=0:")for s, v, a inzip(states, V1, greedy):print(f"{s:8s}: new value = {v:.3f}, greedy action = {a}")
One-step backup from V=0:
Review : new value = 1.000, greedy action = C
Practice: new value = 4.000, greedy action = H
Mastery : new value = 6.000, greedy action = H
Starting from \(V=0\), the first Bellman backup is simply the best immediate expected reward at each state. Later backups incorporate future consequences.
8.9 5.8 Contraction mapping theorem
The key mathematical fact behind dynamic programming is contraction.
For vectors \(V,W\in\mathbb R^m\), define the sup norm
Contraction theorem. If \(0\leq\gamma<1\), then both \(T^\pi\) and \(T\) are \(\gamma\)-contractions under \(\|\cdot\|_\infty\). Each operator has a unique fixed point, and fixed-point iteration converges to that fixed point from any initial vector.
Large \(\gamma\) means that the future matters more. Mathematically, it also means that the contraction is weaker. This is why value iteration often becomes slower as \(\gamma\) approaches \(1\).
8.10 5.9 Value iteration as fixed-point iteration
The Bellman optimality equation \(V^*=TV^*\) suggests the iteration
This is value iteration. It is studied in detail in Chapter 8, but the mathematical foundation belongs here: value iteration is fixed-point iteration for a contraction.
is called the Bellman residual. It measures how close \(V_k\) is to satisfying the Bellman equation.
8.10.1 Python example: value iteration and residuals
def value_iteration(num_iter=50, gamma=0.90): V = np.zeros(len(states)) history = []for k inrange(num_iter): V_new, greedy, _, _ = bellman_optimality_backup(V, gamma) residual = np.max(np.abs(V_new - V)) history.append({"iteration": k +1,"residual": residual,"V": V_new.copy(),"greedy": greedy.copy() }) V = V_newreturn historyhistory = value_iteration(num_iter=25, gamma=gamma)last = history[-1]print("Approximate optimal values after 25 iterations:")for s, v, a inzip(states, last["V"], last["greedy"]):print(f"{s:8s}: V = {v:.4f}, greedy action = {a}")print("Bellman residual:", round(last["residual"], 6))
Approximate optimal values after 25 iterations:
Review : V = 31.8392, greedy action = H
Practice: V = 38.2295, greedy action = H
Mastery : V = 41.7571, greedy action = H
Bellman residual: 0.329699
The curves show how successive Bellman optimality backups move the value estimates toward their fixed point.
8.11 5.10 Bellman residual diagnostics
The Bellman residual is an important diagnostic in both exact and approximate reinforcement learning. Given a candidate value function \(\widehat V\), define
This bound is sometimes conservative, especially when \(\gamma\) is close to \(1\), but it is conceptually useful. It connects a computable quantity to a value-function error bound.
For applied mathematics students, the residual is a nonlinear fixed-point residual. For statistics students, it is also a model-checking and approximation diagnostic: a learned value function should approximately satisfy the Bellman equation under the model or data distribution of interest.
8.12 5.11 Policy improvement from Bellman equations
Suppose \(V^\pi\) is known. Define a new policy \(\pi'\) by choosing actions greedily with respect to the one-step lookahead values:
\[
V^{\pi'}(s)\geq V^\pi(s)
\qquad\text{for all }s.
\]
The idea is that \(\pi'\) is at least as good as \(\pi\) for the first action, measured using the future value of \(\pi\). Repeating this process leads to policy iteration.
Policy improvement from Bellman equations
Evaluate the current policy: solve \(V^\pi=T^\pi V^\pi\).
Compute one-step lookahead action scores using \(V^\pi\).
Choose a greedy action in each state.
The resulting policy is no worse than the original policy.
8.13 5.12 Expectation equation versus optimality equation
The Bellman expectation equation answers an evaluation question:
\[
\text{Given }\pi,\text{ what is }V^\pi?
\]
The Bellman optimality equation answers a control question:
\[
\text{Which policy achieves the largest possible value?}
\]
The distinction is essential.
Equation
Unknown
Linear?
Main use
\(V^\pi=r_\pi+\gamma P_\pi V^\pi\)
\(V^\pi\)
yes
policy evaluation
\(Q^\pi=r+\gamma P^\pi Q^\pi\)
\(Q^\pi\)
yes
action-value evaluation
\(V^*=TV^*\)
\(V^*\)
no
optimal control
\(Q^*=T_QQ^*\)
\(Q^*\)
no
model-free control foundation
Here \(P^\pi\) in the \(Q\)-equation denotes the transition operator on state-action pairs. It is not the same matrix as \(P_\pi\) on states.
The heatmap visualizes action-value scores. The value \(V^\pi(s)\) is a policy-weighted average of the row entries, while \(V^*(s)\) is the row maximum.
8.14 5.13 Bellman equations and statistics
Bellman equations are often written as deterministic equations, but they contain statistical structure. The equality
is the temporal-difference error associated with a candidate value function \(V\). When \(V=V^\pi\), the conditional mean of \(\delta_t\) is zero:
\[
\mathbb E_\pi[\delta_t\mid S_t=s]=0.
\]
This observation is the bridge from dynamic programming to temporal-difference learning in Chapter 10. In model-free RL, we do not know the conditional expectation exactly. We observe samples and use stochastic approximation to push empirical TD errors toward zero.
8.15 5.14 Bellman equations and optimization
The optimal Bellman equation can also be studied through optimization. For finite discounted MDPs, \(V^*\) is the smallest vector satisfying the Bellman inequalities
\[
V(s)\geq r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V(s')
\qquad\text{for all }s,a.
\]
where \(\eta(s)>0\) is a weighting distribution over states. At optimum, the inequalities are tight for optimal actions.
This perspective connects reinforcement learning to convex analysis, duality, occupancy measures, and constrained optimization.
8.16 5.15 AI-assisted learning component
Generative AI tools can help students work with Bellman equations, but they often confuse expectation equations, optimality equations, and sample-based updates. A useful workflow is:
write the state space, action space, transition law, reward function, and discount factor explicitly;
ask the AI tool to write the Bellman expectation equation for a fixed policy;
ask it separately to write the Bellman optimality equation;
check whether it incorrectly replaces an expectation with a sample update;
check whether the policy is fixed or being optimized;
verify dimensions of all matrices and vectors;
test the answer on a small numerical example.
8.16.1 AI prompt: auditing a Bellman equation
Use the following prompt with an AI tool:
I have a finite discounted MDP with states \(s\in\{1,2,3\}\), actions \(a\in\{0,1\}\), transition probabilities \(P(s'\mid s,a)\), rewards \(r(s,a)\), and discount factor \(\gamma=0.9\). Explain the difference between the Bellman expectation equation for a fixed policy \(\pi\) and the Bellman optimality equation. Then give matrix/vector formulas and identify the dimensions of each object.
After receiving the response, check:
Did the answer distinguish \(P_\pi\) from \(P(s'\mid s,a)\)?
Did it distinguish \(V^\pi\) from \(V^*\)?
Did it use \(\max_a\) only in the optimality equation?
Did it correctly state that \(V^\pi=(I-\gamma P_\pi)^{-1}r_\pi\) only applies to a fixed policy?
Did it avoid treating one sampled transition as an exact expectation?
8.16.2 AI debugging exercise
Ask an AI tool to write Python code for value iteration on the study-planning MDP. Then verify whether the code:
computes both action backups separately;
takes a maximum across actions, not across states;
keeps the discount factor inside the expectation over next states;
updates all states consistently;
reports a Bellman residual or another stopping criterion.
The point is not to accept AI-generated code. The point is to use the mathematics of Bellman equations to inspect and correct the code.
8.17 5.16 Summary
Bellman equations are the mathematical center of reinforcement learning. They express long-run value through a one-step decomposition:
For a fixed policy, the Bellman equation is linear:
\[
V^\pi=r_\pi+\gamma P_\pi V^\pi.
\]
For optimal control, the Bellman equation is nonlinear:
\[
V^*=TV^*.
\]
The contraction property explains why iterative methods converge when \(0\leq\gamma<1\). Bellman residuals provide computable diagnostics. Action-value Bellman equations prepare the way for SARSA and Q-learning. The conditional-moment view prepares the way for temporal-difference learning.
8.18 Conceptual exercises
Explain in words why the identity \(G_t=R_{t+1}+\gamma G_{t+1}\) leads to Bellman equations.
Why is the Bellman expectation equation linear for a fixed policy?
Why is the Bellman optimality equation nonlinear?
What is the difference between \(V^\pi(s)\) and \(Q^\pi(s,a)\)?
Why does a large value of \(\gamma\) make convergence slower?
What does the Bellman residual measure?
Explain why a Bellman equation is an expectation equation, while TD learning uses samples to approximate it.
8.19 Mathematical exercises
Starting from the definition of \(V^\pi(s)\), derive \[
V^\pi(s)=r_\pi(s)+\gamma\sum_{s'}P_\pi(s'\mid s)V^\pi(s').
\]
Prove that \(T^\pi\) is a \(\gamma\)-contraction under \(\|\cdot\|_\infty\).
Prove that \(T\) is a \(\gamma\)-contraction under \(\|\cdot\|_\infty\) using \[
|\max_a x_a-\max_a y_a|\leq \max_a |x_a-y_a|.
\]
Show that if \(V^\pi=T^\pi V^\pi\), then \[
V^\pi=(I-\gamma P_\pi)^{-1}r_\pi.
\]
Prove the residual bound \[
\|V-V^*\|_\infty\leq \frac{\|TV-V\|_\infty}{1-\gamma}.
\]
Show that the Bellman inequalities \[
V(s)\geq r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V(s')
\] imply \(V\geq TV\) componentwise.
8.20 Computational exercises
Implement policy evaluation for a deterministic policy that always chooses \(C\).
Implement policy evaluation for a deterministic policy that always chooses \(H\).
Compare the values of the two deterministic policies for \(\gamma=0.5,0.7,0.9,0.97\).
Implement value iteration and stop when the Bellman residual is less than \(10^{-6}\).
Compute \(Q^\pi\) from \(V^\pi\) and verify that \(V^\pi(s)=\sum_a\pi(a\mid s)Q^\pi(s,a)\).
For a random candidate value vector \(V\), compute \(TV\) and the Bellman residual.
Write code that intentionally makes the error of taking a maximum over next states instead of over actions. Explain why the result is mathematically wrong.
8.21 AI-assisted exercises
Ask an AI tool to derive the Bellman expectation equation. Identify every step where conditional expectation is used.
Ask an AI tool to derive the Bellman optimality equation. Check whether it clearly states where the maximum over actions enters.
Ask an AI tool to implement value iteration. Compare the output with your own implementation.
Ask an AI tool for a real-world decision problem that can be modeled as an MDP. Rewrite the model using precise mathematical notation.
Ask an AI tool to explain the difference between \(V^\pi\), \(Q^\pi\), \(V^*\), and \(Q^*\). Find and correct any ambiguity.
8.22 Notes for instructors
This chapter is a bridge between the modeling chapters and the algorithmic chapters. For MA Applied Math students, emphasize fixed points, contraction mappings, nonlinear operators, and linear programming. For MS Statistics students, emphasize conditional expectation, temporal-difference errors, residual diagnostics, and sample-based approximation.
The most important conceptual distinction is:
\[
\text{policy evaluation: fixed }\pi
\qquad\text{versus}\qquad
\text{control: optimize over }a\text{ or }\pi.
\]
Students who understand this distinction will be well prepared for policy evaluation, policy iteration, value iteration, Monte Carlo learning, temporal-difference learning, SARSA, and Q-learning.