Bellman equation: Definition and Examples

The Bellman equation expresses the value of a state recursively: it equals the expected immediate reward plus the discounted value of the state that follows. Almost every value-based reinforcement learning algorithm is a way of solving it, exactly or approximately.

The Bellman expectation equation

For a fixed policy $π$ , the value function satisfies

V^{π} (s) = a \sum π (a ∣ s) s^{'} \sum P (s^{'} ∣ s, a) [R (s, a) + γ V^{π} (s^{'})] .

Here $P$ is the transition probability, $R$ the expected reward and $γ$ the discount factor. It follows from the recursive form of the return, $G_{t} = R_{t + 1} + γ G_{t + 1}$ . In a finite MDP it is a linear system with one equation per state, so $V^{π}$ can be solved for directly.

The Bellman optimality equation

The optimal value function replaces the average over actions with a maximum:

V^{*} (s) = a max s^{'} \sum P (s^{'} ∣ s, a) [R (s, a) + γ V^{*} (s^{'})] .

The max makes the system nonlinear, but the operator on the right is a $γ$ -contraction: applying it to any two value estimates shrinks their largest difference by at least a factor of $γ$ . Repeated application, which is value iteration, therefore converges to the unique fixed point $V^{*}$ from any starting guess.

Worked example

One state offers two actions: stay earns 1 and returns to the same state, go earns 5 and ends the episode. The optimality equation is $V^{*} = max (1 + γ V^{*}, 5)$ . With $γ = 0.9$ , staying forever is worth $1/ (1 - 0.9) = 10 > 5$ , so $V^{*} = 10$ . Value iteration from $V = 0$ gives 5, 5.5, 5.95, 6.36, and creeps toward 10 with the error shrinking by 0.9 per sweep. With $γ = 0.7$ , staying forever is worth only $3.33$ , and $V^{*} = 5$ : check that $max (1 + 0.7 \times 5, 5) = max (4.5, 5) = 5$ .

Where it shows up

Dynamic programming: policy evaluation, policy iteration and value iteration apply the equations as exact backups.
TD learning and Q-learning apply sampled versions, replacing the sum over $s^{'}$ with one observed transition.
Deep RL minimises a squared Bellman residual, the TD error, with a neural network.

Why it matters

The Bellman equation is what lets an agent reason about the long run using only one step of experience at a time. It also explains common failure modes: bootstrapping from your own estimates propagates errors, and combining bootstrapping, function approximation and off-policy data can diverge. Understanding the equation is the shortest route to understanding why deep RL is sometimes unstable.

Sources

Richard S. Sutton, Andrew G. Barto. Reinforcement Learning: An Introduction (2nd edition), 2018. incompleteideas.net
Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming, 1994. doi.org