Deep Q-Networks

Model-free 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 $∣ 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; θ)$ , a convolutional network that reads a state and emits one value per action, and trains $θ$ 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) \leftarrow Q (s, a) + α [r + γ a^{'} max Q (s^{'}, a^{'}) - Q (s, a)] .

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

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.

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 $θ$ being updated	the regression target shifts every step, oscillation and feedback
Distribution shift	the policy that generates data changes as $θ$ 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.

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.

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.

The replay loop. The agent writes transitions to the buffer while learning reads random minibatches from it, decoupling data collection from the gradient step.

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 $θ$ that is being updated also defines $y$ , the regression chases a label that jumps every step. The fix is a second set of weights $θ^{-}$ , a periodically-frozen copy of $θ$ , used only to compute the target.

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

L (θ) = E_{(s, a, r, s^{'}) \sim D} [(r + γ a^{'} max Q (s^{'}, a^{'}; θ^{-}) - Q (s, a; θ))^{2}] .

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

\nabla_{θ} L (θ) = - E [(y - Q (s, a; θ)) \nabla_{θ} Q (s, a; θ)], y = r + γ a^{'} max Q (s^{'}, a^{'}; θ^{-}) .

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 $γ = 0.99$ , and $s^{'}$ non-terminal. The frozen target network evaluates the three actions at $s^{'}$ as

Q (s^{'}, a_{1}; θ^{-}) = 2.0, Q (s^{'}, a_{2}; θ^{-}) = 5.0, Q (s^{'}, a_{3}; θ^{-}) = 3.0,

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

y = r + γ a^{'} max Q (s^{'}, a^{'}; θ^{-}) = 1 + 0.99 \cdot 5.0 = 5.95.

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

δ = y - Q (s, a; θ) = 5.95 - 4.0 = 1.95, ℓ = \frac{1}{2} δ^{2} = \frac{1}{2} (1.95)^{2} \approx 1.90.

The gradient of $ℓ$ with respect to $θ$ is $- δ \nabla_{θ} Q (s, a; θ)$ ; with a positive $δ$ the step $θ \leftarrow θ - η \nabla_{θ} ℓ = θ + η δ \nabla_{θ} Q$ moves the parameters in the direction that raises $Q (s, a; θ)$ , closing the $1.95$ gap. A step size $η$ and a local slope $\nabla_{θ} Q$ that together move the prediction by, say, $0.2 \cdot 1.95 \approx 0.39$ leave $Q (s, a; θ) \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; θ)$ is nudged; the labels stay fixed at $5.95$ until the next $θ^{-}$ refresh, which is what keeps this one step a piece of a stationary regression.

One worked gradient step. The frozen target net produces the label

y = r + γ max_{a^{'}} Q (s^{'}, a^{'}; θ^{-}) = 1 + 0.99 \cdot 5.0 = 5.95

; the online prediction is

4.0

; the TD error

δ = 1.95

drives the squared loss

\frac{1}{2} δ^{2} \approx 1.90

and an ascent on

Q (s, a; θ)

Online versus target network. Both share architecture; the online net (weights

θ

) is updated each step, the target net (weights

θ^{-}

) is a frozen copy refreshed every

C

steps to supply a still target

y

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 $∣ D ∣$ , batch size
Target network	the bootstrapped label	frozen copy $θ^{-}$ refreshed every $C$	refresh period $C$

The DQN algorithm

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

Algorithm:

\textsc{DQN}

— deep Q-learning with replay and a target network

1
initialize replay buffer $\mathcal{D}$ to capacity $M$
2
initialize online weights $\theta$ at random; set $\theta^{-} \gets \theta$
3
for each episode do
4
observe initial state $s$
5
repeat
6
with probability $\epsilon$ pick random $a$ , else $a \gets \arg\max_{a'} Q(s,a';\theta)$
explore vs exploit
7
execute $a$ , observe reward $r$ and next state $s'$
8
store $(s,a,r,s')$ in $\mathcal{D}$
write experience
9
sample minibatch $(s_j,a_j,r_j,s'_j) \sim \mathcal{D}$
decorrelate
10
$y_j \gets r_j + \gamma \max_{a'} Q(s'_j,a';\theta^{-})$ if $s'_j$ non-terminal, else $r_j$
frozen target
11
take a gradient step on $\sum_j \parens{y_j - Q(s_j,a_j;\theta)}^2$
regress
12
every $C$ steps set $\theta^{-} \gets \theta$
refresh target
13
$s \gets s'$
14
until $s$ terminal
15
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.

The DQN training cycle. Acting writes transitions to the buffer; learning reads a random batch, forms targets

y

from

θ^{-}

, and steps

θ

by SGD; every

C

steps

θ^{-} \leftarrow θ

closes the loop.

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 $∣ D ∣$	$1 0^{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$	$1 0^{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 $γ$	$0.99$	weights a horizon of roughly $1/ (1 - γ) = 100$ steps, matching Atari's reward delays without letting the bootstrap sum diverge
Exploration $ϵ$	$1.0 \to 0.1$ over $1 0^{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 \times 1 0^{- 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 ${- 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.

The Atari Q-network. Four stacked

84 \times 84

frames pass through three convolutions and two dense layers to a head of one Q-value per action.

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 $⌊(n - k) / s ⌋ + 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 \cdot 8 \cdot 4 \cdot 32 + 32 = 8, 224$
Conv 2	$4 \times 4$ , stride $2$	$64$	$9 \times 9 \times 64$	$4 \cdot 4 \cdot 32 \cdot 64 + 64 = 32, 832$
Conv 3	$3 \times 3$ , stride $1$	$64$	$7 \times 7 \times 64$	$3 \cdot 3 \cdot 64 \cdot 64 + 64 = 36, 928$
Flatten	—	—	$3136$	0
FC	dense	$512$	$512$	$3136 \cdot 512 + 512 = 1, 606, 144$
Output	dense	$∣ A ∣$	$∣ A ∣$	$512 \cdot ∣ A ∣ + ∣ A ∣$

Working the spatial arithmetic: $⌊(84 - 8) /4 ⌋ + 1 = 20$ , then $⌊(20 - 4) /2 ⌋ + 1 = 9$ , then $⌊(9 - 3) /1 ⌋ + 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 $∣ A ∣$ action values at once, so $max_{a} Q (s, a; θ)$ and $ar g max_{a} Q (s, a; θ)$ 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.

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.

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

y^{DQN} = r + γ Q (s^{'}, ar g a^{'} max Q (s^{'}, a^{'}; θ^{-}); θ^{-}) ⟶ y^{DDQN} = r + γ Q (s^{'}, ar g a^{'} max Q (s^{'}, a^{'}; θ); θ^{-}) .

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

Double DQN splits selection from evaluation. The online net's argmax picks

a^{*} = ar g max_{a^{'}} Q (s^{'}, a^{'}; θ)

; the frozen target net evaluates that chosen action,

Q (s^{'}, a^{*}; θ^{-})

, so no single noisy estimate both selects and scores itself.

Target	Selection	Evaluation	Bias
DQN	$θ^{-}$	$θ^{-}$	overestimates (same net)
Double DQN	$θ$	$θ^{-}$	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.

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; θ) = V (s; θ) + (A (s, a; θ) - \frac{1}{∣ A ∣} a^{'} \sum A (s, a^{'}; θ)) .

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.

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.

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} = (\frac{1}{∣ D ∣} \cdot \frac{1}{P ( i )})^{β}, δ_{i} \leftarrow w_{i} δ_{i},

normalized by $max_{j} w_{j}$ for stability. The exponent $β$ 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/ ∣ D ∣$	none	unbiased, slow on rare events
Greedy prioritized	$\propto ∣ δ_{i} ∣$	needed	fast but over-focuses, can overfit
Proportional ( $α, β$ )	$\propto p_{i}^{α}$	$w_{i}$ with $β \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 $ϵ$ -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, $θ \to μ + σ ⊙ ϵ$ with $ϵ$ random and $μ, σ$ trained, so the policy explores through its own learned uncertainty and the $ϵ$ -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,¹ Double DQN,² the dueling architecture,³ prioritized replay,⁴ and the Rainbow combination.⁵ Two later directions follow, both continued in the full reinforcement-learning subject's deep-RL module.

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 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.

The scaling story split by action space. DQN's one-value-per-action head needs a discrete, small action set: the $max_{a}$ and $ar g 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; θ)$ 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 $θ^{-}$ , refreshed every $C$ steps, freezes the regression label so each interval is a stationary least-squares problem; the DQN loss is $E [(r + γ max_{a^{'}} Q (s^{'}, a^{'}; θ^{-}) - Q (s, a; θ))^{2}]$ .
The Atari pipeline grayscales and stacks four $84 \times 84$ 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 $θ$ ) from evaluation (target $θ^{-}$ ) 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}^{α}$ 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 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. ↩
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 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 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 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. ↩