At the end of §15.1 we estimated the value of a random walker in the gridworld by running it 2,000 times and averaging the returns. That worked, but it was wasteful in a way that should bother you. The value of the start cell and the value of the cell just above it are not unrelated numbers. Once you have taken one step from the start, the rest of your return is a return from the cell you landed in. So the values of neighboring states must be consistent with each other, and that consistency condition is strong enough to pin them down exactly, without a single simulation.

The condition is the Bellman equation (Bellman 1957), and it is the most important equation in reinforcement learning. This section derives it in its two forms, for evaluating a policy and for finding the best one, proves that the obvious way of solving each form converges, and uses them to solve the gridworld exactly. Then we drop the assumption that we know the environment, and the same equations give us temporal-difference learning and Q-learning, which learn from experience alone.

The Bellman expectation equation

Fix a policy $\pi$. As in §15.1, $V^\pi(s) = \mathbb{E}_\pi[G_t \mid s_t = s]$ is the expected return from state $s$, where $G_t = \sum_{k\ge0}\gamma^k r_{t+k}$ is the discounted return, $r(s,a)$ is the expected reward for action $a$ in state $s$, and $P(s'\mid s, a)$ is the probability of moving to $s'$. We want an equation that $V^\pi$ satisfies.

Start from the recursion for returns, $G_t = r_t + \gamma G_{t+1}$, and take the expectation given $s_t = s$,

The first term averages the immediate reward over the action, $\mathbb{E}_\pi[r_t \mid s_t = s] = \sum_a \pi(a\mid s)\, r(s, a)$. For the second term we condition on what happens next, the action $a_t = a$ and the next state $s_{t+1} = s'$, and use the law of total expectation,

This is the step where the Markov property earns its keep. Everything that happens from time $t+1$ on (the actions, drawn from $\pi(\cdot \mid s_{t+1}), \dots$, and the transitions, drawn from $P$) depends on the past only through $s_{t+1}$. So conditioning on $s_t$ and $a_t$ as well changes nothing, and the inner expectation is just the value of $s'$,

Putting the pieces together gives the Bellman expectation equation,

In plain words, the value of a state is the average, over what the policy does and where the world sends you, of the reward you get now plus the discounted value of where you land.

The same argument for the action-value function, now with the first action fixed, gives

which is the pair of relations from §15.1, $Q^\pi(s,a) = r(s,a) + \gamma\sum_{s'}P(s'\mid s,a)V^\pi(s')$ and $V^\pi(s') = \sum_{a'}\pi(a'\mid s')Q^\pi(s',a')$, substituted into each other.

The matrix form, and solving it exactly

With finitely many states, the Bellman expectation equation is a system of $|\mathcal{S}|$ linear equations in $|\mathcal{S}|$ unknowns. Collect the policy's average reward and average transitions,

where $\mathbf{P}_\pi$ is a row-stochastic matrix (nonnegative entries, each row summing to 1), the transition matrix of the Markov chain you get by running $\pi$. Writing $\mathbf{v}$ for the vector of values $V^\pi(s)$, the Bellman equation reads

Is the inverse guaranteed to exist? Yes, when $\gamma < 1$. For any vector $\mathbf{x}$, each entry of $\mathbf{P}_\pi\mathbf{x}$ is an average of entries of $\mathbf{x}$, so $\lVert \mathbf{P}_\pi \mathbf{x}\rVert_\infty \le \lVert\mathbf{x}\rVert_\infty$ and every eigenvalue of $\gamma\mathbf{P}_\pi$ has magnitude at most $\gamma < 1$ (its spectral radius, in the language of §0.10, is at most $\gamma$). Then $\mathbf{I} - \gamma\mathbf{P}_\pi$ has no zero eigenvalue, and its inverse is the convergent Neumann series,

In plain words, the $k$-th term is the expected reward $k$ steps from now ($\mathbf{P}_\pi^k$ is the $k$-step transition matrix), discounted by $\gamma^k$, which is the definition of the value read off term by term. This is the "exact value" we used in §15.1. It costs one linear solve, $O(|\mathcal{S}|^3)$, which is nothing for 11 states and hopeless for a game of Go.

Those are the values of the random walker in every cell, all negative, because a random walk in this world blunders into the pit far more often than it finds the goal. The two terminal cells show 0 because the episode is over there (the $\pm1$ is paid on the step that enters them).

import numpy as np

def evaluate_policy(P, R, pi, gamma):
    raise NotImplementedError

Iterative policy evaluation and contraction

The linear solve does not scale, and it does not generalize to the case where we cannot write $\mathbf{P}_\pi$ down. The alternative is to treat the right-hand side of the Bellman equation as an operator on value functions and apply it repeatedly. Define the Bellman expectation operator $\mathcal{T}^\pi$, which takes any value vector $\mathbf{v}$ (a guess, not necessarily anyone's true value) and returns

The Bellman equation says $V^\pi$ is a fixed point, $\mathcal{T}^\pi V^\pi = V^\pi$. Iterative policy evaluation starts anywhere, say $\mathbf{v}_0 = \mathbf{0}$, and repeats $\mathbf{v}_{k+1} = \mathcal{T}^\pi\mathbf{v}_k$. Why should that converge, and to the right answer? Because $\mathcal{T}^\pi$ is a contraction.

Claim. For any two value vectors $\mathbf{u}$ and $\mathbf{v}$,

where $\lVert\mathbf{x}\rVert_\infty = \max_s |x_s|$ is the largest absolute entry.

Proof. The rewards cancel, so $\mathcal{T}^\pi\mathbf{u} - \mathcal{T}^\pi\mathbf{v} = \gamma\mathbf{P}_\pi(\mathbf{u} - \mathbf{v})$. Entry $s$ of the right side is $\gamma$ times a weighted average of the entries of $\mathbf{u} - \mathbf{v}$, with weights $(\mathbf{P}_\pi)_{ss'} \ge 0$ that sum to 1. An average is never larger in magnitude than the largest thing being averaged, so every entry is at most $\gamma\lVert\mathbf{u}-\mathbf{v}\rVert_\infty$ in magnitude. $\square$

In plain words, one application of the operator brings any two guesses at least a factor $\gamma$ closer together, measured by their worst disagreement.

That one inequality gives everything. Apply it with $\mathbf{u} = \mathbf{v}_k$ and $\mathbf{v} = V^\pi$ (using $\mathcal{T}^\pi V^\pi = V^\pi$),

So the error shrinks geometrically, by at least a factor $\gamma$ per sweep, from any starting point. The fixed point is also unique. If $\mathbf{u}$ and $\mathbf{v}$ were both fixed points, the claim would give $\lVert\mathbf{u}-\mathbf{v}\rVert_\infty \le \gamma\lVert\mathbf{u}-\mathbf{v}\rVert_\infty$, which forces $\mathbf{u} = \mathbf{v}$. This is the Banach fixed-point theorem in action. A contraction on a complete space has exactly one fixed point, and iterating it from anywhere converges there. Every convergence result in this section is that theorem applied to a different operator.

How many sweeps do you need? To shrink an initial error by a factor $\epsilon$ you need $\gamma^k \le \epsilon$, so $k \ge \ln(1/\epsilon)/\ln(1/\gamma) \approx \ln(1/\epsilon)/(1-\gamma)$. With $\gamma = 0.9$, a millionfold reduction takes about 131 sweeps. With $\gamma = 0.99$ it takes about 1,375. Long horizons are slow to evaluate, which is the effective horizon of §15.1 showing up as a convergence rate.

The error always sits at or below the $\gamma^k$ line, as the proof promises, and in this world it falls faster, because the walker is absorbed by a terminal cell well before the discount alone would wash the future out.

The Bellman optimality equation

Evaluating policies is half the job. We want the best one. Recall from §15.1 that $V^\star(s) = \max_\pi V^\pi(s)$ and $Q^\star(s,a) = \max_\pi Q^\pi(s,a)$. An optimal agent in state $s$ takes the action that maximizes immediate reward plus the discounted optimal value of where it lands, so the optimal values should satisfy the Bellman optimality equations,

In plain words, the best you can do from here is the best first move followed by the best you can do from wherever it takes you. The averaging over the policy's actions in the expectation equation has become a maximum.

That paragraph is a heuristic (Bellman's principle of optimality), and it hides a real question, since $V^\star$ is defined by a maximum over all policies separately in each state. Here is a complete proof that the equation has exactly one solution, that the solution is $V^\star$, and that acting greedily with respect to it is optimal in every state at once. It is short, and it uses only the contraction idea from above.

Value iteration

The proof is also an algorithm. Value iteration starts from $\mathbf{v}_0 = \mathbf{0}$ and applies the optimality operator, $\mathbf{v}_{k+1} = \mathcal{T}^\star\mathbf{v}_k$, until the values stop changing, then reads off the greedy policy. Each sweep costs $O(|\mathcal{S}|^2|\mathcal{A}|)$ for a dense $P$.

When should it stop? We cannot measure the distance to the unknown $V^\star$, but we can bound it by the change in the last sweep. By the triangle inequality and the contraction,

and moving the last term to the left gives

In plain words, if a sweep changes no value by more than $\epsilon$, you are within $\gamma\epsilon/(1-\gamma)$ of the optimum, a guarantee you can check without knowing the answer. The greedy policy usually becomes optimal long before the values settle, so in practice value iteration finds the right policy early and then spends many sweeps polishing numbers.

With $\gamma = 1$ these are exactly the utilities printed in Russell and Norvig's textbook for this world (0.812, 0.868, 0.918 along the top row, and so on), a good check that our transition model matches theirs. Value iteration converges here even though $\gamma = 1$ breaks the contraction proof, because every sensible policy ends up in a terminal cell. The optimal policy is worth studying. From the start cell it goes up and around the top, the long way. In the cell left of the pit it moves up, never right, since right walks straight into the pit, and it accepts the 10% chance that an upward move slips sideways into the pit because every safer route costs more steps. And in the bottom-right corner, at $\gamma = 1$, it goes left, the long way round, rather than risking the walk up past the pit. At $\gamma = 0.9$ the agent is more impatient. The cell just left of that corner now goes up, past the pit, instead of taking the long way, and the cell to its left heads right to join it. The discount changed the optimal behavior, just as in the two-state example of §15.1.

import numpy as np

def value_iteration(P, R, gamma, tol=1e-10):
    raise NotImplementedError

Policy iteration

Value iteration improves values a little at a time and lets the policy emerge. Policy iteration (Howard 1960) alternates two complete steps on the policy itself.

1. Evaluate. Compute $V^{\pi}$ exactly, with the linear solve of Exercise 15.2a.
2. Improve. Replace $\pi$ by the greedy policy $\pi'(s) = \arg\max_a Q^\pi(s, a)$, where $Q^\pi(s,a) = r(s,a) + \gamma\sum_{s'}P(s'\mid s,a)V^\pi(s')$.

Stop when the policy no longer changes. Why does the improvement step never make things worse? This is the policy improvement theorem, and its proof is three lines with the tools above. By the definition of $\pi'$, $\mathcal{T}^{\pi'}V^\pi = \mathcal{T}^\star V^\pi \ge \mathcal{T}^\pi V^\pi = V^\pi$. Applying the monotone operator $\mathcal{T}^{\pi'}$ repeatedly gives $V^\pi \le \mathcal{T}^{\pi'}V^\pi \le (\mathcal{T}^{\pi'})^2V^\pi \le \dots \to V^{\pi'}$. So $V^{\pi'} \ge V^\pi$ in every state. If the greedy step changes nothing, then $\mathcal{T}^\star V^\pi = \mathcal{T}^\pi V^\pi = V^\pi$, so $V^\pi$ solves the Bellman optimality equation and $\pi$ is optimal. If $\pi$ is not optimal, then $\mathcal{T}^\star V^\pi$ exceeds $V^\pi$ in some state, and so does $V^{\pi'} \ge \mathcal{T}^{\pi'}V^\pi = \mathcal{T}^\star V^\pi$. So each round strictly improves the policy until it is optimal, no policy can be visited twice, and since there are only finitely many deterministic policies, policy iteration terminates in a finite number of rounds. In practice that number is tiny.

Policy iteration finishes in a handful of rounds, each one an exact linear solve, where value iteration needed 32 cheaper sweeps (and would need far more for $\gamma$ near 1). The initial "always up" policy is terrible (from the start cell it climbs to the top-left corner and keeps bumping into the top edge, paying the step cost and reaching the goal only through lucky sideways slips), and the very first improvement step changes the action in six of the nine states.

All three are instances of what Sutton and Barto call generalized policy iteration, two processes running against each other, one making the values consistent with the policy and one making the policy greedy with respect to the values. Almost every RL algorithm, including actor-critic methods (§15.4) and PPO (§15.6), has this shape, with a critic that evaluates and an actor that improves.

import numpy as np

def policy_iteration(P, R, gamma):
    raise NotImplementedError

Learning without a model, temporal differences

Everything so far needed $P$ and $r$ in hand. That is called planning or dynamic programming. In most problems the agent does not have them. It can only act and observe what happens. Can it still use the Bellman equation?

It can, by replacing the expectation over next states with a single sample. Suppose the agent, following $\pi$, is in state $s_t$, receives reward $r_t$, and lands in $s_{t+1}$. The Bellman equation says $V^\pi(s_t)$ equals the expected value of $r_t + \gamma V^\pi(s_{t+1})$. So $r_t + \gamma V(s_{t+1})$, computed with the current estimate $V$, is a one-sample guess of what $V(s_t)$ should be, and we can nudge the estimate toward it with the incremental-mean update from §15.1,

with a step size $\alpha \in (0, 1]$ (we follow Sutton and Barto in writing $\alpha$ for tabular step sizes). This is TD(0), temporal-difference learning (Sutton 1988), and $\delta_t$ is the TD error, the difference between the bootstrapped target and the current estimate. If $s_{t+1}$ is terminal, its value is zero by definition, and the target is just $r_t$. In plain words, after every single step, move your estimate of where you were toward what you got plus your estimate of where you are now.

Compare it with the Monte Carlo update, $V(s_t) \leftarrow V(s_t) + \alpha\,(G_t - V(s_t))$, which waits for the episode to end and uses the actual return.

This bias-variance trade-off between the full return and a one-step bootstrap is one of the deepest themes in RL. §15.5 builds a continuous dial between the two, generalized advantage estimation, and PPO uses it on every step. With step sizes that shrink appropriately (the Robbins and Monro conditions $\sum_t\alpha_t = \infty$ and $\sum_t\alpha_t^2 < \infty$, met for instance by $\alpha_t = 1/t$ per state), tabular TD(0) converges to $V^\pi$ with probability 1 (Dayan 1992).

The result depends on the step size, and both halves of the bias-variance table show up. With a small step ($\alpha = 0.02$), Monte Carlo is ahead after 100 episodes, because TD's knowledge of the terminal rewards has to creep backward one state per update while its early, wrong estimates bias every target. By 400 episodes TD has overtaken it. With a larger step ($\alpha = 0.1$), TD is ahead throughout, by a factor of two to three, because each Monte Carlo update chases a single noisy return and the large step lets that noise kick the estimate around. TD's targets are quieter, so it can afford the larger step. That is the usual pattern, though not a law. When the value estimates are poor and stay poor, bootstrapping from them hurts.

Q-learning

TD(0) evaluates a fixed policy. To control, we need action values, because, as §15.1 noted, choosing an action from $V$ needs a model to look ahead, while choosing from $Q$ needs only an argmax. Two TD methods learn $Q$.

SARSA applies the Bellman expectation equation for $Q^\pi$ to the sample $(s_t, a_t, r_t, s_{t+1}, a_{t+1})$, using the next action the agent actually takes,

Q-learning (Watkins 1989) applies the Bellman optimality equation instead,

with the target reduced to $r_t$ when $s_{t+1}$ is terminal. In plain words, move the estimate toward the reward plus the value of the best next action, whatever action the agent will actually take next.

That one change, a max instead of the next sampled action, makes Q-learning off-policy. It learns $Q^\star$, the values of the optimal policy, while the agent behaves according to some other policy (for example $\varepsilon$-greedy, which keeps exploring), because the target never refers to the behavior policy's choices. Watkins and Dayan (1992) proved that tabular Q-learning converges to $Q^\star$ with probability 1, provided every state-action pair keeps being tried and the step sizes satisfy the Robbins and Monro conditions. SARSA is on-policy. It learns the value of the policy it follows, exploration included, which makes it more cautious near cliffs, since it accounts for its own random steps.

import numpy as np

def q_learning_update(Q, s, a, r, s_next, terminated, alpha, gamma):
    raise NotImplementedError

Here is Q-learning solving the gridworld from experience alone. The agent never sees $P$. It explores with $\varepsilon$-greedy actions and starts each episode in a random non-terminal cell, so that every state-action pair keeps being visited, as the convergence theorem requires. We compare what it learned with the $Q^\star$ that value iteration computed from the model.

After about 16,000 steps the greedy policy is optimal in every cell, though some action values are still off by more than 0.1. Finding the right ranking of actions is much easier than finding their exact values, which is also why value iteration's policy settled long before its values did.

From tables to networks

Real problems have far too many states for a table, so $Q$ becomes a network $Q_\psi(s, a)$ with parameters $\psi$, trained to regress onto the Q-learning target. Doing this naively is unstable, and DQN (Mnih et al. 2015), which learned to play 49 Atari games from pixels, needed two stabilizers. An experience replay buffer stores past transitions and trains on random minibatches of them, which breaks the correlation between consecutive samples. A target network, a periodically refreshed copy $Q_{\bar\psi}$, computes the targets $r + \gamma\max_{a'}Q_{\bar\psi}(s', a')$, so the regression target does not move with every gradient step. Two further problems are worth knowing by name. The max in the target is biased upward when the estimates are noisy (the maximum of noisy estimates overestimates the maximum of the true values), which double Q-learning fixes by choosing the action with one estimate and evaluating it with another (van Hasselt 2010). And combining function approximation, bootstrapping, and off-policy data, which Sutton and Barto call the deadly triad, can make the values diverge even on tiny problems.

Offline RL, learning from a fixed dataset

Off-policy learning suggests a tempting extreme. If Q-learning can learn from data that some other policy collected, why collect any new data at all? Learning entirely from a fixed log of transitions, with no further interaction, is offline (or batch) RL, and it is what you would want wherever exploring is dangerous or expensive, in medicine, in driving, or with a recommender serving real users.

It is much harder than it looks, and the max in the Q-learning target is the reason. At the next state the max picks whichever action the network rates highest, including actions the dataset never contains, whose values are pure extrapolation. Online, an overrated action gets tried, disappoints, and is corrected. Offline it is never tried, so the error stays, and bootstrapping copies it backward to every state that leads there. The usual result is a policy that heads confidently for exactly the actions the data knows least about, and a deep Q-network trained this way can do worse than just imitating the logged actions (behavior cloning).

The fixes all keep the learned policy close to the data. BCQ (Fujimoto, Meger, and Precup 2019) only considers actions that a model of the logging policy makes likely. Conservative Q-learning (Kumar et al. 2020) adds a penalty that pushes down the values of actions the learned policy favors and pushes up the values of actions in the data, so unseen actions are underrated instead of overrated. Implicit Q-learning (Kostrikov, Nair, and Levine 2022) never evaluates an unseen action at all, replacing the max by an upper expectile of the values of the actions that do appear. Levine et al. (2020) survey the field. The same tension returns with language models. Training on a fixed set of preference pairs, as DPO does, is learning from someone else's samples, and the comparison of online and offline preference learning shows what that costs, while the KL penalty toward a reference model in §15.7 is the same stay-near-the-data idea in another form.

Value-based methods dominate when actions are few and data is cheap to reuse. Language models are the opposite case. They start from a strong pretrained policy (the next-token distribution) that we want to adjust gently, and the policy-gradient methods of §15.3 to §15.6 do exactly that. The Bellman equations do not go away, though. The critic in PPO is a learned $V^\pi$ trained with TD-style targets, and its TD errors are the raw material of the advantage estimates in §15.5.

In PyTorch

Here is the loss DQN optimizes, written the way production code writes it, with a target network, a batch of transitions, and a terminal mask. We fill a replay buffer with random gridworld transitions and take a few gradient steps on a small network.

Read more

• Sutton & Barto (2018). Reinforcement Learning: An Introduction, 2nd edition. Chapters 3, 4, and 6 cover the Bellman equations, dynamic programming, and TD learning, with the gridworld examples that made them famous.
• Bellman (1957). Dynamic Programming. The book that introduced the principle of optimality.
• Watkins & Dayan (1992). Q-learning. The convergence proof for tabular Q-learning.
• Sutton (1988). Learning to Predict by the Methods of Temporal Differences. TD learning and TD($\lambda$), the idea we will turn into GAE in §15.5.
• Mnih et al. (2015). Human-level control through deep reinforcement learning. DQN, with experience replay and a target network.
• Levine, Kumar, Tucker & Fu (2020). Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems. Why learning from a fixed dataset is hard, and the conservative and constrained methods that make it work.
• Szepesvári (2010). Algorithms for Reinforcement Learning. A short, rigorous monograph, with the contraction arguments of this section in full generality.

Watch next

▶

▶

▶

▶