Dueling Network Architectures for Deep Reinforcement Learning — part 2/3
Cleaned-text code points [15349, 30920). Bibliography omitted here; source.md includes it.
To bring this insight to fruition, we design a single Q Q -network architecture, as illustrated in Figure 1 , which we refer to as the dueling network. The lower layers of the dueling network are convolutional as in the original DQNs ( Mnih et al., 2015 ) . However, instead of following the convolutional layers with a single sequence of fully connected layers, we instead use two sequences (or streams) of fully connected layers. The streams are constructed such that they have they have the capability of providing separate estimates of the value and advantage functions. Finally, the two streams are combined to produce a single output Q Q function. As in ( Mnih et al., 2015 ) , the output of the network is a set of Q Q values, one for each action.
Since the output of the dueling network is a Q Q function, it can be trained with the many existing algorithms, such as DDQN and SARSA. In addition, it can take advantage of any improvements to these algorithms, including better replay memories, better exploration policies, intrinsic motivation, and so on.
The module that combines the two streams of fully-connected layers to output a Q Q estimate requires very thoughtful design.
From the expressions for advantage Q π ( s , a ) = V π ( s ) + A π ( s , a ) Q^{\pi}(s,a)=V^{\pi}(s)+A^{\pi}(s,a) and state-value V π ( s ) = 𝔼 a ∼ π ( s ) [ Q π ( s , a ) ] V^{\pi}(s)=\mathbb{E}_{{a\sim\pi(s)}}\left[{Q^{\pi}(s,a)}\right] , it follows that 𝔼 a ∼ π ( s ) [ A π ( s , a ) ] = 0 \mathbb{E}_{{a\sim\pi(s)}}\left[{A^{\pi}(s,a)}\right]=0 . Moreover, for a deterministic policy, a ∗ = arg max a ′ ∈ 𝒜 Q ( s , a ′ ) a^{*}=\argmax_{a^{\prime}\in\mathcal{A}}Q(s,a^{\prime}) , it follows that Q ( s , a ∗ ) = V ( s ) Q(s,a^{*})=V(s) and hence A ( s , a ∗ ) = 0 A(s,a^{*})=0 .
Let us consider the dueling network shown in Figure 1 , where we make one stream of fully-connected layers output a scalar V ( s , θ , β ) {V}(s;\theta,\beta) , and the other stream output an | 𝒜 | |\mathcal{A}| -dimensional vector A ( s , a , θ , α ) {A}(s,a;\theta,\alpha) . Here, θ \theta denotes the parameters of the convolutional layers, while α \alpha and β \beta are the parameters of the two streams of fully-connected layers.
Using the definition of advantage, we might be tempted to construct the aggregating module as follows: Q ( s , a , θ , α , β ) = V ( s , θ , β ) + A ( s , a , θ , α ) , Q(s,a;\theta,\alpha,\beta)={V}(s;\theta,\beta)+{A}(s,a;\theta,\alpha), (7) Note that this expression applies to all ( s , a ) (s,a) instances; that is, to express equation ( 7 ) in matrix form we need to replicate the scalar, V ( s , θ , β ) {V}(s;\theta,\beta) , | 𝒜 | |\mathcal{A}| times.
However, we need to keep in mind that Q ( s , a , θ , α , β ) Q(s,a;\theta,\alpha,\beta) is only a parameterized estimate of the true Q Q -function. Moreover, it would be wrong to conclude that V ( s , θ , β ) {V}(s;\theta,\beta) is a good estimator of the state-value function, or likewise that A ( s , a , θ , α ) {A}(s,a;\theta,\alpha) provides a reasonable estimate of the advantage function.
Equation ( 7 ) is unidentifiable in the sense that given Q Q we cannot recover V {V} and A {A} uniquely. To see this, add a constant to V ( s , θ , β ) {V}(s;\theta,\beta) and subtract the same constant from A ( s , a , θ , α ) {A}(s,a;\theta,\alpha) . This constant cancels out resulting in the same Q Q value. This lack of identifiability is mirrored by poor practical performance when this equation is used directly.
To address this issue of identifiability, we can force the advantage function estimator to have zero advantage at the chosen action. That is, we let the last module of the network implement the forward mapping Q ( s , a , θ , α , β ) = V ( s , θ , β ) + ( A ( s , a , θ , α ) − max a ′ ∈ | 𝒜 | A ( s , a ′ , θ , α ) ) . Q(s,a;\theta,\alpha,\beta)={V}(s;\theta,\beta)~+\\ \left({A}(s,a;\theta,\alpha)-\max_{a^{\prime}\in|\mathcal{A}|}{A}(s,a^{\prime};\theta,\alpha)\right). (8) Now, for a ∗ = arg max a ′ ∈ 𝒜 Q ( s , a ′ , θ , α , β ) = arg max a ′ ∈ 𝒜 A ( s , a ′ , θ , α ) a^{*}=\argmax_{a^{\prime}\in\mathcal{A}}Q(s,a^{\prime};\theta,\alpha,\beta)=\argmax_{a^{\prime}\in\mathcal{A}}A(s,a^{\prime};\theta,\alpha) , we obtain Q ( s , a ∗ , θ , α , β ) = V ( s , θ , β ) Q(s,a^{*};\theta,\alpha,\beta)={V}(s;\theta,\beta) . Hence, the stream V ( s , θ , β ) {V}(s;\theta,\beta) provides an estimate of the value function, while the other stream produces an estimate of the advantage function.
An alternative module replaces the max operator with an average: Q ( s , a , θ , α , β ) = V ( s , θ , β ) + ( A ( s , a , θ , α ) − 1 | 𝒜 | ∑ a ′ A ( s , a ′ , θ , α ) ) . Q(s,a;\theta,\alpha,\beta)={V}(s;\theta,\beta)~+\\ \left({A}(s,a;\theta,\alpha)-\frac{1}{|\mathcal{A}|}\sum_{a^{\prime}}{A}(s,a^{\prime};\theta,\alpha)\right). (9) On the one hand this loses the original semantics of V V and A A because they are now off-target by a constant, but on the other hand it increases the stability of the optimization: with ( 9 ) the advantages only need to change as fast as the mean, instead of having to compensate any change to the optimal action’s advantage in ( 8 ). We also experimented with a softmax version of equation ( 8 ), but found it to deliver similar results to the simpler module of equation ( 9 ). Hence, all the experiments reported in this paper use the module of equation ( 9 ).
Note that while subtracting the mean in equation ( 9 ) helps with identifiability, it does not change the relative rank of the A {A} (and hence Q Q ) values, preserving any greedy or ϵ \epsilon -greedy policy based on Q Q values from equation ( 7 ). When acting, it suffices to evaluate the advantage stream to make decisions.
It is important to note that equation ( 9 ) is viewed and implemented as part of the network and not as a separate algorithmic step. Training of the dueling architectures, as with standard Q Q networks (e.g. the deep Q Q -network of Mnih et al. (2015) ), requires only back-propagation. The estimates V ( s , θ , β ) {V}(s;\theta,\beta) and A ( s , a , θ , α ) {A}(s,a;\theta,\alpha) are computed automatically without any extra supervision or algorithmic modifications.
As the dueling architecture shares the same input-output interface with standard Q Q networks, we can recycle all learning algorithms with Q Q networks ( e.g. , DDQN and SARSA) to train the dueling architecture.
## 4 Experiments
We now show the practical performance of the dueling network. We start with a simple policy evaluation task and then show larger scale results for learning policies for general Atari game-playing.
### 4.1 Policy evaluation
We start by measuring the performance of the dueling architecture on a policy evaluation task. We choose this particular task because it is very useful for evaluating network architectures, as it is devoid of confounding factors such as the choice of exploration strategy, and the interaction between policy improvement and policy evaluation.
In this experiment, we employ temporal difference learning (without eligibility traces, i.e. , λ = 0 \lambda=0 ) to learn Q Q values. More specifically, given a behavior policy π \pi , we seek to estimate the state-action value Q π ( ⋅ , ⋅ ) Q^{\pi}(\cdot,\cdot) by optimizing the sequence of costs of equation ( 4 ), with target y i = r + γ 𝔼 a ′ ∼ π ( s ′ ) [ Q ( s ′ , a ′ , θ i ) ] . y_{i}=r+\gamma\mathbb{E}_{a^{\prime}\sim\pi(s^{\prime})}\left[Q(s^{\prime},a^{\prime};\theta_{i})\right]. The above update rule is the same as that of Expected SARSA ( van Seijen et al., 2009 ) . We, however, do not modify the behavior policy as in Expected SARSA.
To evaluate the learned Q Q values, we choose a simple environment where the exact Q π ( s , a ) Q^{\pi}(s,a) values can be computed separately for all ( s , a ) ∈ 𝒮 × 𝒜 (s,a)\in\cal{S}\times\cal{A} . This environment, which we call the corridor is composed of three connected corridors. A schematic drawing of the corridor environment is shown in Figure 3 , The agent starts from the bottom left corner of the environment and must move to the top right to get the largest reward. A total of 5 5 actions are available: go up, down, left, right and no-op. We also have the freedom of adding an arbitrary number of no-op actions. In our setup, the two vertical sections both have 10 states while the horizontal section has 50.
We use an ϵ \epsilon -greedy policy as the behavior policy π \pi , which chooses a random action with probability ϵ \epsilon or an action according to the optimal Q Q function arg max a ∈ 𝒜 Q ∗ ( s , a ) \argmax_{a\in\cal{A}}Q^{*}(s,a) with probability 1 − ϵ 1-\epsilon . In our experiments, ϵ \epsilon is chosen to be 0.001 0.001 .
We compare a single-stream Q Q architecture with the dueling architecture on three variants of the corridor environment with 5, 10 and 20 actions respectively. The 10 and 20 action variants are formed by adding no-ops to the original environment. We measure performance by Squared Error (SE) against the true state values: ∑ s ∈ 𝒮 , a ∈ 𝒜 ( Q ( s , a , θ ) − Q π ( s , a ) ) 2 \sum_{s\in\mathcal{S},a\in\mathcal{A}}(Q(s,a;\theta)-Q^{\pi}(s,a))^{2} . The single-stream architecture is a three layer MLP with 50 50 units on each hidden layer. The dueling architecture is also composed of three layers. After the first hidden layer of 50 units, however, the network branches off into two streams each of them a two layer MLP with 25 hidden units. The results of the comparison are summarized in Figure 3 .
The results show that with 5 5 actions, both architectures converge at about the same speed. However, when we increase the number of actions, the dueling architecture performs better than the traditional Q Q -network. In the dueling network, the stream V ( s , θ , β ) {V}(s;\theta,\beta) learns a general value that is shared across many similar actions at s s , hence leading to faster convergence. This is a very promising result because many control tasks with large action spaces have this property, and consequently we should expect that the dueling network will often lead to much faster convergence than a traditional single stream network. In the following section, we will indeed see that the dueling network results in substantial gains in performance in a wide-range of Atari games.
### 4.2 General Atari Game-Playing
We perform a comprehensive evaluation of our proposed method on the Arcade Learning Environment ( Bellemare et al., 2013 ) , which is composed of 57 Atari games. The challenge is to deploy a single algorithm and architecture, with a fixed set of hyper-parameters, to learn to play all the games given only raw pixel observations and game rewards. This environment is very demanding because it is both comprised of a large number of highly diverse games and the observations are high-dimensional.
We follow closely the setup of van Hasselt et al. (2015) and compare to their results using single-stream Q Q -networks. We train the dueling network with the DDQN algorithm as presented in Appendix A . At the end of this section, we incorporate prioritized experience replay ( Schaul et al., 2016 ) .
Our network architecture has the same low-level convolutional structure of DQN ( Mnih et al., 2015 ; van Hasselt et al., 2015 ) . There are 3 convolutional layers followed by 2 fully-connected layers. The first convolutional layer has 32 8 × 8 8\times 8 filters with stride 4, the second 64 4 × 4 4\times 4 filters with stride 2, and the third and final convolutional layer consists 64 3 × 3 3\times 3 filters with stride 1. As shown in Figure 1 , the dueling network splits into two streams of fully connected layers. The value and advantage streams both have a fully-connected layer with 512 units. The final hidden layers of the value and advantage streams are both fully-connected with the value stream having one output and the advantage as many outputs as there are valid actions 2 2 2 The number of actions ranges between 3-18 actions in the ALE environment. . We combine the value and advantage streams using the module described by Equation ( 9 ). Rectifier non-linearities ( Fukushima, 1980 ) are inserted between all adjacent layers.
We adopt the optimizers and hyper-parameters of van Hasselt et al. (2015) , with the exception of the learning rate which we chose to be slightly lower (we do not do this for double DQN as it can deteriorate its performance). Since both the advantage and the value stream propagate gradients to the last convolutional layer in the backward pass, we rescale the combined gradient entering the last convolutional layer by 1 / 2 1/\sqrt{2} . This simple heuristic mildly increases stability. In addition, we clip the gradients to have their norm less than or equal to 10. This clipping is not standard practice in deep RL, but common in recurrent network training ( Bengio et al., 2013 ) .
To isolate the contributions of the dueling architecture, we re-train DDQN with a single stream network using exactly the same procedure as described above. Specifically, we apply gradient clipping, and use 1024 1024 hidden units for the first fully-connected layer of the network so that both architectures (dueling and single) have roughly the same number of parameters. We refer to this re-trained model as Single Clip , while the original trained model of van Hasselt et al. (2015) is referred to as Single .
As in ( van Hasselt et al., 2015 ) , we start the game with up to 30 no-op actions to provide random starting positions for the agent. To evaluate our approach, we measure improvement in percentage (positive or negative) in score over the better of human and baseline agent scores: Score Agent − Score Baseline max { Score Human , Score Baseline } − Score Random . {\footnotesize\frac{\mbox{\small Score}_{\mbox{\tiny Agent}}-\mbox{\small Score}_{\mbox{\tiny Baseline}}}{\small\max\{\mbox{Score}_{\mbox{\tiny Human}},\mbox{Score}_{\mbox{\tiny Baseline}}\}-\mbox{Score}_{\mbox{\tiny Random}}}.} (10) We took the maximum over human and baseline agent scores as it prevents insignificant changes to appear as large improvements when neither the agent in question nor the baseline are doing well. For example, an agent that achieves 2% human performance should not be interpreted as two times better when the baseline agent achieves 1% human performance. We also chose not to measure performance in terms of percentage of human performance alone because a tiny difference relative to the baseline on some games can translate into hundreds of percent in human performance difference.
The results for the wide suite of 57 games are summarized in Table 1 . Detailed results are presented in the Appendix.
Using this 30 no-ops performance measure, it is clear that the dueling network (Duel Clip) does substantially better than the Single Clip network of similar capacity. It also does considerably better than the baseline (Single) of van Hasselt et al. (2015) . For comparison we also show results for the deep Q Q -network of Mnih et al. (2015) , referred to as Nature DQN.
Figure 4 shows the improvement of the dueling network over the baseline Single network of van Hasselt et al. (2015) . Again, we seen that the improvements are often very dramatic.
As shown in Table 1 , Single Clip performs better than Single. We verified that this gain was mostly brought in by gradient clipping. For this reason, we incorporate gradient clipping in all the new approaches.