Dueling Network Architectures for Deep Reinforcement Learning — part 1/3
Cleaned-text code points [0, 15349). Bibliography omitted here; source.md includes it.
# Dueling Network Architectures for Deep Reinforcement Learning
###### Abstract
In recent years there have been many successes of using deep representations in reinforcement learning. Still, many of these applications use conventional architectures, such as convolutional networks, LSTMs, or auto-encoders. In this paper, we present a new neural network architecture for model-free reinforcement learning. Our dueling network represents two separate estimators: one for the state value function and one for the state-dependent action advantage function. The main benefit of this factoring is to generalize learning across actions without imposing any change to the underlying reinforcement learning algorithm. Our results show that this architecture leads to better policy evaluation in the presence of many similar-valued actions. Moreover, the dueling architecture enables our RL agent to outperform the state-of-the-art on the Atari 2600 domain.
## 1 Introduction
Over the past years, deep learning has contributed to dramatic advances in scalability and performance of machine learning ( LeCun et al., 2015 ) . One exciting application is the sequential decision-making setting of reinforcement learning (RL) and control. Notable examples include deep Q-learning ( Mnih et al., 2015 ) , deep visuomotor policies ( Levine et al., 2015 ) , attention with recurrent networks ( Ba et al., 2015 ) , and model predictive control with embeddings ( Watter et al., 2015 ) . Other recent successes include massively parallel frameworks ( Nair et al., 2015 ) and expert move prediction in the game of Go ( Maddison et al., 2015 ) , which produced policies matching those of Monte Carlo tree search programs, and squarely beaten a professional player when combined with search ( Silver et al., 2016 ) .
In spite of this, most of the approaches for RL use standard neural networks, such as convolutional networks, MLPs, LSTMs and autoencoders. The focus in these recent advances has been on designing improved control and RL algorithms, or simply on incorporating existing neural network architectures into RL methods. Here, we take an alternative but complementary approach of focusing primarily on innovating a neural network architecture that is better suited for model-free RL. This approach has the benefit that the new network can be easily combined with existing and future algorithms for RL. That is, this paper advances a new network (Figure 1 ), but uses already published algorithms.
The proposed network architecture, which we name the dueling architecture , explicitly separates the representation of state values and (state-dependent) action advantages. The dueling architecture consists of two streams that represent the value and advantage functions, while sharing a common convolutional feature learning module. The two streams are combined via a special aggregating layer to produce an estimate of the state-action value function Q Q as shown in Figure 1 . This dueling network should be understood as a single Q Q network with two streams that replaces the popular single-stream Q Q network in existing algorithms such as Deep Q-Networks ( Mnih et al., 2015 , DQN;) . The dueling network automatically produces separate estimates of the state value function and advantage function, without any extra supervision.
Intuitively, the dueling architecture can learn which states are (or are not) valuable, without having to learn the effect of each action for each state. This is particularly useful in states where its actions do not affect the environment in any relevant way. To illustrate this, consider the saliency maps shown in Figure 2 1 1 1 https://www.youtube.com/playlist?list=PLVFXyCSfS2Pau0gBh0mwTxDmutywWyFBP . These maps were generated by computing the Jacobians of the trained value and advantage streams with respect to the input video, following the method proposed by Simonyan et al. (2013) . (The experimental section describes this methodology in more detail.) The figure shows the value and advantage saliency maps for two different time steps. In one time step (leftmost pair of images), we see that the value network stream pays attention to the road and in particular to the horizon, where new cars appear. It also pays attention to the score. The advantage stream on the other hand does not pay much attention to the visual input because its action choice is practically irrelevant when there are no cars in front. However, in the second time step (rightmost pair of images) the advantage stream pays attention as there is a car immediately in front, making its choice of action very relevant.
Value Advantage
Value Advantage
In the experiments, we demonstrate that the dueling architecture can more quickly identify the correct action during policy evaluation as redundant or similar actions are added to the learning problem.
We also evaluate the gains brought in by the dueling architecture on the challenging Atari 2600 testbed. Here, an RL agent with the same structure and hyper-parameters must be able to play 57 different games by observing image pixels and game scores only. The results illustrate vast improvements over the single-stream baselines of Mnih et al. (2015) and van Hasselt et al. (2015) . The combination of prioritized replay ( Schaul et al., 2016 ) with the proposed dueling network results in the new state-of-the-art for this popular domain.
### 1.1 Related Work
The notion of maintaining separate value and advantage functions goes back to Baird (1993) . In Baird’s original advantage updating algorithm, the shared Bellman residual update equation is decomposed into two updates: one for a state value function, and one for its associated advantage function. Advantage updating was shown to converge faster than Q-learning in simple continuous time domains in ( Harmon et al., 1995 ) . Its successor, the advantage learning algorithm, represents only a single advantage function ( Harmon & Baird, 1996 ) .
The dueling architecture represents both the value V ( s ) V(s) and advantage A ( s , a ) A(s,a) functions with a single deep model whose output combines the two to produce a state-action value Q ( s , a ) Q(s,a) . Unlike in advantage updating, the representation and algorithm are decoupled by construction. Consequently, the dueling architecture can be used in combination with a myriad of model free RL algorithms.
There is a long history of advantage functions in policy gradients, starting with ( Sutton et al., 2000 ) . As a recent example of this line of work, Schulman et al. (2015) estimate advantage values online to reduce the variance of policy gradient algorithms.
There have been several attempts at playing Atari with deep reinforcement learning, including Mnih et al. (2015) ; Guo et al. (2014) ; Stadie et al. (2015) ; Nair et al. (2015) ; van Hasselt et al. (2015) ; Bellemare et al. (2016) and Schaul et al. (2016) . The results of Schaul et al. (2016) are the current published state-of-the-art.
## 2 Background
We consider a sequential decision making setup, in which an agent interacts with an environment ℰ \mathcal{E} over discrete time steps, see Sutton & Barto (1998) for an introduction. In the Atari domain, for example, the agent perceives a video s t s_{t} consisting of M M image frames: s t = ( x t − M + 1 , … , x t ) ∈ 𝒮 s_{t}=(x_{t-M+1},\ldots,x_{t})\in\mathcal{S} at time step t t . The agent then chooses an action from a discrete set a t ∈ 𝒜 = { 1 , … , | 𝒜 | } a_{t}\in\mathcal{A}=\{1,\ldots,|\mathcal{A}|\} and observes a reward signal r t r_{t} produced by the game emulator.
The agent seeks maximize the expected discounted return, where we define the discounted return as R t = ∑ τ = t ∞ γ τ − t r τ R_{t}=\sum_{\tau=t}^{\infty}\gamma^{\tau-t}r_{\tau} . In this formulation, γ ∈ [ 0 , 1 ] \gamma\in[0,1] is a discount factor that trades-off the importance of immediate and future rewards.
For an agent behaving according to a stochastic policy π \pi , the values of the state-action pair ( s , a ) (s,a) and the state s s are defined as follows Q π ( s , a ) \displaystyle Q^{\pi}(s,a) = \displaystyle= 𝔼 [ R t | s t = s , a t = a , π ] , and \displaystyle\mathbb{E}\left[{\left.R_{t}\right|s_{t}=s,a_{t}=a,\pi}\right],~\mbox{ and } V π ( s ) \displaystyle V^{\pi}(s) = \displaystyle= 𝔼 a ∼ π ( s ) [ Q π ( s , a ) ] . \displaystyle\mathbb{E}_{{a\sim\pi(s)}}\left[{Q^{\pi}(s,a)}\right]. (1)
The preceding state-action value function ( Q Q function for short) can be computed recursively with dynamic programming: Q π ( s , a ) = 𝔼 s ′ [ r + γ 𝔼 a ′ ∼ π ( s ′ ) [ Q π ( s ′ , a ′ ) ] | s , a , π ] . Q^{\pi}(s,a)=\mathbb{E}_{{s^{\prime}}}\left[{r+\gamma\mathbb{E}_{{a^{\prime}\sim\pi(s^{\prime})}}\left[{Q^{\pi}(s^{\prime},a^{\prime})}\right]~|~s,a,\pi}\right]. We define the optimal Q ∗ ( s , a ) = max π Q π ( s , a ) . Q^{*}(s,a)=\max_{\pi}Q^{\pi}(s,a). Under the deterministic policy a = arg max a ′ ∈ 𝒜 Q ∗ ( s , a ′ ) a=\argmax_{a^{\prime}\in\mathcal{A}}Q^{*}(s,a^{\prime}) , it follows that V ∗ ( s ) = max a Q ∗ ( s , a ) . V^{*}(s)=\max_{a}Q^{*}(s,a). From this, it also follows that the optimal Q Q function satisfies the Bellman equation: Q ∗ ( s , a ) = 𝔼 s ′ [ r + γ max a ′ Q ∗ ( s ′ , a ′ ) | s , a ] . Q^{*}(s,a)=\mathbb{E}_{s^{\prime}}\left[r+\gamma\max_{a^{\prime}}Q^{*}(s^{\prime},a^{\prime})~|~s,a\right]. (2)
We define another important quantity, the advantage function , relating the value and Q Q functions: A π ( s , a ) = Q π ( s , a ) − V π ( s ) . A^{\pi}(s,a)=Q^{\pi}(s,a)-V^{\pi}(s). (3) Note that 𝔼 a ∼ π ( s ) [ A π ( s , a ) ] = 0 \mathbb{E}_{{a\sim\pi(s)}}\left[{A^{\pi}(s,a)}\right]=0 . Intuitively, the value function V V measures the how good it is to be in a particular state s s . The Q Q function, however, measures the the value of choosing a particular action when in this state. The advantage function subtracts the value of the state from the Q function to obtain a relative measure of the importance of each action.
### 2.1 Deep Q-networks
The value functions as described in the preceding section are high dimensional objects. To approximate them, we can use a deep Q Q -network: Q ( s , a , θ ) Q(s,a;\theta) with parameters θ \theta . To estimate this network, we optimize the following sequence of loss functions at iteration i i : L i ( θ i ) = 𝔼 s , a , r , s ′ [ ( y i D Q N − Q ( s , a , θ i ) ) 2 ] , L_{i}(\theta_{i})=\mathbb{E}_{s,a,r,s^{\prime}}\left[\left(y_{i}^{DQN}-Q(s,a;\theta_{i})\right)^{2}\right], (4) with y i D Q N = r + γ max a ′ Q ( s ′ , a ′ , θ − ) , y_{i}^{DQN}=r+\gamma\max_{a^{\prime}}Q(s^{\prime},a^{\prime};\theta^{-}), (5) where θ − \theta^{-} represents the parameters of a fixed and separate target network . We could attempt to use standard Q Q -learning to learn the parameters of the network Q ( s , a , θ ) Q(s,a;\theta) online. However, this estimator performs poorly in practice. A key innovation in ( Mnih et al., 2015 ) was to freeze the parameters of the target network Q ( s ′ , a ′ , θ − ) Q(s^{\prime},a^{\prime};\theta^{-}) for a fixed number of iterations while updating the online network Q ( s , a , θ i ) Q(s,a;\theta_{i}) by gradient descent. (This greatly improves the stability of the algorithm.) The specific gradient update is ∇ θ i L i ( θ i ) = 𝔼 s , a , r , s ′ [ ( y i D Q N − Q ( s , a , θ i ) ) ∇ θ i Q ( s , a , θ i ) ] \displaystyle\nabla_{\theta_{i}}L_{i}(\theta_{i})=\displaystyle{\mathbb{E}_{s,a,r,s^{\prime}}}\Big[\hskip-2.84526pt\left(y_{i}^{DQN}-Q(s,a;\theta_{i})\right)\hskip-2.84526pt\nabla_{\theta_{i}}Q(s,a;\theta_{i})\Big]
This approach is model free in the sense that the states and rewards are produced by the environment. It is also off-policy because these states and rewards are obtained with a behavior policy (epsilon greedy in DQN) different from the online policy that is being learned.
Another key ingredient behind the success of DQN is experience replay ( Lin, 1993 ; Mnih et al., 2015 ) . During learning, the agent accumulates a dataset 𝒟 t = { e 1 , e 2 , … , e t } \mathcal{D}_{t}=\{e_{1},e_{2},\ldots,e_{t}\} of experiences e t = ( s t , a t , r t , s t + 1 ) e_{t}=(s_{t},a_{t},r_{t},s_{t+1}) from many episodes. When training the Q Q -network, instead only using the current experience as prescribed by standard temporal-difference learning, the network is trained by sampling mini-batches of experiences from 𝒟 \mathcal{D} uniformly at random. The sequence of losses thus takes the form L i ( θ i ) = 𝔼 ( s , a , r , s ′ ) ∼ 𝒰 ( 𝒟 ) [ ( y i D Q N − Q ( s , a , θ i ) ) 2 ] . L_{i}(\theta_{i})=\mathbb{E}_{(s,a,r,s^{\prime})\sim\mathcal{U}(\mathcal{D})}\left[\left(y_{i}^{DQN}-Q(s,a;\theta_{i})\right)^{2}\right]. Experience replay increases data efficiency through re-use of experience samples in multiple updates and, importantly, it reduces variance as uniform sampling from the replay buffer reduces the correlation among the samples used in the update.
### 2.2 Double Deep Q-networks
The previous section described the main components of DQN as presented in ( Mnih et al., 2015 ) . In this paper, we use the improved Double DQN (DDQN) learning algorithm of van Hasselt et al. (2015) . In Q-learning and DQN, the max \max operator uses the same values to both select and evaluate an action. This can therefore lead to overoptimistic value estimates ( van Hasselt, 2010 ) . To mitigate this problem, DDQN uses the following target: y i D D Q N = r + γ Q ( s ′ , arg max a ′ Q ( s ′ , a ′ , θ i ) , θ − ) . y_{i}^{DDQN}=r+\gamma Q(s^{\prime},\argmax_{a^{\prime}}Q(s^{\prime},a^{\prime};\theta_{i});\theta^{-}). (6) DDQN is the same as for DQN (see Mnih et al. (2015) ), but with the target y i D Q N y_{i}^{DQN} replaced by y i D D Q N y_{i}^{DDQN} . The pseudo-code for DDQN is presented in Appendix A .
### 2.3 Prioritized Replay
A recent innovation in prioritized experience replay ( Schaul et al., 2016 ) built on top of DDQN and further improved the state-of-the-art. Their key idea was to increase the replay probability of experience tuples that have a high expected learning progress (as measured via the proxy of absolute TD-error). This led to both faster learning and to better final policy quality across most games of the Atari benchmark suite, as compared to uniform experience replay.
To strengthen the claim that our dueling architecture is complementary to algorithmic innovations, we show that it improves performance for both the uniform and the prioritized replay baselines (for which we picked the easier to implement rank-based variant), with the resulting prioritized dueling variant holding the new state-of-the-art.
## 3 The Dueling Network Architecture
The key insight behind our new architecture, as illustrated in Figure 2 , is that for many states, it is unnecessary to estimate the value of each action choice. For example, in the Enduro game setting, knowing whether to move left or right only matters when a collision is eminent. In some states, it is of paramount importance to know which action to take, but in many other states the choice of action has no repercussion on what happens. For bootstrapping based algorithms, however, the estimation of state values is of great importance for every state.