Revisiting Rainbow: Promoting more Insightful and Inclusive Deep Reinforcement Learning Research — part 1/3
Cleaned-text code points [0, 15747). Bibliography omitted here; source.md includes it.
# Revisiting Rainbow: Promoting more Insightful and Inclusive Deep Reinforcement Learning Research
###### Abstract
Since the introduction of DQN, a vast majority of reinforcement learning research has focused on reinforcement learning with deep neural networks as function approximators. New methods are typically evaluated on a set of environments that have now become standard, such as Atari 2600 games. While these benchmarks help standardize evaluation, their computational cost has the unfortunate side effect of widening the gap between those with ample access to computational resources, and those without. In this work we argue that, despite the community’s emphasis on large-scale environments, the traditional small-scale environments can still yield valuable scientific insights and can help reduce the barriers to entry for underprivileged communities. To substantiate our claims, we empirically revisit the paper which introduced the Rainbow algorithm ( Hessel et al., 2018 ) and present some new insights into the algorithms used by Rainbow.
###### Keywords:
## 1 Introduction
Since the introduction of DQN ( Mnih et al., 2015 ) reinforcement learning has witnessed a dramatic increase in research papers ( Henderson et al., 2018 ) . A large portion of these papers propose new methods that build on the original DQN algorithm and network architecture, often adapting methods introduced before DQN to work well with deep networks (e.g., ( van Hasselt et al., 2016 ; Bacon et al., 2017 ; Castro, 2020 ) ). New methods are typically evaluated on a set of environments that have now become standard, such as the Atari 2600 games made available in the Arcade Learning Environment (ALE) ( Bellemare et al., 2012 ) and the control tasks available in MuJoCo and DM control suites ( Todorov et al., 2012 ; Tassa et al., 2020 ) .
While these benchmarks have helped to evaluate new methods in a standardized manner, they have also implicitly established a minimum amount of computing power in order to be recognized as valid scientific contributions. Although classic reinforcement learning tasks such as MountainCar, CartPole, Acrobot, and grid worlds have not gone away, they are now used mostly for evaluating theoretical contributions (e.g., ( Nachum et al., 2019 ; Lyle et al., 2019 ) ); indeed, in our experience it is quite difficult to have a paper proposing a new reinforcement learning method accepted at one of the major machine learning conferences unless it includes experiments with one of the benchmarks just mentioned. This is unfortunate, as the low computational cost and speed at which one can train on small-scale environments enables broad hyper-parameter sweeps and more thorough investigations into the nuances of the methods being considered, as well as the reevaluation of certain empirical choices that have become “folk wisdom” in these types of experiments.
Furthermore, at a time when efforts such as Black in AI and LatinX in AI are helping bring people from underrepresented (and typically underprivileged) segments of society into the research community, these newcomers are faced with enormous computational hurdles to overcome if they wish to be an integral part of said community.
It thus behooves the reinforcement learning research community to incorporate a certain degree of flexibility and creativity when proposing and evaluating new research; of course, this should not be at the expense of scientific rigour. This paper is partly a position paper, partly an empirical evaluation. We argue for a need to change the status-quo in evaluating and proposing new research to avoid exacerbating the barriers to entry for newcomers from underprivileged communities. In section 4 we complement this argument by revisiting the Rainbow algorithm ( Hessel et al., 2018 ) , which proposed a new state of the art algorithm by combining a number of recent advances, on a set of small- and medium-sized tasks. This allows us to conduct a “counterfactual” analysis: would Hessel et al. (2018) have reached the same conclusions if they had run on the smaller-scale experiments we investigate here? In section 5 we extend this analysis by investigating the interaction between the different algorithms considered and the network architecture used, varying the distribution parameterization and bootstrapping methodology, and the base loss used by DQN. Finally, in section 6 we compare the Rainbow variants we considered, as well as provide insights into the properties of the different environments used in our study.
## 2 Preliminaries
Reinforcement learning methods are used for learning how to act (near) optimally in sequential decision making problems in uncertain environments. In the most common scenario, an agent transitions between states in an environment by making action choices at discrete time steps; upon performing an action, the environment produces a numerical reward and transitions the agent to a new state. This is formalized as a Markov decision process ( Puterman, 1994 ) ⟨ 𝒮 , 𝒜 , ℛ , 𝒫 , γ ⟩ \langle\mathcal{S},\mathcal{A},\mathcal{R},\mathcal{P},\gamma\rangle , where 𝒮 \mathcal{S} is a finite set of states, 𝒜 \mathcal{A} is a finite set of actions, ℛ : 𝒮 × 𝒜 → [ R m i n , R m a x ] \mathcal{R}:\mathcal{S}\times\mathcal{A}\rightarrow[R_{min},R_{max}] is the reward function, 𝒫 : 𝒮 × 𝒜 → Δ ( 𝒮 ) \mathcal{P}:\mathcal{S}\times\mathcal{A}\rightarrow\Delta(\mathcal{S}) is the transition function, where Δ ( X ) \Delta(X) denotes the set of probability distributions over a set X X , and γ ∈ [ 0 , 1 ) \gamma\in[0,1) is a horizon discount factor.
An agent’s behaviour is formalized as a policy π : 𝒮 → Δ ( 𝒜 ) \pi:\mathcal{S}\rightarrow\Delta(\mathcal{A}) which induces a value function V π : 𝒮 → ℝ V^{\pi}:\mathcal{S}\rightarrow\mathbb{R} : V π ( s ) \displaystyle V^{\pi}(s) : = 𝔼 [ ∑ t = 0 ∞ γ t ℛ ( s t , a t ) | s 0 = s , s t , a t ] \displaystyle:=\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}\mathcal{R}(s_{t},a_{t})|s_{0}=s,s_{t},a_{t}\right] = 𝔼 a ∼ π ( s ) [ ℛ ( s , a ) + γ 𝔼 s ′ ∼ 𝒫 ( s , a ) V π ( s ′ ) ] , \displaystyle=\mathbb{E}_{a\sim\pi(s)}\left[\mathcal{R}(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim\mathcal{P}(s,a)}V^{\pi}(s^{\prime})\right],
where s t ∼ 𝒫 ( s t − 1 , a t − 1 ) s_{t}\sim\mathcal{P}(s_{t-1},a_{t-1}) and a t ∼ π ( s t ) a_{t}\sim\pi(s_{t}) . The second line is the well-known Bellman recurrence. It is also convenient to consider the value of actions that differ from those encoded in π \pi via the function Q π : 𝒮 × 𝒜 → ℝ Q^{\pi}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R} : Q π ( s , a ) := ℛ ( s , a ) + γ 𝔼 s ′ ∼ 𝒫 ( s , a ) V π ( s ′ ) Q^{\pi}(s,a):=\mathcal{R}(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim\mathcal{P}(s,a)}V^{\pi}(s^{\prime}) .
It is well known that there exist policies π ∗ \pi^{*} that are optimal in the sense that V ∗ ( s ) := V π ∗ ( s ) ≥ V π ( s ) V^{*}(s):=V^{\pi^{*}}(s)\geq V^{\pi}(s) for all policies π \pi and states s ∈ 𝒮 s\in\mathcal{S} . In reinforcement learning we are typically interested in having agents find these policies by interacting with the environment. One of the most popular ways to do so is via Q Q -learning, where an agent maintains a function Q θ Q_{\theta} , parameterized by θ \theta (e.g. the weights in a neural network), and updates it after observing the transition s → a , r s ′ s\overset{a,r}{\rightarrow}s^{\prime} using the method of temporal differences ( Sutton, 1988 ) : Q θ ( s , a ) ← Q θ ( s , a ) + α ( Q ∗ ( s ′ , a ′ ) − Q θ ( s , a ) ) \displaystyle Q_{\theta}(s,a)\leftarrow Q_{\theta}(s,a)+\alpha\left(Q^{*}(s^{\prime},a^{\prime})-Q_{\theta}(s,a)\right) (1) where α \alpha is a learning rate and the optimal target values Q ∗ ( s ′ , a ′ ) = r + γ max a ′ ∈ 𝒜 Q θ ( s ′ , a ′ ) Q^{*}(s^{\prime},a^{\prime})=r+\gamma\max_{a^{\prime}\in\mathcal{A}}Q_{\theta}(s^{\prime},a^{\prime})
### 2.1 DQN
Mnih et al. (2015) introduced DQN, which combined Q-learning with deep networks. Some of the most salient design choices are: • The Q Q function is represented using a feed forward neural network consisting of three convolutional layers followed by two fully connected layers. Two copies of the Q Q -network are maintained: an online network (parameterized by θ \theta ) and a target network (parameterized by θ ¯ \bar{\theta} ). The online network is updated via the learning process described below, while the target network remains fixed and is synced with the online weights at less frequent (but regular) intervals.
• A large replay buffer D D is maintained to store experienced transitions ( s , a , r , s ′ ) (s,a,r,s^{\prime}) ( Lin, 1992 ) .
• The update in Equation 1 is implemented using the following loss function to update the online network: L ( θ ) = 𝔼 ( s , a , r , s ′ ) ∼ U ( D ) [ ( Y D Q N − Q θ ( s , a ) ) 2 ] \displaystyle L(\theta)=\mathbb{E}_{(s,a,r,s^{\prime})\sim U(D)}[\left(Y^{DQN}-Q_{\theta}(s,a)\right)^{2}] (2) using Y D Q N = ( r + γ max a ′ ∈ 𝒜 Q θ ¯ ( s ′ , a ′ ) ) Y^{DQN}=\left(r+\gamma\max_{a^{\prime}\in\mathcal{A}}Q_{\bar{\theta}}(s^{\prime},a^{\prime})\right) and mini-batches of size 32.
### 2.2 Rainbow
In this section we briefly present the enhancements to DQN that were combined by Hessel et al. (2018) for the Rainbow agent.
Double Q-learning: van Hasselt et al. (2016) added double Q-learning ( Hasselt, 2010 ) to mitigate overestimation bias in the Q Q -estimates by decoupling the maximization of the action from its selection in the target bootstrap.
Prioritized experience replay: Instead of sampling uniformly from the replay buffer ( U ( D ) U(D) ), prioritized experience replay ( Schaul et al., 2016 ) proposed to sample a trajectory t = ( s , a , r , s ′ ) t=(s,a,r,s^{\prime}) with probability p t p_{t} proportional to the temporal difference error.
Dueling networks: Wang et al. (2016) introduced dueling networks by modifying the DQN network architecture. Specifically, two streams share the initial convolutional layers, separately estimating V ∗ ( s ) V^{*}(s) , and the advantages for each action: A ( s , a ) := Q ∗ ( s , a ) − V ∗ ( s ) A(s,a):=Q^{*}(s,a)-V^{*}(s) . The output of the network is a combination of these two streams. Multi-step learning: Instead of computing the temporal difference error using a single-step transition, one can use multi-step targets instead ( Sutton, 1988 ) , where for a trajectory ( s 0 , a 0 , r 0 , s 1 , a 1 , ⋯ ) (s_{0},a_{0},r_{0},s_{1},a_{1},\cdots) and update horizon n n : R t ( n ) := ∑ k = 0 n − 1 γ k r t + k + 1 R_{t}^{(n)}:=\sum_{k=0}^{n-1}\gamma^{k}r_{t+k+1} , yielding the multi-step temporal difference: R t ( n ) + γ n max a ′ ∈ 𝒜 Q θ ¯ ( s t + n , a ′ ) − Q θ ( s t , a t ) R_{t}^{(n)}+\gamma^{n}\max_{a^{\prime}\in\mathcal{A}}Q_{\bar{\theta}}(s_{t+n},a^{\prime})-Q_{\theta}(s_{t},a_{t}) .
Distributional RL: Bellemare et al. (2017) demonstrated that the Bellman recurrence also holds for value distributions : Z ( x , a ) = 𝐷 R ( s , a ) + γ Z ( X ′ , A ′ ) Z(x,a)\overset{D}{=}R(s,a)+\gamma Z(X^{\prime},A^{\prime}) , where Z Z , R R , and ( X ′ , A ′ ) (X^{\prime},A^{\prime}) are random variables representing the return, immediate reward, and next state-action, respectively. The authors present an algorithm (C51) to maintain an estimate Z θ Z_{\theta} of the return distribution Z Z by use of a parameterized categorical distribution with 51 atoms.
Noisy nets: Fortunato et al. (2018) propose replacing the simple ϵ \epsilon -greedy exploration strategy used by DQN with noisy linear layers that include a noisy stream.
## 3 The cost of Rainbow
Although the value of the hybrid agent uncovered by Hessel et al. (2018) is undeniable, this result could have only come from a large research laboratory with ample access to compute. Indeed, each Atari 2600 game from the ALE (there are 57 in total) takes roughly 5 days to fully train using specialized hardware (for example, an NVIDIA Tesla P100 GPU). 1 1 1 The computational expense is not limited to the ALE: MuJoCo tasks from the DM control suite take about 2 days with the same hardware. Additionally, in order to be able to report performance with confidence bounds it is common to use at least five independent runs ( Henderson et al., 2018 ; Machado et al., 2018 ) .
Thus, to provide the convincing empirical evidence for Rainbow, Hessel et al. (2018) required approximately 34,200 GPU hours (or 1425 days). Note that this cost does not include the hyper-parameter tuning that was necessary to optimize the various components. Considering that the cost of a Tesla P100 GPU is around US$6,000, providing this evidence will take an unreasonably long time as it is prohibitively expensive to have multiple GPUs in a typical academic lab so they can be used in parallel. As a reference point, the average minimum monthly wage in South America (excluding Venezuela) is approximately US$313 2 2 2 Taken from https://www.statista.com/statistics/953880/latin-america-minimum-monthly-wages/ ; in other words, one GPU is the equivalent of approximately 20 minimum wages. Needless to say, this expectation is far from inclusive.
In light of this, we wish to investigate three questions: 1. Would Hessel et al. (2018) have arrived at the same qualitative conclusions, had they run their experiments on a set of smaller-scale experiments?
2. Do the results of Hessel et al. (2018) generalize well to non-ALE environments, or are their results overly-specific to the chosen benchmark?
3. Is there scientific value in conducting empirical research in reinforcement learning when restricting oneself to small- to mid-scale environments?
We investigate the first two in Section 4 , and the last in Sections 5 and 6 .
## 4 Revisiting Rainbow
### 4.1 Methodology
We follow a similar process as Hessel et al. (2018) in evaluating the various algorithmic variants mentioned above: we investigate the effect of adding each on top of the original DQN agent as well as the effect of dropping each from the final Rainbow agent, sweeping over learning rates for each. Our implementation is based on the Dopamine framework ( Castro et al., 2018 ) . Note that Dopamine includes a ‘‘lite’’ version of Rainbow, which does not include noisy networks, double DQN, nor dueling networks, but we have added all these components in our implementation 3 3 3 Source code available at https://github.com/JohanSamir/revisiting_rainbow .
We perform our empirical evaluation on small-scale environments (CartPole, Acrobot, LunarLander, and MountainCar) which are all available as part of the OpenAI Gym library ( Brockman et al., 2016 ) (see Appendix A for a detailed description of each environment). We used multilayer perceptrons (MLPs) with 2 layers of 512 units each for these experiments. The agents were all trained on a CPU; it is worth noting that of these environments the one that took longest to train (LunarLander) is still able to finish in under two hours.
In order to strengthen the Rainbow Connection, we also ran a set of experiments on the MinAtar environment ( Young and Tian, 2019 ) , which is a set of miniaturized versions of five ALE games (Asterix, Breakout, Freeway, Seaquest, and SpaceInvaders). These environments are considerably larger than the four classic control environments previously explored, but they are significantly faster to train than regular ALE environments. Specifically, training one of these agents takes approximately 12-14 hours on a P100 GPU. For these experiments, we followed the network architecture used by Young and Tian (2019) consisting of a single convolutional layer followed by a linear layer.
### 4.2 Empirical evaluation