Deep Q-Networks

Every method up to now approximated value with a linear map: pick features $\mathbf{x}(s,a)$ by hand, and estimate $Q(s,a)\approx {\mathbf{w}}^{\top }\mathbf{x}(s,a)$. That works when a person can design good features, and it comes with the projected-Bellman-error geometry that makes stable off-policy methods possible. It fails the moment the state is a raw image. An Atari frame is $210\times 160$ pixels over three color channels; the number of distinct states is astronomically larger than the number of atoms in the observable universe, and no hand-built feature set can cover it.¹ Deep reinforcement learning instead lets a neural network be the feature extractor and the value head at once, learned end to end from reward.

A deep Q-network approximates the action-value function with a neural network whose weights are $\mathbf{w}$:

The network takes the state, and outputs one Q-value per action in a single forward pass. That is the whole idea. The rest of this lesson is about the one thing that makes it hard: a nonlinear approximator trained by online Q-learning is unstable, and left alone it diverges. DQN made it converge in practice, and is the algorithm that started modern deep RL.²

From features to a network

A tabular Q-learner keeps a matrix indexed by state and action. Function approximation replaces that lookup with a parametric function, and the gain is generalization: adjusting $\mathbf{w}$ to fix the value of one state-action pair also shifts the value of every similar pair, so the agent learns from states it has never visited. In a linear model that generalization is limited to what the chosen features can express; a neural network discovers its own features, and can represent the intricate value surfaces that raw perception requires.³

There are two ways to wire a network for $Q$, and the choice matters. One feeds in both the state and an action and outputs a single scalar; evaluating all actions then costs one forward pass per action. The efficient alternative — the one DQN uses — feeds in the state alone and outputs a vector of Q-values, one per action. A single forward pass then scores every action at once, handing an $\epsilon$-greedy or softmax policy the full vector it consumes.⁴

Given this network, the greedy action in a state is $\arg {\max }_{a}Q(s,a;\mathbf{w})$, computed from one pass, and the whole apparatus of generalized policy iteration carries over: evaluate the current policy by regressing $Q$ toward a target, improve by acting greedily (with exploration) on the new estimates, repeat. The catch is that with a nonlinear $Q$ there are no convergence guarantees left.

The ideal objective, and why it is out of reach

Training the network would be ordinary supervised learning if the correct answers were available. They are not, so the target must be manufactured from the network's own estimates, at the cost of a non-stationary target.

If we somehow had access to the optimal action-value function $q_{\ast }$, learning $Q$ would be ordinary supervised regression: minimize the squared distance to the true values,

This objective is unavailable.⁵ We have no $q_{\ast }$ to regress against — if we did, there would be nothing to learn — and we cannot even sample $q_{\ast }$, because we have neither the optimal policy nor the environment's model. The fix is the same bootstrapping trick as tabular Q-learning: replace the unavailable $q_{\ast }(s,a)$ with a target built from the network's own next-state estimate. For an off-policy Q-learning target,

so the loss over sampled experience tuples $(s,a,r,s^{\prime })$ becomes

Differentiating, and treating the target as a constant with respect to $\mathbf{w}$ — the gradient flows only through the predicted value $Q(s,a;\mathbf{w})$, never through the target — gives the update direction

Detaching the target matters. In supervised learning the labels are fixed constants; here the label is manufactured from the very network being optimized, so letting the gradient propagate through it optimizes a moving definition of correctness. Backpropagate through the prediction only.⁶

Why the naive version diverges

Assemble the obvious algorithm — a neural $Q$, the Q-learning target above, an $\epsilon$-greedy behavior policy, an MSE loss, and a step of RMSprop after each transition — and it will train for a while and then come apart. This is not a bug in the implementation; it is the deadly triad in its most dangerous configuration. All three ingredients are present: function approximation (a neural network), bootstrapping (the TD target), and off-policy training (the $\max$ learns the greedy policy while behavior explores). Any two are safe; all three can diverge. Two mechanisms cause the instability.⁷

The target is non-stationary. The regression target $y$ is computed from $Q(\cdot ;\mathbf{w})$, so every gradient step that changes $\mathbf{w}$ also changes the target for the next step. The network chases a value it is itself moving. Worse, because the approximator generalizes, updating $Q(s,a;\mathbf{w})$ drags the value of the next state $s^{\prime }$ along with it — and $s^{\prime }$ is precisely what the target for $(s,a)$ depends on. Improve the prediction and you spoil the target that defined improvement, which can spiral into divergence.

The data is not IID. Optimization methods assume samples are independent and identically distributed; online RL supplies the opposite. Consecutive transitions come from the same trajectory, so the sample at time $t+1$ is highly correlated with the one at $t$ — the network overfits to whatever local region of the state space the current episode is wandering through. And because the behavior policy keeps changing, the sample distribution drifts too, so the data is neither independent nor identically distributed.⁸ Both violations push the optimizer toward instability.

DQN's contribution is two mechanisms that repair exactly these two problems, and between them make deep value-based RL behave enough like supervised learning to train reliably.

Stabilizer one: experience replay

The fix for correlated, non-IID data is to stop training on the online stream. As the agent acts, it stores each transition $(s,a,r,s^{\prime })$ in a large replay buffer $D$; training then draws a mini-batch uniformly at random from $D$ rather than using the most recent transitions.⁹

Random sampling from a large buffer breaks the temporal correlation: a mini-batch now mixes transitions from many different trajectories and many past policies, so the updates look far more like draws from a fixed distribution — approximately IID, as the optimizer assumes. The second benefit is data efficiency: each transition can be sampled and learned from many times rather than being seen once and thrown away, which matters when interaction with the environment is the expensive part.

The gradient is unchanged in form; only the sampling distribution moves from the online stream to a uniform draw over the buffer, written $(s,a,r,s^{\prime })\sim \mathcal{U}(D)$:

Experience replay predates deep RL — Lin proposed it in 1992 — but pairing it with a neural Q-function is what enabled stable training from raw experience.⁹

Stabilizer two: the target network

Replay handles the data; it does nothing about the moving target. For that, DQN keeps a second copy of the network whose weights are frozen and used only to compute targets: the target network, with weights ${\mathbf{w}}^{-}$.¹⁰

The two networks share the same architecture; they differ only in the age of the weights. The online network $\mathbf{w}$ is the one we optimize on every step. The target network ${\mathbf{w}}^{-}$ is a snapshot of the online weights from up to $C$ steps ago, and it defines the target. The DQN gradient differs from the naive one in exactly one symbol — ${\mathbf{w}}^{-}$ where the target's parameters used to be $\mathbf{w}$:

Because ${\mathbf{w}}^{-}$ is fixed between refreshes, the target stops moving for $C$ steps at a time. Each such window is an ordinary, stationary regression problem: a fixed set of labels the online network can descend toward without the goalposts sliding. Every $C$ steps the labels are updated all at once and a new stationary problem is set. Freezing the target does not guarantee convergence to the optimum — that does not exist under nonlinear approximation — but it substantially reduces the risk of divergence, which is the actual failure mode.

How often to refresh depends on the problem. For a small control task like the cart-pole, copying every 10 to 20 steps works; for the convolutional networks used on Atari, the target is frozen for on the order of 10,000 steps. (Steps, not episodes — a common and costly confusion.) A softer variant, Polyak averaging, avoids the abrupt copy entirely: instead of ${\mathbf{w}}^{-}\leftarrow \mathbf{w}$ every $C$ steps, blend a little of the online weights into the target on every step,

so the target always lags but by a small, smoothly-shrinking gap rather than jumping in discrete leaps.¹¹

The full DQN algorithm

Replay and the target network are the two additions; everything else is standard value-based RL. The complete loop:

Two implementation details matter. Terminal states must be grounded to zero: when $s^{\prime }$ is terminal there is no future, so the target is just $r$, and forgetting this lets phantom future value leak in and destabilize training.⁶ And the network outputs a full vector of Q-values, so the prediction for the update is the entry $Q(s,a;\mathbf{w})$ at the action actually taken, gathered from that vector.

The original DQN paper (Mnih et al., 2013) introduced the replay buffer; the 2015 follow-up added the target network, and that two-mechanism version — sometimes called Nature DQN — is the one described above and the baseline every later improvement builds on.²

A minibatch of targets, worked end to end

Take $\gamma =0.99$ and a minibatch of four transitions sampled from the buffer. For each we need the frozen target network's Q-values at the next state $s^{\prime }$, the online network's prediction $Q(s,a;\mathbf{w})$ at the action actually taken, and a terminal flag. Suppose the target network reports these next-state values, and the online network these predictions:

The target for a non-terminal transition is $y=r+\gamma {\max }_{a^{\prime }}Q(s^{\prime },a^{\prime };{\mathbf{w}}^{-})$; for the terminal transition it is just $y=r$, with no bootstrap term. Reading down the table:

The minibatch loss is the mean squared TD error, $\frac{1}{4}{\sum }_i{\delta }_i^2=\frac{1}{4}(1.42^2+1.68^2+0.60^2+0.65^2)=\frac{1}{4}(2.02+2.82+0.36+0.42)=1.40$. The gradient for each transition is $-{\delta }_i{\nabla }_{\mathbf{w}}Q(s_i,a_i;\mathbf{w})$, so transitions 1 and 2 raise their predicted values (the target sat above the prediction) while 3 and 4 lower theirs. Two details this makes concrete: transition 3 shows the terminal grounding — had we bootstrapped a phantom $+\gamma \max Q$ there, $y_3$ would have carried future value the episode does not have, and that leak is a classic source of divergence. And every gradient flows only through the $Q(s,a;\mathbf{w})$ column; the target column is a constant, computed from ${\mathbf{w}}^{-}$ and detached.

The Atari architecture and results

The demonstration that made DQN famous is Sutton and Barto's chosen case study: a single agent, with no game-specific features, learning to play dozens of Atari 2600 games directly from pixels.¹² The setup is worth stating precisely, because its choices recur throughout deep RL.

Input. Each raw frame is $210\times 160$ pixels with 128 colors at 60 Hz. DQN preprocesses every frame down to an $84\times 84$ array of luminance values, then stacks the four most recent frames so the network input has dimension $84\times 84\times 4$. Stacking matters: a single frame does not reveal velocity or direction — is the ball rising or falling? — and four stacked frames restore enough of that to make the state approximately Markov.

Network. Three convolutional layers extract spatial features, followed by a fully-connected hidden layer and a linear output. Concretely: a first conv layer producing 32 feature maps of $20\times 20$, a second producing 64 of $9\times 9$, a third producing 64 of $7\times 7$, each with a ReLU nonlinearity; the $3,136$ units of the last conv layer feed a fully-connected layer of 512 units, which connects to up to 18 outputs — one Q-value per possible Atari action. This is the state-in, values-out design at scale.

Training choices. The reward is clipped to its sign — $+1$ when the game score rises, $-1$ when it falls, $0$ otherwise — so one step size works across games whose raw scores span wildly different scales. Behavior is $\epsilon$-greedy with $\epsilon$ decaying linearly over the first million frames and then held low. The optimizer is RMSprop over mini-batches of 32, and the TD error itself is clipped to $[-1,1]$, a further stabilizer on top of replay and the target network. The semi-gradient Q-learning update the paper uses is precisely the one derived above.

Results. The same architecture, the same hyperparameters, and the same raw pixel input were applied to 49 different games, with only the network weights reset per game.¹² Learning ran for 50 million frames per game — roughly 38 days of game experience. Measured against a professional human tester, DQN played at or above human level on 29 of the 46 games evaluated, and beat the best prior (linear, feature-engineered) reinforcement-learning systems on all but 6. What made it a landmark is the uniformity rather than any single score: one learning system, no per-game engineering, reaching human-competitive play across games as different as Breakout, Pong, and Space Invaders. The games it failed — Montezuma's Revenge, where DQN scored about as well as a random player — were the ones demanding long-horizon planning beyond what one-step Q-learning was built for, a gap later chapters take up. This lesson built the core value-based deep agent. The three refinements that make it the standard modern one — Double DQN for the maximization bias, dueling networks, and prioritized experience replay, plus the Rainbow agent that combines them — continue in DQN Improvements: Double, Dueling, and Prioritized Replay.