Deep Q-Networks and Variants

"They handed me a screen full of pixels and a single number called reward, and said nothing else. I built a table to remember what every screen was worth, then ran out of memory somewhere around the fourth frame. So I learned to guess instead of remember, and the guessing is going rather well, thank you. I have now played this level eleven million times and I would like to keep going."

A Q-Network That Learned to Play From Pixels and Will Not Stop

In Section 24.5 we built tabular Q-learning: an agent that maintains a table $Q(s, a)$, one entry per state-action pair, and updates each entry toward a bootstrapped target using the temporal-difference rule. We proved it converges to the optimal action-value function $Q^\star$ under mild conditions, and we watched it solve small gridworlds exactly. We also flagged the limitation that this section exists to remove: the table has one row per state, so the method dies the moment the state space is large, continuous, or high-dimensional. A robot arm with continuous joint angles, an inventory controller with real-valued stock levels, an Atari game whose state is a screen of pixels: none of these has a finite, enumerable state set, and so none of them admits a table. The Markov decision process machinery of Chapter 22 still applies, the Bellman optimality equation still holds, but the representation must change. We use the unified notation of Appendix A throughout: $s$ the state, $a$ the action, $r$ the reward, $\gamma$ the discount factor, $\boldsymbol{\theta}$ the network parameters.

Why does function approximation deserve a chapter rather than a remark that "you just fit a network to the Q-values"? Because the very generalization that makes a network useful, the ability to share structure across similar states so that learning about one informs many, is what breaks the convergence guarantee of the tabular case. In a table, updating one cell touches exactly that cell; in a network, updating $\boldsymbol{\theta}$ to fix the estimate at one state shifts the estimate at every state, including the state that the bootstrap target was built from. The target moves while you chase it, the chase moves the target, and without care the whole process spirals. The history of value-based deep RL is the history of taming that feedback loop, and the two devices DQN introduced, replay and target networks, are the taming. The competencies this section installs are these: to state the Q-network loss and the deadly triad that threatens it; to explain precisely how experience replay and a target network restore stability; to name the bias each major variant corrects and how; and to implement DQN both from scratch and with a library, on a real control task, and read the learning curve. These are the load-bearing skills for the policy-gradient methods of Section 25.2 and everything in Chapter 26.

1. From Tabular Q-Learning to Function Approximation Beginner

The object every value-based method estimates is the optimal action-value function $Q^\star(s, a)$, the expected discounted return from taking action $a$ in state $s$ and acting optimally thereafter. It satisfies the Bellman optimality equation, the fixed-point identity that Chapter 22 derived:

Tabular Q-learning of Section 24.5 turns this identity into an update by treating the right-hand side as a target and nudging the stored estimate toward it: $Q(s, a) \leftarrow Q(s, a) + \alpha\,[\,r + \gamma \max_{a'} Q(s', a') - Q(s, a)\,]$. The bracketed quantity is the temporal-difference error, the same TD error that drove the forecasters of Chapter 9 in a supervised guise. The update is local: it changes one cell and leaves the rest of the table untouched, which is exactly why the convergence proof goes through and exactly why the method cannot scale.

Function approximation replaces the table with a parametric function. Instead of storing $Q(s, a)$ as a cell, we compute it as $Q(s, a; \boldsymbol{\theta})$, the output of a model with parameters $\boldsymbol{\theta}$. For a problem with a handful of discrete actions, the standard architecture is a network that takes the state $s$ as input and emits a vector of $|\mathcal{A}|$ action-values in one forward pass, one output unit per action, so that $\max_{a'} Q(s', a'; \boldsymbol{\theta})$ is a single cheap maximum over the output vector rather than a loop of forward passes. The table was a special case: a one-hot encoding of the state fed into a linear layer with no sharing recovers exactly the lookup table. Every other choice of features or architecture introduces sharing, and sharing is generalization. Figure 25.1.1 contrasts the two representations.

The obvious algorithm is to keep the TD update and fit the network to the bootstrapped target by gradient descent: define a target $y = r + \gamma \max_{a'} Q(s', a'; \boldsymbol{\theta})$, treat it as a regression label, and take a gradient step on the squared error $(y - Q(s, a; \boldsymbol{\theta}))^2$. This is naive online Q-learning with a function approximator, and run exactly as stated it frequently diverges: the loss climbs, the Q-values blow up, the policy collapses. Understanding why is the whole point of the next subsection, and it is the reason DQN needed two extra ideas rather than zero.

The mechanism of divergence has a name. Sutton and Barto identify three properties whose combination is dangerous: bootstrapping (the target $y$ is built from the network's own current estimate of the next state's value, not from a true label), off-policy learning (the data is generated by a behavior policy, often an old or exploratory one, that differs from the greedy policy being evaluated), and function approximation (errors at one state leak to others through shared parameters). Any one or two of these is benign; all three together form the deadly triad, and their interaction is what lets the squared TD loss send the Q-values to infinity. DQN does not remove any leg of the triad, value-based deep RL needs all three, it makes the combination survivable, which is the subject of subsection two.

2. The Two Stabilizers: Experience Replay and a Target Network Intermediate

DQN keeps the squared TD loss and adds two devices that each defuse a different leg of the deadly triad. The first attacks the correlation and off-policy problems; the second attacks the moving-target problem of bootstrapping. Together they turn the diverging procedure of subsection one into one that reliably learns.

Experience replay. Rather than train on each transition the instant it occurs and then discard it, the agent stores every transition $(s, a, r, s', \text{done})$ in a large circular buffer, the replay memory, and trains on minibatches sampled uniformly at random from that buffer. This does two things. It breaks the strong temporal correlation between consecutive samples, because successive frames of a trajectory are nearly identical and training on them in order makes the gradient updates highly correlated, which destabilizes stochastic gradient descent. And it reuses each transition many times, so the sample efficiency improves: an expensive interaction with the environment contributes to many updates rather than one. The buffer also smooths the data distribution, averaging over many behavior policies rather than tracking the latest one, which softens the off-policy leg of the triad.

Target network. The bootstrapped target $y = r + \gamma \max_{a'} Q(s', a'; \boldsymbol{\theta})$ depends on the same parameters $\boldsymbol{\theta}$ we are updating, so every gradient step moves the target. DQN breaks this loop by computing the target with a separate, frozen copy of the network, the target network with parameters $\boldsymbol{\theta}^-$, that is held fixed for many steps and only periodically synchronized to the online network. The target becomes $y = r + \gamma \max_{a'} Q(s', a'; \boldsymbol{\theta}^-)$, a stable regression label for the duration of the freeze, so the online network chases a stationary objective the way ordinary supervised learning does. Every $C$ steps (or via a slow Polyak average $\boldsymbol{\theta}^- \leftarrow \tau\boldsymbol{\theta} + (1-\tau)\boldsymbol{\theta}^-$) the frozen copy is refreshed. The DQN loss minimized at each step is therefore

where $\mathcal{D}$ is the replay buffer and $\boldsymbol{\theta}^-$ is held constant when the gradient with respect to $\boldsymbol{\theta}$ is taken (the target is a constant, not differentiated through, the deep-RL analogue of the detach we used for truncation in Section 9.3). For terminal transitions the bootstrap term is dropped, $y = r$, because there is no next state. Figure 25.1.2 traces the data flow through both stabilizers.

The two devices are complementary, not redundant. Replay fixes the input side: it controls which samples the gradient sees and in what order, breaking correlation and recycling data. The target network fixes the label side: it controls what the samples are trained toward, freezing the bootstrap so the objective stops moving. Remove replay and the gradient updates correlate and the data distribution chases the latest policy; remove the target network and the regression target moves under every step and the values can diverge. DQN needed both because the deadly triad attacks from both sides at once.

3. The Variants That Fixed DQN's Biases Intermediate

Vanilla DQN works but has specific, diagnosable defects, and a sequence of papers each isolated one defect and fixed it with a small change. Knowing the defect each variant targets is more useful than memorizing the variant, because the defects recur throughout value-based RL.

Double DQN (van Hasselt, Guez, Silver, 2016) corrects an overestimation bias. The $\max$ in the target both selects and evaluates the next action with the same estimates, and because the estimates are noisy, the max systematically picks the action whose value was overestimated by noise, inflating the target. Double DQN decouples selection from evaluation: the online network chooses the next action, the target network evaluates it, $y = r + \gamma\, Q\big(s', \arg\max_{a'} Q(s', a'; \boldsymbol{\theta}); \boldsymbol{\theta}^-\big)$. The selecting network and the evaluating network rarely overestimate the same action, so the upward bias shrinks, and the change is a one-line edit to the target.

Dueling DQN (Wang et al., 2016) changes the architecture to split the action-value into a state-value stream $V(s)$ and an advantage stream $A(s, a)$, recombined as $Q(s, a) = V(s) + \big(A(s, a) - \tfrac{1}{|\mathcal{A}|}\sum_{a'} A(s, a')\big)$. The motivation is that in many states the choice of action barely matters, what matters is whether the state itself is good, and the dueling head learns $V(s)$ once and shares it across all actions rather than relearning the state's worth inside every action's value. It improves learning where actions are near-equivalent.

Prioritized Experience Replay (Schaul et al., 2016) fixes the wastefulness of uniform sampling: most transitions are already well-predicted and carry little learning signal, while a few high-TD-error transitions carry a lot. PER samples a transition with probability proportional to its TD-error magnitude (raised to a power), so the network revisits its biggest mistakes more often, with an importance-sampling correction to undo the bias the non-uniform sampling introduces. It speeds learning substantially on many tasks.

n-step returns trade bias for variance in the target by bootstrapping after $n$ real rewards instead of one: $y = \sum_{i=0}^{n-1} \gamma^i r_{t+i} + \gamma^n \max_{a'} Q(s_{t+n}, a'; \boldsymbol{\theta}^-)$. A larger $n$ propagates reward information faster and leans less on the bootstrap, at the cost of more variance and a mild off-policy bias over the multi-step window. Rainbow (Hessel et al., 2018) is the integration: it combines Double, Dueling, PER, multi-step returns, distributional value learning (C51), and noisy-network exploration into one agent, and the ablation in that paper shows each component contributes, with prioritized replay and multi-step returns the largest individual gains. Rainbow was for years the standard strong baseline for value-based Atari. Figure 25.1.3 summarizes the defect each variant targets.

4. DQN for Temporal and Operational Control Intermediate

Atari made DQN famous, but the algorithm's natural home in this book is the family of temporal operational control problems with a modest number of discrete actions, which recur across the application chapters. The defining shape is a system that evolves over time under a controller's discrete choices, where each choice earns a reward and the goal is to maximize cumulative discounted reward over a horizon. DQN fits whenever the action set is small and discrete and the state, however high-dimensional or continuous, can be fed to a network.

Three recurring operational settings illustrate the fit. In energy and grid control (the energy series of Chapter 29 and the applications of Chapter 35), a battery controller chooses among discrete charge, hold, and discharge actions each interval to arbitrage price and smooth load, with state comprising the current charge, recent prices, and a demand forecast. In inventory and supply control, a manager picks a discrete reorder quantity each period under stochastic demand, the classic operational MDP. In traffic and resource scheduling, a controller selects among a few signal phases or job-dispatch actions to minimize delay. Each is a sequential decision problem with a small discrete action set and a rich temporal state, exactly DQN's regime.

The connection to the temporal thread of this book is direct. The state of an operational controller is almost never a single instantaneous reading; it is a window of recent history, a short time series, because the right action depends on trend and context, not just the current value. So the network that computes $Q(s, a; \boldsymbol{\theta})$ frequently begins with a temporal encoder, the recurrent cells of Chapter 10, the temporal convolutions of Chapter 11, or the attention of Chapter 12, that summarizes the recent window into a state representation, on top of which the DQN head predicts action-values. Value-based deep RL is therefore not a departure from the rest of the book but a continuation: the temporal representation learners of Part III become the perception front-end, and DQN becomes the decision head. When the state is only partially observable, a window or a recurrent state is what restores the Markov property, the bridge to the POMDPs of Chapter 23.

5. Worked Example: DQN From Scratch and With a Library on CartPole Advanced

We now make the whole algorithm executable on a standard gymnasium control task, CartPole, where the agent pushes a cart left or right to balance a pole and earns one reward per timestep it stays upright (episode capped at 500). The state is a four-dimensional continuous vector, so a table is already impossible and a tiny network suffices. The plan is the same demonstration of correctness we used elsewhere in the book: build a minimal DQN from scratch with an explicit replay buffer, target network, and training step, then reproduce it with stable-baselines3 in a few lines, and plot both learning curves. Code 25.1.1 is the from-scratch replay buffer and Q-network.

import random, collections
import numpy as np
import torch
import torch.nn as nn
import torch.nn.functional as F
import gymnasium as gym

Transition = collections.namedtuple("Transition", "s a r s2 done")

class ReplayBuffer:
    """Circular buffer of transitions; sample() returns a decorrelated minibatch."""
    def __init__(self, capacity=50_000):
        self.buf = collections.deque(maxlen=capacity)   # old transitions drop out
    def push(self, *args):
        self.buf.append(Transition(*args))
    def sample(self, batch):
        xs = random.sample(self.buf, batch)             # UNIFORM random -> decorrelate
        s  = torch.tensor(np.array([t.s  for t in xs]), dtype=torch.float32)
        a  = torch.tensor([t.a    for t in xs], dtype=torch.int64).unsqueeze(1)
        r  = torch.tensor([t.r    for t in xs], dtype=torch.float32).unsqueeze(1)
        s2 = torch.tensor(np.array([t.s2 for t in xs]), dtype=torch.float32)
        d  = torch.tensor([t.done for t in xs], dtype=torch.float32).unsqueeze(1)
        return s, a, r, s2, d
    def __len__(self):
        return len(self.buf)

class QNet(nn.Module):
    """Maps a state to one Q-value per action in a single forward pass."""
    def __init__(self, n_obs, n_act):
        super().__init__()
        self.net = nn.Sequential(
            nn.Linear(n_obs, 128), nn.ReLU(),
            nn.Linear(128, 128),   nn.ReLU(),
            nn.Linear(128, n_act))                       # one output unit per action
    def forward(self, x):
        return self.net(x)

Code 25.1.2 is the training loop: it instantiates an online and a target network, runs $\epsilon$-greedy episodes filling the buffer, and at each step performs one gradient update on the squared TD loss with the frozen target, syncing the target network every target_sync steps. This is the loss equation of subsection two turned into code, with the target detached exactly as discussed.

def train_dqn(episodes=400, gamma=0.99, batch=128, target_sync=500):
    env = gym.make("CartPole-v1")
    n_obs, n_act = env.observation_space.shape[0], env.action_space.n
    online, target = QNet(n_obs, n_act), QNet(n_obs, n_act)
    target.load_state_dict(online.state_dict())          # start identical
    opt = torch.optim.Adam(online.parameters(), lr=1e-3)
    buf = ReplayBuffer()
    eps, step, returns = 1.0, 0, []

    for ep in range(episodes):
        s, _ = env.reset(); done = False; ep_ret = 0.0
        while not done:
            if random.random() < eps:                    # epsilon-greedy exploration
                a = env.action_space.sample()
            else:
                with torch.no_grad():
                    a = int(online(torch.tensor(s, dtype=torch.float32)).argmax())
            s2, r, term, trunc, _ = env.step(a); done = term or trunc
            buf.push(s, a, r, s2, float(term))           # store transition
            s = s2; ep_ret += r; step += 1
            eps = max(0.05, eps * 0.995)                 # anneal exploration

            if len(buf) >= 1000:                         # learn once warmed up
                bs, ba, br, bs2, bd = buf.sample(batch)
                q = online(bs).gather(1, ba)             # Q(s,a) for actions taken
                with torch.no_grad():                    # target is a CONSTANT label
                    q_next = target(bs2).max(1, keepdim=True).values
                    y = br + gamma * q_next * (1 - bd)    # drop bootstrap if terminal
                loss = F.smooth_l1_loss(q, y)            # Huber on the TD error
                opt.zero_grad(); loss.backward(); opt.step()
                if step % target_sync == 0:              # freeze/refresh the target net
                    target.load_state_dict(online.state_dict())
        returns.append(ep_ret)
    env.close()
    return returns

scratch_returns = train_dqn()
print("from-scratch DQN: mean return over last 50 ep = %.1f" % np.mean(scratch_returns[-50:]))

from-scratch DQN: mean return over last 50 ep = 463.2

Now the library equivalent. Code 25.1.3 trains the same task with stable-baselines3, whose DQN class implements the replay buffer, target network, $\epsilon$-greedy schedule, Huber loss, and target syncing internally. The entire ninety-line apparatus of Code 25.1.1 and 25.1.2 collapses to roughly three lines of model construction and a single learn call.

from stable_baselines3 import DQN
from stable_baselines3.common.evaluation import evaluate_policy
import gymnasium as gym

env = gym.make("CartPole-v1")
model = DQN("MlpPolicy", env, learning_rate=1e-3, buffer_size=50_000,
            target_update_interval=500, exploration_fraction=0.2, verbose=0)
model.learn(total_timesteps=100_000)                     # buffer, target net, TD loss: all internal

mean_ret, std_ret = evaluate_policy(model, env, n_eval_episodes=50)
print("stable-baselines3 DQN: mean return = %.1f +/- %.1f" % (mean_ret, std_ret))

stable-baselines3 DQN: mean return = 481.6 +/- 38.4

Read the three code blocks together. Code 25.1.1 built the replay buffer and Q-network; Code 25.1.2 wired them into the exact loss of subsection two with a frozen target and decorrelated samples, and the agent learned; Code 25.1.3 reproduced the same result with a library in a fraction of the code. The pedagogical payoff is that DQN is not a black box: the stabilizers you can implement by hand in two short classes are precisely what the production library does internally, and once you have seen the from-scratch version, the library's hyperparameters read as exactly the knobs of subsection two.

Exercises

1. Conceptual. Name the three legs of the deadly triad and, for each of experience replay and the target network, state which leg (or legs) it primarily defuses and by what mechanism. Then explain why removing the target network but keeping replay can still let the Q-values diverge, referring to the moving-target argument of subsection two.
2. Implementation. Modify the from-scratch training loop of Code 25.1.2 to use a Double DQN target: have the online network select the next action with argmax and the target network evaluate it, $y = r + \gamma\, Q(s', \arg\max_{a'} Q(s', a'; \boldsymbol{\theta}); \boldsymbol{\theta}^-)$. Train both the original and the Double-DQN version on CartPole, log the mean predicted $Q(s,a)$ over a fixed batch of held-out states across training, and verify that the Double-DQN curve sits below the vanilla one, the overestimation reduction of subsection three made visible.
3. Open-ended. Take one operational control problem from subsection four (battery arbitrage, inventory reorder, or traffic-signal control), define its state as a temporal window, its small discrete action set, and a reward, and sketch a DQN whose front-end is a temporal encoder from Part III (an RNN from Chapter 10 or a TCN from Chapter 11). Discuss which DQN variant you would add first and why, and what failure mode of the deadly triad you most expect to see on autocorrelated operational data.