Volume 1 followed the policy-learning family: algorithms that directly learn how to act in each state. This volume follows the other great lineage — value learning: estimate what each action is worth in each state, and act by looking up the best estimate. The format is the same: every algorithm is a patch for the previous one's most painful failure, from a lookup table to Rainbow — an algorithm that is, openly, just six patches combined.
The value-learning premise: don't parameterize behavior at all. Estimate the value of every action, and derive behavior from the estimates.
Volume 1 covered policy learning: algorithms that directly learn how to act in each state, as a policy \(\pi_\theta(a\mid s)\). Value learning makes the opposite bet. Suppose that, for every state, you could learn the expected return of taking each action and behaving well afterward — then acting is trivial: look up the best action and take it. That long-term return of action \(a\) in state \(s\) is the action-value function \(Q(s,a)\). A scorecard for choices, if you like.
The rest of this volume is one long attempt to learn that function well: first with a table, then with a neural network, then with six increasingly targeted patches.
Before neural networks: one table, one update rule, and a convergence guarantee.
Imagine a 5×7 gridworld — 35 states the agent can be in — where the agent can move in any of four directions: four actions per state. Following the motivation above, what you need to learn is a 35 × 4 table of \(Q^*(s,a)\) values, so you can look up the best action in every state. Which immediately raises a fair question:
How can you learn scores about the future without waiting for the future? This is where the Bellman equation comes in — the same move that powered all of Volume 1's bootstrapping. Richard Bellman noticed that correct action-values have to be self-consistent: the value of doing \(a\) now must equal the reward you get immediately, plus — discounted by \(\gamma\) — everything you'll collect if you behave optimally afterward, which here means always picking the best action from then on based on the value function, no second-guessing.
$$Q^*(s,a)\;=\;\mathbb{E}\big[\,r+\gamma \max_{a'} Q^*(s',a')\,\big]$$
That self-consistency is the whole trick: you can check a score without seeing the future. One step of experience, plus the scorecard itself, is enough.
Q-learning (Watkins, 1989) turns that consistency check into an algorithm: maintain a table of Q-values, act in the world, and after every step nudge the entry you used toward the one-step target:
$$Q(s,a)\;\leftarrow\;Q(s,a)+\alpha\,\underbrace{\big[\,r+\gamma \max_{a'}Q(s',a')-Q(s,a)\,\big]}_{\delta,\ \text{the surprise}}$$
The bracket is the temporal-difference (TD) error \(\delta\): how wrong your estimate just proved to be. Positive surprise, nudge the score up. Negative, nudge it down. Reward information ripples backward through the table, one bootstrap at a time — watch it happen:
Two properties of this loop matter later. First, with a table and enough exploration, it provably converges to \(Q^*\) (I'll let you look up the proof yourself). Second — remember this one — look at the \(\max\) in the target: Q-learning learns the value of the greedy policy no matter how sloppily you behave while collecting experience. It is off-policy: old experience, exploratory experience, even someone else's experience — all of it remains valid training data.
So are we done?
A table needs one row per state — fine for gridworlds, hopeless for anything practical. An Atari screen has more possible states than there are atoms in the universe, and a table can't generalize: two frames differing by one pixel are total strangers to it. We need a function that generalizes, not a table that memorizes. And a table assumes you can even enumerate its rows: with continuous states (a robot arm's joint angles, a car's speed) or continuous actions (how hard to press the accelerator), there is no finite table to write down at all.
Swap the table for a network and training explodes. Two structural fixes tamed it — and started the deep RL era.
The obvious move: replace the table with a neural network \(Q_\theta(s,a)\) that maps raw pixels to scores, and train it by regression toward the same one-step targets as the tabular approach. People tried versions of this for years, and it kept failing the same way: training diverges — values blow up or collapse. Theorists even named the failure: the deadly triad of function approximation, bootstrapping, and off-policy learning. Concretely, two things go wrong.
1. The data is correlated. An agent's experience arrives as a stream, and consecutive frames are nearly identical. Stochastic gradient descent — the workhorse that trains neural networks — assumes shuffled, roughly independent samples (recall how you shuffle the training images when training an image classifier). Feed it an hour of highly correlated frames and the network overfits whatever happened in the last minute while quietly forgetting everything else.
2. You're regressing toward a moving target. Look at the label: \(r+\gamma\max_{a'}Q_\theta(s',a')\). The network being trained is inside its own target, so every gradient step moves the target itself. Imagine training a classifier to tell cats from dogs, except every update also changes the labels on your training images.
DQN (Mnih et al., 2013; the 2015 Nature version) tamed both these issues with two structural fixes:
Fix 1 — experience replay. Don't train on the stream. Act in the environment — move around the gridworld, play the Atari game, whatever the task is — and store every transition \((s,a,r,s')\) in a big buffer; train on random minibatches drawn from it. Randomizing across a million timesteps breaks the correlation, and every experience gets reused many times. This brings deep RL training much closer to ordinary supervised learning on a shuffled dataset.
How does the agent act while it fills the buffer? In the original paper: ε-greedily with respect to its current network — mostly its own best guess, occasionally a random action — with ε annealed from 1.0 down to 0.1 over training. The freedom off-policy learning buys is not that behavior doesn't matter (you still need to explore); it's that the update stays valid no matter which policy generated the data. Old memories came from an older, worse policy, and Q-learning doesn't care. Compare Volume 1, where the on-policy family's data expired with every update: replay is precisely the trick they couldn't use — a payoff of the off-policy property from Part 2.
Fix 2 — the target network. Keep a frozen copy of the network, \(\theta^-\), and compute the labels with it. Sync the copy every few thousand steps. Now you're regressing toward a fixed target that only jumps periodically:
$$L(\theta)\;=\;\mathbb{E}\Big[\big(\,r+\gamma \max_{a'} Q_{\theta^-}(s',a')-Q_\theta(s,a)\,\big)^2\Big]$$
With these two fixes, one architecture learned 49 different Atari games from raw pixels — same network, same hyperparameters, many games at superhuman level.
That 2015 result is why deep RL exists as a field.
But the value estimates a trained DQN reports have a problem: they are systematically inflated. Think about where its training labels come from: the target network's own imperfect Q-estimates — and, crucially, a \(\max\) over them. If any action's value happens to be overestimated, even slightly, the max picks that one, and its too-high number becomes the label the network is regressed toward. Optimism isn't averaged out; it's selected for, action by action, update by update.
The max in DQN's target doesn't just read the noisy estimates — it systematically selects the most inflated one and trains on it. How bad is that in practice, and what do you do about it?
A max over imperfect estimates is not an estimate of the max — and bootstrapping compounds the error.
A network's Q-estimates always carry some error — it has limited capacity, it generalizes from similar states, and it has only ever seen finite data. So at any state, some actions' estimates sit a little above their true values and some a little below. And the \(\max\) is not neutral about those errors: it never picks an action whose estimate is accidentally low, and it eagerly picks the one whose estimate is accidentally high. Taking \(\max_{a'}Q(s',a')\) doesn't select the best action — it selects the most overestimated one. Statisticians call this the winner's curse; in RL it's known as maximization bias.
In Q-learning it's a feedback loop: today's inflated max becomes tomorrow's regression label, which inflates other estimates, whose maxes inflate the next labels. Optimism compounds through the bootstrap chain.
Double DQN (van Hasselt et al., 2015) attacks the bias at its source: never let the same errors both nominate and score — where nominating means picking which action looks best (the argmax), and scoring means supplying that action's value for the label. Use one network to nominate, and a different network to score. DQN conveniently already has two networks lying around — online and target — so split the roles: the online network chooses, the target network evaluates.
Why does that kill the bias? The two networks are snapshots from different points in training, so their errors differ. The online network's most overestimated action is just an ordinary action to the target network — the odds that both networks independently overestimate the same action are low, so the value that actually enters the label is roughly honest. Two judges rarely make the same mistake.
And doesn't putting \(Q_\theta\) back in the target reintroduce the moving-target problem from Part 3? Barely — look at what moves. The online network now only chooses an index (which action); the number still comes from the frozen target network. A target whose value occasionally switches between actions is far gentler than one whose values shift under every gradient step, and in practice stability is unaffected. Seen that way, Double DQN changes nothing about what is learned or how the agent behaves — it only changes which action's value gets read off inside the label.
Side by side — one symbol changes, namely who does the choosing:
$$\text{DQN target:}\qquad r+\gamma\,Q_{\theta^-}\!\big(s',\;\arg\max_{a'}\,\textcolor{#ce4747}{Q_{\theta^-}}(s',a')\big)$$
$$\text{Double DQN target:}\qquad r+\gamma\,Q_{\theta^-}\!\big(s',\;\arg\max_{a'}\,\textcolor{#2b50e0}{Q_{\theta}}(s',a')\big)$$
It is close to a one-line code change, it costs nothing, and it makes the value estimates measurably more accurate — and the play measurably better.
The estimates are honest now, but the machine is still wasteful in three separate ways. One: it replays every memory equally often, whether or not it has anything left to teach. Two: it relearns "this situation is good" separately for every action. Three: reward information crawls backward one link per update. Three wastes, three patches — and keep count of the patches, because they are about to matter all at once.
Double DQN fixed what the machine believes. The next five patches fix how it spends its effort — one station of the loop at a time.
Every algorithm from here on lives inside the same loop, run millions of times: act in the world, store the transition, sample a minibatch, predict values, build the target, update. None of the coming patches changes the loop — each rebuilds exactly one station of it, and that independence is what will let the finale turn them all on at once. Two stations are already rebuilt: DQN patched storage and the target, and Double DQN re-patched the target. Here is the machine as it stands — the dim stations are where the waste lives:
So far, every \((s,a,r,s')\) is sampled uniformly from the buffer. Uniform replay treats each transition identically, but most of an agent's experience has nothing left to teach — the useful gradient lives in the rare moments where the value estimate was badly wrong. It's the difference between rereading the whole textbook front to back and drilling the flashcards you keep getting wrong. Conveniently, Q-learning already computes "how wrong was I" on every single step: the TD error \(\delta\). So sample in proportion to it. Prioritized Experience Replay (Schaul et al., 2015) replays transitions with probability proportional to their surprise, spending updates where predictions failed. (Non-uniform sampling skews the statistics, so each sample carries a small importance weight to keep the math honest.)
Follow one sampled memory to the next station — what does the network actually do with it?
Watch plain DQN fail at something that should be easy. The agent discovers a lucrative state it has only ever tried one action in — it always happened to go left there. It has learned that \(Q(s,\text{left})\) is high… and it believes nothing about the other actions in that state. That should strike you as wasteful: most of that value plainly belongs to the state — being there is what's good — not to the particular choice of going left. But a plain Q-network has no way to say so. Each action's value is a separate output, so "this situation is good" must be relearned separately for every action, from experiences where that specific action was tried.
The waste is structural. \(Q(s,a)\) entangles two different quantities: how good the situation is regardless of what you do — the state value \(V(s)\) from Volume 1 — and how much your particular choice adds or subtracts on top, the advantage \(A(s,a)\). And in most states the second part is tiny: cruising an empty highway, every reasonable action leads to roughly the same future, so all the Q-values are one big shared number plus small differences. Only occasionally — a car swerving into your lane — does the choice dominate.
The dueling architecture (Wang et al., 2015) builds that decomposition into the network itself: one stream estimates \(V(s)\), another estimates \(A(s,a)\), and they recombine into \(Q = V + A\). Now the failure above disappears: the single left-visit raises \(V(s)\), so every action's estimate in that state starts out sensible, and only the small differences remain to be learned — the shared part is learned once, not once per action. (The advantage stream is centered so the two streams can't trade off against each other.) In the paper's Atari saliency maps you can watch the division of labor: the V stream stares at the horizon, and the A stream only wakes up when other cars get close.
The next waste hides in the target itself: how far each update's information travels.
So far, every training sample has been a single step — one \((s,a,r,s')\) tuple — so the target contains one real reward plus a bootstrapped guess about everything after. That means reward information moves exactly one link backward per update: the state before the goal learns first, then the state before that, and so on down a long corridor. The fix: store and sample short snippets of \(n\) consecutive steps instead, and build the target from \(n\) real rewards before handing off to the bootstrap:
$$r_1+\gamma r_2+\cdots+\gamma^{\,n-1} r_n+\gamma^{\,n}\max_{a'}Q(s_{t+n},a')$$
Now each update moves information \(n\) links at once. The price is variance: more real rewards in the target means more randomness from the environment leaking in. If this dial sounds familiar, it should — it's Volume 1's GAE trade-off, living in the value family:
Three stations in, two red ones left — and they hide the two deepest assumptions in the machine: that a value is a single number, and that exploring means flipping a coin.
Put yourself in one specific moment of Pac-Man. The agent is one tile from a power pellet, and a ghost is closing in from the other side. Consider the action go for the pellet. Two futures genuinely exist: roughly half the time the ghost arrives first and the episode ends — return around 0 — and the other half, the agent grabs the pellet, the ghost turns blue, and a feast follows — return around 20. Every algorithm in this volume compresses that moment into a single number, the expected return: 10. But 10 is a fiction — no actual future is worth 10. Worse, a completely different action with a guaranteed return of 10 — say, safely hoovering dots in a quiet corner — receives exactly the same score. To a mean-predicting network, a coin flip between disaster and triumph and a sure thing are indistinguishable.
C51 (Bellemare et al., 2017) stops compressing. For each action, the network outputs a full histogram of possible returns — concretely, probabilities over 51 fixed return values ("atoms") spanning the value range. The pellet gamble now reads as what it is: half the mass near 0, half near 20. The safe corner reads as one spike at 10. Different situations, finally different predictions. (Why 51? Nothing sacred — a histogram needs bins, 51 worked well empirically, and the name stuck: Categorical, 51 atoms.)
Training keeps the same Bellman logic, just applied to whole histograms: shift and shrink the next state's predicted histogram by the reward and \(\gamma\), snap it onto the 51 bins, and train the network to match that target with a cross-entropy loss — value learning becomes, in effect, a 51-class classification problem. The projection details are the heart of the original paper (Bellemare, Dabney & Munos, 2017, A Distributional Perspective on Reinforcement Learning), worth a read.
To be precise about what changes and what doesn't: acting doesn't change — compute each action's mean from its histogram, take the argmax. What changes is the learning problem: the output per action (51 probabilities instead of one number), the target (a histogram instead of a scalar), and the loss (cross-entropy instead of squared error). And why does that help if decisions still use the mean? Because matching a whole shape forces the network to build internal features that can tell the pellet gamble apart from the safe corner — features a mean-only network has no reason to learn, since both actions score 10. Better features generalize better, and the means computed on top of them come out more accurate and more stable. (The precise theory of why this works so well is still being untangled; the effect itself is robust.)
One station left: acting.
Watch ε-greedy exploration — act greedily, except with probability ε take a random action — fail in both directions at once. In a state the agent has mastered, it still lurches at random ε of the time, throwing away reward it knows how to collect. In a state it has never understood, it explores no harder than anywhere else. The dial is state-blind and hand-annealed, bolted to the outside of the agent. Noisy Nets (Fortunato et al., 2017) move exploration inside: replace some weights with learned noise distributions, so the network's own uncertainty drives exploration — strong where uncertainty remains, fading where confidence is earned, per state, for free.
Five patches, five papers — each rebuilt one station of the loop, and each was only ever evaluated on its own. What nobody had measured: the machine with every station switched on at once.
The least original, most effective algorithm in the family.
Every station is green. Rainbow (Hessel et al., 2017) asks the obvious question nobody had bothered to answer rigorously: these six patches — double, PER, dueling, multi-step, distributional, noisy — were all developed independently on top of DQN. What happens if you turn them all on at once?
They stack. Rainbow beat every individual variant on the Atari benchmark, by a wide margin. And the ablations — unplug one station at a time and measure the damage — double as a summary of this whole tutorial:
Notice what Rainbow is. It contains no new idea whatsoever — and that's precisely the point. Nobody invented Rainbow from scratch, and nobody could have: it is six answers to six specific failures, discovered one painful problem at a time over four years. The name isn't decoration. It's an admission.
Same lesson as Volume 1, from the other family: none of these algorithms fell from the sky. If you remember the problem each was born to solve, you can re-derive the shape of the fix.
Where to go from here: this family's superpower — act by argmax — is also its ceiling. When actions are continuous (motor torques, steering angles), there is no menu to take a max over. Solving that requires marrying the two family trees: learn an actor to perform the argmax the critic can't compute. That lineage — DDPG → TD3 → SAC — is Volume 3 material. Meanwhile, this family's inventions never left: replay buffers, target networks, and distributional heads are standard parts in agents far beyond Atari. Missed Volume 1? The policy lineage (REINFORCE → PPO → GRPO) is here.