---
title: Deep Q-Networks
module: Reinforcement Learning
moduleNumber: 11
lessonNumber: 3
order: 1103
summary: >
  A Deep Q-Network replaces the tabular action-value function with a neural
  approximator $Q(s,a;\theta)$ and trains it by regression toward a bootstrapped
  target. Naive online Q-learning with a network diverges, so DQN adds two
  stabilizers: an experience-replay buffer that decorrelates samples, and a
  periodically-frozen target network that holds the regression target still. We
  derive the loss, give the full algorithm and the Atari pipeline, and then layer
  on Double DQN, the dueling split, prioritized replay, and the Rainbow
  combination.
topics: [Reinforcement Learning]
sources:
  - book: Goodfellow
    ref: "Ch. 1 — deep networks as function approximators for control"
---

[Model-free control](/deep-learning/reinforcement-learning/model-free-prediction-and-control)
gave us Q-learning: a table of action values $Q(s,a)$ updated toward a
one-step bootstrap. The table is the bottleneck. With $\abs{\mathcal{S}}$ in
the billions, raw Atari frames at $210 \times 160 \times 3$ being one example,
there is no table to fill and no way to generalize across the states never
visited. A **Deep Q-Network** replaces the table with a parametric function
$Q(s,a;\theta)$, a [convolutional network](/deep-learning/architectures/convolutional-networks)
that reads a state and emits one value per action, and trains $\theta$ by
regression. The substitution is immediate; making it _stable_ is the
entire lesson.

## From a table to a network

Tabular Q-learning stores one independent number per $(s,a)$ and updates it by
the rule

$$
Q(s,a) \gets Q(s,a) + \alpha \brackets{\, r + \gamma \max_{a'} Q(s',a') - Q(s,a)\,}.
$$

Replace the lookup with a network $Q(s,a;\theta)$ and the update by a gradient
step that drives $Q(s,a;\theta)$ toward the same target $y = r + \gamma \max_{a'}
Q(s',a';\theta)$. The per-sample objective is the squared temporal-difference
error.

> **Definition (Q-network).** A function approximator $Q(s,a;\theta)$, parametrized
> by weights $\theta$, that estimates the action-value $Q^{\ast}(s,a)$. For a discrete
> action set $\mathcal{A}$ the network maps a state $s$ to the vector
> $\parens{Q(s,a;\theta)}_{a \in \mathcal{A}}$ in one forward pass, so the greedy
> action $\arg\max_a Q(s,a;\theta)$ and the target $\max_a Q(s,a;\theta)$ each
> cost a single evaluation.

The single number per cell is gone; a state never seen still receives a value
through the shared weights. That generalization is the benefit, and also the source
of every instability that follows.

> **Definition (Bootstrapped TD target).** The regression target for $(s,a,r,s')$,
> $$
> y = r + \gamma \max_{a'} Q(s',a';\theta),
> $$
> is itself computed from the current network. The label depends on the parameters
> being fit, so the target moves as $\theta$ moves: training chases a target it is
> simultaneously displacing.

### Why naive online Q-learning diverges

Run Q-learning online, one gradient step per transition as it arrives, with a
neural $Q$, and training is unstable. Three forces compound.

| Problem | Cause | Effect on training |
| --- | --- | --- |
| Correlated samples | consecutive transitions in a trajectory are near-identical | gradient steps are not i.i.d.; the net overfits the current locality |
| Moving target | $y$ uses the same $\theta$ being updated | the regression target shifts every step, oscillation and feedback |
| Distribution shift | the policy that generates data changes as $\theta$ changes | the data distribution drifts under the optimizer |

The combination is an instance of the **deadly triad**: function approximation,
bootstrapping, and off-policy training together can make value estimates diverge,
even though any two of the three are safe.

> **Definition (Deadly triad).** The simultaneous presence of (i) function
> approximation, (ii) bootstrapping (a target built from the current estimate
> rather than a Monte-Carlo return), and (iii) off-policy updates (learning a
> greedy policy from data drawn by another). With all three, the value-error
> dynamics can have an expansive update operator, and the estimates can grow
> without bound.

DQN does not remove a leg of the triad; it keeps all three and damps the feedback
loop with two engineering devices, **experience replay** for the correlation and
**a target network** for the moving target.

## Experience replay

Rather than learn from each transition once, in order, and discard it, store
every transition in a buffer and train on _random minibatches_ drawn from it.

> **Definition (Replay buffer).** A fixed-capacity FIFO memory
> $\mathcal{D} = \braces{(s_i, a_i, r_i, s'_i)}_{i=1}^{\abs{\mathcal{D}}}$ holding the
> most recent transitions. Each gradient step samples a minibatch
> $B \sim \text{Uniform}(\mathcal{D})$ and minimizes the TD loss on $B$. The agent
> writes new experience to $\mathcal{D}$ as it acts and reads random samples to
> learn.

Two benefits follow directly. Random sampling breaks the temporal correlation
between successive updates, so the minibatch gradient approximates an expectation
over a broad, stationary mixture of past states rather than the current trajectory.
And every transition can be reused many times before eviction, so the sample
efficiency rises: rare, informative transitions contribute to many updates instead
of one.

$$
% caption: The replay loop. The agent writes transitions to the buffer while
% learning reads random minibatches from it, decoupling data collection from the
% gradient step.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, thick, minimum width=24mm, minimum height=11mm, align=center},
  buf/.style={draw=acc, thick, fill=acc!15, minimum width=28mm, minimum height=13mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (env) at (0,3.0) {environment};
  \node[box] (agent) at (0,0) {agent net Q};
  \node[buf] (buf) at (5.4,1.5) {replay buf\/fer D};
  \node[box] (learn) at (10.4,1.5) {learner (SGD)};
  % act / observe loop on the left
  \draw[->, thick] (agent.west) .. controls (-2.6,1.5) .. (env.west)
    node[midway, left, font=\scriptsize] {action};
  \draw[->, thick] (env.east) .. controls (2.2,1.5) .. (agent.east)
    node[pos=0.4, right, font=\scriptsize] {state, reward};
  % write to buffer
  \draw[->, acc, thick] (env.south east) -- (buf.north west);
  \node[acc, font=\scriptsize, anchor=south] at (2.9,2.55) {store};
  % sample minibatch
  \draw[->, thick] (buf.east) -- (learn.west);
  \node[font=\scriptsize, anchor=south] at (7.9,1.55) {random batch};
  % update weights back
  \draw[->, acc, thick] (learn.south) .. controls (5.4,-1.5) .. (agent.south);
  \node[acc, font=\scriptsize, anchor=north] at (5.4,-1.35) {update weights};
\end{tikzpicture}
$$

The buffer makes the data look i.i.d. to the optimizer, restoring the
assumption stochastic gradient descent needs.

## Target network

Replay fixes correlation but not the moving target: if the same $\theta$ that is
being updated also defines $y$, the regression chases a label that jumps every
step. The fix is a second set of weights $\theta^{-}$, a periodically-frozen copy
of $\theta$, used only to compute the target.

> **Definition (Target network).** A copy $Q(s,a;\theta^{-})$ of the Q-network
> whose parameters $\theta^{-}$ are held fixed and refreshed to the online weights,
> $\theta^{-} \gets \theta$, only every $C$ steps. The bootstrap target is built
> from $\theta^{-}$, so between refreshes it is a _stationary_ regression problem.

The DQN loss is the expected squared TD error with the target evaluated under the
frozen weights.

$$
L(\theta) = \mathbb{E}_{(s,a,r,s') \sim \mathcal{D}}
\brackets{\,\parens{\, r + \gamma \max_{a'} Q(s',a';\theta^{-}) - Q(s,a;\theta)\,}^{2}\,}.
$$

Differentiating, and treating $\theta^{-}$ as a constant because it is frozen, the
gradient is

$$
\nabla_\theta L(\theta) = -\,\mathbb{E}\brackets{\,
\parens{\, y - Q(s,a;\theta)\,}\,\nabla_\theta Q(s,a;\theta)\,},
\qquad
y = r + \gamma \max_{a'} Q(s',a';\theta^{-}).
$$

This is a plain supervised regression gradient: target minus prediction, times the
prediction's gradient. The only unusual part is that $y$ was produced by a stale
copy of the same network, which is precisely what makes it stable.

### One gradient step, worked

Take a single transition and push it through. Suppose a
sampled transition is $(s, a, r, s')$ with reward $r = 1$, discount
$\gamma = 0.99$, and $s'$ non-terminal. The frozen target network evaluates the
three actions at $s'$ as

$$
Q(s',a_1;\theta^{-}) = 2.0,\qquad
Q(s',a_2;\theta^{-}) = 5.0,\qquad
Q(s',a_3;\theta^{-}) = 3.0,
$$

so $\max_{a'} Q(s',a';\theta^{-}) = 5.0$ and the bootstrapped label is

$$
y = r + \gamma \max_{a'} Q(s',a';\theta^{-}) = 1 + 0.99 \cdot 5.0 = 5.95.
$$

Say the online network currently predicts $Q(s,a;\theta) = 4.0$ for the action
actually taken. The TD error and the per-sample loss are

$$
\delta = y - Q(s,a;\theta) = 5.95 - 4.0 = 1.95,
\qquad
\ell = \tfrac{1}{2}\delta^{2} = \tfrac{1}{2}(1.95)^{2} \approx 1.90.
$$

The gradient of $\ell$ with respect to $\theta$ is $-\delta\,\nabla_\theta
Q(s,a;\theta)$; with a positive $\delta$ the step $\theta \gets \theta - \eta
\nabla_\theta \ell = \theta + \eta\,\delta\,\nabla_\theta Q$ moves the parameters in
the direction that _raises_ $Q(s,a;\theta)$, closing the $1.95$ gap. A step size
$\eta$ and a local slope $\nabla_\theta Q$ that together move the prediction by,
say, $0.2 \cdot 1.95 \approx 0.39$ leave $Q(s,a;\theta) \approx 4.39$ after the
step: closer to $5.95$, but not there, because the same step also perturbs the
predictions at every other state that shares those weights. Only $Q(s,a;\theta)$ is
nudged; the labels stay fixed at $5.95$ until the next $\theta^{-}$ refresh, which
is what keeps this one step a piece of a stationary regression.

$$
% caption: One worked gradient step. The frozen target net produces the label
% $y = r + \gamma \max_{a'} Q(s',a';\theta^{-}) = 1 + 0.99\cdot 5.0 = 5.95$; the
% online prediction is $4.0$; the TD error $\delta = 1.95$ drives the squared loss
% $\tfrac{1}{2}\delta^2 \approx 1.90$ and an ascent on $Q(s,a;\theta)$.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  val/.style={draw, thick, minimum width=20mm, minimum height=11mm, align=center},
  tgt/.style={draw=acc, thick, fill=acc!15, minimum width=24mm, minimum height=11mm, align=center},
  res/.style={draw=acc, text=acc, thick, minimum width=22mm, minimum height=11mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \node[tgt] (mx)  at (0,1.6)  {frozen max\\\texttt{5.0}};
  \node[val] (rew) at (0,-0.6) {reward\\\texttt{1.0}};
  \node[res] (y)   at (4.2,0.5) {label y\\\texttt{5.95}};
  \node[val] (pred) at (4.2,-1.9) {online pred\\\texttt{4.0}};
  \node[res] (d)   at (8.6,0.5)  {TD error\\\texttt{1.95}};
  \node[val] (loss) at (8.6,-1.9) {loss\\\texttt{1.90}};
  \draw[->, acc, thick] (mx.east) -- (y.north west);
  \draw[->, thick] (rew.east) -- (y.south west);
  \node[font=\footnotesize, anchor=south] at (2.9,1.85) {\texttt{1+0.99*5.0}};
  \draw[->, acc, thick] (y.east) -- (d.west);
  \draw[->, thick] (pred.east) .. controls (6.4,-1.9) .. (d.south);
  \node[font=\footnotesize, anchor=south] at (6.4,0.6) {\texttt{y-pred}};
  \draw[->, thick] (d.south) -- (loss.north);
  \node[font=\footnotesize, anchor=west] at (8.75,-0.7) {\texttt{half square}};
\end{tikzpicture}
$$

$$
% caption: Online versus target network. Both share architecture; the online net
% (weights $\theta$) is updated each step, the target net (weights $\theta^{-}$) is
% a frozen copy refreshed every $C$ steps to supply a still target $y$.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  net/.style={draw, thick, minimum width=26mm, minimum height=16mm, align=center},
  tgt/.style={draw=acc, thick, fill=acc!15, minimum width=26mm, minimum height=16mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \node[net] (on) at (0,0) {online net\\online weights};
  \node[tgt] (tg) at (6.4,0) {target net\\frozen weights};
  % gradient updates online
  \draw[->, thick] (-3.2,1.5) -- (on.north west);
  \node[font=\scriptsize, anchor=south] at (-2.4,1.55) {SGD each step};
  % periodic copy
  \draw[->, acc, thick] (on.east) -- (tg.west);
  \node[acc, font=\scriptsize, anchor=south] at (3.2,0.15) {copy every C steps};
  % target net emits the label
  \draw[->, thick] (tg.south) .. controls (6.4,-2.2) and (0,-2.2) .. (on.south);
  \node[font=\scriptsize, anchor=north] at (3.2,-1.95) {supplies target y};
\end{tikzpicture}
$$

> **Theorem (Stationary regression between refreshes).** Hold $\theta^{-}$ fixed.
> Then $L(\theta)$ is an ordinary least-squares objective with a fixed target
> field $y(s,a,r,s') = r + \gamma \max_{a'} Q(s',a';\theta^{-})$, and a sufficiently
> small SGD step on $L$ contracts the prediction toward $y$ in expectation.

> **Proof.** With $\theta^{-}$ constant, $y$ does not depend on $\theta$, so $L$ is
> the mean squared error between the fixed labels $y$ and the predictions
> $Q(\cdot;\theta)$. Its gradient $-\mathbb{E}[(y - Q)\nabla_\theta Q]$ is the
> standard regression gradient, which for a step size below $2/\lambda_{\max}$ of
> the local Gauss-Newton curvature decreases $\mathbb{E}[(y - Q)^2]$ monotonically,
> the classical least-squares convergence. The bootstrap re-enters only at the
> refresh $\theta^{-} \gets \theta$, which restarts the regression against an
> updated, but again fixed, target. $\qed$

The two devices are complementary. Replay makes the _inputs_ look i.i.d.; the
target network makes the _labels_ hold still. Without either, the network tracks a
fast-moving feedback loop and diverges.

| Device | What it stabilizes | Mechanism | Hyperparameter |
| --- | --- | --- | --- |
| Experience replay | input correlation, data efficiency | random minibatch from a FIFO buffer | capacity $\abs{\mathcal{D}}$, batch size |
| Target network | the bootstrapped label | frozen copy $\theta^{-}$ refreshed every $C$ | refresh period $C$ |

## The DQN algorithm

Putting the pieces together gives the algorithm of the 2015 Nature paper:
$\epsilon$-greedy action selection, a replay write each step, a minibatch gradient
step against the target network, and a periodic refresh.

```algorithm
caption: $\textsc{DQN}$ — deep Q-learning with replay and a target network
initialize replay buffer $\mathcal{D}$ to capacity $M$
initialize online weights $\theta$ at random; set $\theta^{-} \gets \theta$
for each episode do
  observe initial state $s$
  repeat
    with probability $\epsilon$ pick random $a$, else $a \gets \arg\max_{a'} Q(s,a';\theta)$ // explore vs exploit
    execute $a$, observe reward $r$ and next state $s'$
    store $(s,a,r,s')$ in $\mathcal{D}$ // write experience
    sample minibatch $(s_j,a_j,r_j,s'_j) \sim \mathcal{D}$ // decorrelate
    $y_j \gets r_j + \gamma \max_{a'} Q(s'_j,a';\theta^{-})$ if $s'_j$ non-terminal, else $r_j$ // frozen target
    take a gradient step on $\sum_j \parens{y_j - Q(s_j,a_j;\theta)}^2$ // regress
    every $C$ steps set $\theta^{-} \gets \theta$ // refresh target
    $s \gets s'$
  until $s$ terminal
return $\theta$
```

The whole thing is one cycle: the agent acts, stores what it saw, samples an
unrelated batch of old experience, builds targets from the frozen copy, takes one
SGD step, and every $C$ steps copies its weights into that frozen copy.

$$
% caption: The DQN training cycle. Acting writes transitions to the buffer;
% learning reads a random batch, forms targets $y$ from $\theta^{-}$, and steps
% $\theta$ by SGD; every $C$ steps $\theta^{-} \gets \theta$ closes the loop.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  clab/.style={draw, thick, minimum width=23mm, minimum height=10mm, align=center},
  acc/.style={draw=acc, thick, fill=acc!15, minimum width=23mm, minimum height=10mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \node[clab] (act)   at (0,2.4)   {act (eps-greedy)};
  \node[acc]  (store) at (5.0,2.4) {store in buf\/fer};
  \node[acc]  (samp)  at (10.0,2.4) {sample batch};
  \node[clab] (tgt)   at (10.0,0)  {target from\\frozen net};
  \node[clab] (sgd)   at (5.0,0)   {SGD step on\\online net};
  \node[acc]  (refr)  at (0,0)     {every C steps\\copy weights};
  \draw[->, thick] (act.east)   -- (store.west);
  \draw[->, thick] (store.east) -- (samp.west);
  \draw[->, thick] (samp.south) -- (tgt.north);
  \draw[->, thick] (tgt.west)   -- (sgd.east);
  \draw[->, acc, thick] (sgd.west)  -- (refr.east);
  \draw[->, acc, thick] (refr.north) -- (act.south);
  \node[font=\footnotesize, anchor=south] at (7.5,2.45) {\texttt{(s,a,r,s')}};
  \node[font=\footnotesize, anchor=east] at (9.9,1.2) {\texttt{batch}};
  \node[font=\footnotesize, anchor=north] at (7.5,-0.05) {\texttt{y-Q}};
\end{tikzpicture}
$$

### Hyperparameter defaults

The Nature agent fixed one set of hyperparameters across all games. The defaults
are not arbitrary; each trades off a specific failure mode.

| Hyperparameter | Default | Why this value |
| --- | --- | --- |
| Replay capacity $\abs{\mathcal{D}}$ | $10^{6}$ | large enough to hold minutes of play, so batches mix many episodes and old policies; too small and the buffer re-correlates with the current trajectory |
| Target refresh $C$ | $10^{4}$ steps | long enough that the label is effectively stationary between refreshes, short enough that it does not lag the online net into staleness |
| Minibatch size | $32$ | a gradient estimate with usable variance at low compute per step; larger batches waste samples the buffer could reuse across more updates |
| Discount $\gamma$ | $0.99$ | weights a horizon of roughly $1/(1-\gamma) = 100$ steps, matching Atari's reward delays without letting the bootstrap sum diverge |
| Exploration $\epsilon$ | $1.0 \to 0.1$ over $10^{6}$ steps | anneal from all-random to mostly-greedy so early play covers the state space and later play exploits the learned values, then hold a small floor for continued exploration |
| Learning rate | $2.5\times10^{-4}$ | small enough that the moving-target feedback does not blow up, given the frozen-target damping |

### The Atari setup

The benchmark that made DQN famous is the Arcade Learning Environment: one network,
one set of hyperparameters, learning $49$ games from raw pixels and the score
alone. The input pipeline turns the screen into a Markov state and the CNN turns
that state into action values.

| Stage | Operation | Output |
| --- | --- | --- |
| Grayscale + downsample | RGB $210 \times 160$ to luminance, resize | $84 \times 84$ |
| Frame stack | concatenate the last $4$ frames | $84 \times 84 \times 4$ |
| Frame skip | repeat each action for $4$ frames | $4\times$ fewer decisions |
| Reward clip | clip reward to $\braces{-1,0,+1}$ | one scale across games |

A single frame is not Markov: it shows position but not velocity or direction. The
**frame stack** of four restores enough state for the dynamics to be (approximately)
Markov, so the CNN can read motion from the channel axis.

$$
% caption: The Atari Q-network. Four stacked $84\times84$ frames pass through three
% convolutions and two dense layers to a head of one Q-value per action.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  conv/.style={draw, fill=acc!15, minimum width=9mm, minimum height=16mm, align=center, font=\scriptsize},
  fc/.style={draw, fill=acc!15, minimum width=8mm, minimum height=11mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[draw, thick, minimum width=12mm, minimum height=18mm, align=center, font=\scriptsize] (in) at (0,0) {4 frames\\84x84};
  \node[conv] (c1) at (1.9,0) {conv\\8x8};
  \node[conv] (c2) at (3.4,0) {conv\\4x4};
  \node[conv] (c3) at (4.9,0) {conv\\3x3};
  \node[fc]   (f1) at (6.5,0) {fc\\512};
  % Q head: one value per action
  \node[draw=acc, text=acc, thick, minimum width=10mm, minimum height=7mm, font=\scriptsize] (q1) at (8.7,1.4) {Q(s,up)};
  \node[draw=acc, text=acc, thick, minimum width=10mm, minimum height=7mm, font=\scriptsize] (q2) at (8.7,0.0) {Q(s,down)};
  \node[draw=acc, text=acc, thick, minimum width=10mm, minimum height=7mm, font=\scriptsize] (q3) at (8.7,-1.4) {Q(s,f\/ire)};
  \draw[->, thick] (in) -- (c1); \draw[->, thick] (c1) -- (c2);
  \draw[->, thick] (c2) -- (c3); \draw[->, thick] (c3) -- (f1);
  \draw[->, acc, thick] (f1) -- (q1);
  \draw[->, acc, thick] (f1) -- (q2);
  \draw[->, acc, thick] (f1) -- (q3);
\end{tikzpicture}
$$

Trace the convolutional stack of the Nature architecture dimension by
dimension. The input tensor is the frame stack $84 \times 84 \times 4$ (height,
width, channels). Three convolutions, each followed by a ReLU, shrink the spatial
extent while growing the channel count; a valid convolution with kernel $k$, stride
$s$, and no padding maps a spatial size $n$ to $\lfloor (n - k)/s \rfloor + 1$.

| Layer | Kernel / stride | Filters | Output tensor | Parameters |
| --- | --- | --- | --- | --- |
| Input | — | — | $84 \times 84 \times 4$ | 0 |
| Conv 1 | $8 \times 8$, stride $4$ | $32$ | $20 \times 20 \times 32$ | $8\cdot8\cdot4\cdot32 + 32 = 8{,}224$ |
| Conv 2 | $4 \times 4$, stride $2$ | $64$ | $9 \times 9 \times 64$ | $4\cdot4\cdot32\cdot64 + 64 = 32{,}832$ |
| Conv 3 | $3 \times 3$, stride $1$ | $64$ | $7 \times 7 \times 64$ | $3\cdot3\cdot64\cdot64 + 64 = 36{,}928$ |
| Flatten | — | — | $3136$ | 0 |
| FC | dense | $512$ | $512$ | $3136\cdot512 + 512 = 1{,}606{,}144$ |
| Output | dense | $\abs{\mathcal{A}}$ | $\abs{\mathcal{A}}$ | $512\cdot\abs{\mathcal{A}} + \abs{\mathcal{A}}$ |

Working the spatial arithmetic: $\lfloor(84-8)/4\rfloor + 1 = 20$, then
$\lfloor(20-4)/2\rfloor + 1 = 9$, then $\lfloor(9-3)/1\rfloor + 1 = 7$. The final
$7 \times 7 \times 64$ feature map flattens to $7 \cdot 7 \cdot 64 = 3136$ units,
which the dense layer compresses to $512$ and the output head expands to one value
per action. For a $6$-action game the output is a length-$6$ vector and the whole
network holds roughly $1.69$ million weights, dominated by the first dense layer.

The Q-head is the key design choice: the network outputs all $\abs{\mathcal{A}}$
action values at once, so $\max_a Q(s,a;\theta)$ and $\arg\max_a Q(s,a;\theta)$ are
both a single forward pass, not one pass per action.

## Overestimation and Double DQN

The $\max$ operator in the target has a bias. The target uses the same network both
to _select_ the best next action and to _evaluate_ its value, and a single noisy
estimate that happens to be too high is preferentially selected by the $\max$. The
result is a systematic **overestimation** of action values.

> **Theorem (Overestimation of the max).** Let $\hat{Q}(s',a')$ be unbiased
> estimates of equal true values $Q(s',a') = q$ for all $a'$, with independent
> noise. Then
> $$
> \mathbb{E}\brackets{\max_{a'} \hat{Q}(s',a')} \;\ge\; \max_{a'} \mathbb{E}\brackets{\hat{Q}(s',a')} = q,
> $$
> with strict inequality whenever the estimates have positive variance. The
> bootstrap target inherits this upward bias at every step.

> **Proof.** The maximum is a convex function of its arguments, so by Jensen's
> inequality $\mathbb{E}[\max_{a'} \hat{Q}] \ge \max_{a'} \mathbb{E}[\hat{Q}]$. When
> all true values are equal to $q$ and the $\hat{Q}$ carry independent noise, the
> sampled maximum exceeds $q$ with probability one as soon as any estimate is
> positive-variance, so $\mathbb{E}[\max_{a'} \hat{Q}] > q$ strictly. The
> inequality measures the gap between selecting and evaluating with the same
> noisy estimates. $\qed$

$$
% caption: Overestimation. A single noisy estimator (blue) used for both selection
% and evaluation yields a max above the true value (black line); decoupling the two
% removes the upward bias.
\begin{tikzpicture}[>=stealth, font=\footnotesize, x=1.0cm, y=1.0cm]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % axes
  \draw[->, thick] (0,0) -- (6.6,0) node[right, font=\scriptsize] {actions};
  \draw[->, thick] (0,0) -- (0,3.6) node[above, font=\scriptsize] {value};
  % true value: horizontal black line
  \draw[black, very thick] (0.3,1.6) -- (6.0,1.6);
  \node[black, anchor=south west, font=\scriptsize] at (0.3,1.62) {true value $q$};
  % noisy estimates as dots scattered around q
  \fill[acc] (0.9,1.2) circle (2.2pt);
  \fill[acc] (1.8,2.1) circle (2.2pt);
  \fill[acc] (2.7,1.4) circle (2.2pt);
  \fill[acc] (3.6,2.7) circle (2.2pt);
  \fill[acc] (4.5,1.5) circle (2.2pt);
  \fill[acc] (5.4,1.9) circle (2.2pt);
  % the selected max (highest dot)
  \draw[red, thick, ->] (3.6,3.2) -- (3.6,2.85);
  \node[red, anchor=south, font=\scriptsize] at (3.6,3.2) {selected max};
  \draw[red, dashed] (0,2.7) -- (3.6,2.7);
  \node[red, anchor=east, font=\scriptsize] at (-0.1,2.7) {biased high};
\end{tikzpicture}
$$

**Double DQN** breaks the coupling. The online network $\theta$ selects the action;
the target network $\theta^{-}$ evaluates it. Selecting with one estimator and
evaluating with another removes the systematic bias of selecting and evaluating
with the same noise.

$$
y^{\text{DQN}} = r + \gamma\, Q\!\parens{s', \arg\max_{a'} Q(s',a';\theta^{-});\, \theta^{-}}
\quad\longrightarrow\quad
y^{\text{DDQN}} = r + \gamma\, Q\!\parens{s', \arg\max_{a'} Q(s',a';\theta);\, \theta^{-}}.
$$

The change is one symbol: the $\arg\max$ now uses the online weights $\theta$, while
the value lookup still uses $\theta^{-}$. No new network is added; DQN already
carries both $\theta$ and $\theta^{-}$, so the fix is free.

$$
% caption: Double DQN splits selection from evaluation. The online net's argmax
% picks $a^{*} = \arg\max_{a'} Q(s',a';\theta)$; the frozen target net evaluates
% that chosen action, $Q(s',a^{*};\theta^{-})$, so no single noisy estimate both
% selects and scores itself.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  onl/.style={draw, thick, minimum width=26mm, minimum height=12mm, align=center},
  tgt/.style={draw=acc, thick, fill=acc!15, minimum width=26mm, minimum height=12mm, align=center},
  res/.style={draw=acc, text=acc, thick, minimum width=22mm, minimum height=12mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \node[onl] (sel) at (0,0)   {online net\\argmax picks a};
  \node[tgt] (ev)  at (5.6,0) {target net\\scores it};
  \node[res] (y)   at (11.0,0) {y = r + gamma\\times score};
  \draw[->, thick] (sel.east) -- (ev.west);
  \node[font=\footnotesize, anchor=south] at (2.8,0.1) {\texttt{chosen action a}};
  \draw[->, acc, thick] (ev.east) -- (y.west);
  \node[font=\footnotesize, anchor=south] at (8.3,0.1) {\texttt{value of a}};
\end{tikzpicture}
$$

| Target | Selection | Evaluation | Bias |
| --- | --- | --- | --- |
| DQN | $\theta^{-}$ | $\theta^{-}$ | overestimates (same net) |
| Double DQN | $\theta$ | $\theta^{-}$ | decoupled, near-unbiased |

## The dueling architecture

Many states have similar value under every action: when no action matters, the
detail of _which_ action is slightly better is noise. The **dueling network**
factors the Q-value into a state-value $V(s)$ and an action-advantage $A(s,a)$,
estimated by two streams off a shared convolutional trunk and recombined.

> **Definition (Advantage function).** The advantage of action $a$ in state $s$,
> $$
> A^{\pi}(s,a) = Q^{\pi}(s,a) - V^{\pi}(s),
> $$
> measures how much better $a$ is than the state's average. By construction
> $\mathbb{E}_{a \sim \pi}\brackets{A^{\pi}(s,a)} = 0$: advantage carries only the
> _relative_ ranking of actions, with the absolute level absorbed into $V$.

The naive recombination $Q(s,a) = V(s) + A(s,a)$ is **unidentifiable**: adding a
constant to $V$ and subtracting it from every $A$ leaves $Q$ unchanged, so the two
streams cannot be recovered uniquely. Subtracting the mean advantage pins them
down.

$$
Q(s,a;\theta) = V(s;\theta) + \parens{\, A(s,a;\theta) - \frac{1}{\abs{\mathcal{A}}}\sum_{a'} A(s,a';\theta)\,}.
$$

> **Theorem (Identifiability via mean subtraction).** With the centered combination
> above, $V(s;\theta)$ is forced to equal the mean of $Q(s,\cdot;\theta)$ over
> actions, and $A(s,a;\theta)$ is forced to be zero-mean, so the decomposition is
> unique.

> **Proof.** Average the defining equation over $a$. The advantage term has zero
> mean by the subtraction, so $\frac{1}{\abs{\mathcal{A}}}\sum_a Q(s,a;\theta) =
> V(s;\theta)$, fixing $V$ as the action-mean of $Q$. Then $A(s,a;\theta) =
> Q(s,a;\theta) - V(s;\theta)$ up to the same zero-mean constraint, so no constant
> can be shuffled between the streams without breaking the zero-mean condition.
> The map between $(V,A)$ and $Q$ is now a bijection. $\qed$

$$
% caption: The dueling split. A shared trunk feeds two streams, a scalar value
% $V(s)$ and a per-action advantage $A(s,a)$, recombined by adding $V$ to the
% mean-centered advantage.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, thick, minimum width=20mm, minimum height=10mm, align=center},
  stream/.style={draw=acc, thick, fill=acc!15, minimum width=22mm, minimum height=10mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (trunk) at (0,0) {conv trunk};
  \node[stream] (v) at (4.2,1.4) {value $V(s)$\\(scalar)};
  \node[stream] (a) at (4.2,-1.4) {advantage\\$A(s,a)$ (per action)};
  \node[draw=acc, text=acc, thick, minimum width=16mm, minimum height=10mm, align=center] (comb) at (8.6,0) {combine\\$Q(s,a)$};
  \draw[->, thick] (trunk.east) -- (v.west);
  \draw[->, thick] (trunk.east) -- (a.west);
  \draw[->, acc, thick] (v.east) -- (comb.north west);
  \draw[->, acc, thick] (a.east) -- (comb.south west);
  \node[anchor=north, font=\scriptsize] at (8.6,-0.95) {V plus centered A};
\end{tikzpicture}
$$

The gain is data efficiency: the value stream learns $V(s)$ from _every_ transition
in a state regardless of the action taken, so states are evaluated accurately even
for actions rarely tried.

## Prioritized experience replay

Uniform replay samples every transition equally, but transitions are not equally
informative: one with a large TD error carries more to learn from than one the
network already predicts well. **Prioritized experience replay** samples in
proportion to TD-error magnitude.

> **Definition (Prioritized sampling).** Assign transition $i$ a priority
> $p_i = \abs{\delta_i} + \varepsilon$, where $\delta_i = y_i - Q(s_i,a_i;\theta)$ is
> its last TD error and $\varepsilon > 0$ keeps every priority positive. Sample $i$
> with probability
> $$
> P(i) = \frac{p_i^{\,\alpha}}{\sum_j p_j^{\,\alpha}},
> $$
> where $\alpha \in [0,1]$ interpolates between uniform ($\alpha = 0$) and fully
> greedy prioritization ($\alpha = 1$).

Biasing the sampling distribution biases the expected gradient: the network now
trains on a distribution that is not the buffer's empirical one, so high-error
transitions are over-represented. **Importance sampling** corrects the estimate by
down-weighting each sampled transition by the inverse of how much it was
over-sampled.

$$
w_i = \parens{\frac{1}{\abs{\mathcal{D}}} \cdot \frac{1}{P(i)}}^{\beta},
\qquad
\delta_i \;\leftarrow\; w_i\,\delta_i,
$$

normalized by $\max_j w_j$ for stability. The exponent $\beta$ is annealed from a
small value toward $1$ over training, so the correction is full only near
convergence, when the unbiased gradient matters most.

| Scheme | Sampling $P(i)$ | Correction | Effect |
| --- | --- | --- | --- |
| Uniform replay | $1/\abs{\mathcal{D}}$ | none | unbiased, slow on rare events |
| Greedy prioritized | $\propto \abs{\delta_i}$ | needed | fast but over-focuses, can overfit |
| Proportional ($\alpha,\beta$) | $\propto p_i^{\alpha}$ | $w_i$ with $\beta \to 1$ | tunable, asymptotically unbiased |

## Rainbow and beyond

Each improvement targets a distinct defect, and they are largely orthogonal.
**Rainbow** combines six of them into one agent and shows the gains compound rather
than cancel.

| Variant | Problem it fixes |
| --- | --- |
| Experience replay | correlated, single-use samples |
| Target network | a moving bootstrap target |
| Double DQN | overestimation from coupled $\max$ |
| Dueling | wasted value learning across actions |
| Prioritized replay | uniform sampling ignores TD error |
| Multi-step returns | slow one-step credit assignment |
| Distributional (C51) | a point estimate discards return spread |
| Noisy nets | hand-tuned $\epsilon$-greedy exploration |

Two of the Rainbow ingredients change what the network predicts. **Distributional
RL (C51)** replaces the scalar $Q(s,a)$ with a full distribution over returns,
modeled as a categorical over a fixed set of atoms, and minimizes a cross-entropy
to the distributional Bellman target; the mean of that distribution recovers the
usual $Q$, but the spread carries extra signal. **Noisy nets** make
exploration learnable by adding parametric noise to the weights,
$\theta \to \mu + \sigma \odot \epsilon$ with $\epsilon$ random and $\mu,\sigma$
trained, so the policy explores through its own learned uncertainty and the
$\epsilon$-greedy schedule disappears.

## What came after Rainbow

Goodfellow's text predates DQN's Rainbow line, so the citations here are the canonical papers themselves: the 2015 Nature DQN,[^mnih-dqn] Double DQN,[^vanhasselt-ddqn] the dueling architecture,[^wang-dueling] prioritized replay,[^schaul-per] and the Rainbow combination.[^hessel-rainbow] Two later directions follow, both continued in the full [reinforcement-learning subject's deep-RL module](/reinforcement-learning/deep-rl/deep-q-networks).

**Sample efficiency became the frontier.** Rainbow needed hundreds of millions of frames per game. The successors — data-efficient variants and model-based agents that _learn_ a world model and plan inside it — reach comparable scores from a small fraction of the data. Learning a model recovers the planning power the [foundations lesson](/deep-learning/reinforcement-learning/foundations-of-reinforcement-learning) had with a known model, without being handed one, and it is the value-based counterpart to the policy-based methods of the [next lesson](/deep-learning/reinforcement-learning/policy-gradients-and-actor-critic).

**The scaling story split by action space.** DQN's one-value-per-action head needs a discrete, small action set: the $\max_a$ and $\arg\max_a$ enumerate actions, which is impossible for continuous control (a robot's torques). That limitation motivates the actor-critic and policy-gradient methods of the following lesson, which parameterize the policy directly and so handle continuous actions the $\max$ cannot. Value-based deep RL owns the discrete-action, high-sample-budget regime; policy-based methods own continuous control.

In short, DQN solved value-based deep RL for discrete actions, and everything after either made it cheaper (sample efficiency, model-based planning) or worked around its discrete-action ceiling (policy gradients). The two stabilizers this lesson built — replay and a frozen target — survive into nearly every value-based deep-RL agent since.

## Takeaways

- A **Q-network** $Q(s,a;\theta)$ replaces the tabular action-value with a CNN that
  emits one value per action in a single forward pass, generalizing across states
  no table could hold.
- Naive online Q-learning with a network diverges: **correlated samples**, a
  **moving bootstrapped target**, and off-policy updates form the **deadly triad**.
- **Experience replay** stores transitions and samples random minibatches,
  decorrelating updates and reusing each transition many times.
- A **target network** $\theta^{-}$, refreshed every $C$ steps, freezes the
  regression label so each interval is a stationary least-squares problem; the DQN
  loss is $\mathbb{E}\brackets{(r + \gamma \max_{a'} Q(s',a';\theta^{-}) - Q(s,a;\theta))^2}$.
- The **Atari** pipeline grayscales and stacks four $84\times84$ frames for an
  approximate Markov state, feeding a three-conv CNN with a one-value-per-action head.
- The $\max$ operator **overestimates** action values; **Double DQN** decouples
  selection (online $\theta$) from evaluation (target $\theta^{-}$) to remove the bias.
- The **dueling** architecture splits $Q = V + (A - \overline{A})$ into value and
  mean-centered advantage streams, made identifiable by the mean subtraction.
- **Prioritized replay** samples by TD-error magnitude $p_i^{\alpha}$ and corrects
  the induced bias with importance weights $w_i$ annealed to full strength.
- **Rainbow** combines replay, target nets, Double DQN, dueling, prioritized replay,
  multi-step returns, **distributional (C51)** values, and **noisy-net** exploration
  into one agent whose gains compound.
- **After DQN:** DQN solved value-based deep RL for _discrete_ actions; its
  successors made it cheaper (sample-efficient and model-based agents), while the
  discrete-action ceiling of the $\max_a$ head is what motivates the policy-gradient
  and actor-critic methods for continuous control in the next lesson.

[^mnih-dqn]: **Mnih et al.**, _Human-level Control through Deep Reinforcement Learning_, Nature 2015 — the DQN agent: a convolutional Q-network trained with experience replay and a periodically-frozen target network, learning 49 Atari games from pixels.
[^vanhasselt-ddqn]: **van Hasselt, Guez & Silver**, _Deep Reinforcement Learning with Double Q-learning_, AAAI 2016 — decouples action selection (online net) from evaluation (target net) to remove the max-operator overestimation bias.
[^wang-dueling]: **Wang et al.**, _Dueling Network Architectures for Deep Reinforcement Learning_, ICML 2016 — splits the Q-network into a state-value and a mean-centered advantage stream for more data-efficient value learning.
[^schaul-per]: **Schaul et al.**, _Prioritized Experience Replay_, ICLR 2016 — samples transitions in proportion to TD-error magnitude with importance-sampling correction, focusing learning on surprising experience.
[^hessel-rainbow]: **Hessel et al.**, _Rainbow: Combining Improvements in Deep Reinforcement Learning_, AAAI 2018 — integrates six DQN extensions (double, dueling, prioritized replay, multi-step, distributional C51, noisy nets) into one agent whose gains compound.