Value-Based Deep RL: From Q-Tables to DQN#
The thread continues from Q-learning: we had an algorithm that learns optimal behavior from experience alone — and a table that cannot survive contact with a real state space.
The substitution, and why it isn’t free#
Replace the table with a network: $Q_\theta(s, a)$, trained by SGD on the squared TD error,
$$ \mathcal{L}(\theta) = \Big( \underbrace{r + \gamma \max_{a'} Q_\theta(s', a')}_{\text{target (no gradient)}} - \; Q_\theta(s, a) \Big)^2 . $$For a tabular parameterization this SGD step is classical Q-learning, symbol for symbol (the correspondence is made exact in the fitted-Q deep dive). So it is tempting to conclude that nothing changes with a network. Two things change, and each one can kill the algorithm:
- The target moves. Every gradient step changes $\theta$, which changes the target $r + \gamma \max_{a'} Q_\theta(s',a')$ that defines the loss. We are regressing on a label that our own regression keeps rewriting. Tables localize this feedback (updating one cell barely disturbs others); a network generalizes, so every update perturbs the targets everywhere.
- The data is sequentially correlated. Consecutive transitions in an episode are nearly identical, and the distribution of visited states shifts as the policy improves, which is precisely the non-i.i.d. regime SGD’s assumptions exclude.
The deadly triad. Bootstrapping + function approximation + off-policy data — any two are fine, all three together can make the value estimates diverge, not merely converge slowly. This is not a hypothetical: simple linear counterexamples (Baird, 1995) blow up monotonically. Everything in this sub-section is engineering to live safely inside the triad.
DQN: two problems, two fixes#
DQN (Mnih et al., 2013/2015) is Q-learning plus exactly one countermeasure per problem above:
| Problem | Fix | Mechanism |
|---|---|---|
| Correlated, shifting data | Replay buffer | Store transitions $(s,a,r,s')$; train on random minibatches, which breaks temporal correlation and reuses data |
| Moving target | Target network | Compute targets with a frozen copy $\theta^-$, refreshed every $C$ steps |
Both fixes have a clean interpretation in the fitted-Q picture: the target network means partially solving each regression before refreshing the target (batch FQI solves it fully; online Q-learning refreshes every step; DQN sits between), and the replay buffer is the “batch.” Note the quiet dependency: reusing old transitions is only legitimate because Q-learning is off-policy — the $\max$ backup doesn’t care which policy collected the data. An on-policy method could not use a replay buffer at all; hold that thought for the policy-based page.
The payoff in 2015: one architecture and one hyperparameter set, superhuman on dozens of Atari games from raw pixels — the result that started deep RL as a field.
In code, the loss is three lines, and the two fixes are visible as buffer.sample()
and detach()/target_net:
s, a, r, s2, done = buffer.sample(batch_size) # fix 1: replay
with torch.no_grad(): # fix 2: frozen target
target = r + gamma * (1 - done) * target_net(s2).max(dim=1).values
loss = F.mse_loss(q_net(s).gather(1, a), target)The refinement lineage: each fix names a flaw#
Each successor is best remembered as a one-line diagnosis of what DQN still gets wrong:
- Double DQN — the $\max$ over noisy estimates selects noise upward, so values are systematically overestimated (we met this optimizer’s curse twice already: in the gridworld corner and in the fitted-Q discussion). Fix: decouple selection from evaluation, $\;r + \gamma\, Q_{\theta^-}\!\big(s', \arg\max_{a'} Q_\theta(s', a')\big)$.
- Dueling networks — in many states the choice of action barely matters, but plain DQN must learn $Q$ from scratch per action. Fix: decompose $Q(s,a) = V(s) + A(s,a)$ so the shared state-value is learned once.
- Prioritized replay — uniform sampling wastes gradient steps on transitions the network already predicts well. Fix: sample proportionally to TD error (with importance weights to stay unbiased).
- Rainbow (2017) — all of the above plus n-step returns, distributional RL, and noisy exploration, ablated carefully; the standing lesson is that the improvements are largely complementary.
Deep dive: distributional RL in three paragraphs
Everything above learns the mean of the return. Distributional RL (C51, QR-DQN) learns the full return distribution $Z(s,a)$ with $Q(s,a) = \mathbb{E}[Z(s,a)]$, via a distributional Bellman equation $Z(s,a) \stackrel{D}{=} r + \gamma Z(s', a')$.
Why bother, if actions are still chosen by the mean? Empirically it is one of the largest single gains inside Rainbow. The leading explanation is representational: predicting a distribution is a richer auxiliary task that shapes better features, and it interacts well with nonstationarity. The theory is subtle — the distributional operator is a contraction in the Wasserstein metric but not in KL, which drove the design of the quantile-regression variants.
For a statistics audience this is familiar territory: it is the move from regression to conditional-quantile / distributional regression, with the same payoffs (robustness, risk-sensitivity — a CVaR-style policy needs the tail, not the mean) and the same costs.
When to reach for value-based methods#
Choose value-based when: actions are discrete and not too many; sample efficiency matters (off-policy replay reuses every transition); and a deterministic greedy policy is acceptable.
Look elsewhere when: actions are continuous or combinatorially structured — $\arg\max_a Q_\theta(s,a)$ is itself an optimization problem you cannot afford per step. That failure is not a detail; it is the opening argument of the next page, where the policy becomes the thing we parameterize.
One more forward pointer: the value-learning machinery of this page does not retire when we move on — it returns inside policy methods as the critic, doing exactly the TD learning you met in the fundamentals.
References for this page#
- Mnih et al. (2015), Human-level control through deep reinforcement learning, Nature — DQN.
- van Hasselt et al. (2016), Deep RL with Double Q-learning — Double DQN.
- Wang et al. (2016), Dueling network architectures — dueling heads.
- Schaul et al. (2016), Prioritized experience replay.
- Hessel et al. (2018), Rainbow: combining improvements in deep RL — the ablation study worth reading in full.
- Bellemare, Dabney & Munos (2017), A distributional perspective on RL — C51.
- Sutton & Barto, ch. 11, for the deadly triad and Baird’s counterexample.