The Bellman equation: derivation, intuition and a worked example

The Bellman equation says that the value of a state equals the reward you expect on the next step plus the discounted value of the state you land in. It turns a sum over an entire future into a relation between neighbouring states, and almost every reinforcement learning algorithm, from value iteration to Q-learning to actor-critic, is a way of solving it. This page derives both forms of the equation, works one backup through with real numbers, shows why it always has exactly one solution, and measures how fast the standard solvers converge on a small gridworld.

A worked example: one Bellman backup with real numbers#

We use the reference gridworld from this series: a 5 by 5 grid with a goal worth +1 in the top-right corner, a pit worth $-1$ just left of the column below it, three wall cells, and a start in the bottom-left corner. Moves are slippery: the agent goes where it intended with probability 0.8 and slides to each side with probability 0.1. Walking into a wall or the edge leaves it in place. Entering the goal pays +1 and ends the episode, entering the pit pays $-1$ and ends it, every other step pays 0, and the discount factor is $\gamma =0.9$. (The Markov decision process article builds this world from scratch.)

Take the cell in row 2, column 3, directly below the pit. Its optimal value turns out to be 0.403. Here is why, computed from the optimal values of its neighbours: 0.649 for the cell to its right, 0.359 for the cell to its left, and 0 for the pit, which is terminal.

The best action is to step right, away from the pit and towards the column that leads to the goal, and its value is 0.403. The value of the cell appears on both sides (the "stay" outcome of moving right uses 0.403 itself): a consistency condition, which is what makes this a system of equations rather than a formula. Stepping down scores almost as well (0.381) because it never risks the pit. The 0.022 gap is the price of a 10% slip into a $-1$ outcome, discounted against reaching the goal one step sooner. Every optimal value satisfies this same one-step relation with its neighbours. That relation is the Bellman equation.

Deriving the Bellman equation from the return#

An agent following policy $\pi$ collects rewards $R_{t+1},R_{t+2},\dots$. The discounted return from time $t$ is

where $\gamma \in [0,1)$ is the discount factor, the weight given to a reward one step further away. The state-value function is the expected return when starting in state $s$ and following $\pi$ afterwards: $V^{\pi }(s)={\mathbb{E}}_{\pi }[G_t\mid S_t=s]$. The whole derivation rests on one line of algebra. Pull the first reward out of the sum:

The return is the next reward plus the discounted return from the next step. Take expectations given $S_t=s$, and use the Markov property: once you know the next state $S_{t+1}=s^{\prime }$, the expected future return from there is $V^{\pi }(s^{\prime })$, regardless of how you arrived. Averaging over the action the policy picks and the state the environment produces gives the Bellman expectation equation:

Here $\pi (a\mid s)$ is the probability the policy picks action $a$ in state $s$, $P(s^{\prime }\mid s,a)$ is the probability the environment moves to $s^{\prime }$, and $R(s,a,s^{\prime })$ is the reward for that transition. Terminal states have value 0. In words: a state is worth the average, over what you do and what happens next, of the immediate reward plus the discounted worth of where you end up.

Some textbooks write the dynamics as a joint distribution $p(s^{\prime },r\mid s,a)$ over next state and reward [6], others use an expected reward $R(s,a)$ [4]. All three conventions give the same values; only the bookkeeping differs. We use $R(s,a,s^{\prime })$ because rewards in our gridworld depend on the cell you enter.

The action-value (Q) form#

The same argument applied to the action-value function $Q^{\pi }(s,a)$, the expected return after taking action $a$ in $s$ and following $\pi$ afterwards, gives

The two functions are linked by $V^{\pi }(s)={\sum }_a\pi (a\mid s)Q^{\pi }(s,a)$: the value of a state is the policy-weighted average of the values of its actions. The Q form matters in practice because you can pick the best action from $Q$ without knowing $P$, which is what lets Q-learning work from experience alone.

Because values are defined by this equation, any change to the reward changes them, and usually changes the best policy too. One family of changes is provably harmless: potential-based reward shaping adds $\gamma \Phi (s^{\prime })-\Phi (s)$ to every reward, for any function $\Phi$ of the state. Substituting into the optimality equation shows that every $Q^{\ast }(s,a)$ simply shifts by $-\Phi (s)$, the same amount for every action in a state, so the best action never changes [11].

Bellman expectation equation vs Bellman optimality equation#

The expectation equation evaluates a given policy. The optimality equation describes the best possible policy, and it comes from Bellman's principle of optimality: "An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision" [2]. If you will act optimally from the next state onwards, the only choice left is the first action, so you pick the one with the highest one-step lookahead:

$V^{\ast }$ and $Q^{\ast }$ are the optimal state and action values, the largest expected return any policy can achieve. Once you have $Q^{\ast }$, acting greedily, ${\pi }^{\ast }(s)=\arg {\max }_a{Q}^{\ast }(s,a)$, is optimal. The cell in the worked example was an optimality backup: we took the maximum of four action values.

The matrix form: one linear solve#

Stack the values of all $n$ states into a vector $V^{\pi }$. For a fixed policy, define the matrix $P^{\pi }$ with entries $P_{s{s}^{\prime }}^{\pi }={\sum }_a\pi (a\mid s)P(s^{\prime }\mid s,a)$ and the vector $R^{\pi }$ with $R_s^{\pi }={\sum }_a\pi (a\mid s){\sum }_{s^{\prime }}P(s^{\prime }\mid s,a)R(s,a,s^{\prime })$. The expectation equation for every state at once is

$I$ is the identity matrix. The inverse exists whenever $\gamma <1$, because every eigenvalue of the stochastic matrix $P^{\pi }$ has modulus at most 1, so no eigenvalue of $\gamma P^{\pi }$ can equal 1.

For the uniformly random policy in the reference gridworld (each of the four actions with probability 1/4), the solve gives a start-state value of $-0.0327$. A random walk is slightly more likely to stumble into the pit than to reach the goal before discounting erodes the reward, and the cells to the left of and below the pit are worth $-0.462$ and $-0.463$. As a check, 20,000 simulated episodes (seed 7) of the random policy from the start gave a mean discounted return of $-0.0316\pm 0.0013$ (95% interval), which contains the exact answer.

The catch is cost. Solving an $n$-state linear system takes on the order of $n^3$ operations. With numpy on a laptop CPU, a 20-state solve took 0.05 milliseconds, 1,000 states took 7 milliseconds, and 4,000 states took a quarter of a second. Fine for tabular problems, hopeless for a game with $10^{20}$ states, which is why iterative and sample-based methods dominate.

Why the Bellman equation has exactly one solution#

Write the right-hand side of each equation as an operator acting on a value function. The Bellman expectation operator is $(T^{\pi }V)(s)={\sum }_a\pi (a\mid s){\sum }_{s^{\prime }}P(s^{\prime }\mid s,a)[R(s,a,s^{\prime })+\gamma V(s^{\prime })]$, and the optimality operator $T^{\ast }$ is the same with a max in place of the average. The Bellman equations say $V^{\pi }=T^{\pi }{V}^{\pi }$ and $V^{\ast }=T^{\ast }{V}^{\ast }$: the true value functions are fixed points of these operators.

Both operators are contractions in the sup norm $\Vert V{\Vert }_{\infty }={\max }_s|V(s)|$:

For $T^{\pi }$ the proof is one line: the rewards cancel, and an average of differences cannot exceed the largest difference, so what is left is at most $\gamma$ times the largest gap. For $T^{\ast }$ you also need $|{\max }_{a}f(a)-{\max }_{a}g(a)|\le {\max }_a|f(a)-g(a)|$, which holds because the max of one function can exceed the max of the other by no more than the largest pointwise gap. Blackwell gave general sufficient conditions (monotonicity and discounting) for this property [3].

The Banach fixed-point theorem then delivers three guarantees at once. There is exactly one fixed point, so the Bellman equation has a unique solution. Repeatedly applying the operator from any starting guess converges to it. And the error after $k$ applications obeys

where $V_k$ is the estimate after $k$ sweeps and $V$ the fixed point. Each sweep shrinks the worst-case error by at least a factor $\gamma$. This is the convergence proof behind value iteration and policy iteration, and the same idea, applied to noisy samples, underlies the convergence proofs for TD learning and Q-learning [7, 8].

The bound is real, and usually loose#

Simulation (seeded, exact arithmetic). We started from $V_0=0$ and applied each operator repeatedly to the reference gridworld at $\gamma =0.9$, measuring the sup-norm distance to the exact fixed point after every sweep.

Three results stand out. For the random policy, the error shrank by a factor of 0.885 per sweep in the long run, slightly faster than $\gamma =0.9$. That rate is not a coincidence: it matches the spectral radius of $\gamma P^{\pi }$, 0.884, because episodes can end in the goal or the pit, so some probability mass leaves the system every step. Reaching an error of $10^{-8}$ took 132 sweeps where the bound promised no more than 168.

Value iteration was much faster than its bound. For the first seven sweeps the error shrank by about 0.87 per sweep, while value was still propagating back from the goal; after that the rate dropped to about 0.45 per sweep, which equals the spectral radius of $\gamma P^{{\pi }^{\ast }}$ under the optimal policy (0.445). The optimal policy reaches the goal quickly and rarely loops, so errors die out fast. The greedy policy read off $V_k$ was already optimal after 11 sweeps, while the values themselves were still 0.03 away from their limit. This gap between "policy is right" and "values are right" is why policy iteration, which only needs the former, usually takes so few iterations.

The discount factor dominates the cost:

The effective horizon is about $1/(1-\gamma )$ steps, and the solver needs about that many sweeps per factor of $e$ in accuracy. At $\gamma =0.5$ the goal eight steps away is worth almost nothing from the start; at $\gamma =0.99$ it is worth 0.81, and evaluation needs nearly five times the sweeps of $\gamma =0.9$.

Explore: the Bellman backup inspector#

The figure below runs the exact backups from this article on the reference gridworld. Click any cell to see its backup: the four action values computed from the previous sweep, and, for the highlighted action, each successor state with its probability, reward and discounted value. Step through sweeps from $V=0$ and watch the error track, then beat, the ${\gamma }^k$ bound. Switch to expectation backups to evaluate the random policy instead, and move the discount and slip sliders to see how they change both the values and the convergence rate.

From equation to algorithm#

Nearly every value-based method is one of four ways to solve a Bellman equation, sorted by whether you know the model and which equation you target.

• Iterative policy evaluation applies $T^{\pi }$ repeatedly with known dynamics. Value iteration applies $T^{\ast }$. Policy iteration alternates exact evaluation with greedy improvement. All three are covered with side-by-side measurements in value iteration vs policy iteration.
• Temporal-difference learning replaces the expectation over $s^{\prime }$ with a single sampled transition [7]. TD(0) nudges the estimate towards a one-sample Bellman target: $V(s)\leftarrow V(s)+\alpha [r+\gamma V(s^{\prime })-V(s)]$, with step size $\alpha$. The bracket is the TD error, a noisy sample of the Bellman residual.
• Q-learning does the same for the optimality equation, using the target $r+\gamma {\max }_{a^{\prime }}Q(s^{\prime },a^{\prime })$ [8]. Deep Q-networks use a neural network for $Q$ and the same target [10]; see Q-learning and DQN.
• Critics in actor-critic methods learn $V^{\pi }$ with TD targets, and the TD error becomes an estimate of the advantage that scales the policy gradient.

Sample-based backups: what noise costs#

Simulation (seeded). We ran TD(0) on the random policy in the reference gridworld, every episode starting from the start cell, for 10 seeds of 10,000 episodes each, and measured the root-mean-square error over the 20 non-terminal states against the exact $V^{\pi }$ from the linear solve.

Here $n$ is the number of times that state has been updated. A constant step size learns fast, then stalls at a noise floor that scales with $\alpha$. A step size that shrinks with the visit count keeps improving, which is what the stochastic approximation conditions in the convergence proofs require (step sizes that sum to infinity but whose squares sum to a finite number) [7, 8]. For comparison, the exact solve and 132 sweeps of expectation backups both reach $10^{-8}$. Samples buy independence from the model and cost precision.

Code#

The exact solve and one optimality backup in plain numpy, with a two-state example you can check by hand:

import numpy as np

def evaluate_exact(P, R, pi, gamma):
    """Solve the Bellman expectation equation V = R_pi + gamma P_pi V.
    P: (S, A, S) transition probabilities, R: (S, A) expected reward, pi: (S, A) policy."""
    P_pi = np.einsum("sa,sat->st", pi, P)
    R_pi = (pi * R).sum(1)
    return np.linalg.solve(np.eye(len(R)) - gamma * P_pi, R_pi)

def optimality_backup(V, P, R, gamma):
    """One application of the Bellman optimality operator: (T* V)(s) = max_a Q(s, a)."""
    Q = R + gamma * P @ V          # (S, A)
    return Q.max(1)

# two states, two actions: "stay" earns 1 in state 0, "move" swaps state and earns 0
P = np.zeros((2, 2, 2)); P[0, 0, 0] = P[1, 0, 1] = 1; P[0, 1, 1] = P[1, 1, 0] = 1
R = np.array([[1.0, 0.0], [0.0, 0.0]])
uniform = np.full((2, 2), 0.5)
print(evaluate_exact(P, R, uniform, 0.9))      # [2.75 2.25]

V = np.zeros(2)
for k in range(200):
    V = optimality_backup(V, P, R, 0.9)
print(V.round(4))                               # [10.0, 9.0]

The Bellman equation in economics and continuous time#

Bellman's own setting was multi-stage decision problems in operations research and economics [1, 2]. The textbook example is consumption and saving. A household with capital $k$ chooses consumption $c$, gets utility $u(c)$, and carries $k^{\prime }=f(k)-c$ into next period, where $f$ is production. Its value function satisfies

where $\beta$ is the discount factor, the same role $\gamma$ plays in reinforcement learning. The structure is identical: immediate payoff plus discounted value of the next state, maximised over the choice. Economists solve it by value function iteration on a grid over $k$.

In continuous time, with dynamics $\dot{x}=f(x,u)$, reward rate $r(x,u)$ and discount rate $\rho$, letting the time step shrink to zero turns the Bellman equation into a partial differential equation, the Hamilton-Jacobi-Bellman (HJB) equation:

Here $\nabla V(x)$ is the gradient of the value with respect to the state, and $\nabla V\cdot f$ is the rate at which value changes as the state moves. Optimal control and much of continuous-time finance are built on it.

Common mistakes and failure modes#

Forgetting terminal states. Terminal states must have value 0 and must not be backed up. Bootstrapping from a terminal state's (garbage) estimate is a classic bug, and in episodic tasks with time limits, treating the time-out as a true terminal biases values downwards. If an episode is cut off by a step limit, bootstrap from $V(s^{\prime })$ instead of using 0.

Undiscounted continuing tasks. With $\gamma =1$ the contraction argument fails and returns can be infinite. Episodic tasks that always terminate are fine; continuing tasks need $\gamma <1$ or the average-reward formulation [4].

Function approximation breaks the contraction. The guarantees above are for tables. Once $V$ or $Q$ is a neural network, a backup followed by fitting the network is no longer a contraction in general. Combining bootstrapping, function approximation and off-policy data, which Sutton and Barto call the deadly triad [6], can make values diverge. Baird constructed a small example where off-policy TD with a linear approximator diverges [9]. Target networks and replay buffers in DQN [10] are engineering responses to exactly this; the problem is sharpest in offline reinforcement learning, where the max in the Bellman target latches onto actions the data never covered.

Minimising the Bellman residual is not the same as solving the equation. It is tempting to train a network by minimising $(r+\gamma V(s^{\prime })-V(s){)}^2$ over samples. With stochastic transitions, the expected squared sample residual includes the variance of $V(s^{\prime })$, so the minimiser is biased towards smoother, flatter value functions. Fixing this needs two independent samples of $s^{\prime }$ from the same $s$ (the double-sampling problem [9]), which a real environment rarely provides.

Reward convention mismatches. Mixing $R(s)$, $R(s,a)$ and $R(s,a,s^{\prime })$ conventions, or counting the reward of entering the goal twice, shifts every value. Cross-check a few states against Monte Carlo returns, as we did above.

A practical checklist#

1. Write the backup for one state by hand, with numbers, before writing code. If you cannot, your reward or terminal convention is not pinned down.
2. For tabular problems under a few thousand states, solve $(I-\gamma P^{\pi })V=R^{\pi }$ directly for evaluation; use it as ground truth for any iterative or sampled method.
3. Stop iterating on $\Vert V_{k+1}-V_k{\Vert }_{\infty }$, not on a fixed sweep count. Since $\Vert V_{k+1}-V{\Vert }_{\infty }\le \frac{\gamma }{1-\gamma }\Vert V_{k+1}-V_k{\Vert }_{\infty }$, at $\gamma =0.9$ the true error can be up to nine times the last change.
4. With sampled backups, decay the step size or average iterates if you need precise values; a constant step size gives a noise floor.
5. With function approximation, monitor value estimates against held-out returns, and treat steadily rising values as a sign of divergence or overestimation.

For the wider map, start at what is reinforcement learning; for how the terms are used on this site, see the glossary.

Frequently asked questions#

Sources#

1. R. Bellman. The theory of dynamic programming, 1954. doi.org
2. R. Bellman. Dynamic Programming, 1957. doi.org
3. D. Blackwell. Discounted Dynamic Programming, 1965. doi.org
4. M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming, 1994. doi.org
5. D. P. Bertsekas, J. N. Tsitsiklis. Neuro-Dynamic Programming, 1996. athenasc.com
6. R. S. Sutton, A. G. Barto. Reinforcement Learning: An Introduction (2nd ed.), 2018. incompleteideas.net
7. R. S. Sutton. Learning to predict by the methods of temporal differences, 1988. doi.org
8. C. J. C. H. Watkins, P. Dayan. Q-learning, 1992. doi.org
9. L. Baird. Residual Algorithms: Reinforcement Learning with Function Approximation, 1995. doi.org
10. V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al.. Human-level control through deep reinforcement learning, 2015. doi.org
11. A. Y. Ng, D. Harada, S. Russell. Policy invariance under reward transformations: Theory and application to reward shaping, 1999. people.eecs.berkeley.edu