Rainbow: Combining Improvements in Deep Reinforcement Learning — part 2/3

Cleaned-text code points [15959, 31811). Bibliography omitted here; source.md includes it.

First, we replace the 1-step distributional loss ( 3 ) with a multi-step variant. We construct the target distribution by contracting the value distribution in S t + n S_{t+n} according to the cumulative discount, and shifting it by the truncated n n -step discounted return. This corresponds to defining the target distribution as d t ( n ) = ( R t ( n ) + γ t ( n ) ​ 𝒛 , 𝒑 θ ¯ ​ ( S t + n , a t + n ∗ ) ) d^{(n)}_{t}=(R^{(n)}_{t}+\gamma_{t}^{(n)}\bm{z},~~\bm{p}_{\overline{\theta}}(S_{t+n},a^{*}_{t+n})) . The resulting loss is D KL ( Φ 𝒛 d t ( n ) | | d t ) , D_{\text{KL}}(\Phi_{\bm{z}}d_{t}^{(n)}||d_{t})\,, where, again, Φ 𝒛 \Phi_{\bm{z}} is the projection onto 𝒛 \bm{z} .

We combine the multi-step distributional loss with double Q-learning by using the greedy action in S t + n S_{t+n} selected according to the online network as the bootstrap action a t + n ∗ a^{*}_{t+n} , and evaluating such action using the target network .

In standard proportional prioritized replay [ 2015 ] the absolute TD error is used to prioritize the transitions. This can be computed in the distributional setting, using the mean action values. However, in our experiments all distributional Rainbow variants prioritize transitions by the KL loss, since this is what the algorithm is minimizing: p t ∝ ( D KL ( Φ 𝒛 d t ( n ) | | d t ) ) ω . p_{t}\propto\left(D_{\text{KL}}(\Phi_{\bm{z}}d_{t}^{(n)}||d_{t})\right)^{\omega}\,. The KL loss as priority might be more robust to noisy stochastic environments because the loss can continue to decrease even when the returns are not deterministic.

The network architecture is a dueling network architecture adapted for use with return distributions. The network has a shared representation f ξ ​ ( s ) f_{\xi}(s) , which is then fed into a value stream v η v_{\eta} with N atoms N_{\text{atoms}} outputs, and into an advantage stream a ξ a_{\xi} with N atoms × N actions N_{\text{atoms}}\times N_{\text{actions}} outputs, where a ξ i ​ ( f ξ ​ ( s ) , a ) a^{i}_{\xi}(f_{\xi}(s),a) will denote the output corresponding to atom i i and action a a . For each atom z i z^{i} , the value and advantage streams are aggregated, as in dueling DQN, and then passed through a softmax layer to obtain the normalised parametric distributions used to estimate the returns’ distributions: p θ i ​ ( s , a ) = exp ⁡ ( v η i ​ ( ϕ ) + a ψ i ​ ( ϕ , a ) − a ¯ ψ i ​ ( s ) ) ∑ j exp ⁡ ( v η j ​ ( ϕ ) + a ψ j ​ ( ϕ , a ) − a ¯ ψ j ​ ( s ) ) , p^{i}_{\theta}(s,a)=\frac{\exp(v^{i}_{\eta}(\phi)+a^{i}_{\psi}(\phi,a)-\overline{a}^{i}_{\psi}(s))}{\sum_{j}\exp(v^{j}_{\eta}(\phi)+a^{j}_{\psi}(\phi,a)-\overline{a}^{j}_{\psi}(s))}\,, where ϕ = f ξ ​ ( s ) \phi=f_{\xi}(s) and a ¯ ψ i ​ ( s ) = 1 N actions ​ ∑ a ′ a ψ i ​ ( ϕ , a ′ ) \overline{a}^{i}_{\psi}(s)=\frac{1}{N_{\text{actions}}}\sum_{a^{\prime}}a^{i}_{\psi}(\phi,a^{\prime}) .

We then replace all linear layers with their noisy equivalent described in Equation ( 4 ). Within these noisy linear layers we use factorised Gaussian noise [ 2017 ] to reduce the number of independent noise variables.

## Experimental Methods

We now describe the methods and setup used for configuring and evaluating the learning agents.

### Evaluation Methodology.

We evaluated all agents on 57 Atari 2600 games from the arcade learning environment [ 2013 ] . We follow the training and evaluation procedures of ? ( ? ) and van Hasselt et al. ( ? ). The average scores of the agent are evaluated during training, every 1M steps in the environment, by suspending learning and evaluating the latest agent for 500K frames. Episodes are truncated at 108K frames (or 30 minutes of simulated play), as in van Hasselt et al. ( ? ).

Agents’ scores are normalized, per game, so that 0% corresponds to a random agent and 100% to the average score of a human expert. Normalized scores can be aggregated across all Atari levels to compare the performance of different agents. It is common to track the median human normalized performance across all games. We also consider the number of games where the agent’s performance is above some fraction of human performance, to disentangle where improvements in the median come from. The mean human normalized performance is potentially less informative, as it is dominated by a few games (e.g., Atlantis) where agents achieve scores orders of magnitude higher than humans do.

Besides tracking the median performance as a function of environment steps, at the end of training we re-evaluate the best agent snapshot using two different testing regimes. In the no-ops starts regime, we insert a random number (up to 30) of no-op actions at the beginning of each episode (as we do also in training). In the human starts regime, episodes are initialized with points randomly sampled from the initial portion of human expert trajectories [ 2015 ] ; the difference between the two regimes indicates the extent to which the agent has over-fit to its own trajectories.

Due to space constraints, we focus on aggregate results across games. However, in the appendix we provide full learning curves for all games and all agents, as well as detailed comparison tables of raw and normalized scores, in both the no-op and human starts testing regimes.

### Hyper-parameter tuning.

All Rainbow’s components have a number of hyper-parameters. The combinatorial space of hyper-parameters is too large for an exhaustive search, therefore we have performed limited tuning. For each component, we started with the values used in the paper that introduced this component, and tuned the most sensitive among hyper-parameters by manual coordinate descent.

DQN and its variants do not perform learning updates during the first 200 ​ K 200K frames, to ensure sufficiently uncorrelated updates. We have found that, with prioritized replay, it is possible to start learning sooner, after only 80 ​ K 80K frames.

DQN starts with an exploration ϵ \epsilon of 1, corresponding to acting uniformly at random; it anneals the amount of exploration over the first 4M frames, to a final value of 0.1 (lowered to 0.01 in later variants). Whenever using Noisy Nets, we acted fully greedily ( ϵ = 0 \epsilon=0 ), with a value of 0.5 0.5 for the σ 0 \sigma_{0} hyper-parameter used to initialize the weights in the noisy stream 1 1 1 The noise was generated on the GPU. Tensorflow noise generation can be unreliable on GPU. If generating the noise on the CPU, lowering σ 0 \sigma_{0} to 0.1 may be helpful. . For agents without Noisy Nets, we used ϵ \epsilon -greedy but decreased the exploration rate faster than was previously used, annealing ϵ \epsilon to 0.01 in the first 250 ​ K 250K frames.

We used the Adam optimizer [ 2014 ] , which we found less sensitive to the choice of the learning rate than RMSProp. DQN uses a learning rate of α = 0.00025 \alpha=0.00025 In all Rainbow’s variants we used a learning rate of α / 4 \alpha/4 , selected among { α / 2 , α / 4 , α / 6 } \{\alpha/2,\alpha/4,\alpha/6\} , and a value of 1.5 × 10 − 4 1.5\times 10^{-4} for Adam’s ϵ \epsilon hyper-parameter.

For replay prioritization we used the recommended proportional variant, with priority exponent ω \omega of 0.5 0.5 , and linearly increased the importance sampling exponent β \beta from 0.4 to 1 over the course of training. The priority exponent ω \omega was tuned comparing values of { 0.4 , 0.5 , 0.7 } \{0.4,0.5,0.7\} . Using the KL loss of distributional DQN as priority, we have observed that performance is very robust to the choice of ω \omega .

The value of n n in multi-step learning is a sensitive hyper-parameter of Rainbow. We compared values of n = 1 , 3 , and ​ 5 n=1,\ 3,\ \text{and }5 . We observed that both n = 3 n=3 and 5 5 did well initially, but overall n = 3 n=3 performed the best by the end.

The hyper-parameters (see Table 1 ) are identical across all 57 games, i.e., the Rainbow agent really is a single agent setup that performs well across all the games.

## Analysis

In this section we analyse the main experimental results. First, we show that Rainbow compares favorably to several published agents. Then we perform ablation studies, comparing several variants of the agent, each corresponding to removing a single component from Rainbow.

### Comparison to published baselines.

In Figure 1 we compare the Rainbow’s performance (measured in terms of the median human normalized score across games) to the corresponding curves for A3C, DQN, DDQN, Prioritized DDQN, Dueling DDQN, Distributional DQN, and Noisy DQN. We thank the authors of the Dueling and Prioritized agents for providing the learning curves of these, and report our own re-runs for DQN, A3C, DDQN, Distributional DQN and Noisy DQN. The performance of Rainbow is significantly better than any of the baselines, both in data efficiency, as well as in final performance. Note that we match final performance of DQN after 7M frames, surpass the best final performance of these baselines in 44M frames, and reach substantially improved final performance.

In the final evaluations of the agent, after the end of training, Rainbow achieves a median score of 223% in the no-ops regime; in the human starts regime we measured a median score of 153%. In Table 2 we compare these scores to the published median scores of the individual baselines.

In Figure 2 (top row) we plot the number of games where an agent has reached some specified level of human normalized performance. From left to right, the subplots show on how many games the different agents have achieved 20%, 50%, 100%, 200% and 500% human normalized performance. This allows us to identify where the overall improvements in performance come from. Note that the gap in performance between Rainbow and other agents is apparent at all levels of performance: the Rainbow agent is improving scores on games where the baseline agents were already good, as well as improving in games where baseline agents are still far from human performance.

### Learning speed.

As in the original DQN setup, we ran each agent on a single GPU. The 7M frames required to match DQN’s final performance correspond to less than 10 hours of wall-clock time. A full run of 200M frames corresponds to approximately 10 days, and this varies by less than 20% between all of the discussed variants. The literature contains many alternative training setups that improve performance as a function of wall-clock time by exploiting parallelism, e.g., ? ( ? ), ? ( ? ), and ? ( ? ). Properly relating the performance across such very different hardware/compute resources is non-trivial, so we focused exclusively on algorithmic variations, allowing apples-to-apples comparisons. While we consider them to be important and complementary, we leave questions of scalability and parallelism to future work.

### Ablation studies.

Since Rainbow integrates several different ideas into a single agent, we conducted additional experiments to understand the contribution of the various components, in the context of this specific combination.

To gain a better understanding of the contribution of each component to the Rainbow agent, we performed ablation studies. In each ablation, we removed one component from the full Rainbow combination. Figure 3 shows a comparison for median normalized score of the full Rainbow to six ablated variants. Figure 2 (bottom row) shows a more detailed breakdown of how these ablations perform relative to different thresholds of human normalized performance, and Figure 4 shows the gain or loss from each ablation for every game, averaged over the full learning run.

Prioritized replay and multi-step learning were the two most crucial components of Rainbow, in that removing either component caused a large drop in median performance. Unsurprisingly, the removal of either of these hurt early performance. Perhaps more surprisingly, the removal of multi-step learning also hurt final performance. Zooming in on individual games (Figure 4 ), we see both components helped almost uniformly across games (the full Rainbow performed better than either ablation in 53 games out of 57).

Distributional Q-learning ranked immediately below the previous techniques for relevance to the agent’s performance. Notably, in early learning no difference is apparent, as shown in Figure 3 , where for the first 40 million frames the distributional-ablation performed as well as the full agent. However, without distributions, the performance of the agent then started lagging behind. When the results are separated relatively to human performance in Figure 2 , we see that the distributional-ablation primarily seems to lags on games that are above human level or near it.

In terms of median performance, the agent performed better when Noisy Nets were included; when these are removed and exploration is delegated to the traditional ϵ \epsilon -greedy mechanism, performance was worse in aggregate (red line in Figure 3 ). While the removal of Noisy Nets produced a large drop in performance for several games, it also provided small increases in other games (Figure 4 ).

In aggregate, we did not observe a significant difference when removing the dueling network from the full Rainbow. The median score, however, hides the fact that the impact of Dueling differed between games, as shown by Figure 4 . Figure 2 shows that Dueling perhaps provided some improvement on games with above-human performance levels (# games > 200 % >200\% ), and some degradation on games with sub-human performance (# games > 20 % >20\% ).

Also in the case of double Q-learning, the observed difference in median performance (Figure 3 ) is limited, with the component sometimes harming or helping depending on the game (Figure 4 ). To further investigate the role of double Q-learning, we compared the predictions of our trained agents to the actual discounted returns computed from clipped rewards. Comparing Rainbow to the agent where double Q-learning was ablated, we observed that the actual returns are often higher than 10 10 and therefore fall outside the support of the distribution, spanning from − 10 -10 to + 10 +10 . This leads to underestimated returns, rather than overestimations. We hypothesize that clipping the values to this constrained range counteracts the overestimation bias of Q-learning. Note, however, that the importance of double Q-learning may increase if the support of the distributions is expanded.

In the appendix, for each game we show final performance and learning curves for Rainbow, its ablations, and baselines.

## Discussion

We have demonstrated that several improvements to DQN can be successfully integrated into a single learning algorithm that achieves state-of-the-art performance. Moreover, we have shown that within the integrated algorithm, all but one of the components provided clear performance benefits. There are many more algorithmic components that we were not able to include, which would be promising candidates for further experiments on integrated agents. Among the many possible candidates, we discuss several below.

We have focused here on value-based methods in the Q-learning family. We have not considered purely policy-based RL algorithms such as trust-region policy optimisation [ 2015 ] , nor actor-critic methods [ 2016 , 2016 ] .

A number of algorithms exploit a sequence of data to achieve improved learning efficiency. Optimality tightening [ 2016 ] uses multi-step returns to construct additional inequality bounds, instead of using them to replace the 1-step targets used in Q-learning. Eligibility traces allow a soft combination over n-step returns [ 1988 ] . However, sequential methods all leverage more computation per gradient than the multi-step targets used in Rainbow. Furthermore, introducing prioritized sequence replay raises questions of how to store, replay and prioritise sequences.