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

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

# Rainbow: Combining Improvements in Deep Reinforcement Learning

###### Abstract

The deep reinforcement learning community has made several independent improvements to the DQN algorithm. However, it is unclear which of these extensions are complementary and can be fruitfully combined. This paper examines six extensions to the DQN algorithm and empirically studies their combination. Our experiments show that the combination provides state-of-the-art performance on the Atari 2600 benchmark, both in terms of data efficiency and final performance. We also provide results from a detailed ablation study that shows the contribution of each component to overall performance.

## Introduction

The many recent successes in scaling reinforcement learning (RL) to complex sequential decision-making problems were kick-started by the Deep Q-Networks algorithm (DQN; ? ? , ? ). Its combination of Q-learning with convolutional neural networks and experience replay enabled it to learn, from raw pixels, how to play many Atari games at human-level performance. Since then, many extensions have been proposed that enhance its speed or stability.

Double DQN (DDQN; ? ? ) addresses an overestimation bias of Q-learning [ 2010 ] , by decoupling selection and evaluation of the bootstrap action. Prioritized experience replay [ 2015 ] improves data efficiency, by replaying more often transitions from which there is more to learn. The dueling network architecture [ 2016 ] helps to generalize across actions by separately representing state values and action advantages. Learning from multi-step bootstrap targets [ 1988 , 1998 ] , as used in A3C [ 2016 ] , shifts the bias-variance trade-off and helps to propagate newly observed rewards faster to earlier visited states. Distributional Q-learning [ 2017 ] learns a categorical distribution of discounted returns, instead of estimating the mean. Noisy DQN [ 2017 ] uses stochastic network layers for exploration. This list is, of course, far from exhaustive.

Each of these algorithms enables substantial performance improvements in isolation. Since they do so by addressing radically different issues, and since they build on a shared framework, they could plausibly be combined. In some cases this has been done: Prioritized DDQN and Dueling DDQN both use double Q-learning, and Dueling DDQN was also combined with prioritized experience replay. In this paper we propose to study an agent that combines all the aforementioned ingredients. We show how these different ideas can be integrated, and that they are indeed largely complementary. In fact, their combination results in new state-of-the-art results on the benchmark suite of 57 Atari 2600 games from the Arcade Learning Environment [ 2013 ] , both in terms of data efficiency and of final performance. Finally we show results from ablation studies to help understand the contributions of the different components.

## Background

Reinforcement learning addresses the problem of an agent learning to act in an environment in order to maximize a scalar reward signal. No direct supervision is provided to the agent, for instance it is never directly told the best action.

### Agents and environments.

At each discrete time step t = 0 , 1 , 2 ​ … t=0,1,2\ldots , the environment provides the agent with an observation S t S_{t} , the agent responds by selecting an action A t A_{t} , and then the environment provides the next reward R t + 1 R_{t+1} , discount γ t + 1 \gamma_{t+1} , and state S t + 1 S_{t+1} . This interaction is formalized as a Markov Decision Process , or MDP, which is a tuple ⟨ 𝒮 , 𝒜 , T , r , γ ⟩ \langle\mathcal{S},\mathcal{A},T,r,\gamma\rangle , where 𝒮 \mathcal{S} is a finite set of states, 𝒜 \mathcal{A} is a finite set of actions, T ( s , a , s ′ ) = P [ S t + 1 = s ′ ∣ S t = s , A t = a ] T(s,a,s^{\prime})=P[S_{t+1}=s^{\prime}\mid S_{t}=s,A_{t}=a] is the (stochastic) transition function, r ( s , a ) = 𝔼 [ R t + 1 ∣ S t = s , A t = a ] r(s,a)=\mathbb{E}[R_{t+1}\mid S_{t}=s,A_{t}=a] is the reward function, and γ ∈ [ 0 , 1 ] \gamma\in[0,1] is a discount factor. In our experiments MDPs will be episodic with a constant γ t = γ \gamma_{t}=\gamma , except on episode termination where γ t = 0 \gamma_{t}=0 , but the algorithms are expressed in the general form.

On the agent side, action selection is given by a policy π \pi that defines a probability distribution over actions for each state. From the state S t S_{t} encountered at time t t , we define the discounted return G t = ∑ k = 0 ∞ γ t ( k ) ​ R t + k + 1 G_{t}=\sum_{k=0}^{\infty}{\gamma_{t}^{(k)}R_{t+k+1}} as the discounted sum of future rewards collected by the agent, where the discount for a reward k k steps in the future is given by the product of discounts before that time, γ t ( k ) = ∏ i = 1 k γ t + i \gamma_{t}^{(k)}=\prod_{i=1}^{k}\gamma_{t+i} . An agent aims to maximize the expected discounted return by finding a good policy.

The policy may be learned directly, or it may be constructed as a function of some other learned quantities. In value-based reinforcement learning, the agent learns an estimate of the expected discounted return, or value, when following a policy π \pi starting from a given state, v π ​ ( s ) = E π ​ [ G t | S t = s ] v^{\pi}(s)=E_{\pi}[G_{t}|S_{t}=s] , or state-action pair, q π ( s , a ) = E π [ G t | S t = s , A t = a ] q^{\pi}(s,a)=E_{\pi}[G_{t}|S_{t}=s,A_{t}=a] . A common way of deriving a new policy from a state-action value function is to act ϵ \epsilon -greedily with respect to the action values. This corresponds to taking the action with the highest value (the greedy action) with probability ( 1 − ϵ ) (1-\epsilon) , and to otherwise act uniformly at random with probability ϵ \epsilon . Policies of this kind are used to introduce a form of exploration : by randomly selecting actions that are sub-optimal according to its current estimates, the agent can discover and correct its estimates when appropriate. The main limitation is that it is difficult to discover alternative courses of action that extend far into the future; this has motivated research on more directed forms of exploration.

### Deep reinforcement learning and DQN.

Large state and/or action spaces make it intractable to learn Q value estimates for each state and action pair independently. In deep reinforcement learning, we represent the various components of agents, such as policies π ⁡ ( s , a ) \pi(s,a) or values q ⁡ ( s , a ) q(s,a) , with deep (i.e., multi-layer) neural networks. The parameters of these networks are trained by gradient descent to minimize some suitable loss function.

In DQN [ 2015 ] deep networks and reinforcement learning were successfully combined by using a convolutional neural net to approximate the action values for a given state S t S_{t} (which is fed as input to the network in the form of a stack of raw pixel frames). At each step, based on the current state, the agent selects an action ϵ \epsilon -greedily with respect to the action values, and adds a transition ( S t , A t , R t + 1 , γ t + 1 , S t + 1 S_{t},A_{t},R_{t+1},\gamma_{t+1},S_{t+1} ) to a replay memory buffer [ 1992 ] , that holds the last million transitions. The parameters of the neural network are optimized by using stochastic gradient descent to minimize the loss ( R t + 1 + γ t + 1 ​ max a ′ ​ q θ ¯ ​ ( S t + 1 , a ′ ) − q θ ​ ( S t , A t ) ) 2 , (R_{t+1}+\gamma_{t+1}\max_{a^{\prime}}q_{\overline{\theta}}(S_{t+1},a^{\prime})-q_{\theta}(S_{t},A_{t}))^{2}\ , (1) where t t is a time step randomly picked from the replay memory. The gradient of the loss is back-propagated only into the parameters θ \theta of the online network (which is also used to select actions); the term θ ¯ \overline{\theta} represents the parameters of a target network ; a periodic copy of the online network which is not directly optimized. The optimization is performed using RMSprop [ 2012 ] , a variant of stochastic gradient descent, on mini-batches sampled uniformly from the experience replay. This means that in the loss above, the time index t t will be a random time index from the last million transitions, rather than the current time. The use of experience replay and target networks enables relatively stable learning of Q values, and led to super-human performance on several Atari games.

## Extensions to DQN

DQN has been an important milestone, but several limitations of this algorithm are now known, and many extensions have been proposed. We propose a selection of six extensions that each have addressed a limitation and improved overall performance. To keep the size of the selection manageable, we picked a set of extensions that address distinct concerns (e.g., just one of the many addressing exploration).

### Double Q-learning.

Conventional Q-learning is affected by an overestimation bias, due to the maximization step in Equation 1 , and this can harm learning. Double Q-learning [ 2010 ] , addresses this overestimation by decoupling, in the maximization performed for the bootstrap target, the selection of the action from its evaluation. It is possible to effectively combine this with DQN [ 2016 ] , using the loss ( R t + 1 + γ t + 1 ​ q θ ¯ ​ ( S t + 1 , arg ⁡ max a ′ ⁡ q θ ​ ( S t + 1 , a ′ ) ) − q θ ​ ( S t , A t ) ) 2 . (R_{t+1}+\gamma_{t+1}q_{\overline{\theta}}(S_{t+1},\argmax_{a^{\prime}}q_{\theta}(S_{t+1},a^{\prime}))-q_{\theta}(S_{t},A_{t}))^{2}. This change was shown to reduce harmful overestimations that were present for DQN, thereby improving performance.

### Prioritized replay.

DQN samples uniformly from the replay buffer. Ideally, we want to sample more frequently those transitions from which there is much to learn. As a proxy for learning potential, prioritized experience replay [ 2015 ] samples transitions with probability p t p_{t} relative to the last encountered absolute TD error : p t ∝ | R t + 1 + γ t + 1 ​ max a ′ ​ q θ ¯ ​ ( S t + 1 , a ′ ) − q θ ​ ( S t , A t ) | ω , p_{t}\propto\left|R_{t+1}+\gamma_{t+1}\max_{a^{\prime}}q_{\overline{\theta}}(S_{t+1},a^{\prime})-q_{\theta}(S_{t},A_{t})\right|^{\omega}\,, where ω \omega is a hyper-parameter that determines the shape of the distribution. New transitions are inserted into the replay buffer with maximum priority, providing a bias towards recent transitions. Note that stochastic transitions might also be favoured, even when there is little left to learn about them.

### Dueling networks.

The dueling network is a neural network architecture designed for value based RL. It features two streams of computation, the value and advantage streams, sharing a convolutional encoder, and merged by a special aggregator [ 2016 ] . This corresponds to the following factorization of action values: q θ ​ ( s , a ) = v η ​ ( f ξ ​ ( s ) ) + a ψ ​ ( f ξ ​ ( s ) , a ) − ∑ a ′ a ψ ​ ( f ξ ​ ( s ) , a ′ ) N actions , q_{\theta}(s,a)=v_{\eta}(f_{\xi}(s))+a_{\psi}(f_{\xi}(s),a)-\frac{\sum_{a^{\prime}}a_{\psi}(f_{\xi}(s),a^{\prime})}{N_{\text{actions}}}, where ξ \xi , η \eta , and ψ \psi are, respectively, the parameters of the shared encoder f ξ f_{\xi} , of the value stream v η v_{\eta} , and of the advantage stream a ψ a_{\psi} ; and θ = { ξ , η , ψ } \theta=\{\xi,\eta,\psi\} is their concatenation.

### Multi-step learning.

Q-learning accumulates a single reward and then uses the greedy action at the next step to bootstrap. Alternatively, forward-view multi-step targets can be used [ 1988 ] . We define the truncated n n -step return from a given state S t S_{t} as R t ( n ) ≡ ∑ k = 0 n − 1 γ t ( k ) ​ R t + k + 1 . R_{t}^{(n)}\equiv\sum_{k=0}^{n-1}{\gamma_{t}^{(k)}R_{t+k+1}}\,. (2) A multi-step variant of DQN is then defined by minimizing the alternative loss, ( R t ( n ) + γ t ( n ) ​ max a ′ ​ q θ ¯ ​ ( S t + n , a ′ ) − q θ ​ ( S t , A t ) ) 2 . (R_{t}^{(n)}+\gamma_{t}^{(n)}\max_{a^{\prime}}q_{\overline{\theta}}(S_{t+n},a^{\prime})-q_{\theta}(S_{t},A_{t}))^{2}. Multi-step targets with suitably tuned n n often lead to faster learning [ 1998 ] .

### Distributional RL.

We can learn to approximate the distribution of returns instead of the expected return. Recently Bellemare, Dabney, and Munos (2017) proposed to model such distributions with probability masses placed on a discrete support 𝒛 {\bm{z}} , where 𝒛 \bm{z} is a vector with N atoms ∈ ℕ + N_{\text{atoms}}\in\mathbb{N}^{+} atoms , defined by z i = v min + ( i − 1 ) ​ v max − v min N atoms − 1 z^{i}=v_{\min}+(i-1)\frac{v_{\max}-v_{\min}}{N_{\text{atoms}}-1} for i ∈ { 1 , … , N atoms } i\in\{1,\ldots,N_{\text{atoms}}\} . The approximating distribution d t d_{t} at time t t is defined on this support, with the probability mass p θ i ​ ( S t , A t ) p^{i}_{\theta}(S_{t},A_{t}) on each atom i i , such that d t = ( 𝒛 , 𝒑 θ ​ ( S t , A t ) ) d_{t}=(\bm{z},\bm{p}_{\theta}(S_{t},A_{t})) . The goal is to update θ \theta such that this distribution closely matches the actual distribution of returns.

To learn the probability masses, the key insight is that return distributions satisfy a variant of Bellman’s equation. For a given state S t S_{t} and action A t A_{t} , the distribution of the returns under the optimal policy π ∗ \pi^{*} should match a target distribution defined by taking the distribution for the next state S t + 1 S_{t+1} and action a t + 1 ∗ = π ∗ ​ ( S t + 1 ) a^{*}_{t+1}=\pi^{*}(S_{t+1}) , contracting it towards zero according to the discount, and shifting it by the reward (or distribution of rewards, in the stochastic case). A distributional variant of Q-learning is then derived by first constructing a new support for the target distribution, and then minimizing the Kullbeck-Leibler divergence between the distribution d t d_{t} and the target distribution d t ′ ≡ ( R t + 1 + γ t + 1 ​ 𝒛 , 𝒑 θ ¯ ​ ( S t + 1 , a ¯ t + 1 ∗ ) ) d^{\prime}_{t}\equiv(R_{t+1}+\gamma_{t+1}\bm{z},~~\bm{p}_{\overline{\theta}}(S_{t+1},\overline{a}^{*}_{t+1})) , D KL ( Φ 𝒛 d t ′ | | d t ) . D_{\text{KL}}(\Phi_{\bm{z}}d^{\prime}_{t}||d_{t})\,. (3) Here Φ 𝒛 \Phi_{\bm{z}} is a L2-projection of the target distribution onto the fixed support 𝒛 \bm{z} , and a ¯ t + 1 ∗ = arg ⁡ max a ⁡ q θ ¯ ​ ( S t + 1 , a ) \overline{a}^{*}_{t+1}=\argmax_{a}q_{\overline{\theta}}(S_{t+1},a) is the greedy action with respect to the mean action values q θ ¯ ​ ( S t + 1 , a ) = 𝒛 ⊤ ​ 𝒑 θ ​ ( S t + 1 , a ) q_{\overline{\theta}}(S_{t+1},a)=\bm{z}^{\top}\bm{p}_{\theta}(S_{t+1},a) in state S t + 1 S_{t+1} .

As in the non-distributional case, we can use a frozen copy of the parameters θ ¯ \overline{\theta} to construct the target distribution. The parametrized distribution can be represented by a neural network, as in DQN, but with N atoms × N actions N_{\text{atoms}}\times N_{\text{actions}} outputs. A softmax is applied independently for each action dimension of the output to ensure that the distribution for each action is appropriately normalized.

### Noisy Nets.

The limitations of exploring using ϵ \epsilon -greedy policies are clear in games such as Montezuma’s Revenge, where many actions must be executed to collect the first reward. Noisy Nets [ 2017 ] propose a noisy linear layer that combines a deterministic and noisy stream, 𝒚 = ( 𝒃 + W ​ 𝒙 ) + ( 𝒃 n ​ o ​ i ​ s ​ y ⊙ ϵ b + ( W n ​ o ​ i ​ s ​ y ⊙ ϵ w ) ​ 𝒙 ) , \bm{y}=(\bm{b}+\textbf{W}\bm{x})+(\bm{b}_{noisy}\odot\epsilon^{b}+(\textbf{W}_{noisy}\odot\epsilon^{w})\bm{x}), (4) where ϵ b \epsilon^{b} and ϵ w \epsilon^{w} are random variables, and ⊙ \odot denotes the element-wise product. This transformation can then be used in place of the standard linear 𝒚 = 𝒃 + W ​ 𝒙 \bm{y}=\bm{b}+\textbf{W}\bm{x} . Over time, the network can learn to ignore the noisy stream, but will do so at different rates in different parts of the state space, allowing state-conditional exploration with a form of self-annealing.

## The Integrated Agent

In this paper we integrate all the aforementioned components into a single integrated agent, which we call Rainbow .