VerifiedarXiv:1710.0229830 min
Reinforcement learning · Atari

Rainbow DQN: Combining Improvements in Deep Reinforcement Learning

Six published improvements to DQN, combined in one agent, raise its median Atari score from 79% to 223% of a human expert's.

Rainbow adds double Q-learning, prioritized replay, a dueling network, multi-step returns, distributional value learning and noisy-network exploration to DQN, fits them into a single loss, and then removes each one in turn to measure what it contributed.

Explaining the paperRainbow: Combining Improvements in Deep Reinforcement LearningHessel, Modayil, van Hasselt, Schaul, Ostrovski, Dabney, Horgan, Piot, Azar, Silver · AAAI 2018 · arXiv:1710.02298 ↗

A 2017 DeepMind paper that proposes no new mechanism. It shows how six earlier ones fit together, tunes one hyper-parameter sheet for all 57 games, and matches DQN's final score after 7M of the 200M training frames.

Between 2015 and 2017, DeepMind researchers published a series of extensions to DQN, the network that learned to play Atari games from pixels. Each targeted one weakness and was tested against a DQN baseline. A few had been combined (prioritized replay and the dueling network were each published on top of double Q-learning, and the dueling paper also tried prioritized replay), but nobody had put all six in one agent, so it was unknown whether their gains would add up or cancel. Matteo Hessel and nine coauthors at DeepMind did that, called the result Rainbow, and evaluated it on the 57-game Atari benchmark.

The page follows the paper's order. It first sets up DQN and its loss, then takes the six extensions one at a time, each with the problem it fixes and the equation it changes:

  1. double Q-learning, against the upward bias of the max in the target;
  2. prioritized replay, to replay surprising transitions more often;
  3. the dueling network, which splits a state's value from each action's advantage;
  4. multi-step returns, to move reward information backward several steps per update;
  5. distributional RL, which predicts the whole distribution of returns instead of its mean;
  6. Noisy Nets, which explore by sampling noise in the weights instead of taking random actions.

Then it assembles the combined loss, with a code listing of one update, and reads the results and the ablations.

What DQN does

An agent interacts with an environment in discrete steps. At step tt it observes a state StS_t, picks an action AtA_t, and receives a reward Rt+1R_{t+1}, a discount γt+1\gamma_{t+1} and the next state St+1S_{t+1}. In the Atari experiments the discount is 0.99 on every step and 0 when an episode ends. The agent wants to maximise the discounted return, the sum of future rewards with each one shrunk by the product of the discounts before it:

Gt=∑k=0∞γt(k)Rt+k+1,γt(k)=∏i=1kγt+iG_t = \sum_{k=0}^{\infty} \gamma_t^{(k)} R_{t+k+1}, \qquad \gamma_t^{(k)} = \prod_{i=1}^{k} \gamma_{t+i}Gt=∑k=0∞γt(k)Rt+k+1,γt(k)=∏i=1kγt+i\begin{gathered} G_t = \sum_{k=0}^{\infty} \gamma_t^{(k)} R_{t+k+1}, \\ \gamma_t^{(k)} = \prod_{i=1}^{k} \gamma_{t+i} \end{gathered}

With γ=0.99\gamma = 0.99, a reward 100 steps away counts 0.99100≈0.370.99^{100} \approx 0.37 as much as one received now. Writing the discount as a product lets one formula handle episode ends: once a discount of 0 appears, every later reward is multiplied by 0.

A value-based agent learns q(s,a)q(s, a), the expected return from taking action aa in state ss and acting well afterwards, and then acts by taking the action with the largest qq. DQN represents qq with a convolutional network. The input is the last 4 game frames, converted to grey and downsampled to 84 by 84 pixels, so a state is a tensor of shape 4 × 84 × 84. Three convolutional layers (32, 64 and 64 channels) feed a 512-unit hidden layer and an output layer with one number per action; Atari games have between 3 and 18 legal actions. DQN explores with ϵ\epsilon-greedy: with probability ϵ\epsilon it takes a random action instead of the best one.

Every step is stored as a transition (St,At,Rt+1,γt+1,St+1)(S_t, A_t, R_{t+1}, \gamma_{t+1}, S_{t+1}) in a replay memory that holds the last million transitions. Every 4 steps DQN samples 32 transitions uniformly from it and takes a gradient step on

(Rt+1+γt+1max⁡a′qθˉ(St+1,a′)−qθ(St,At))2\Big(R_{t+1} + \gamma_{t+1} \max_{a'} q_{\bar\theta}(S_{t+1}, a') - q_{\theta}(S_t, A_t)\Big)^2(Rt+1+γt+1max⁡a′qθˉ(St+1,a′)−qθ(St,At))2\begin{aligned} \Big(R_{t+1} &+ \gamma_{t+1} \max_{a'} q_{\bar\theta}(S_{t+1}, a') \\ &- q_{\theta}(S_t, A_t)\Big)^2 \end{aligned}
(1)

The first two terms are the target: the observed reward plus the discounted value of the best next action. The gradient flows only into the online parameters θ\theta, the network that also chooses actions. θˉ\bar\theta is the target network, a copy of the online network refreshed periodically (every 32K frames in Rainbow) and not trained directly, so the target does not shift with every gradient step. A worked transition: reward 1, next-state values from the target network whose largest entry is 2.0, and an online estimate of 2.5 for the action taken. The target is 1+0.99×2.0=2.981 + 0.99 \times 2.0 = 2.98, the error 0.48, the loss 0.2304. With 32 transitions sampled per 4 new ones, each transition is replayed 8 times on average over its stay in memory.

Each of the six extensions changes one part of this: the target (double Q-learning changes how its max is taken, multi-step returns how many real rewards it sums), which transitions get sampled (prioritized replay), the network's output head (dueling, distributional), the loss (distributional), or how actions are explored (Noisy Nets).

Double Q-learning: the overestimation of the max

The target in (1) takes a maximum over the target network's estimates, and those estimates have errors. The maximum of several noisy estimates is biased upward even when every estimate is unbiased, because the max picks out whichever estimate happens to have the largest positive error. Van Hasselt, Guez and Silver work out a clean case. Suppose all mm actions in a state have the same true value, 0, and each estimate has an independent error drawn uniformly from [−a,a][-a, a]. Then

E[max⁡a′q^(s,a′)]=m−1m+1 a\mathbb{E}\Big[\max_{a'} \hat q(s, a')\Big] = \frac{m-1}{m+1}\, a

With 18 actions and errors of up to 1, the target is too high by 17/19≈0.8917/19 \approx 0.89 on average, from estimation noise alone. The bias then propagates: the overestimated target trains q(St,At)q(S_t, A_t) up, which raises the targets of the states that lead to StS_t. The Double DQN paper measured DQN's value estimates against the actual discounted returns and found overestimation on all 49 games it tested.

Double Q-learning separates the two jobs the max does at once: choosing the next action and reporting its value. If the action is chosen with one set of estimates and its value read from a second, independent set, the second set's error at the chosen action is independent of the choice, so it averages to zero. Double DQN takes the online network as the chooser and the existing target network as the evaluator, which adds no parameters:

(Rt+1+γt+1 qθˉ(St+1,argmax⁡a′qθ(St+1,a′))−qθ(St,At))2\Big(R_{t+1} + \gamma_{t+1}\, q_{\bar\theta}\big(S_{t+1}, \operatorname*{argmax}_{a'} q_{\theta}(S_{t+1}, a')\big) - q_{\theta}(S_t, A_t)\Big)^2(Rt+1+γt+1 qθˉ(St+1,argmax⁡a′qθ(St+1,a′))−qθ(St,At))2\begin{aligned} \Big(R_{t+1} &+ \gamma_{t+1}\, q_{\bar\theta}\big(S_{t+1}, \operatorname*{argmax}_{a'} q_{\theta}(S_{t+1}, a')\big) \\ &- q_{\theta}(S_t, A_t)\Big)^2 \end{aligned}

The two networks are not independent, since the target network is a recent copy of the online one, so the decoupling is partial. It was enough, in the Double DQN paper, to remove the runaway value estimates DQN showed on games such as Asterix and Wizard of Wor and to improve the scores there.

In Figure 1 every action's true value is 0. Each trial draws fresh estimates; the outlined bar is the max that DQN's target would use, and the violet dot is the second estimate of that same action, which a double estimator would use. Set m=1m = 1 or the noise to 0 and the bias vanishes; raise mm to 18 and the single estimator's running mean climbs toward aa.

Figure 1 · the bias of the max
6
1.00
Noisy estimates of actions whose true value is 0. The single estimator takes their max; the double estimator reads a second, independent estimate of the chosen action. Drag the number of actions and the noise width; the readouts are running means over all trials at the current setting, next to the exact values.

Prioritized replay: sampling transitions with large errors

Uniform replay spends most of its updates on transitions the network already predicts well. Prioritized experience replay (Schaul et al.) gives each stored transition a priority pip_i and samples it with probability

P(i)=pi ω∑kpk ωP(i) = \frac{p_i^{\,\omega}}{\sum_k p_k^{\,\omega}}

In the original method pip_i is the transition's absolute TD error, the size of the bracket in (1), recorded the last time it was replayed, plus a small constant so that no transition reaches probability 0. The exponent ω\omega (the PER paper calls it α\alpha) interpolates between uniform sampling at 0 and fully proportional sampling at 1. A new transition has no TD error yet, so it enters with the largest priority seen so far, which guarantees it is replayed at least once soon after it arrives. Sampling from a million priorities that change after every minibatch uses a sum tree, a binary tree whose internal nodes store the sums of their children, so both sampling and updating cost O(log⁡N)O(\log N).

Prioritized sampling changes the expected gradient: high-priority transitions now count more than their share of the data. Prioritized replay corrects for that with importance-sampling weights that multiply each sampled transition's loss,

wi=(1N⋅P(i))β/max⁡jwjw_i = \Big(\frac{1}{N \cdot P(i)}\Big)^{\beta} \Big/ \max_j w_j

At β=1\beta = 1 the correction is complete: a transition sampled 3 times as often as under uniform replay gets a third of the weight, so its expected contribution is the same as under uniform replay. The division by the largest weight keeps every weight at or below 1, so the correction only ever scales updates down. The PER paper argues the bias matters most near the end of training, when the targets stop moving, so it starts β\beta lower and anneals it to 1 by the end. Rainbow uses ω=0.5\omega = 0.5 and anneals β\beta linearly from 0.4 to 1.0. PER lowered its learning rate by a factor of 4 because prioritized minibatches carry larger errors and so larger gradients; Rainbow's learning rate is also DQN's divided by 4, picked from a sweep over 2, 4 and 6.

Figure 2 is a 20-transition buffer. At the defaults (ω=0.5\omega = 0.5, β=0.4\beta = 0.4) the transition with priority 2.4 is sampled with probability 16.2%, 3.2 times its uniform share, and the 4 highest-priority transitions together take 46.8% of the samples instead of 20%. At ω=1\omega = 1 those numbers become 32.7% and 72.9%. The readout's last number, N⋅P(i)⋅wiN \cdot P(i) \cdot w_i, is the transition's expected update weight relative to uniform replay; slide β\beta to 1 and it becomes the same for every bar.

Figure 2 · prioritized sampling and its correction
0.50
0.40
Top: sampling probability of each transition for priority exponent ω. Bottom: importance-sampling weight for exponent β, scaled so the largest is 1. Click a bar to read its values.

The Rainbow paper notes a weakness of TD-error priorities: for a transition with a random outcome, the network learns the average over outcomes, so the TD error of any one stored outcome stays large and the transition keeps being replayed after there is little left to learn from it.

Dueling networks: value plus advantage

In many Atari states the choice of action barely matters (no enemy is near, the ball is far away), but DQN still has to learn every action's value separately. The dueling architecture (Wang et al.) splits the network after the convolutional encoder fξf_\xi into two streams: a value stream vηv_\eta that outputs one number per state, and an advantage stream aψa_\psi that outputs one number per action. They are combined as

qθ(s,a)=vη(fξ(s))+aψ(fξ(s),a)−∑a′aψ(fξ(s),a′)Nactionsq_\theta(s, a) = v_\eta(f_\xi(s)) + a_\psi(f_\xi(s), a) - \frac{\sum_{a'} a_\psi(f_\xi(s), a')}{N_{\text{actions}}}qθ(s,a)=vη(fξ(s))+aψ(fξ(s),a)−∑a′aψ(fξ(s),a′)Nactions\begin{aligned} q_\theta(s, a) &= v_\eta(f_\xi(s)) + a_\psi(f_\xi(s), a) \\ &\quad - \frac{\sum_{a'} a_\psi(f_\xi(s), a')}{N_{\text{actions}}} \end{aligned}

where θ={ξ,η,ψ}\theta = \{\xi, \eta, \psi\}. A worked case with 4 actions: the value stream outputs 2.0 and the advantage stream outputs (1.0, 0.2, 0.5, −0.1), whose mean is 0.4. The Q-values are 2.0+a−0.42.0 + a - 0.4, or (2.6, 1.8, 2.1, 1.5).

The subtracted mean fixes an ambiguity. Without it, a value output of 1.6 with the same advantages gives exactly the same four Q-values, and so would any constant moved from one stream to the other: the loss cannot tell the splits apart, and Wang et al. report that the unconstrained sum trains poorly. With the mean subtracted, the value stream has to equal the average Q-value over actions, here (2.6+1.8+2.1+1.5)/4=2.0(2.6 + 1.8 + 2.1 + 1.5)/4 = 2.0. Wang et al. also tried subtracting the maximum advantage instead, which makes vv the value of the best action, and chose the mean because the advantages then only have to move as fast as their mean instead of tracking every change in the best action. The ranking of actions, and so the greedy policy, is the same either way.

Every update to any action's Q-value also updates vv, so the state's overall value is learned from all the actions taken there, not only from the one being updated.

Multi-step returns: moving reward backward faster

The target in (1) contains one real reward and then bootstraps, meaning it substitutes the network's own estimate for everything after one step. A reward therefore moves back by one state per round of updates. A multi-step target sums nn real rewards before bootstrapping. The truncated nn-step return is

Rt(n)≡∑k=0n−1γt(k)Rt+k+1R_t^{(n)} \equiv \sum_{k=0}^{n-1} \gamma_t^{(k)} R_{t+k+1}
(2)

and the loss becomes

(Rt(n)+γt(n)max⁡a′qθˉ(St+n,a′)−qθ(St,At))2\Big(R_t^{(n)} + \gamma_t^{(n)} \max_{a'} q_{\bar\theta}(S_{t+n}, a') - q_\theta(S_t, A_t)\Big)^2(Rt(n)+γt(n)max⁡a′qθˉ(St+n,a′)−qθ(St,At))2\begin{aligned} \Big(R_t^{(n)} &+ \gamma_t^{(n)} \max_{a'} q_{\bar\theta}(S_{t+n}, a') \\ &- q_\theta(S_t, A_t)\Big)^2 \end{aligned}

Rainbow uses n=3n = 3. With clipped rewards of 1, 0 and 1 over the next three steps, Rt(3)=1+0+0.992=1.9801R_t^{(3)} = 1 + 0 + 0.99^2 = 1.9801 and the bootstrap is discounted by 0.993=0.9702990.99^3 = 0.970299. If the episode ends inside the window, the product γt(n)\gamma_t^{(n)} is 0 and the target is the rewards alone. The replay memory has to store, or reconstruct, the next nn rewards and the state nn steps later for every transition.

The intermediate actions in Rt(n)R_t^{(n)} are whatever the agent did at the time, possibly an exploratory move, and possibly chosen by an older version of the network. One-step Q-learning does not depend on that, because it bootstraps with the max right after the first action. The nn-step target instead estimates the return of the behaviour that was actually followed for n−1n - 1 more steps, and Rainbow applies no correction for the difference, so the target is biased toward the value of the behaviour policy. Larger nn means faster propagation and more of this bias, plus more variance from the extra random rewards. The paper compared n=1n = 1, 3 and 5: both 3 and 5 did well early, and 3 was best by the end.

Figure 3 runs both effects on a 12-state corridor whose only reward is +1 for stepping off the right end. Each sweep replaces every value by its expected nn-step target. With the random-move probability at 0 the reward reaches the start state after ⌈12/n⌉\lceil 12/n \rceil sweeps, 12 for n=1n = 1 and 4 for n=3n = 3, and the values converge to the optimum. Raise the random-move probability to 0.1 and n=3n = 3 converges to 0.880 at the start instead of the optimal 0.895, while n=1n = 1 stays exact.

Figure 3 · n-step targets on a corridor
sweep 2
3
0.00
Learned values of moving right, against the optimal values, after a number of sweeps. Press Play or scrub the sweeps; change n and the probability that the behaviour policy steps left instead.

Distributional RL: predicting the distribution of returns

The return from a state-action pair is a random variable: the same action can lead to different futures. DQN learns only its mean. Distributional RL, in the form Bellemare, Dabney and Munos called C51, learns a probability distribution over the return, represented as probabilities on a fixed grid of NatomsN_{\text{atoms}} values called atoms:

zi=vmin⁡+(i−1) vmax⁡−vmin⁡Natoms−1,i=1,…,Natomsz^i = v_{\min} + (i - 1)\, \frac{v_{\max} - v_{\min}}{N_{\text{atoms}} - 1}, \qquad i = 1, \dots, N_{\text{atoms}}zi=vmin⁡+(i−1) vmax⁡−vmin⁡Natoms−1,i=1,…,Natoms\begin{gathered} z^i = v_{\min} + (i - 1)\, \frac{v_{\max} - v_{\min}}{N_{\text{atoms}} - 1}, \\ i = 1, \dots, N_{\text{atoms}} \end{gathered}

Rainbow uses 51 atoms on [−10,10][-10, 10], so they sit 0.4 apart: −10,−9.6,…,9.6,10-10, -9.6, \dots, 9.6, 10. For each action the network outputs 51 numbers and a softmax turns them into probabilities pθi(s,a)p^i_\theta(s, a) that sum to 1, so the output layer has Natoms×NactionsN_{\text{atoms}} \times N_{\text{actions}} units, 918 for an 18-action game. The agent still acts on the mean, q(s,a)=z⊤pθ(s,a)q(s, a) = \boldsymbol{z}^{\top} \boldsymbol{p}_\theta(s, a).

The training target comes from a distributional form of the Bellman equation. If the return from the next state is distributed as some Z′Z', the return from the current state is Rt+1+γt+1Z′R_{t+1} + \gamma_{t+1} Z': the next-state distribution shrunk toward zero by the discount and shifted by the reward. So the target moves every atom of the next-state distribution to Rt+1+γt+1zjR_{t+1} + \gamma_{t+1} z^j and keeps its probability:

dt′≡(Rt+1+γt+1z,  pθˉ(St+1,aˉt+1∗))d'_t \equiv \big(R_{t+1} + \gamma_{t+1} \boldsymbol{z},\; \boldsymbol{p}_{\bar\theta}(S_{t+1}, \bar a^{*}_{t+1})\big)

where aˉt+1∗\bar a^{*}_{t+1} is the action with the largest mean under the target network. The moved atoms no longer sit on the grid (with γ=0.99\gamma = 0.99 they are 0.396 apart, not 0.4), so before comparing the two distributions C51 projects the target back onto the grid. Each moved atom, clipped to [vmin⁡,vmax⁡][v_{\min}, v_{\max}], gives its probability to the two grid atoms on either side, in proportion to how close it is to each:

(Φzdt′)i=∑j[1−∣[Rt+1+γt+1zj]vmin⁡vmax⁡−zi∣Δz]01 pθˉj(\Phi_{\boldsymbol z} d'_t)_i = \sum_{j} \Big[1 - \frac{\big|[R_{t+1} + \gamma_{t+1} z^j]_{v_{\min}}^{v_{\max}} - z^i\big|}{\Delta z}\Big]_0^1\, p^j_{\bar\theta}(Φzdt′)i=∑j[1−∣[Rt+1+γt+1zj]vmin⁡vmax⁡−zi∣Δz]01pθˉj\begin{aligned} (\Phi_{\boldsymbol z} d'_t)_i = \sum_{j} \Big[1 &- \frac{\big|[R_{t+1} + \gamma_{t+1} z^j]_{v_{\min}}^{v_{\max}} - z^i\big|}{\Delta z}\Big]_0^1 \\ &\quad p^j_{\bar\theta} \end{aligned}

Here [x]ab[x]_a^b clamps xx to [a,b][a, b] and Δz=0.4\Delta z = 0.4. Worked through for one atom: with reward 1 and discount 0.99, the atom at 4.0 moves to 1+0.99×4.0=4.961 + 0.99 \times 4.0 = 4.96, which lies between the grid atoms 4.8 and 5.2. It is 0.16 from 4.8 and 0.24 from 5.2, so 60% of its probability goes to 4.8 and 40% to 5.2. An atom at 10 moves to 10.9, beyond the support, and is clipped to 10 with all of its probability. The loss is the KL divergence from the projected target to the prediction:

DKL(Φzdt′ ∥ dt)D_{\mathrm{KL}}\big(\Phi_{\boldsymbol z} d'_t \,\|\, d_t\big)
(3)

The target is held fixed when differentiating, so minimising (3) is the same as minimising the cross-entropy −∑imilog⁡pθi(St,At)-\sum_i m_i \log p^i_\theta(S_t, A_t) with m=Φzdt′m = \Phi_{\boldsymbol z} d'_t; the two differ by the target's entropy, which does not depend on θ\theta. The value update becomes a 51-class classification problem with soft labels.

In Figure 4 the top panel is the target network's next-state distribution and the bottom panel the projected target. Click a top bar to follow one atom: its thin line marks where it lands and the two outlined bars receive its probability. Push the return to the right and watch probability pile up on the +10 atom; switch on the terminal state and every atom lands on the same point.

Figure 4 · the categorical target and its projection
1.00
1
Next-state return distribution and the projected target on Rainbow's 51-atom grid. Thin amber lines mark where each atom lands before the split. The shaded bands are outside the support.

The Rainbow paper does not explain why a distribution helps an agent that acts only on its mean; a plausible reason is the richer training signal of 51 numbers per action instead of one. C51 reported that its 51-atom agent beat DQN on all five of its training games, with performance rising as atoms were added. The support also caps the return: with rewards clipped to [−1,1][-1, 1] and γ=0.99\gamma = 0.99, a discounted return can reach 100, but anything above 10 is clipped to the top atom, a cap that comes back in the ablations.

Noisy Nets: exploration through noise in the weights

ϵ\epsilon-greedy explores one random action at a time. In a game such as Montezuma's Revenge, where a long specific sequence of moves comes before the first reward, independent random actions almost never produce that sequence. Noisy Nets (Fortunato et al.) put the randomness into the network instead. A noisy linear layer computes

y=(b+Wx)+(bnoisy⊙ϵb+(Wnoisy⊙ϵw)x)\boldsymbol{y} = (\boldsymbol{b} + \mathbf{W}\boldsymbol{x}) + \big(\boldsymbol{b}_{noisy} \odot \epsilon^{b} + (\mathbf{W}_{noisy} \odot \epsilon^{w})\boldsymbol{x}\big)y=(b+Wx)+(bnoisy⊙ϵb+(Wnoisy⊙ϵw)x)\begin{aligned} \boldsymbol{y} &= (\boldsymbol{b} + \mathbf{W}\boldsymbol{x}) \\ &+ \big(\boldsymbol{b}_{noisy} \odot \epsilon^{b} + (\mathbf{W}_{noisy} \odot \epsilon^{w})\boldsymbol{x}\big) \end{aligned}
(4)

where ϵb\epsilon^b and ϵw\epsilon^w are random and ⊙\odot is elementwise multiplication. Both the ordinary weights W,b\mathbf{W}, \boldsymbol{b} and the noise scales Wnoisy,bnoisy\mathbf{W}_{noisy}, \boldsymbol{b}_{noisy} are trained by the ordinary loss; in NoisyNet-DQN the noise is resampled before every action, with independent draws for the online and target networks. One draw defines one perturbed Q-function, and the agent acts greedily on it, so Rainbow sets ϵ=0\epsilon = 0.

With independent unit-Gaussian noise, the noisy part of an output has variance bnoisy2+∑jWnoisy,j2 xj2b_{noisy}^2 + \sum_j W_{noisy,j}^2\, x_j^2, which depends on the layer's input x\boldsymbol x and therefore on the state. The paper describes the network learning to ignore the noisy stream at different rates in different parts of the state space, so the amount of exploration varies from state to state. Whether noise changes the chosen action depends on how close the top two Q-values are: where one action is clearly better, moderate noise rarely flips the choice.

Independent noise needs one random number per weight: pq+qpq + q for a layer with pp inputs and qq outputs, 1,606,144 for the 3136-to-512 layer after Rainbow's encoder. Rainbow uses factorised Gaussian noise instead, p+qp + q unit Gaussians per layer (3,648 here), combined as

ϵi,jw=f(ϵi) f(ϵj),ϵjb=f(ϵj),f(x)=sgn⁡(x)∣x∣\epsilon^w_{i,j} = f(\epsilon_i)\, f(\epsilon_j), \qquad \epsilon^b_j = f(\epsilon_j), \qquad f(x) = \operatorname{sgn}(x)\sqrt{|x|}ϵi,jw=f(ϵi) f(ϵj),ϵjb=f(ϵj),f(x)=sgn⁡(x)∣x∣\begin{gathered} \epsilon^w_{i,j} = f(\epsilon_i)\, f(\epsilon_j), \qquad \epsilon^b_j = f(\epsilon_j), \\ f(x) = \operatorname{sgn}(x)\sqrt{|x|} \end{gathered}

The noise scales start at σ0/p\sigma_0/\sqrt{p} with σ0=0.5\sigma_0 = 0.5, which is 0.0089 for the 3136-input layer and 0.022 for a 512-input layer. A footnote in the paper reports that the noise was generated on the GPU and that TensorFlow's GPU noise generation can be unreliable; generating it on the CPU, the authors suggest lowering σ0\sigma_0 to 0.1.

Figure 5 is a noisy layer with one input feature x≥0x \ge 0 and two outputs, the Q-values of two actions whose means cross at x=1x = 1. The bottom curve is the probability that the action chosen on a noisy draw differs from the action chosen on the means. With the same σ\sigma on every weight it peaks at the crossing and falls off on both sides; on the per-weight example, where only action 2's weight noise stayed large, it stays high at large xx. At σ=0\sigma = 0 it is 0 everywhere.

Figure 5 · state-dependent exploration from weight noise
0.25
Mean Q-values of action 1 and action 2 with one-standard-deviation bands and three sampled noisy lines, and the probability that noise changes the greedy choice. Move the pointer across the plot to read it at one state.

How Rainbow combines the six extensions

The combination has to settle which loss is minimised, which action the target bootstraps from, what the priority is, and how a distributional output fits a dueling head. Rainbow's answers, in the paper's order:

Multi-step distributional target. The 1-step target dt′d'_t becomes an nn-step one: the distribution at St+nS_{t+n} is shrunk by the cumulative discount and shifted by the nn-step return from (2),

dt(n)=(Rt(n)+γt(n)z,  pθˉ(St+n,at+n∗))d^{(n)}_t = \big(R^{(n)}_t + \gamma^{(n)}_t \boldsymbol{z},\; \boldsymbol{p}_{\bar\theta}(S_{t+n}, a^{*}_{t+n})\big)

and the loss is

DKL(Φzdt(n) ∥ dt)D_{\mathrm{KL}}\big(\Phi_{\boldsymbol z} d^{(n)}_t \,\|\, d_t\big)

Set the return to 1.98 and nn to 3 in Figure 4 for the numbers from the multi-step section: the atom at 4.0 moves to 1.9801+0.970299×4.0=5.8611.9801 + 0.970299 \times 4.0 = 5.861, and 34.7% of its probability goes to 5.6, 65.3% to 6.0. Every atom above about 8.27 now lands beyond 10.

Double Q-learning. The bootstrap action at+n∗a^{*}_{t+n} is the action with the largest mean in St+nS_{t+n} according to the online network, and its distribution is read from the target network.

Priority. The TD error of the means could still be computed, but Rainbow prioritizes by the loss it minimises:

pt∝(DKL(Φzdt(n) ∥ dt))ωp_t \propto \Big(D_{\mathrm{KL}}\big(\Phi_{\boldsymbol z} d^{(n)}_t \,\|\, d_t\big)\Big)^{\omega}

The authors suggest the KL priority might cope better with stochastic environments, because the KL loss can keep decreasing even when returns are not deterministic. They found performance "very robust" to ω\omega with this priority, comparing 0.4, 0.5 and 0.7.

Dueling head for distributions. The value stream outputs 51 numbers and the advantage stream 51×Nactions51 \times N_{\text{actions}}. The dueling combination is applied atom by atom, before the softmax:

pθi(s,a)=softmax⁡i(vηi(ϕ)+aψi(ϕ,a)−aˉψi(s))p^{i}_{\theta}(s, a) = \operatorname{softmax}_i\big(v^{i}_{\eta}(\phi) + a^{i}_{\psi}(\phi, a) - \bar a^{i}_{\psi}(s)\big)pθi(s,a)=softmax⁡i(vηi(ϕ)+aψi(ϕ,a)−aˉψi(s))\begin{aligned} p^{i}_{\theta}(s, a) = \operatorname{softmax}_i\big(&v^{i}_{\eta}(\phi) + a^{i}_{\psi}(\phi, a) \\ &- \bar a^{i}_{\psi}(s)\big) \end{aligned}

with ϕ=fξ(s)\phi = f_\xi(s), aˉψi(s)\bar a^{i}_{\psi}(s) the mean of atom ii's advantages over actions, and the softmax taken over the atoms ii of each action (the paper writes it out as an exponential divided by its sum over atoms). For an 18-action game the shapes are: input 4 × 84 × 84; encoder output 7 × 7 × 64 = 3136 features; each stream has a 512-unit hidden layer; value output 51, advantage output 18 × 51; combined logits 18 × 51, with a softmax over the 51 atoms of each action.

Noisy layers. Every linear layer, in both streams, is replaced by a noisy layer with factorised Gaussian noise. The convolutional encoder stays deterministic.

The listing below is a single learner update, with tensor shapes and the point where the gradient enters:

# One Rainbow learner update. Runs every 4 agent steps. B = 32, K = 51 atoms.
z = linspace(-10, 10, K)                       # atom values, spacing 0.4
idx, w = replay.sample(B, omega=0.5, beta=beta_t)   # P(i) ~ p_i^0.5, IS weights
s, a, R3, g3, s3 = replay.get(idx)  # R3 = r1 + .99 r2 + .99^2 r3, g3 = .99^3 or 0
with no_grad():
    q_next = (online(s3) * z).sum(-1)          # [B, A] mean of each action
    a_star = q_next.argmax(1)                  # double: online net selects
    p_next = target(s3)[arange(B), a_star]     # [B, K] target net evaluates
    tz = clamp(R3[:, None] + g3[:, None] * z, -10, 10)  # [B, K] moved atoms
    m = project(tz, p_next, z)                 # [B, K] split onto the grid
logp = log_softmax(online_logits(s), -1)[arange(B), a]  # [B, K]
ce = -(m * logp).sum(-1)                       # cross-entropy per transition
(w * ce).mean().backward()                     # gradient into online net only
kl = ce + (m * log(m + 1e-8)).sum(-1)          # KL(m || p) = CE - H(m)
replay.update_priorities(idx, kl.detach())     # sampled again with p ~ KL^0.5
# every 32K frames (8,000 agent steps): target.load(online)

Computing the split with floor and ceiling, as C51's Algorithm 1 does, gives both neighbours a share of zero when a moved atom lands exactly on a grid point, and its probability disappears. This happens often: every atom clipped to −10 or +10 lands exactly on the end atom, and on a terminal transition with a 3-step return of 0 (a life lost with no reward) every atom lands on the atom at 0. The two-line fix below is from Kaixhin's Rainbow reimplementation:

def project(tz, p_next, z, dz=0.4, vmin=-10.0):
    # tz, p_next: [B, K]. Returns m: [B, K], each row sums to 1.
    b = (tz - vmin) / dz                       # fractional atom index, 0..K-1
    l, u = floor(b), ceil(b)
    l[(u > 0) & (l == u)] -= 1                 # b landed on an atom: without
    u[(l < K - 1) & (l == u)] += 1             # these two lines its mass is lost
    m = zeros_like(p_next)
    m.scatter_add_(1, l, p_next * (u - b))     # share for the lower neighbour
    m.scatter_add_(1, u, p_next * (b - l))     # share for the upper neighbour
    return m

The hyper-parameters are the same for all 57 games. The paper tuned them by hand, one component at a time, starting from each component's published values:

# Rainbow, Table 1 of the paper (identical for all 57 games)
min history before learning   80K frames     # DQN: 200K
Adam learning rate            0.0000625      # = 0.00025 / 4
Adam epsilon                  1.5e-4
exploration epsilon           0.0            # Noisy Nets do the exploring
Noisy Nets sigma_0            0.5
target network period         32K frames     # 8,000 agent steps
prioritization                proportional, omega = 0.5
importance sampling beta      0.4 -> 1.0     # linear over training
multi-step n                  3
atoms                         51 on [-10, 10]
# inherited from DQN (Tables 3 and 4)
input 84x84 grey, 4 frames stacked; action repeat 4; reward clip [-1, 1]
loss of a life = terminal; episodes capped at 108K frames (30 minutes)
discount 0.99; replay memory 1M transitions; minibatch 32 every 4 agent steps

Two settings differ from DQN's for reasons the paper gives. DQN waits for 200K frames of experience before its first update; with prioritized replay, Rainbow could start after 80K. And Adam replaced RMSProp, with a learning rate of DQN's 0.00025 divided by 4, chosen from 2, 4 and 6; the authors found Adam less sensitive to the learning rate.

Results on 57 Atari games

Scores are normalised per game so that 0% is a random agent and 100% is a human expert:

scorenorm=scoreagent−scorerandomscorehuman−scorerandom\text{score}_{\text{norm}} = \frac{\text{score}_{\text{agent}} - \text{score}_{\text{random}}}{\text{score}_{\text{human}} - \text{score}_{\text{random}}}

The paper reports the median over the 57 games. During training, every 1M environment steps, learning pauses and the latest agent plays 500K frames; episodes are capped at 108K frames, 30 minutes of play. After training the best snapshot is re-evaluated two ways: no-op starts, which begin each episode with up to 30 do-nothing actions, as in training, and human starts, which begin from points sampled from human expert play. The gap between the two shows how much an agent depends on situations its own play produces.

Rainbow's final median is 223% with no-op starts and 153% with human starts. The strongest single extension with no-op starts, distributional DQN, reaches 164% (125% with human starts, where prioritized DDQN's 128% is the best baseline); DQN itself scores 79% and 68%. On learning speed, Rainbow matched DQN's final performance after 7M frames, less than 10 hours on one GPU, and passed the final performance of every baseline within 44M frames. A full 200M-frame run took about 10 days. The DDQN, prioritized, dueling and A3C rows of the table are the published numbers from those papers; DQN's come from the dueling paper; the distributional and noisy rows are the authors' own re-runs.

The median hides how scores are spread. Figure 6 normalises the raw no-op scores from the paper's appendix Table 6, which lists 54 of the 57 games, with the human and random reference scores from the dueling paper. Over those 54 games Rainbow's median is 227% and DQN's 79%. The means are 1,389% and 449%, and a single game accounts for most of the difference between mean and median: in Video Pinball the human reference is only 1,411 points above random (17,667.9 against 16,256.9), so Rainbow's 533,936 points normalise to 36,689%. Without Video Pinball the means drop to 723% and 217%. The paper uses the median for this reason, and adds counts of games above several thresholds; at 100%, 40 of the 54 games for Rainbow against 23 for DQN.

Figure 6 · per-game scores and the Table 2 medians
100%
Human-normalised no-op scores for DQN and Rainbow on a logarithmic axis, with each agent's median and a threshold you can drag. Click a dot to see that game in both rows. The second tab shows the paper's Table 2.

Rainbow scores below DQN on 4 of the 54 games: Bowling, Robotank, Tennis and Venture. On Venture it scores 0.5% of human, 5.5 points, where Distributional DQN reached 1,107. The paper's threshold counts show the gains on both kinds of game: those where earlier agents were already above human level and those where they were far below it.

Which components matter: the ablations

Each ablation removes one component from the full agent and keeps everything else, so it measures a component's contribution in this particular combination, which is different from what it adds to plain DQN.

The authors checked why double Q-learning added so little. Comparing the trained agents' predictions with the actual discounted returns (computed from clipped rewards), they found the returns often exceeded 10, so they fell outside the support, and the distributional agents underestimated those returns instead of overestimating them. They hypothesise that clipping to [−10,10][-10, 10] counteracts Q-learning's overestimation bias, and that double Q-learning may become more important with a wider support. In Figure 4, a return of 3 with n=3n = 3 already moves every atom above 7.2 past the top of the grid.

Limits

The study is restricted to value-based agents of the Q-learning family. It leaves out policy-based methods such as TRPO and actor-critic methods such as A3C, whose multi-step returns it does borrow, and it does not use parallel actors: every agent ran on one GPU, which makes the comparison between agents like for like but says nothing about wall-clock speed under parallelism. The paper also lists candidate components it did not try, including eligibility traces, episodic control, other exploration methods (Bootstrapped DQN, count-based exploration, intrinsic motivation), hierarchical RL and auxiliary tasks.

It keeps DQN's modifications of the game: rewards clipped to [−1,1][-1, 1], a fixed 4-frame action repeat, a 4-frame stack in place of memory, and a lost life treated as a terminal transition. Reward clipping in particular interacts with the distributional support: a game's actual point values are invisible to the agent, and its returns are measured in clipped units that the [−10, 10] grid then truncates.

The tuning was limited (manual coordinate descent from each component's published settings), and the ablations remove one component at a time, so they cannot show pairwise interactions beyond the one the authors diagnosed between double Q-learning and the support. The paper does not state how many runs each curve averages, and reports no confidence intervals. The authors did not release code; Google's Dopamine library ships a simplified Rainbow with only multi-step returns, prioritized replay and distributional learning, the three components the ablations ranked highest, and it differs in details listed in the Provenance panel.

Provenance Verified against primary literatureHow we verify
Hessel et al. (2017), main textEquations (1)-(4) and the unnumbered losses, Table 1 hyper-parameters, Table 2 medians (no-ops 223%, human starts 153%), Tables 3-4 inherited settings, and the ablation findings. Read from the arXiv v1 HTML render and PDF.
van Hasselt, Guez & Silver (2016)Double DQN target: online network selects the argmax, target network evaluates it. Section 3: with all true values equal and errors uniform on [-1, 1], the max overestimates by (m-1)/(m+1); overestimation seen on all 49 games tested.
Schaul, Quan, Antonoglou & Silver (2016)P(i) = p_i^alpha / sum_k p_k^alpha (Rainbow calls the exponent omega); proportional p_i = |delta_i| + epsilon; new transitions get the maximum priority so far; w_i = (1/(N P(i)))^beta normalised by 1/max w; beta annealed to 1; sum-tree sampling. PER used alpha = 0.6, beta_0 = 0.4 and a learning rate 4x lower than Double DQN.
Wang et al. (2016)Dueling Eq. (9): subtract the mean advantage. Without it, V and A are unidentifiable (a constant moves between them). The random and human reference scores used on this page to normalise Rainbow's Table 6 come from this paper's appendix table.
Bellemare, Dabney & Munos (2017)C51: Eq. (7) projection onto the two nearest atoms with clipping to [V_MIN, V_MAX]; V_MAX = -V_MIN = 10; loss is the cross-entropy term of the KL divergence; on five training games performance rose with the number of atoms and 51 atoms beat DQN on all five.
Rowland et al. (2018)The heuristic C51 projection is exactly the orthogonal projection under the Cramer distance (an L2 distance between CDFs), which is the sense in which Rainbow calls it an "L2-projection".
Fortunato et al. (2018)Noisy Nets: factorised noise uses p + q unit Gaussians instead of pq + q, with f(x) = sgn(x) sqrt(|x|); init mu ~ U[-1/sqrt(p), 1/sqrt(p)], sigma = sigma_0 / sqrt(p), sigma_0 = 0.5; for DQN, new noise every step, independent noise for online and target networks.
google/dopamine, tf/agents/rainbow/rainbow_agent.pyA simplified Rainbow (n-step, prioritized replay, distributional only). Lines ~269-293: softmax cross-entropy loss, priorities set to sqrt(loss + 1e-10), fixed beta = 0.5 via 1/sqrt(prob). The Rainbow authors released no code of their own.
Kaixhin/Rainbow, agent.py lines 84-86The fix for the floor/ceil projection: when b is an integer, l = u and both shares are zero; the code moves l down or u up by one so the mass survives.
correctionThree checkable slips. (1) In "The Integrated Agent", the advantage stream is written a_xi, but xi is the shared encoder's parameters; the advantage stream is a_psi, as in the equation that follows. (2) In "Distributional RL", the greedy action is defined from q_theta-bar(S_t+1, a) = z^T p_theta(S_t+1, a); the mean must use the same target network, p_theta-bar. (3) The appendix score tables (Tables 5 and 6) list 54 games, not 57: James Bond, River Raid and Up'n Down are absent, so the per-game figure here reproduces a 227% median from Table 6 against the 223% the paper reports over all 57. Separately, C51's Algorithm 1, the projection Rainbow's Phi refers to, loses the probability of any atom whose moved position lands exactly on a grid point (floor = ceil, both shares zero). In Rainbow that includes every atom clipped to -10 or +10 and, on terminal transitions with a return of 0, every atom. The page teaches the Eq. (7) form and the floor/ceil fix, which keep it.

Questions you might still have

?

Does Rainbow introduce a new algorithm?
No new component. Every piece is from an earlier paper. What is new is fitting them into one loss (a multi-step, double, distributional target whose KL divergence is both the loss and the replay priority), a single hyper-parameter sheet for all 57 games, and the ablation study that removes each component from the full agent.

?

Which components should I implement first if I can only add a few?
The ablations rank prioritized replay and multi-step returns first: removing either caused the largest drop in median score, and the full agent beat both ablations on 53 of 57 games. Distributional learning came next, then Noisy Nets. Removing dueling or double Q-learning made no significant aggregate difference in this combination. Dopamine's simplified Rainbow keeps exactly the top three.

?

Why did double Q-learning matter so little here?
The paper offers a hypothesis, not a proof. Its distributional support stops at +10, but discounted returns of clipped rewards often exceed 10, so the predictions are clipped and underestimate instead of overestimate. That may cancel the upward bias that double Q-learning exists to remove. The authors note double Q-learning may matter more with a wider support.

?

Does Rainbow still use epsilon-greedy?
Not when Noisy Nets are in. Rainbow acts greedily on the noisy Q-values (epsilon = 0), so all exploration comes from the sampled weight noise. The ablation without Noisy Nets falls back to epsilon-greedy, annealed to 0.01 over the first 250K frames.

?

How expensive is a Rainbow run?
One game, 200M frames, on a single GPU took about 10 days, and the cost varied by less than 20% across the variants. Matching DQN's final score took 7M frames, under 10 hours. A frame is one emulator frame; with action repeat 4, 200M frames are 50M agent decisions and 12.5M gradient updates.

?

Why 51 atoms on [-10, 10]?
Both come from C51, which found performance rose with the number of atoms on its training games and chose V_MAX = 10 from preliminary experiments. With rewards clipped to [-1, 1] and gamma = 0.99 the return could in principle reach 100, so the support is a deliberate truncation, the one the double Q-learning hypothesis turns on.

?

How does Rainbow relate to DQN and A3C?
It keeps DQN's network body, preprocessing, replay memory and target network, and borrows the multi-step return from A3C, which used it with parallel actors instead of a replay memory. The DQN and A3C explainers cover those two papers.

Footnotes & further reading

  1. The paper: Hessel et al., Rainbow: Combining Improvements in Deep Reinforcement Learning (AAAI 2018; arXiv October 2017). The appendix has per-game learning curves for every agent and ablation.
  2. DQN: Mnih et al., Human-level control through deep reinforcement learning (Nature 2015), the version with the target network; the 2013 workshop paper is covered in the DQN explainer.
  3. Double DQN: van Hasselt, Guez & Silver, Deep Reinforcement Learning with Double Q-learning (AAAI 2016). Prioritized replay: Schaul, Quan, Antonoglou & Silver, Prioritized Experience Replay (ICLR 2016). Dueling: Wang et al., Dueling Network Architectures for Deep Reinforcement Learning (ICML 2016).
  4. Distributional RL: Bellemare, Dabney & Munos, A Distributional Perspective on Reinforcement Learning (ICML 2017); the projection's interpretation is in Rowland et al., An Analysis of Categorical Distributional Reinforcement Learning (AISTATS 2018). Noisy Nets: Fortunato et al., Noisy Networks for Exploration (ICLR 2018).
  5. Multi-step returns go back to Sutton, Learning to Predict by the Methods of Temporal Differences (Machine Learning, 1988). A3C's use of them, with parallel actors and no replay, is in the A3C explainer; Rainbow replaces RMSProp with Adam.
  6. Code: the simplified Rainbow in google/dopamine and the full six-component reimplementation in Kaixhin/Rainbow, whose projection fix is quoted above.