Pearl
Lab

Chapter 05 · Value-based deep RL

Q-learning & Deep Q-Networks

Abstract. Q-learning is off-policy TD control: it learns \(Q^*\) while behaving with any exploratory policy, by bootstrapping from \(\max_{a'}Q(s',a')\). This chapter develops tabular Q-learning carefully (update, convergence conditions, maximisation bias), then explains why a literal neural substitution \(Q(s,a;\theta)\) is unstable. The Deep Q-Network (DQN) stabilises that substitution with two ideas — experience replay and a lagged target network — which we derive as responses to specific failure modes. We then cover Double DQN, dueling architectures, prioritised replay, and the Rainbow stack. The laboratory implements tabular Q-learning with optional replay and target freezes so you can watch the DQN machinery operate without a GPU.

1. Overview

Chapter 04 introduced Q-learning as the off-policy sibling of SARSA. Here we slow down and go deep: first the tabular algorithm as a stochastic approximation of the Bellman optimality operator, then the engineering that made the same idea work with deep networks on Atari (Mnih et al., 2013/2015).

Historically this is the hinge between “textbook RL” and “deep RL.” Everything that follows in the value-based line — Double DQN, PER, Rainbow, C51, QR-DQN — patches a pathology of the basic DQN recipe. The actor–critic / policy-gradient line (next chapters) is a different response to related instability.

2. Tabular Q-learning

Definition 2.1 · Q-learning update

After observing transition \((s_t,a_t,r_{t+1},s_{t+1})\), \[ Q(s_t,a_t) \leftarrow Q(s_t,a_t) + \alpha_t \Big( r_{t+1} + \gamma \max_{a'} Q(s_{t+1},a') - Q(s_t,a_t) \Big), \] with the understanding that \(\max_{a'}Q(s_{t+1},a')=0\) if \(s_{t+1}\) is terminal.

The quantity in parentheses is the TD error for the optimality backup:

(1) \[ \delta_t = r_{t+1} + \gamma \max_{a'} Q(s_{t+1},a') - Q(s_t,a_t). \]

Compare to the Bellman optimality equation (Chapter 02):

(2) \[ Q^*(s,a) = \mathbb{E}\!\left[ r + \gamma \max_{a'} Q^*(s',a') \,\middle|\, s,a \right]. \]

Q-learning is a sample backup of (2): one realised \((r,s')\) stands in for the expectation over \(P\), and the current table stands in for \(Q^*\). Behavior policy \(\beta\) (often \(\varepsilon\)-greedy w.r.t. \(Q\)) only decides which \((s,a)\) pairs are sampled; the target always points at the greedy/optimal backup.

2.1 Pseudocode

Initialize Q(s,a) arbitrarily; Q(terminal,·)=0
For each episode:
  Initialize s
  While s is not terminal:
    a ← behavior(s)          # e.g. ε-greedy(Q)
    Take a, observe r, s'
    Q(s,a) ← Q(s,a) + α [ r + γ max_a' Q(s',a') − Q(s,a) ]
    s ← s'

2.2 Greedy readout

At test time (and inside the target), \(\pi(s)\in\arg\max_a Q(s,a)\). No model of \(P\) is required — that is why Q-learning is the canonical model-free control algorithm for discrete actions.

3. Convergence (tabular)

Theorem 3.1 · Watkins & Dayan (informal)

In a finite MDP with bounded rewards, discount \(\gamma\in[0,1)\), learning rates satisfying \(\sum_t \alpha_t(s,a)=\infty\) and \(\sum_t \alpha_t(s,a)^2 < \infty\) for every pair \((s,a)\) visited, and every pair visited infinitely often, \(Q_t \to Q^*\) with probability 1.

Proof idea: cast the update as a noisy contraction toward the unique fixed point of \(\mathcal{T}^*\). The max operator is a non-expansion in \(\|\cdot\|_\infty\); multiplied by \(\gamma\) it becomes a contraction. Stochastic approximation theory then gives almost-sure convergence under the step-size and visitation conditions.

Two practical corollaries:

  1. You must keep exploring forever (or long enough) — fixed \(\varepsilon>0\), or decaying \(\varepsilon\), or visiting schedules.
  2. The result is for tables. It does not automatically transfer to neural \(Q_\theta\).

4. The \(\max\) operator and overestimation

Let \(\hat Q(s',a') = Q^*(s',a') + \epsilon_{a'}\) with zero-mean noise. Then

(3) \[ \mathbb{E}\big[\max_{a'}\hat Q(s',a')\big] \;\ge\; \max_{a'}\mathbb{E}\big[\hat Q(s',a')\big] = \max_{a'} Q^*(s',a'). \]

Jensen’s inequality for the convex \(\max\) function: noisy estimates make \(\max_{a'}\hat Q\) optimistically biased. Q-learning inherits that bias in every bootstrap. In tables with enough visits the noise dies and the bias vanishes asymptotically; early in learning — and chronically with function approximation — overestimation can pick wrong actions and destabilise updates.

Double Q-learning (van Hasselt, 2010) and Double DQN (Section 10) decorrelate action selection from action evaluation to reduce this bias.

Analysis · SARSA vs Q-learning (reprise)

SARSA’s target \(\gamma Q(s',a')\) with \(a'\sim\pi_\varepsilon\) does not take a hard max over noisy estimates in the same way, and evaluates the exploring policy. Q-learning’s hard max is exactly what buys off-policy optimality — and exactly what invites overestimation. There is no free lunch in that design choice.

5. Why naïve deep Q-learning fails

Replace the table by a neural network \(Q(s,a;\theta)\) and minimise \(\big(r+\gamma\max_{a'}Q(s',a';\theta)-Q(s,a;\theta)\big)^2\) by gradient descent on the same \(\theta\) that appears in the target. Three pathologies hit at once:

  1. Correlated samples. Consecutive Atari frames (or robot steps) are highly dependent. SGD assumes roughly i.i.d. minibatches; online updates chase a moving, correlated stream and overfit the recent trajectory.
  2. Non-stationary targets. The bootstrap target depends on \(\theta\). Every gradient step moves the target. Optimising a regression problem whose labels move with the weights is unstable — especially with a flexible approximator.
  3. Deadly triad. Function approximation + bootstrapping + off-policy sampling (Chapter 04) has no general convergence guarantee; divergence is possible.

DQN’s two headline fixes address (1) and (2) directly. The triad is mitigated, not eliminated — hence later tricks and the rise of on-policy deep policy gradients.

6. Experience replay

Definition 6.1 · Replay buffer

Store transitions \((s,a,r,s',\mathrm{done})\) in a buffer \(\mathcal{D}\) of capacity \(N\) (FIFO). Each learning step, draw a minibatch of size \(B\) uniformly (or by priority — Section 11) and perform a gradient update on that minibatch.

Why it helps:

  • Breaks temporal correlation — random minibatches mix distant experiences.
  • Data efficiency — each transition is reused many times (off-policy learning makes this valid in principle).
  • Smooths learning — averages over a broader state distribution than the current episode.

Cost: the buffer’s distribution lags the current policy (old exploratory data). Extreme policy shifts can make old data off-policy in a harmful way; in practice large buffers and slow \(\varepsilon\) schedules keep this manageable for DQN-style discrete control.

Remark · Why SARSA rarely uses huge replay

SARSA is on-policy: the target uses \(a'\sim\pi_{\mathrm{current}}\). Replaying old \((s,a,a')\) under a new \(\pi\) is incorrect without importance sampling. Q-learning’s \(\max\) target does not need the behavior’s next action — replay fits naturally.

7. Target networks

Introduce a second network \(Q(s,a;\theta^-)|\) whose weights \(\theta^-\) are a lagged copy of \(\theta\). The TD target becomes

(4) \[ y_t = r_{t+1} + \gamma \max_{a'} Q(s_{t+1}, a'; \theta^-). \]

Online network \(\theta\) is trained to match \(y_t\); \(\theta^-\) is held fixed for \(C\) steps (hard update: \(\theta^- \leftarrow \theta\)) or tracked slowly (soft / Polyak: \(\theta^- \leftarrow \tau\theta + (1-\tau)\theta^-\)).

Intuition: freeze the bootstrap bootstrap source so the regression target is a slowly moving “label generator.” You still bootstrap, but not into a target that jitters every minibatch.

Design note

Hard updates every \(C\in[10^3,10^4]\) steps were used in the original DQN paper. Soft updates with small \(\tau\) (e.g. \(0.005\)) are common in continuous-control cousins (DDPG/TD3/SAC). Both implement the same idea: target lag.

8. The DQN algorithm (Mnih et al.)

Putting the pieces together for Atari-scale discrete control: 

Initialize online Q_θ, target Q_θ⁻ ← Q_θ, replay D
For step t = 1, 2, …:
  With prob ε: a_t ~ Uniform(A); else a_t = argmax_a Q(s_t,a; θ)
  Execute a_t, observe r_t, s_{t+1}, done
  Store (s_t, a_t, r_t, s_{t+1}, done) in D
  Sample minibatch {(s_j,a_j,r_j,s_j',d_j)} from D
  y_j = r_j + γ (1−d_j) max_a' Q(s_j', a'; θ⁻)
  Gradient descent on (1/B) Σ_j (y_j − Q(s_j,a_j; θ))²
  Every C steps: θ⁻ ← θ
  Decay ε

State preprocessing in Atari (for completeness): grayscale, downsample, stack the last 4 frames (approximate Markov state — Chapter 01), reward clipping to \(\{−1,0,+1\}\) for stability across games.

Architecture sketch

Classic DQN CNN: conv layers over the frame stack → fully connected → \(|A|\) outputs (one Q-value per action). Evaluating \(\arg\max_a Q(s,a)\) is one forward pass. This output layout is why DQN wants discrete actions; continuous \(A\) needs actor–critic / DPG instead.

9. Loss, gradients, and training details

(5) \[ \mathcal{L}(\theta) = \mathbb{E}_{(s,a,r,s')\sim\mathcal{D}} \Big[ \big( r + \gamma \max_{a'} Q(s',a';\theta^-) - Q(s,a;\theta) \big)^2 \Big]. \]

Important implementation subtleties:

  • Stop-gradient on \(y\). Treat \(y=r+\gamma\max Q_{\theta^-}\) as a constant w.r.t. \(\theta\). Do not backprop through the target network (or through \(\max\) into \(\theta^-\)).
  • Huber loss (Smooth L1) is often used instead of pure MSE to reduce the effect of large TD errors.
  • Gradient clipping and careful learning rates (Adam/RMSProp) matter; DQN is famously hyperparameter-sensitive.
  • Terminal masking: multiply the bootstrap by \((1-\mathrm{done})\).
(6) \[ \nabla_\theta \mathcal{L} \approx -\,\mathbb{E}\Big[ \delta\, \nabla_\theta Q(s,a;\theta) \Big], \qquad \delta = y - Q(s,a;\theta). \]

Same structural form as tabular \(Q \leftarrow Q + \alpha\delta\), with \(\nabla_\theta Q\) generalising the “indicator of cell \((s,a)\)”.

10. Double DQN

Standard DQN uses the target network for both selecting and evaluating the max: \(\max_{a'}Q(s',a';\theta^-)\). Double DQN (van Hasselt et al., 2016) uses the online net to select and the target net to evaluate:

(7) \[ y = r + \gamma\, Q\!\left( s',\, \arg\max_{a'} Q(s',a';\theta),\, \theta^- \right). \]

Selection can still be optimistic, but evaluation uses a different set of weights, cutting the systematic overestimation that a single noisy \(\max\) produces. Empirically this improves value accuracy and often policies on Atari.

11. Dueling networks & prioritised replay

11.1 Dueling architecture

Factor \(Q\) into a state-value stream \(V(s)\) and an advantage stream \(A(s,a)\):

(8) \[ Q(s,a) = V(s) + \Big( A(s,a) - \tfrac{1}{|A|}\sum_{a'} A(s,a') \Big). \]

The subtraction identifies \(Q\) (otherwise \(V\) and \(A\) are unidentifiable up to a constant). Benefit: the network can learn which states are valuable even when the action does not matter much — useful when many actions have similar outcomes.

11.2 Prioritised Experience Replay (PER)

Sample transitions with probability proportional to TD-error magnitude \(p_i \propto |\delta_i|^\omega\), then correct the bias with importance-sampling weights \(w_i = (N\cdot P(i))^{-\beta}\). Idea: replay surprising transitions more often. Hyperparameters \(\omega,\beta\) anneal during training.

12. Rainbow and the wider family

Rainbow (Hessel et al., 2018) combines: Double DQN, dueling, PER, multi-step returns, distributional RL (C51 — learn a distribution over returns, not a scalar mean), and noisy nets (learned exploration instead of \(\varepsilon\)-greedy). Ablations showed distributional RL, multi-step, and PER among the largest gains.

Further lines: QR-DQN / IQN (quantile distributions), Rainbow variants, and model-based extensions. For continuous actions the value-based \(\arg\max\) story ends — DDPG/TD3/SAC take over with actor networks (later chapters).

DQN
Replay + target net + CNN Q.
DDQN
Decouple select / evaluate to cut overestimation.
Rainbow
Stack of orthogonal improvements on the DQN skeleton.

13. Laboratory · Q-learning with DQN machinery

Same 4×8 cliff as Chapter 04, but now you can toggle replay and a target table (tabular stand-in for \(\theta^-\)). This is not a neural net — it is the algorithmic skeleton of DQN made inspectable: correlated online updates vs shuffled replay, and bootstrapping from a lagged \(Q^-\) vs from live \(Q\).

Tabular DQN-style control

Replay · target lag · Double option
Machinery
Hyperparameters
Run

Online Q · greedy

Target Q⁻ · max

Episodes0
Updates0
Buffer0
Avg |δ|—
Last G—
Avg G₂₀—
Syncs0
Overest. proxy—

Ledger

Enable replay + target, run episodes. Compare online vs Q⁻ grids; watch buffer size and sync count.

14. Worked calculations

14.1 One Q-learning step

\(Q(s,a)=0.5\), \(\alpha=0.1\), \(\gamma=0.99\), \(r=1\), next Q-values \((2.0, 2.4, 1.1)\). Then \(\max=2.4\), \(\delta=1+0.99\cdot 2.4-0.5=2.876\), \(Q\leftarrow 0.5+0.1\cdot 2.876=0.7876\).

14.2 Double target vs vanilla

Online Q at \(s'\): \((5.0, 4.0)\). Target Q⁻: \((3.0, 4.5)\). Vanilla DQN target uses \(\max Q^-=4.5\). Double DQN selects \(\arg\max Q_{\mathrm{online}}=a_0\), evaluates \(Q^-(s',a_0)=3.0\). Same state, different bootstrap — Double is less optimistic here.

  1. Vanilla y = r + γ max_a' Q⁻(s',a').
  2. Double: a* = argmax_a Q(s',a;θ), y = r + γ Q(s',a*;θ⁻).
  3. Example: max Q⁻=4.5 but Q⁻(a*)=3.0 → lower target.
  4. Replay: store (s,a,r,s',done); sample i.i.d.-ish minibatches.
  5. Every C updates: θ⁻ ← θ (hard sync), or soft Polyak.
  6. Loss L = E[(y − Q_θ(s,a))²] with y stop-grad.

15. What follows

Q-learning + DQN dominate discrete action spaces. Continuous control needs a different story: policy gradients and actor–critics (REINFORCE → A2C → TRPO/PPO) or deterministic policy gradients (DDPG/TD3) and entropy-regularised soft Q-learning (SAC). Those chapters come next.

See also

  • Mnih et al., 2015 — Human-level control through deep RL (DQN Nature paper).
  • van Hasselt et al., 2016 — Deep Reinforcement Learning with Double Q-learning.
  • Hessel et al., 2018 — Rainbow.
  • Chapter 04 — TD, SARSA, deadly triad.

Previous

← Temporal-Difference Learning

Next chapter

Policy Gradients

REINFORCE, baselines, actor–critic — leave argmax_a Q behind.

Continue →