Function approximation and DQN

A pole is balanced on a cart. The state is four real numbers: cart position, cart velocity, pole angle, angular velocity. Your Q-learning agent from Chapter 5 keeps one number per state–action pair in a table. Which row does it look up for the state $(0.0213, -0.1870, 0.0441, 0.3302)$? There is no such row, and there never will be: the agent will almost surely never see exactly that state again. Yet you know what to do there, because you have seen thousands of states like it.

That is the problem this chapter solves. Tables learn each entry separately; real problems need agents that generalize, so that experience in one state teaches them about similar states. You’ll replace the table with a function that has a fixed number of parameters: first a linear function of hand-made features, then a neural network. You’ll see why this, combined with bootstrapping and off-policy learning, can make value estimates blow up to infinity. Then you’ll meet the Deep Q-Network (DQN), the 2015 agent that learned to play 49 Atari games from raw pixels (a separate network for each game, but one recipe for all), and the small set of engineering fixes that made it work. By the end you’ll have built DQN yourself and trained it to balance CartPole.

Why tables fail

Tabular methods have two problems, one obvious and one deeper.

The obvious one is size. Chop each of CartPole’s four variables into 10 bins and you get $10^4$ cells, times 2 actions: fine. Chop them into 100 bins each and you need $2 \times 10^8$ entries. An Atari frame is $210 \times 160$ pixels with 128 possible colors; the number of distinct screens is beyond astronomical. This is the curse of dimensionality you met at the end of Chapter 4: the table grows exponentially with the number of state variables.

The deeper problem is no generalization. Even if memory were free, a table learns about a cell only when that exact cell is visited. In a continuous space you essentially never revisit a state, so every update is wasted on a cell you’ll never see again. A finer table makes this worse, not better: each cell gets less data.

The fix is to learn a function with far fewer parameters than there are states, chosen so that states that “look alike” get similar values. Then an update in one state moves the values of its neighbors too. That is a gift (you learn from far less data) and, as you’ll see, a curse (an update meant for one state can damage others).

Values from features

The linear value function

Describe each state $s$ by a feature vector $\phi(s) \in \mathbb{R}^d$: $d$ numbers that summarize what matters about the state. Then approximate the value as a weighted sum of features:

$$\hat V(s; w) = w^\top \phi(s) = \sum_{i=1}^{d} w_i \, \phi_i(s).$$

The weights $w \in \mathbb{R}^d$ are what we learn. We write $w$ for value-function weights, as Sutton & Barto do, and save $\theta$ for neural networks and policies. The key number is $d$: you learn $d$ weights, no matter how many states there are.

Some feature choices, on a one-dimensional state $x \in [0, 1]$:

• One-hot features (a table). If there are finitely many states, set $\phi_i(s) = 1$ if $s$ is the $i$-th state and 0 otherwise. Then $w_i$ is just the table entry for state $i$. Tables are the special case of linear function approximation with no sharing.
• Bins (state aggregation). Split $[0, 1]$ into $d$ intervals; $\phi_i(x) = 1$ if $x$ falls in bin $i$. Every state in a bin shares one value: generalization within a bin, none across bins.
• Hat features (piecewise-linear interpolation). Place $d$ nodes evenly on $[0,1]$; $\phi_i$ is a triangle that is 1 at node $i$ and falls linearly to 0 at the neighboring nodes. $\hat V$ is then the straight-line interpolation between the node values $w_i$.
• Radial basis functions (RBFs). Gaussian bumps $\phi_i(x) \propto \exp\!\big(-(x - c_i)^2 / 2\sigma^2\big)$ centered at $c_i$. The width $\sigma$ sets how far one state’s experience spreads.
• Polynomials, Fourier features, and tile coding (several offset grids of bins, summed) are other classic choices. In a deep network, the last hidden layer is a learned feature vector, and the output layer is exactly this linear formula.

A worked example: watch the neighbors move

Take the simplest hat features on $[0, 1]$, just two of them: $\phi(x) = (1 - x,\; x)$. So $\hat V(x; w) = w_1 (1 - x) + w_2 x$, a straight line with value $w_1$ at $x = 0$ and $w_2$ at $x = 1$. Start from $w = (0, 0)$.

Suppose you observe, from state $x = 0.8$, a return of 1. You want $\hat V(0.8)$ closer to 1. Treat this as a regression problem: take a gradient step on the squared error $\tfrac12 \big(1 - \hat V(0.8; w)\big)^2$ with step size $\alpha = 0.5$. The gradient of $\hat V$ with respect to $w$ is just the feature vector, $\nabla_w \hat V(x; w) = \phi(x)$, so

$$w \leftarrow w + \alpha \big(1 - \hat V(0.8; w)\big)\, \phi(0.8) = (0, 0) + 0.5 \times 1 \times (0.2,\, 0.8) = (0.1,\, 0.4).$$

Now read off values:

$x$	0	0.2	0.5	0.8	1
$\hat V(x; w)$ before	0	0	0	0	0
$\hat V(x; w)$ after	0.10	0.16	0.25	0.34	0.40

You updated at one state, $x = 0.8$, and every state’s value moved, including $x = 0.2$, which you have never visited. With a table, only the cell containing 0.8 would have changed.

Two more things to notice. First, $\hat V(0.8)$ went from 0 to 0.34, not to 1. With step size $\alpha$, a single update at $x$ changes $\hat V(x)$ by $\alpha \lVert \phi(x) \rVert^2$ times the error, and here $\lVert \phi(0.8) \rVert^2 = 0.04 + 0.64 = 0.68$. Second, which neighbors move, and by how much, is decided entirely by the features. Choosing features is choosing how your agent generalizes.

What should the weights minimize?

With $d$ weights and many more states, you generally cannot get every state’s value right. You have to decide which errors matter. The standard answer is the mean squared value error, weighted by how often each state is visited:

$$\overline{\text{VE}}(w) = \sum_{s} \mu(s) \big[ V^\pi(s) - \hat V(s; w) \big]^2 .$$

Here $\mu(s)$ is the on-policy distribution: the fraction of time the policy $\pi$ spends in state $s$. Spend your limited accuracy where the agent actually goes. Remember this $\mu$; it is the hero of the stability story later in this chapter.

If an oracle handed you $V^\pi(s_t)$ for each visited state, you would do stochastic gradient descent:

$$w \leftarrow w + \alpha \big[ V^\pi(s_t) - \hat V(s_t; w) \big] \nabla_w \hat V(s_t; w).$$

There is no oracle. As in Chapter 5, you substitute a target $U_t$ that you can compute from experience:

• Monte Carlo: $U_t = G_t$, the actual return. Since $\mathbb{E}[G_t \mid s_t] = V^\pi(s_t)$, this is an unbiased stand-in, and the update is honest stochastic gradient descent on $\overline{\text{VE}}$. It converges (to a local optimum for nonlinear $\hat V$), but it is slow and noisy and must wait for the episode to end.
• TD(0): $U_t = r_t + \gamma \hat V(s_{t+1}; w)$. Lower variance, learns online, but the target is built from our own estimate. This is where things get interesting.

Semi-gradient TD: why “semi”

Plug the TD target into the update:

$$w \leftarrow w + \alpha\, \delta_t \, \nabla_w \hat V(s_t; w), \qquad \delta_t = r_t + \gamma \hat V(s_{t+1}; w) - \hat V(s_t; w).$$

This is semi-gradient TD(0). For linear features the gradient is $\phi(s_t)$, so the update is just $w \leftarrow w + \alpha \delta_t \phi(s_t)$. With one-hot features it reduces exactly to the tabular TD(0) of Chapter 5.

Why “semi”? The target $r_t + \gamma \hat V(s_{t+1}; w)$ depends on $w$ too, but the update ignores that dependence. It differentiates only the prediction $\hat V(s_t; w)$ and treats the target as if it were a fixed label. If you took the true gradient of $\tfrac12 \delta_t^2$, you’d get an extra term:

$$-\nabla_w \tfrac12 \delta_t^2 = \delta_t \big[ \nabla_w \hat V(s_t; w) - \gamma \nabla_w \hat V(s_{t+1}; w) \big].$$

Semi-gradient TD keeps the first half of the chain rule and drops the second half.

So why not use the full gradient? The full-gradient method exists (it is called the residual-gradient algorithm). It really is gradient descent, but on the squared TD error, which is the wrong objective when transitions are random. Minimizing $\mathbb{E}[\delta_t^2]$ also tries to make the randomness of the next state disappear, which pulls values toward wrong answers. In practice it also learns much more slowly. Exercise 6.3 works through this.

The price of “semi” is that the update is no longer the gradient of any objective. That has a consequence: we lose the guarantee that every step goes downhill. Hold onto this; it is the root of the deadly triad.

A worked TD step, and a moving target

Continue the example, with $w = (0.1, 0.4)$, $\gamma = 0.9$ and $\alpha = 0.5$. The agent moves from $x = 0.5$ to $x' = 0.8$ with reward 0.

• Prediction: $\hat V(0.5) = 0.5 \times 0.1 + 0.5 \times 0.4 = 0.25$.
• Target: $r + \gamma \hat V(0.8) = 0 + 0.9 \times 0.34 = 0.306$.
• TD error: $\delta = 0.306 - 0.25 = 0.056$.
• Update: $w \leftarrow (0.1, 0.4) + 0.5 \times 0.056 \times (0.5, 0.5) = (0.114,\, 0.414)$.

Now recompute the target with the new weights: $\hat V(0.8) = 0.114 \times 0.2 + 0.414 \times 0.8 = 0.354$, so the target is now $0.9 \times 0.354 = 0.319$. The target moved up because we moved toward it. Generalization tied $x = 0.5$ and $x = 0.8$ together, so raising one raised the other. In this example the chase settles down. You will soon see a case where it never does.

What linear TD converges to

With linear features, on-policy sampling, and a suitably decreasing step size, semi-gradient TD(0) converges with probability one (Tsitsiklis & Van Roy, 1997). It converges to the TD fixed point $w_\text{TD}$, the weights where the expected update is zero:

$$\mathbb{E}_{s \sim \mu}\big[ \delta \, \phi(s) \big] = 0 .$$

In words, the TD error is uncorrelated with every feature, so there is no direction in feature space that the updates still want to move. That is not the same as the best fit $\min_w \overline{\text{VE}}(w)$, but it is provably not far off:

$$\overline{\text{VE}}(w_\text{TD}) \;\le\; \frac{1}{1-\gamma}\, \min_w \overline{\text{VE}}(w).$$

When $\gamma$ is near 1 the bound is loose. TD trades some asymptotic accuracy for much lower variance and faster learning, the same bias–variance trade you saw in Chapter 5.

∂ The TD fixed point is a Galerkin projection, and why on-policy sampling makes it stable

Use matrix notation for a finite MDP under policy $\pi$: $\Phi$ is the $|\mathcal S| \times d$ matrix whose rows are $\phi(s)^\top$, $P_\pi$ the transition matrix, $r_\pi$ the expected-reward vector, and $D = \text{diag}(\mu)$ the state-weighting.

The expected update. Averaging the update $\alpha\,\delta\,\phi(s)$ over $s \sim \mu$ and the next state gives

$$\mathbb{E}[\Delta w] = \alpha\, \Phi^\top D \big( r_\pi + \gamma P_\pi \Phi w - \Phi w \big) = \alpha\,(b - A w),$$

with $b = \Phi^\top D r_\pi$ and $\mathbf{A} = \Phi^\top D (I - \gamma P_\pi) \Phi$, a $d \times d$ matrix (Sutton & Barto’s notation; the bold face is there so you don’t confuse it with state A of the example below). The fixed point solves $\mathbf{A} w_\text{TD} = b$.

Galerkin. The fixed-point condition says the Bellman residual $r_\pi + \gamma P_\pi \Phi w - \Phi w$ is orthogonal to every feature column under the inner product $\langle u, v \rangle_D = u^\top D v$. That is exactly a Galerkin method: look for a solution in a subspace (the span of the features) and require the residual of the equation to be orthogonal to that subspace. Equivalently, $\Phi w_\text{TD} = \Pi\, T^\pi(\Phi w_\text{TD})$, where $T^\pi v = r_\pi + \gamma P_\pi v$ is the Bellman operator and $\Pi$ is the $D$-weighted orthogonal projection onto the feature span. Apply a Bellman backup (which leaves the subspace), then project back.

Stability. The error $e = w - w_\text{TD}$ of the expected dynamics $w \leftarrow w + \alpha (b - \mathbf{A}w)$ obeys $e \leftarrow (I - \alpha \mathbf{A})\, e$. This shrinks for small enough $\alpha$ if every eigenvalue of $\mathbf{A}$ has a positive real part. A sufficient condition is that $\mathbf{A}$ is positive definite, meaning $u^\top \mathbf{A} u > 0$ for every $u \neq 0$ ($\mathbf{A}$ need not be symmetric; if $\mathbf{A}u = \lambda u$ for complex $u$, then $\text{Re}\,\lambda \, \lVert u \rVert^2 = \text{Re}(\bar u^\top \mathbf{A} u) > 0$). Write $v = \Phi u$. Then $u^\top \mathbf{A} u = v^\top D v - \gamma\, v^\top D P_\pi v$. By Cauchy–Schwarz in the $D$-inner product, $v^\top D P_\pi v \le \lVert v \rVert_D \lVert P_\pi v \rVert_D$.

Now the crucial step. If $\mu$ is the stationary distribution of $P_\pi$ (that is, $\mu^\top P_\pi = \mu^\top$), then

$$\lVert P_\pi v \rVert_D^2 = \sum_s \mu(s) \Big( \sum_{s'} P_\pi(s'|s) v(s') \Big)^2 \le \sum_s \mu(s) \sum_{s'} P_\pi(s'|s) v(s')^2 = \sum_{s'} \mu(s') v(s')^2 = \lVert v \rVert_D^2,$$

using Jensen’s inequality and then stationarity. So $P_\pi$ does not stretch vectors in the $D$-norm, and $u^\top \mathbf{A} u \ge (1 - \gamma) \lVert v \rVert_D^2 > 0$ when the features are linearly independent (and every state has $\mu(s) > 0$). On-policy linear TD is stable. (In an episodic task, $P_\pi$ leaks probability to the terminal state and $\mu^\top P_\pi \le \mu^\top$ entrywise; both inequalities still hold.)

If $\mu$ is not the on-policy distribution, the inequality $\lVert P_\pi v \rVert_D \le \lVert v \rVert_D$ can fail: the states $P_\pi$ moves you to may carry little weight in $D$, so their errors are rarely corrected. If $P_\pi$ stretches some $v$ by more than a factor $1/\gamma$ in the $D$-norm, $\gamma\, v^\top D P_\pi v$ can exceed $v^\top D v$, $\mathbf{A}$ can have an eigenvalue with negative real part, and the expected update pushes $w$ away from the fixed point. That is the deadly triad in one line of linear algebra. The two-state example below has $\mathbf{A} = 1 - 2\gamma$ (a $1 \times 1$ matrix), which is negative for $\gamma > 1/2$.

The same argument shows $\Pi T^\pi$ is a $\gamma$-contraction in $\lVert \cdot \rVert_D$ when $\mu$ is on-policy (projection is non-expansive, and $T^\pi$ contracts by $\gamma$). This is the function-approximation version of the contraction argument from Chapter 4.

From V to Q: semi-gradient Q-learning

For control we need action values. Approximate $Q(s, a; w)$ (for example with features $\phi(s, a)$) and plug in Q-learning’s target from Chapter 5:

$$w \leftarrow w + \alpha \Big[ r_t + \gamma \max_{a'} Q(s_{t+1}, a'; w) - Q(s_t, a_t; w) \Big] \nabla_w Q(s_t, a_t; w).$$

That’s the whole algorithm. Everything else in this chapter is about making it work when $Q$ is a neural network.

See it: generalization on a continuous corridor

The demo below is a continuous version of Chapter 5’s random walk. A robot sits on a rail at position $x \in [0, 1]$. It makes no decisions, so this is prediction (estimating $V$ of a fixed behavior), as in Chapter 5. Each step it drifts right by 0.025 on average, with Gaussian noise of standard deviation 0.05; a wall at $x = 0$ stops it from going further left. Reaching $x = 1$ pays $+1$ and ends the episode; every step that lands in the puddle costs $0.2$; $\gamma = 0.96$. The dashed curve is the true $V(x)$, computed exactly. The solid curve is a linear $\hat V(x; w)$ that you can teach by hand (tap the plot) or train with semi-gradient TD(0) (Play). The faint bumps are the pieces $w_i \phi_i(x)$; the curve is their sum. The strip at the bottom shows the features themselves, with the ones touched by the latest update highlighted.

All three feature types here are normalized so that $\sum_i \phi_i(x) = 1$ at every $x$. One consequence: an update with step size $\alpha$ closes at most a fraction $\alpha$ of the gap at the updated state, which makes the TD slider easy to read.

Features:Bins (a table)HatsRBFs

Number of features 12RBF width σ 0.06TD step size α 0.20

▶ Play TD(0)Reset weightsSpeed 30 steps/frame show the pieces wᵢφᵢ(x)

Tap anywhere on the plot: one gradient step moves V at that position exactly onto your tap. Watch what else moves.

What to try: (1) With RBFs, tap high above x = 0.3. Watch V rise around 0.3, by less with distance. (2) Switch to Bins (a table) and tap again: only one bin moves. (3) Press Play with RBFs, σ = 0.06; the RMS error falls to about 0.05 within a few hundred episodes. Reset, set σ = 0.25, and play again: the curve is smooth, but it can't follow the sharp rise after the puddle. (4) Compare Bins with 12 features against Bins with 40: the coarse table learns faster at first, the fine one ends up more accurate.

The demo shows the central trade-off of function approximation. Coarse or wide features generalize aggressively: each weight pools data from a large region, so a rough answer appears quickly, but you can’t represent sharp changes, and an update in one place disturbs values far away. Fine or narrow features can represent much more detail, but each one learns only from the data that lands near it, and you drift back toward the slow, data-hungry behavior of a table. Neural networks partly escape this trade-off by learning features that are wide where the value is smooth and narrow where it changes fast.

Neural network Q-functions

Hand-designed features work for a 1D corridor. They do not work for raw pixels: nobody knows how to write down $\phi(\text{screen})$ by hand. A neural network learns its own features. In a Q-network $Q(s, a; \theta)$, the hidden layers compute a learned feature vector, and the last layer is a linear map from it to Q-values.

DQN made one architectural choice that you will reuse in the lab. The network takes the state as input and outputs one Q-value per action, a vector in $\mathbb{R}^{|\mathcal{A}|}$. A single forward pass then gives $\max_{a'} Q(s', a'; \theta)$ and the greedy action, instead of one pass per action.

For Atari, Mnih et al. (2015) fed the network the last 4 frames, downsampled to $84 \times 84$ grayscale and stacked. One frame does not show which way the ball is moving; four frames do. Stacking frames makes the state (closer to) Markov, the fix you met in Chapter 3. The network had three convolutional layers, a 512-unit fully connected layer, and one output per action (up to 18). For CartPole the state is already Markov and tiny, so an MLP with two hidden layers is plenty.

The obvious first attempt, often called naive deep Q-learning, is semi-gradient Q-learning with a network:

for each step t:
    pick a_t epsilon-greedily from Q(s_t, ·; θ)
    observe r_t, s_{t+1}
    y = r_t + γ · max_a' Q(s_{t+1}, a'; θ)         # 0 instead of the max if s_{t+1} is terminal
    take one gradient step on (y − Q(s_t, a_t; θ))², with y held constant

It usually fails. In the lab’s ablation run (python run.py --compare), removing just the target network from DQN on CartPole makes the Q-values explode (the loss climbs past $10^8$), and the greedy agent drops the pole after about 10 steps. To understand why, we need a small example where everything can be computed by hand.

The deadly triad

Sutton & Barto name three ingredients that are each useful on their own but can cause divergence when all three are present. They call the combination the deadly triad:

1. Function approximation: states share parameters, so an update to one state changes others.
2. Bootstrapping: targets are built from current estimates ($r + \gamma \hat V(s')$) rather than actual returns.
3. Off-policy learning: the distribution of updates differs from the distribution of states the target policy would actually visit.

Any two are fine. Tabular Q-learning is off-policy and bootstraps, and it converges. On-policy linear TD bootstraps and approximates, and the Derivation above shows it is stable. Monte Carlo with function approximation is plain regression. All three together can diverge, even with linear features, even with the exact expected updates, and even when a perfect solution exists.

The smallest example: $w \to 2w$

Here is the example from Sutton & Barto (section 11.2). There are two states, A and B. A leads to B with reward 0; B leads to the end with reward 0. The true values are $V(A) = V(B) = 0$. Use one shared weight $w$ with features $\phi(A) = 1$ and $\phi(B) = 2$, so

$$\hat V(A) = w, \qquad \hat V(B) = 2w.$$

$w = 0$ represents the truth exactly. Start at $w = 1$.

Now the off-policy part. Under the policy you are evaluating, every visit to A is followed by a visit to B, so on-policy data would update B exactly as often as A. Suppose instead that the data you learn from contains the A → B transition over and over, and B is never updated. In Sutton & Barto’s version, A → B is a fragment of a larger MDP: the behavior policy keeps leaving B through actions the target policy would never take, and those samples get importance weight 0, so B’s update never happens. All you need here is the result: many updates at A, none at B, a distribution of updates the target policy would never produce. The semi-gradient TD update on A → B is

$$w \leftarrow w + \alpha \big( 0 + \gamma \cdot 2w - w \big) \cdot 1 = \big(1 + \alpha (2\gamma - 1)\big)\, w .$$

For $\gamma > 1/2$ the factor is bigger than 1, so $w$ grows geometrically. With $\alpha = 0.1$ and $\gamma = 0.9$, each update multiplies $w$ by $1.08$, and after 100 updates $w \approx 1.08^{100} \approx 2200$. The step size doesn’t matter: a smaller $\alpha$ only slows the explosion.

Why? Each update tries to make $\hat V(A)$ equal to $\gamma \hat V(B) = 1.8w$. The only way to raise $\hat V(A)$ is to raise $w$, which raises $\hat V(B)$ twice as much, which raises the target. The target runs away faster than the prediction can chase it, and nothing ever pulls $\hat V(B)$ back down, because B is never updated.

Now remove one ingredient at a time:

• Make it on-policy. Every episode passes through A and B, so update on both transitions. The B update has target 0 (B leads to the end): $w \leftarrow w + \alpha (0 - 2w) \cdot 2 = (1 - 4\alpha) w$. Per episode, $w$ is multiplied by $1.08 \times 0.6 = 0.648$, and it converges to 0. The update at B, which sees B’s value is too high, keeps things in check.
• Drop function approximation. Give A and B separate table entries. $V(A)$ moves toward $\gamma V(B) = 1.8$ and stops there. That is wrong (B was never corrected), but finite.
• Drop bootstrapping. Use the Monte Carlo return as the target for A, which is 0. Then $w \leftarrow (1 - \alpha) w \to 0$.

Run all four cases yourself:

Function approximationBootstrappingOff-policy updatesTarget network (copy every 25)

Discount γ 0.90Step size α 0.10

▶ RunStepReset

What to try: (1) Press Run with all three ingredients on: a straight line upward on the log scale is exponential divergence. (2) Turn off Off-policy updates: the error plunges (the dashed line keeps the previous run for comparison). (3) Turn Off-policy back on, then turn off Function approximation instead: V(A) settles at 2γ = 1.8, which is wrong but finite. (4) With all three on, drag γ below 0.5 and press Run: now it converges. (5) Turn on Target network: does it save you?

How this shows up in deep Q-learning

Naive deep Q-learning has all three ingredients at full strength, plus some extra problems of its own:

• Off-policy by construction. The target uses $\max_{a'}$ (the greedy policy) while the data comes from ε-greedy behavior. On top of that, the states you update on are whatever you happened to visit recently, not a balanced sample.
• Correlated samples. Consecutive states in an episode are nearly identical. Training on them in order is like fitting a regression on data sorted by $x$: the network fits the current region, forgets the rest (catastrophic forgetting), and the gradient steps are far from the independent samples that stochastic gradient descent assumes.
• A target that moves with every step. The target $y = r + \gamma \max_{a'} Q(s', a'; \theta)$ uses the same $\theta$ you are updating, and $s'$ is usually very close to $s$. A step that raises $Q(s, a)$ also raises $Q(s', \cdot)$, which raises the target: the $w \to 2w$ mechanism, now in a million dimensions.
• The max is optimistic. $\max_{a'}$ over noisy estimates is biased upward, and bootstrapping copies that bias backward through the states. More on this under Double DQN.
• Unbounded error sizes. A single surprising transition can produce a huge error, a huge gradient, and a huge jump in $\theta$.

DQN: four stabilizers

Mnih et al. (2013; 2015) kept semi-gradient Q-learning and added fixes aimed at exactly these problems. None of them comes with a convergence proof. Together they worked well enough to learn dozens of Atari games with one set of hyperparameters.

1. Experience replay

Store every transition $(s_t, a_t, r_t, s_{t+1}, \text{done}_t)$ in a replay buffer $\mathcal{D}$ that holds the last $N$ transitions (DQN used $N = 10^6$). For each gradient step, sample a minibatch uniformly at random from the buffer instead of using the latest transition. Experience replay goes back to Lin (1992). It helps in three ways:

• Decorrelation. A random minibatch mixes transitions from many episodes and many parts of the state space, much closer to the independent samples that stochastic gradient descent expects.
• Data reuse. Each transition is used in many updates, not once. Environment steps are often the expensive part, so this matters.
• Smoothing. The buffer holds data from many past policies, so the training distribution changes slowly even when the greedy policy flips suddenly.

Replay is possible only because Q-learning is off-policy: its target $r + \gamma \max_{a'} Q(s', a')$ is valid no matter which policy produced the transition. SARSA’s target needs $a_{t+1}$ from the current policy, so stale transitions would give the wrong target. Notice the tension, though. Replay makes the data more off-policy, since it comes from older policies, which is one leg of the triad. It still helps on balance, because its decorrelating and smoothing effects dominate.

2. A target network

Keep a second copy of the network, with parameters $\theta^-$, and compute targets with it:

$$y = r + \gamma \, (1 - \text{done}) \max_{a'} Q(s', a'; \theta^-).$$

Every $C$ steps, copy $\theta^- \leftarrow \theta$ (DQN used $C = 10{,}000$ updates). In between, the targets stay put. Each block of $C$ steps then becomes an ordinary supervised regression: fit $Q(\cdot; \theta)$ to fixed labels computed from $\theta^-$. Updates to $\theta$ no longer drag their own targets along within a block.

There is a nice way to see the whole loop. Each block approximately computes $Q_{k+1} \approx \mathcal{T} Q_k$ (one Bellman optimality backup, done by regression), and then the copy sets up the next block. That is value iteration from Chapter 4, with each sweep replaced by a regression on sampled data. Value iteration converges because $\mathcal T$ is a contraction. DQN hopes that the regression errors stay small enough not to undo that.

A common variant is the soft or Polyak update, $\theta^- \leftarrow \tau \theta + (1 - \tau) \theta^-$ with small $\tau$ (like 0.005) every step. It’s popular in continuous-control methods. The lab implements both.

3. The Huber loss (error clipping)

DQN limits how hard any single transition can pull on $\theta$. Write the error as $e = Q(s, a; \theta) - y$. The Huber loss is quadratic for small errors and linear for large ones:

$$L(e) = \begin{cases} \tfrac12 e^2 & \text{if } \lvert e \rvert \le 1, \\ \lvert e \rvert - \tfrac12 & \text{otherwise,} \end{cases} \qquad \frac{dL}{de} = \text{clip}(e, -1, 1).$$

Its gradient is the squared-error gradient, clipped to $[-1, 1]$. Mnih et al. describe this as clipping the error term to $[-1, 1]$; it is the same thing. Huge errors are common early in training and after rare events. With Huber they push with bounded force, and they still push in the right direction. In PyTorch it is F.smooth_l1_loss.

4. Reward clipping

Atari scores range from single digits to tens of thousands per game. DQN clipped every reward to $[-1, 1]$ (positive rewards become $+1$, negative ones $-1$). This kept the scale of Q-values and gradients similar across games, so one learning rate worked for all 49 of them. The cost is real: the agent can no longer tell a small reward from a big one. Later work replaced clipping with smarter normalization. For CartPole, where every reward is already $+1$, it doesn’t matter.

The DQN algorithm

DQN with experience replay and a target network
 1. initialize Q-network θ, target network θ⁻ ← θ, empty replay buffer D (capacity N)
 2. for step t = 0, 1, 2, ...:
 3.     ε ← schedule(t)                                    # e.g. 1.0 → 0.05 linearly
 4.     a_t ← random action with prob. ε, else argmax_a Q(s_t, a; θ)
 5.     take a_t, observe r_t, s_{t+1}, done_t; store (s_t, a_t, r_t, s_{t+1}, done_t) in D
 6.     sample a random minibatch of B transitions (s, a, r, s', done) from D
 7.     y ← r + γ (1 − done) max_a' Q(s', a'; θ⁻)           # no gradient through y
 8.     loss ← mean Huber(Q(s, a; θ) − y)
 9.     take a gradient step on the loss with respect to θ
10.     every C steps: θ⁻ ← θ

The Nature paper’s settings, for reference: buffer $N = 10^6$, minibatch $B = 32$, $C = 10^4$, $\gamma = 0.99$, RMSProp with learning rate $2.5 \times 10^{-4}$, ε annealed from 1.0 to 0.1 over the first million frames, one update every 4 actions, each action repeated for 4 frames. CartPole needs a much smaller scale: the lab uses a 50k buffer, $B = 128$, $C = 500$, Adam at $5 \times 10^{-4}$, and 50,000 steps, which takes about a minute on a laptop.

A worked minibatch

Here is one loss computation by hand, with tiny Q-tables standing in for networks so you can see every number. Three states, two actions, $\gamma = 0.5$. The online and target networks are

	$Q(\cdot, a_0; \theta)$	$Q(\cdot, a_1; \theta)$	$Q(\cdot, a_0; \theta^-)$	$Q(\cdot, a_1; \theta^-)$
state 0	0	2.2	0	0
state 1	5	1	1	3
state 2	0	4	2	−1

and the minibatch is $(s, a, r, s', \text{done})$ = $(0, a_1, 1, 1, 0)$, $(1, a_0, 0, 2, 0)$, $(2, a_1, -1, 1, 1)$.

• Targets from $\theta^-$: $y_1 = 1 + 0.5 \max(1, 3) = 2.5$; $y_2 = 0 + 0.5 \max(2, -1) = 1$; $y_3 = -1$ (terminal, no bootstrap).
• Predictions $Q(s, a; \theta)$: 2.2, 5, 4.
• Errors $e$: $-0.3$, $4$, $5$.
• Huber: $0.5 \times 0.09 = 0.045$, then $4 - 0.5 = 3.5$, then $5 - 0.5 = 4.5$. Mean loss $= 8.045 / 3 \approx 2.68$.
• Gradient with respect to the three entries used: $\text{clip}(e, -1, 1)/3 = (-0.1, \; 0.33, \; 0.33)$. The two big errors push with the same capped force.

Exercise 6.7 has you redo this with Double DQN targets. The lab’s tests use exactly these numbers.

The Atari result

Mnih et al. (2015) evaluated DQN on 49 Atari 2600 games, training a separate agent on each game but with the same network architecture, hyperparameters and training procedure for all of them. The agent saw only the screen pixels and the score. The paper reports that DQN outperformed the best previous reinforcement learning methods on 43 of the games, and reached more than 75% of a professional human games tester’s score on 29 of them, which is more than half. It did best on reactive games like Breakout and Pong. It did essentially nothing on games that need long-range exploration, most famously Montezuma’s Revenge, where rewards are rare and ε-greedy dithering almost never finds them.

The paper’s ablations matter for this chapter. Removing experience replay hurt dramatically. Removing the target network also hurt, by less. The combination was best. The 2013 workshop version (Mnih et al., “Playing Atari with Deep Reinforcement Learning”) already had replay but not the separate target network.

Improvements in brief

DQN started a long line of refinements. Each one targets a specific weakness.

Double DQN: fixing optimism

Suppose that in state $s'$ all actions are truly worth 0, but your estimates are noisy: each is $+1$ or $-1$ with equal probability, independently. The true $\max_{a'} Q$ is 0. The estimated max is $+1$ unless both estimates come out at $-1$, which happens with probability $1/4$. So $\mathbb{E}[\max] = \tfrac34(1) + \tfrac14(-1) = 0.5$. The max of noisy estimates is biased upward, and bootstrapping copies that bias into the values of the states before $s'$.

You met the fix in Chapter 5 as Double Q-learning: don’t use the same noisy numbers to choose the best action and to evaluate it. Double DQN (van Hasselt, Guez & Silver, 2016) gets a second estimator for free from the target network:

$$y = r + \gamma\, Q\big(s', \; \arg\max_{a'} Q(s', a'; \theta); \; \theta^- \big).$$

The online network picks the action and the target network scores it. If the two networks’ errors are not perfectly correlated, the action that happens to look best by luck under $\theta$ won’t get the same lucky score under $\theta^-$. It’s a one-line change (Task 4 in the lab). It reduced overestimation and improved scores on many Atari games, and the lab uses it by default.

Dueling networks, prioritized replay, and more

• Dueling architecture (Wang et al., 2016). Split the head into a state value $V(s)$ and per-action advantages $A(s, a)$, and recombine them as $Q = V + \big(A - \text{mean}_a A\big)$. Many states don’t depend much on the action, so the shared $V$ learns from every update.
• Prioritized experience replay (Schaul et al., 2016). Sample transitions in proportion to $\lvert \delta \rvert^{\omega}$ (the paper writes α for this exponent), so the surprising ones get replayed more. Importance-sampling weights correct the bias that this non-uniform sampling introduces.
• Multi-step targets. Use $r_t + \gamma r_{t+1} + \dots + \gamma^{n-1} r_{t+n-1} + \gamma^n \max_{a'} Q(s_{t+n}, a')$, the n-step returns of Chapter 5. They bootstrap less, so information propagates faster.
• Distributional RL (C51, Bellemare et al., 2017). Learn the whole distribution of returns rather than only its mean.
• Noisy networks (Fortunato et al., 2018). Learnable noise in the weights replaces ε-greedy for exploration.
• Rainbow (Hessel et al., 2018). Combines all six (Double, prioritized, dueling, multi-step, distributional, noisy) and reports results far above any one of them alone on Atari. Its ablations found prioritized replay and multi-step returns to be among the most important pieces.

Where value-based methods run out

DQN-style methods are still a strong choice for discrete-action problems where data is expensive (replay reuses every sample many times). But they have limits that motivate the rest of Part II:

• Discrete actions only. Acting needs $\arg\max_a Q(s, a)$. With 18 actions that’s 18 numbers. With a continuous action (a torque) it’s an optimization problem at every step. Actor-critic methods such as DDPG and SAC learn a separate network to do that maximization; Chapter 10 describes SAC.
• Deterministic greedy policies. The greedy policy picks one action. In games and partially observed problems, the best policy is sometimes random (think rock–paper–scissors), and ε-greedy is a crude way to be random.
• No guarantees. As you’ve seen, the deadly triad is present by design. Training curves are often jumpy, and runs with different seeds can differ a lot. Your lab run will show this.
• Indirect. You learn values and derive the policy from them. A small change in Q can flip the argmax and change behavior abruptly.

The alternative is to parameterize the policy itself and push it uphill on expected return. That is the subject of Chapter 7, and it is the family that LLM training is built on.

Summary

• Tables don’t scale and don’t generalize. Replace them with a parametric $\hat V(s; w)$ or $Q(s, a; \theta)$ so that experience in one state updates similar states. Tables are the special case of linear features that are one-hot.
• Linear function approximation: $\hat V = w^\top \phi(s)$, gradient $\phi(s)$. The features decide how updates spread: wide features learn fast but blur detail; narrow features are precise but data-hungry.
• Semi-gradient TD updates $w \leftarrow w + \alpha \delta_t \nabla_w \hat V(s_t; w)$, treating the bootstrapped target as a constant label. It’s not the gradient of any objective, but on-policy linear TD provably converges to the TD fixed point (a Galerkin projection of the Bellman equation).
• The deadly triad is function approximation + bootstrapping + off-policy updates. Any two are fine; all three can diverge. The $w \to 2w$ example blows up geometrically, by a factor of $1 + \alpha(2\gamma - 1)$ per update.
• DQN = semi-gradient Q-learning with a neural network plus stabilizers: experience replay (decorrelate, reuse data), a target network (fixed regression targets for C steps, like approximate value iteration), the Huber loss (bounded gradients), and reward clipping (one scale across games).
• Double DQN removes most of the upward bias of $\max$ by choosing the action with the online network and scoring it with the target network. Dueling heads, prioritized replay, multi-step returns, distributional RL and noisy nets combine into Rainbow.
• Value-based methods need a max over actions and give deterministic policies, so they don’t suit continuous actions or LLMs. That motivates policy gradients.

Exercises

Exercise 6.1Tables are linear function approximationConcept●○○

(a) Show that semi-gradient TD(0) with one-hot features $\phi(s) = e_s$ (the $s$-th unit vector) is exactly the tabular TD(0) update from Chapter 5.

(b) Now use state aggregation: states are grouped, and $\phi(s) = e_{g(s)}$, where $g(s)$ is the group of $s$. Write out the update. Which values change after an update at $s$?

Solution

(a) With $\phi(s) = e_s$, $\hat V(s; w) = w^\top e_s = w_s$, so $w$ is the value table. The gradient is $\nabla_w \hat V(s_t; w) = e_{s_t}$. The update $w \leftarrow w + \alpha \delta_t e_{s_t}$ changes only coordinate $s_t$:

$$w_{s_t} \leftarrow w_{s_t} + \alpha \big( r_t + \gamma w_{s_{t+1}} - w_{s_t} \big),$$

which is tabular TD(0) with $V(s) = w_s$.

(b) $\hat V(s; w) = w_{g(s)}$, and the update is $w_{g(s_t)} \leftarrow w_{g(s_t)} + \alpha \big( r_t + \gamma w_{g(s_{t+1})} - w_{g(s_t)} \big)$. One weight changes, and with it the value of every state in the same group as $s_t$. Nothing outside the group changes. This is the “Bins” setting in the corridor demo: generalization within a bin, none across bins.

I've done this one

Exercise 6.2Interference by handPen & paper●○○

Continue the hat-feature example. After the first update you had $w = (0.1, 0.4)$ with $\phi(x) = (1 - x, x)$. Now you observe a return of 0 from state $x = 0.1$. Take one gradient step with $\alpha = 0.5$ toward that target.

(a) What are the new weights?

(b) What is $\hat V(0.8)$ now? It was 0.34. You never touched $x = 0.8$ in this step. Explain what happened in one sentence.

Solution

(a) $\phi(0.1) = (0.9, 0.1)$. Prediction: $\hat V(0.1) = 0.9 \times 0.1 + 0.1 \times 0.4 = 0.13$. Error: $0 - 0.13 = -0.13$. Update:

$$w \leftarrow (0.1, 0.4) + 0.5 \times (-0.13) \times (0.9, 0.1) = (0.1 - 0.0585,\; 0.4 - 0.0065) = (0.0415,\; 0.3935).$$

(b) $\hat V(0.8) = 0.2 \times 0.0415 + 0.8 \times 0.3935 = 0.0083 + 0.3148 = 0.3231$. It fell from 0.34 to about 0.32, because the two states share weights: lowering the value at $x = 0.1$ also lowered the line everywhere, a little. This is interference, the flip side of generalization. Here it’s mild and sensible. When features are poorly matched to the problem, an update in one region can undo learning in another. Catastrophic forgetting in neural networks is the extreme case.

I've done this one

Exercise 6.3Why treat the target as a constant?Pen & paper●●○

Consider one state $s$ with a random next state $s'$ and reward $r$. Define the TD error $\delta = r + \gamma \hat V(s'; w) - \hat V(s; w)$.

(a) Compute $-\nabla_w \tfrac12 \delta^2$ (the full gradient) and compare it with the semi-gradient update direction $\delta \nabla_w \hat V(s; w)$.

(b) Show that $\mathbb{E}[\delta^2] = \big(\mathbb{E}[\delta]\big)^2 + \text{Var}\big[r + \gamma \hat V(s'; w)\big]$, where the expectation and variance are over $(r, s')$ given $s$.

(c) Use (b) to explain why minimizing the sampled squared TD error (the residual-gradient method) can converge to the wrong values when transitions are stochastic, while the expected semi-gradient update is zero exactly when $\hat V(s) = \mathbb{E}[r + \gamma \hat V(s')]$.

Hint

In (b), $\hat V(s; w)$ is a constant given $s$; only $r + \gamma \hat V(s'; w)$ is random. Use $\mathbb{E}[X^2] = (\mathbb{E}X)^2 + \text{Var}X$.

Solution

(a) $\nabla_w \delta = \gamma \nabla_w \hat V(s'; w) - \nabla_w \hat V(s; w)$. Therefore

$$-\nabla_w \tfrac12 \delta^2 = -\delta\, \nabla_w \delta = \delta \big[ \nabla_w \hat V(s; w) - \gamma \nabla_w \hat V(s'; w) \big].$$

The semi-gradient keeps only $\delta \nabla_w \hat V(s; w)$. The dropped term, $-\gamma \delta \nabla_w \hat V(s'; w)$, would move the next state’s value to shrink the error, that is, change the target to agree with the prediction.

(b) Let $X = r + \gamma \hat V(s'; w)$, a random variable given $s$, and $c = \hat V(s; w)$, a constant. Then $\delta = X - c$ and

$$\mathbb{E}[\delta^2] = \mathbb{E}[(X - c)^2] = (\mathbb{E}X - c)^2 + \text{Var}X = (\mathbb{E}\delta)^2 + \text{Var}\big[r + \gamma \hat V(s'; w)\big].$$

(c) The quantity we care about is $(\mathbb{E}\delta)^2$: it is zero exactly when $\hat V(s)$ satisfies the Bellman equation $\hat V(s) = \mathbb{E}[r + \gamma \hat V(s')]$. The residual-gradient method minimizes $\mathbb{E}[\delta^2]$, which adds the variance term $\gamma^2 \text{Var}[\hat V(s')]$ (plus terms involving $r$). That term depends on $w$ through the next-state values, so the minimizer trades Bellman accuracy for making $\hat V$ flatter across possible next states. With deterministic transitions the variance term is constant and both agree; with stochastic transitions they don’t. Fixing this requires two independent samples of $s'$ from the same $s$ (the “double sampling” problem), which you usually can’t get from a single stream of experience.

The expected semi-gradient update is $\mathbb{E}[\delta] \nabla_w \hat V(s; w)$, because the gradient doesn’t depend on $s'$. It vanishes exactly when $\mathbb{E}[\delta] = 0$, the Bellman condition. In the linear case, the sum of these conditions over states, weighted by $\mu$, gives the TD fixed point $\mathbb{E}_\mu[\delta \phi(s)] = 0$.

I've done this one

Exercise 6.4Anatomy of the w → 2w divergencePen & paper●●○

Use the two-state example: $\hat V(A) = w$, $\hat V(B) = 2w$, A → B → end, all rewards 0.

(a) Off-policy (update only on A → B): show that $w_{k+1} = \big(1 + \alpha(2\gamma - 1)\big) w_k$. For which $\gamma$ does $w$ diverge, for any $\alpha > 0$?

(b) On-policy: each sweep updates on A → B and then on B → end. Find the per-sweep factor and show that it converges for $\alpha = 0.1$ and every $\gamma \in [0, 1]$.

(c) Compute the Derivation’s matrix $\mathbf{A}$ (here a $1 \times 1$ matrix, a number) in both cases. For a deterministic transition $s \to s'$ it is $\mathbf{A} = \sum_s \mu(s)\, \phi(s) \big(\phi(s) - \gamma\, \phi(s')\big)$, where $\mu(s)$ counts how often $s$ is updated per sweep: $\mu(A) = 1$, $\mu(B) = 0$ off-policy and $\mu(A) = \mu(B) = 1$ on-policy. Use $\phi(\text{end}) = 0$. Connect the sign of $\mathbf{A}$ to (a) and (b).

Hint

For (b), the B update is $w \leftarrow w + \alpha(0 - 2w)\cdot 2$. For (c), all rewards are 0, so $b = 0$ and the expected update per sweep is $\Delta w = -\alpha \mathbf{A} w$.

Solution

(a) The target for A is $0 + \gamma \hat V(B) = 2\gamma w$, the prediction is $w$, and the gradient is $\phi(A) = 1$. So $w \leftarrow w + \alpha(2\gamma w - w) = (1 + \alpha(2\gamma - 1)) w$. The factor exceeds 1 exactly when $2\gamma - 1 > 0$, so $w$ diverges for every $\alpha > 0$ when $\gamma > 1/2$ (and every $w_0 \neq 0$). At $\gamma = 1/2$ it stays put; below, it converges.

(b) The B update: target 0 (terminal), prediction $2w$, gradient 2, so $w \leftarrow w + \alpha(0 - 2w) \cdot 2 = (1 - 4\alpha) w$. The per-sweep factor is $f = (1 + \alpha(2\gamma - 1))(1 - 4\alpha)$. For $\alpha = 0.1$: $f = (0.9 + 0.2\gamma)(0.6)$, which ranges from $0.54$ (at $\gamma = 0$) to $0.66$ (at $\gamma = 1$). Always in $(0, 1)$, so $w \to 0$.

(c) Off-policy, only the A term: $\mathbf{A} = 1 \cdot 1 \cdot (1 - 2\gamma) = 1 - 2\gamma$. On-policy, add the B term $1 \cdot 2 \cdot (2 - \gamma \cdot 0) = 4$, so $\mathbf{A} = 5 - 2\gamma$. The expected dynamics are $w \leftarrow w - \alpha \mathbf{A} w = (1 - \alpha \mathbf{A}) w$. Positive $\mathbf{A}$ means the update pulls $w$ toward 0 (for small $\alpha$); negative $\mathbf{A}$ means it pushes away. Off-policy, $\mathbf{A} < 0$ exactly when $\gamma > 1/2$: indeed $1 - \alpha \mathbf{A} = 1 + \alpha(2\gamma - 1)$, the factor from (a). On-policy, $\mathbf{A} \ge 3 > 0$ for every $\gamma \le 1$, matching (b). (The sweep in (b) applies the two updates one after the other, so its factor differs from $1 - \alpha \mathbf{A}$ by a term of order $\alpha^2$; the sign story is the same.) This is the scalar version of the Derivation’s statement that on-policy weighting makes $\mathbf{A}$ positive definite.

I've done this one

Exercise 6.5Does a target network fix w → 2w?Pen & paper●●●

Add a target network to the off-policy two-state example: within a block, the target for A is $\gamma \cdot 2 w^-$ with $w^-$ frozen, and after $C$ updates you set $w^- \leftarrow w$.

(a) Show that after $C$ updates in a block starting from $w = w^-$,

$$w = (1-\alpha)^C w^- + \big[1 - (1-\alpha)^C\big]\, 2\gamma\, w^- .$$

(b) Deduce the per-block growth factor, and show that the iteration over blocks diverges when $\gamma > 1/2$ for any $C \ge 1$. What happens as $C \to \infty$?

(c) Interpret: what problem does the target network solve, and what problem does it not solve?

Hint

Within a block the update is $w \leftarrow (1 - \alpha) w + \alpha \cdot 2\gamma w^-$, a linear recursion with a constant input. Its fixed point is $2\gamma w^-$.

Solution

(a) Within a block, $w_{k+1} = (1-\alpha) w_k + \alpha\, 2\gamma w^-$. The fixed point is $w^\star = 2\gamma w^-$, and $w_{k+1} - w^\star = (1 - \alpha)(w_k - w^\star)$. So after $C$ steps from $w_0 = w^-$,

$$w_C = w^\star + (1-\alpha)^C (w^- - w^\star) = (1-\alpha)^C w^- + \big[1 - (1-\alpha)^C\big] 2\gamma w^- .$$

(b) Dividing by $w^-$, the per-block factor is $g = (1-\alpha)^C + \big[1 - (1-\alpha)^C\big] 2\gamma$, a weighted average of $1$ and $2\gamma$ with positive weights (for $0 < \alpha < 1$). If $\gamma > 1/2$, then $2\gamma > 1$ and $g > 1$: geometric growth from block to block. As $C \to \infty$, $(1-\alpha)^C \to 0$ and $g \to 2\gamma$. Each block fits its regression exactly, and you’re running value iteration with an expanding projected backup: $w^- \leftarrow 2\gamma w^-$.

(c) The target network removes the moving-target problem: within a block, the regression has fixed labels and converges (the inner recursion contracts at rate $1 - \alpha$). It doesn’t fix the projected Bellman backup being an expansion under an off-policy weighting, here $w^- \mapsto 2\gamma w^-$. Only changing the distribution of updates (on-policy), the features, or the use of bootstrapping removes that. You can watch the stepwise growth in the triad demo with the target network on.

I've done this one

Exercise 6.6Replay, correlation, and buffer sizeConcept●●○

(a) In CartPole, each step advances time by $\Delta t = 0.02$ s. Why are consecutive states $s_t$ and $s_{t+1}$ highly correlated? What goes wrong if each gradient step uses only the latest transition?

(b) Describe what DQN becomes with a replay buffer of capacity 1, and with a buffer so large that it never discards anything over a long run. Name one problem of each extreme.

(c) Replay makes the data more off-policy. Why does DQN tolerate this, and why would you need importance weights to do the same thing with SARSA or with policy-gradient methods?

Hint

For (b), think about how old the oldest transition is relative to the current policy, and about how often the rare useful transitions get sampled.

Solution

(a) The state changes by roughly $\Delta t$ times its rates of change per step, so $s_{t+1} \approx s_t$. Fifty consecutive transitions all describe nearly the same situation. Gradient steps on them in sequence fit $Q$ to that one region and overwrite what the network knew about other regions (catastrophic forgetting). The effective step is also many correlated steps in the same direction, which acts like a much larger learning rate and destabilizes training.

(b) Capacity 1: each update uses the latest transition, so you get naive online deep Q-learning: maximally correlated, no reuse, and the training distribution jumps around whenever the policy changes. Infinite capacity: after a long run, most of the buffer comes from early, poor policies (for example, the random-action phase). Uniform sampling then spends most updates on states the current policy never visits and dilutes the recent, relevant data. Memory also becomes a problem. In practice $N$ is chosen to hold many episodes but to turn over a few times during training. In the lab, --no-replay (buffer = 128) still learns somewhat, but more erratically.

(c) Q-learning’s target $r + \gamma \max_{a'} Q(s', a')$ evaluates the greedy policy using only $(s, a, r, s')$, so it’s a valid sample of the Bellman optimality backup for $(s, a)$ whichever policy chose $a$. The behavior policy affects only which $(s, a)$ pairs get updated, the weighting $\mu$, not the correctness of each target. That’s exactly the off-policy leg of the triad, which is why it’s not entirely free. SARSA’s target uses $a'$ drawn from the policy being evaluated; an old $a'$ came from an old policy, so the target estimates the wrong policy’s value unless you reweight by $\pi(a'|s')/b(a'|s')$. Policy-gradient estimators are expectations under the current policy, so they need the same kind of ratio $\rho_t(\theta)$ (Chapter 9).

I've done this one

Exercise 6.7A DQN loss by hand, with Double DQNPen & paper●○○

Use the Q-tables and minibatch from the worked minibatch section ($\gamma = 0.5$). Recompute the targets, errors, Huber losses and mean loss with Double DQN targets: choose $a^\star = \arg\max_{a'} Q(s', a'; \theta)$ with the online table, then evaluate $Q(s', a^\star; \theta^-)$ with the target table. Compare with the standard DQN loss of $8.045 / 3 \approx 2.68$.

Solution

• Transition 1: $s' = 1$. The online row is $(5, 1)$, so $a^\star = a_0$; the target table gives $Q(1, a_0; \theta^-) = 1$. $y_1 = 1 + 0.5 \times 1 = 1.5$.
• Transition 2: $s' = 2$. The online row is $(0, 4)$, so $a^\star = a_1$; the target gives $Q(2, a_1; \theta^-) = -1$. $y_2 = 0 + 0.5 \times (-1) = -0.5$.
• Transition 3: terminal, $y_3 = -1$.

Predictions are unchanged: $2.2, 5, 4$. Errors: $0.7$, $5.5$, $5$. Huber: $0.5 \times 0.49 = 0.245$, $5.5 - 0.5 = 5.0$, $5 - 0.5 = 4.5$. Mean: $9.745/3 \approx 3.25$.

The Double targets are lower (1.5 vs 2.5, and −0.5 vs 1). The standard max picked the target network’s largest entry in each row; Double DQN asks the target network about the action the online network likes, which here is not the target network’s favorite. When the two disagree, this removes the upward bias of the max. The lab’s test_task4_loss_value checks both numbers.

I've done this one

Exercise 6.8How optimistic is the max?Pen & paper●●○

All $n$ actions in state $s'$ have true value 0. Your estimates $\hat Q_1, \dots, \hat Q_n$ are independent, each $+1$ or $-1$ with probability $1/2$.

(a) Compute $\mathbb{E}[\max_i \hat Q_i]$ for general $n$. What is it for $n = 2$ and $n = 18$ (the full Atari action set)?

(b) Now suppose you have a second, independent set of estimates $\tilde Q_i$ with the same distribution. Pick $i^\star = \arg\max_i \hat Q_i$ (break ties uniformly) and report $\tilde Q_{i^\star}$. Show this is unbiased.

(c) The bias in (a) enters the target $r + \gamma \max_{a'} Q(s', a')$. Explain in two sentences why bootstrapping makes the problem worse than a single biased target.

Hint

The max is $-1$ only if every estimate is $-1$.

Solution

(a) $\max_i \hat Q_i = -1$ only if all $n$ estimates are $-1$, which has probability $2^{-n}$; otherwise it is $+1$. So

$$\mathbb{E}\big[\max_i \hat Q_i\big] = (1 - 2^{-n}) \cdot 1 + 2^{-n} \cdot (-1) = 1 - 2^{1-n}.$$

For $n = 2$: $1 - 1/2 = 0.5$. For $n = 18$: $1 - 2^{-17} \approx 0.99999$. With many actions, the max is essentially always the most optimistic error.

(b) $i^\star$ is a function of $\hat Q$ only, and $\tilde Q$ is independent of $\hat Q$. So $\mathbb{E}[\tilde Q_{i^\star}] = \mathbb{E}\big[\mathbb{E}[\tilde Q_{i^\star} \mid \hat Q]\big] = \mathbb{E}[0] = 0$, since each $\tilde Q_i$ has mean 0 whatever index is chosen. Selection and evaluation use different noise, so luck in one doesn’t carry into the other. Double DQN approximates this with $\theta$ and $\theta^-$, which are not fully independent, so it reduces the bias rather than eliminating it.

(c) The overestimated target at $s'$ raises $Q(s, a)$; when $s$ itself is a next state for an earlier state, that inflated value is again maxed over (picking up fresh optimistic noise) and copied backward. Bias accumulates along chains of states, discounted by $\gamma$ at each step, and with function approximation the inflated values also leak into neighboring states.

I've done this one

Exercise 6.9Explore both demosExplore the demo●●○

Corridor demo.

(a) Choose Hats with 2 features (a straight line). Tap a target of 1.0 at $x = 0.8$. Which states moved the most, and which the least? Now press Play. Why does the learned line never match the true curve, however long you train?

(b) Train Bins with 12 features, then Bins with 40 features (Reset between runs; α = 0.2). Which has lower RMS error after about 100 episodes, and which after about 500? Explain the crossover in terms of generalization and resolution. Then try RBFs with σ = 0.06 and σ = 0.25: why does the wide one plateau at a higher error?

(c) Set α to 1.0 and press Play. Then set α to 0.05. Describe the curve’s behavior in each case and connect it to the “constant step size” discussion of Chapter 2.

Triad demo.

(d) With all three ingredients on and α = 0.1, find the smallest γ (to two decimals) for which the run diverges. Does your answer depend on α? Check against Exercise 6.4.

(e) Turn the target network on with γ = 0.9. Read off roughly how much $\lvert V(A) \rvert$ grows per 25-sweep block and compare with Exercise 6.5.

Hint

For (b), there is no single best resolution: it depends on how much data you have. For (c), recall that a constant step size gives an exponentially weighted average of recent targets.

Solution

(a) With $\phi(x) = (1 - x, x)$, a tap at $x = 0.8$ changes $w$ in direction $(0.2, 0.8)$. The right end moves most, the left end least, and every point moves by an amount that varies linearly with $x$. The true value is strongly curved (flat and negative, a dip at the puddle, then a sharp rise), and a straight line can’t represent it. TD converges to the TD fixed point within the family of lines; the remaining error is approximation error, not lack of training.

(b) With the demo’s seed, 12 bins are ahead early (RMS about 0.10 vs 0.22 after 100 episodes): each bin covers a wide stretch, so it collects data quickly and every update teaches a whole region. By about 300 episodes the 40-bin table has caught up and then stays ahead (about 0.06 vs 0.08 at 500 episodes): its bins are narrow enough to follow the sharp rise after the puddle, which a 12-step staircase can’t. Coarse features have low variance and high approximation error; fine features the reverse. Which is better depends on how much data you have.

The wide RBF (σ = 0.25) blurs the value over a width comparable to the puddle, so it can’t represent the sharp rise no matter how long you train; it plateaus near RMS 0.1 while σ = 0.06 gets to about 0.05. Exact numbers wobble because of the constant step size.

(c) With α = 1 each TD update closes a large part of the gap toward a single noisy target, so the curve jumps around and never settles (with the demo’s seed the RMS error keeps fluctuating, anywhere from about 0.04 to 0.4). With α = 0.05 the curve moves slowly and smoothly: it’s far off after 50 episodes (about 0.3) but reaches about 0.03 by 1,000. A constant α makes the estimate an exponentially weighted average of recent targets with effective memory about $1/\alpha$ updates: large α means fast tracking but noisy, small α means slow but accurate. That’s the same trade-off as in nonstationary bandits.

(d) γ = 0.51. The threshold is exactly γ = 1/2: at 0.50, $w$ stays at 1 (the factor is exactly 1); at 0.51 it grows slowly, by a factor $1.002$ per sweep. It doesn’t depend on α, because the factor $1 + \alpha(2\gamma - 1)$ exceeds 1 exactly when $\gamma > 1/2$. α only changes the speed.

(e) Within each block $\lvert V(A) \rvert$ approaches $2\gamma w^-$; with α = 0.1 and C = 25, $(0.9)^{25} \approx 0.07$, so the per-block factor is $0.07 + 0.93 \times 1.8 \approx 1.74$. You see a staircase rising about 1.74× per block, which is slower than without a target network ($1.08^{25} \approx 6.8$ per 25 sweeps) but still divergent.

I've done this one

Exercise 6.10Build DQN (the coding lab)Code●●○

In exercises/06-dqn/dqn.py, implement the five tasks in order, running python -m pytest -q -k taskN after each:

1. linear_td0_update: semi-gradient TD(0) for linear features. The tests include the worked examples from this chapter and the $w \to 2w$ divergence.
2. ReplayBuffer.push and ReplayBuffer.sample: a circular buffer.
3. QNetwork, epsilon_by_step, select_action: the acting side.
4. compute_td_targets (standard and Double DQN) and dqn_loss (Huber). The tests use the worked minibatch from this chapter and check that no gradient flows through the target.
5. update_target (hard and soft) and train_step.

Then run python run.py. In about a minute it trains on CartPole and saves dqn_cartpole.png. Finally, break it on purpose: python run.py --compare trains full DQN, DQN without a target network, and DQN without replay, all from the same seed. Describe what you see in each panel, in particular the loss curve of the run without a target network.

Hint

The two easiest bugs to make: forgetting (1 - done) in the target, and computing the target with gradients enabled (wrap it in torch.no_grad()). For dqn_loss, pick out $Q(s_i, a_i)$ with q_all.gather(1, actions.unsqueeze(1)).squeeze(1).

Solution

The reference implementation is in exercises/06-dqn/solutions/dqn.py. The key lines:

• Task 1: delta = r + gamma * (0 if done else w @ phi_next) - w @ phi, then return w + alpha * delta * phi. Gradient of $w^\top\phi$ is $\phi$, and the target is a plain number.
• Task 2: write into slot idx, then idx = (idx + 1) % capacity and size = min(size + 1, capacity). Sample indices with rng.integers(0, size, batch_size), never past size.
• Task 4: inside torch.no_grad(), next_v = target_net(next_obs).max(1).values (or, for Double DQN, argmax from the online net and gather from the target net), then y = r + gamma * (1 - done) * next_v. The loss is F.smooth_l1_loss(q_sa, y). The no_grad is the code version of “semi-gradient”: the test that uses the same network as online and target checks that the gradient matches $\text{clip}(e, -1, 1)\,\nabla Q(s,a)/B$ exactly.
• Task 5: p_t.mul_(1 - tau).add_(tau * p) under no_grad; train_step is sample, loss, zero_grad, backward, clip_grad_norm_, step.

What you should see. Full DQN on seed 0 reaches a final greedy return around 430 out of 500. The evaluation curve is jumpy: drops from near 500 to about 150 and back are normal for DQN. Note that the loss rises early in training and then stays roughly flat. The DQN loss is not a progress meter: as Q-values grow toward their true scale (about 100 for $\gamma = 0.99$) and the targets move, the regression errors grow too. Without the target network, the Q-values diverge: the loss climbs to around $10^8$ and the agent never balances the pole for more than about 10 steps. That’s the deadly triad in a real network. Without replay (buffer of 128), the agent learns something, but less reliably: on seed 0 it ends around 210 instead of 430. Your numbers will differ with other seeds; the ranking is what matters.

I've done this one

Further reading

• Sutton & Barto (2018), Reinforcement Learning: An Introduction, ch. 9–11. Chapter 9 covers linear function approximation and semi-gradient TD (including the TD fixed-point bound); chapter 11 covers the deadly triad, the $w \to 2w$ example and Baird’s counterexample. The best next step after this chapter.
• Mnih et al. (2015), Human-level control through deep reinforcement learning. The Nature DQN paper. Read the Methods section for every detail, and the extended data tables for the hyperparameters and the replay/target-network ablation.
• Mnih et al. (2013), Playing Atari with Deep Reinforcement Learning. The short workshop paper that started it: seven games, replay, no separate target network yet.
• van Hasselt, Guez & Silver (2016), Deep Reinforcement Learning with Double Q-learning. Clear explanation of overestimation and the one-line fix.
• Hessel et al. (2018), Rainbow: Combining Improvements in Deep Reinforcement Learning. A tour of six DQN extensions with an ablation of each; also a good reading list.
• van Hasselt et al. (2018), Deep Reinforcement Learning and the Deadly Triad. An empirical study of when deep Q-learning actually diverges, and which ingredients matter.
• Tsitsiklis & Van Roy (1997), An analysis of temporal-difference learning with function approximation. The convergence proof for on-policy linear TD, with examples of off-policy and nonlinear divergence. For when you want the full mathematics.
• Wang et al. (2016), Dueling Network Architectures for Deep Reinforcement Learning, and Schaul et al. (2016), Prioritized Experience Replay. Two of Rainbow’s ingredients, each short and readable.

Next, you’ll stop learning values and start optimizing the policy directly: Chapter 7, Policy gradients and REINFORCE.