Improving DQN: Double, Dueling, Prioritised Replay and Rainbow

DQN opened deep RL, but it had clear weaknesses. Over the following years, researchers proposed a series of targeted improvements, each addressing a specific problem. In 2018, Hessel et al. combined six of them into Rainbow, which substantially outperformed each component alone on the Atari benchmark. Studying these ideas teaches you how to diagnose and fix learning algorithms.

1. Double DQN: fixing overestimation#

The target $\max_{a'}Q(s', a'; \theta^-)$ uses the same values to select and evaluate the best action. With noisy estimates, the max picks up positive noise — maximisation bias — and values are systematically overestimated. Van Hasselt, Guez and Silver (2016) decoupled selection and evaluation:

y = r + \gamma\,Q\Big(s',\; \arg\max_{a'}Q(s', a'; \theta);\; \theta^-\Big)

The online network selects the action; the target network evaluates it. A one-line change that reduces overestimation and improves scores on many games.

python

import torch

def double_dqn_target(q_online, q_target, r, s_next, done, gamma=0.99):
    with torch.no_grad():
        best = q_online(s_next).argmax(1, keepdim=True)          # select with online net
        next_q = q_target(s_next).gather(1, best).squeeze(1)     # evaluate with target net
        return r + gamma * (1 - done) * next_q

2. Prioritised experience replay#

Uniform sampling wastes updates on transitions the network already predicts well. Schaul et al. (2016) sample transitions with probability proportional to their TD error:

P(i) = \frac{p_i^\alpha}{\sum_kp_k^\alpha}, \qquad p_i = |\delta_i| + \epsilon

Non-uniform sampling biases the gradient, so updates are corrected with importance-sampling weights $w_i = (N\cdot P(i))^{-\beta}$, with $\beta$ annealed to 1. A sum-tree data structure makes sampling efficient. Prioritisation speeds learning considerably.

3. Dueling networks#

Wang et al. (2016) observed that in many states the choice of action barely matters (nothing is happening), while the state's value does. The dueling architecture splits the network into two streams — a state value $V(s)$ and advantages $A(s, a)$ — combined as

Q(s, a) = V(s) + \left(A(s, a) - \frac{1}{|\mathcal{A}|}\sum_{a'}A(s, a')\right)

Subtracting the mean advantage makes the decomposition identifiable. The value stream learns from every update, improving policy evaluation when many actions are similar.

4. Multi-step returns#

Use n-step targets $\sum_{k=0}^{n-1}\gamma^kr_{t+k+1} + \gamma^n\max_{a'}Q(s_{t+n}, a')$ to propagate rewards faster (typically $n = 3$). Rainbow's ablations found multi-step returns among the most important components.

5. Distributional RL (C51)#

Instead of predicting only the expected return, Bellemare, Dabney and Munos (2017) predicted the full distribution of returns, represented as probabilities over 51 fixed "atoms" (hence C51), trained with a distributional Bellman operator and a cross-entropy/KL loss after projecting the target distribution onto the atoms. Learning distributions gave richer training signals and better performance, even when acting only on the mean. Follow-ups (QR-DQN, IQN) represent distributions with quantiles. Distributional RL also supports risk-sensitive decisions.

6. Noisy networks for exploration#

ε-greedy explores the same way in every state. NoisyNets (Fortunato et al., 2018) add learned, parameterised noise to network weights:

y = (\boldsymbol{\mu}^w + \boldsymbol{\sigma}^w\odot\boldsymbol{\epsilon}^w)\mathbf{x} + \boldsymbol{\mu}^b + \boldsymbol{\sigma}^b\odot\boldsymbol{\epsilon}^b

The network learns how much to explore and can reduce noise where it is confident — state-dependent exploration.

Rainbow#

Combining Double Q-learning, prioritised replay, dueling networks, multi-step returns, distributional RL and noisy nets, Rainbow achieved much better median human-normalised performance than DQN and reached DQN's final performance with a fraction of the frames. Ablations showed prioritised replay and multi-step returns mattered most, followed by distributional learning.

Component	Problem addressed
Double DQN	Overestimation from max
Prioritised replay	Inefficient uniform sampling
Dueling	Poor value/advantage separation
Multi-step	Slow reward propagation
Distributional (C51)	Losing information by predicting only the mean
Noisy nets	Naive state-independent exploration

Beyond Rainbow#

Distributed agents (Ape-X, R2D2 with recurrent networks and many parallel actors), exploration bonuses (e.g. Random Network Distillation made progress on Montezuma's Revenge), and Agent57 (2020), the first agent to outperform the human baseline on all 57 Atari games, using adaptive exploration strategies. Model-based agents such as MuZero and later world-model agents pushed sample efficiency further.

#double dqn#dueling network#prioritized replay#rainbow#distributional rl

Written by

Janin A Apurba

B.Sc. in CSE, AUST · Advanced ICT Officer, CNRS-UNHCR. Teaching AI, ML and Deep Learning to the next generation of engineers and researchers.