Deep Reinforcement Learning with Double Q-learning — part 2/3

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

The different rows in Figure 2 show variations of the same experiment. The difference between the top and middle rows is the true value function, demonstrating that overestimations are not an artifact of a specific true value function. The difference between the middle and bottom rows is the flexibility of the function approximation. In the left-middle plot, the estimates are even incorrect for some of the sampled states because the function is insufficiently flexible. The function in the bottom-left plot is more flexible but this causes higher estimation errors for unseen states, resulting in higher overestimations. This is important because flexible parametric function approximators are often employed in reinforcement learning (see, e.g., Tesauro 1995 ; Sallans and Hinton 2004 ; Riedmiller 2005 ; Mnih et al. 2015 ).

In contrast to van Hasselt (2010) we did not use a statistical argument to find overestimations, the process to obtain Figure 2 is fully deterministic. In contrast to Thrun and Schwartz (1993) , we did not rely on inflexible function approximation with irreducible asymptotic errors; the bottom row shows that a function that is flexible enough to cover all samples leads to high overestimations. This indicates that the overestimations can occur quite generally.

In the examples above, overestimations occur even when assuming we have samples of the true action value at certain states. The value estimates can further deteriorate if we bootstrap off of action values that are already overoptimistic, since this causes overestimations to propagate throughout our estimates. Although uniformly overestimating values might not hurt the resulting policy, in practice overestimation errors will differ for different states and actions. Overestimation combined with bootstrapping then has the pernicious effect of propagating the wrong relative information about which states are more valuable than others, directly affecting the quality of the learned policies.

The overestimations should not be confused with optimism in the face of uncertainty ( Sutton, 1990 ; Agrawal, 1995 ; Kaelbling et al., 1996 ; Auer et al., 2002 ; Brafman and Tennenholtz, 2003 ; Szita and Lőrincz, 2008 ; Strehl et al., 2009 ) , where an exploration bonus is given to states or actions with uncertain values. Conversely, the overestimations discussed here occur only after updating, resulting in overoptimism in the face of apparent certainty. This was already observed by Thrun and Schwartz (1993) , who noted that, in contrast to optimism in the face of uncertainty, these overestimations actually can impede learning an optimal policy. We will see this negative effect on policy quality confirmed later in the experiments as well: when we reduce the overestimations using Double Q-learning, the policies improve.

## Double DQN

The idea of Double Q-learning is to reduce overestimations by decomposing the max operation in the target into action selection and action evaluation. Although not fully decoupled, the target network in the DQN architecture provides a natural candidate for the second value function, without having to introduce additional networks. We therefore propose to evaluate the greedy policy according to the online network, but using the target network to estimate its value. In reference to both Double Q-learning and DQN, we refer to the resulting algorithm as Double DQN. Its update is the same as for DQN, but replacing the target Y t DQN Y^{\text{DQN}}_{t} with Y t DoubleDQN ≡ R t + 1 + γ ​ Q ​ ( S t + 1 , arg ⁡ max a ⁡ Q ​ ( S t + 1 , a , 𝜽 t ) , 𝜽 t − ) . Y^{\text{DoubleDQN}}_{t}\equiv R_{t+1}+\gamma Q(S_{t+1},\argmax_{a}Q(S_{t+1},a;\bm{\theta}_{t}),\bm{\theta}^{-}_{t})\,. In comparison to Double Q-learning ( 4 ), the weights of the second network 𝜽 t ′ \bm{\theta}^{\prime}_{t} are replaced with the weights of the target network 𝜽 t − \bm{\theta}^{-}_{t} for the evaluation of the current greedy policy. The update to the target network stays unchanged from DQN, and remains a periodic copy of the online network.

This version of Double DQN is perhaps the minimal possible change to DQN towards Double Q-learning. The goal is to get most of the benefit of Double Q-learning, while keeping the rest of the DQN algorithm intact for a fair comparison, and with minimal computational overhead.

## Empirical results

In this section, we analyze the overestimations of DQN and show that Double DQN improves over DQN both in terms of value accuracy and in terms of policy quality. To further test the robustness of the approach we additionally evaluate the algorithms with random starts generated from expert human trajectories, as proposed by Nair et al. (2015) .

Our testbed consists of Atari 2600 games, using the Arcade Learning Environment ( Bellemare et al., 2013 ) . The goal is for a single algorithm, with a fixed set of hyperparameters, to learn to play each of the games separately from interaction given only the screen pixels as input. This is a demanding testbed: not only are the inputs high-dimensional, the game visuals and game mechanics vary substantially between games. Good solutions must therefore rely heavily on the learning algorithm — it is not practically feasible to overfit the domain by relying only on tuning.

We closely follow the experimental setting and network architecture outlined by Mnih et al. (2015) . Briefly, the network architecture is a convolutional neural network ( Fukushima, 1988 ; LeCun et al., 1998 ) with 3 convolution layers and a fully-connected hidden layer (approximately 1.5M parameters in total). The network takes the last four frames as input and outputs the action value of each action. On each game, the network is trained on a single GPU for 200M frames, or approximately 1 week.

### Results on overoptimism

Figure 3 shows examples of DQN’s overestimations in six Atari games. DQN and Double DQN were both trained under the exact conditions described by Mnih et al. (2015) . DQN is consistently and sometimes vastly overoptimistic about the value of the current greedy policy, as can be seen by comparing the orange learning curves in the top row of plots to the straight orange lines, which represent the actual discounted value of the best learned policy. More precisely, the (averaged) value estimates are computed regularly during training with full evaluation phases of length T = 125,000 T=125,000 steps as 1 T ​ ∑ t = 1 T arg ⁡ max a ⁡ Q ​ ( S t , a , 𝜽 ) . \frac{1}{T}\sum_{t=1}^{T}\argmax_{a}Q(S_{t},a;\bm{\theta})\,. The ground truth averaged values are obtained by running the best learned policies for several episodes and computing the actual cumulative rewards. Without overestimations we would expect these quantities to match up (i.e., the curve to match the straight line at the right of each plot). Instead, the learning curves of DQN consistently end up much higher than the true values. The learning curves for Double DQN, shown in blue, are much closer to the blue straight line representing the true value of the final policy. Note that the blue straight line is often higher than the orange straight line. This indicates that Double DQN does not just produce more accurate value estimates but also better policies.

More extreme overestimations are shown in the middle two plots, where DQN is highly unstable on the games Asterix and Wizard of Wor. Notice the log scale for the values on the y y -axis. The bottom two plots shows the corresponding scores for these two games. Notice that the increases in value estimates for DQN in the middle plots coincide with decreasing scores in bottom plots. Again, this indicates that the overestimations are harming the quality of the resulting policies. If seen in isolation, one might perhaps be tempted to think the observed instability is related to inherent instability problems of off-policy learning with function approximation ( Baird, 1995 ; Tsitsiklis and Van Roy, 1997 ; Sutton et al., 2008 ; Maei, 2011 ; Sutton et al., 2015 ) . However, we see that learning is much more stable with Double DQN, suggesting that the cause for these instabilities is in fact Q-learning’s overoptimism. Figure 3 only shows a few examples, but overestimations were observed for DQN in all 49 tested Atari games, albeit in varying amounts.

### Quality of the learned policies

Overoptimism does not always adversely affect the quality of the learned policy. For example, DQN achieves optimal behavior in Pong despite slightly overestimating the policy value. Nevertheless, reducing overestimations can significantly benefit the stability of learning; we see clear examples of this in Figure 3 . We now assess more generally how much Double DQN helps in terms of policy quality by evaluating on all 49 games that DQN was tested on.

As described by Mnih et al. (2015) each evaluation episode starts by executing a special no-op action that does not affect the environment up to 30 times, to provide different starting points for the agent. Some exploration during evaluation provides additional randomization. For Double DQN we used the exact same hyper-parameters as for DQN, to allow for a controlled experiment focused just on reducing overestimations. The learned policies are evaluated for 5 mins of emulator time (18,000 frames) with an ϵ \epsilon -greedy policy where ϵ = 0.05 \epsilon=0.05 . The scores are averaged over 100 episodes. The only difference between Double DQN and DQN is the target, using Y t DoubleDQN Y^{\text{DoubleDQN}}_{t} rather than Y DQN Y^{\text{DQN}} . This evaluation is somewhat adversarial, as the used hyper-parameters were tuned for DQN but not for Double DQN.

To obtain summary statistics across games, we normalize the score for each game as follows: score normalized = score agent − score random score human − score random . \text{score}_{\text{normalized}}=\frac{\text{score}_{\text{agent}}-\text{score}_{\text{random}}}{\text{score}_{\text{human}}-\text{score}_{\text{random}}}. (5) The ‘random’ and ‘human’ scores are the same as used by Mnih et al. (2015) , and are given in the appendix.

Table 1 , under no ops , shows that on the whole Double DQN clearly improves over DQN. A detailed comparison (in appendix) shows that there are several games in which Double DQN greatly improves upon DQN. Noteworthy examples include Road Runner (from 233% to 617%), Asterix (from 70% to 180%), Zaxxon (from 54% to 111%), and Double Dunk (from 17% to 397%).

The Gorila algorithm ( Nair et al., 2015 ) , which is a massively distributed version of DQN, is not included in the table because the architecture and infrastructure is sufficiently different to make a direct comparison unclear. For completeness, we note that Gorila obtained median and mean normalized scores of 96% and 495%, respectively.

### Robustness to Human starts

One concern with the previous evaluation is that in deterministic games with a unique starting point the learner could potentially learn to remember sequences of actions without much need to generalize. While successful, the solution would not be particularly robust. By testing the agents from various starting points, we can test whether the found solutions generalize well, and as such provide a challenging testbed for the learned polices ( Nair et al., 2015 ) .

We obtained 100 starting points sampled for each game from a human expert’s trajectory, as proposed by Nair et al. (2015) . We start an evaluation episode from each of these starting points and run the emulator for up to 108,000 frames (30 mins at 60Hz including the trajectory before the starting point). Each agent is only evaluated on the rewards accumulated after the starting point.

For this evaluation we include a tuned version of Double DQN. Some tuning is appropriate because the hyperparameters were tuned for DQN, which is a different algorithm. For the tuned version of Double DQN, we increased the number of frames between each two copies of the target network from 10,000 to 30,000, to reduce overestimations further because immediately after each switch DQN and Double DQN both revert to Q-learning. In addition, we reduced the exploration during learning from ϵ = 0.1 \epsilon=0.1 to ϵ = 0.01 \epsilon=0.01 , and then used ϵ = 0.001 \epsilon=0.001 during evaluation. Finally, the tuned version uses a single shared bias for all action values in the top layer of the network. Each of these changes improved performance and together they result in clearly better results. 3 3 3 Except for Tennis, where the lower ϵ \epsilon during training seemed to hurt rather than help.

Table 2 reports summary statistics for this evaluation on the 49 games from Mnih et al. (2015) . Double DQN obtains clearly higher median and mean scores. Again Gorila DQN ( Nair et al., 2015 ) is not included in the table, but for completeness note it obtained a median of 78% and a mean of 259%. Detailed results, plus results for an additional 8 games, are available in Figure 4 and in the appendix. On several games the improvements from DQN to Double DQN are striking, in some cases bringing scores much closer to human, or even surpassing these.

Double DQN appears more robust to this more challenging evaluation, suggesting that appropriate generalizations occur and that the found solutions do not exploit the determinism of the environments. This is appealing, as it indicates progress towards finding general solutions rather than a deterministic sequence of steps that would be less robust.

## Discussion

This paper has five contributions. First, we have shown why Q-learning can be overoptimistic in large-scale problems, even if these are deterministic, due to the inherent estimation errors of learning. Second, by analyzing the value estimates on Atari games we have shown that these overestimations are more common and severe in practice than previously acknowledged. Third, we have shown that Double Q-learning can be used at scale to successfully reduce this overoptimism, resulting in more stable and reliable learning. Fourth, we have proposed a specific implementation called Double DQN, that uses the existing architecture and deep neural network of the DQN algorithm without requiring additional networks or parameters. Finally, we have shown that Double DQN finds better policies, obtaining new state-of-the-art results on the Atari 2600 domain.

## Acknowledgments

We would like to thank Tom Schaul, Volodymyr Mnih, Marc Bellemare, Thomas Degris, Georg Ostrovski, and Richard Sutton for helpful comments, and everyone at Google DeepMind for a constructive research environment.

## Appendix

###### Theorem 1 .

Consider a state s s in which all the true optimal action values are equal at Q ∗ ​ ( s , a ) = V ∗ ​ ( s ) Q_{*}(s,a)=V_{*}(s) for some V ∗ ​ ( s ) V_{*}(s) . Let Q t Q_{t} be arbitrary value estimates that are on the whole unbiased in the sense that ∑ a ( Q t ​ ( s , a ) − V ∗ ​ ( s ) ) = 0 \sum_{a}(Q_{t}(s,a)-V_{*}(s))=0 , but that are not all zero, such that 1 m ​ ∑ a ( Q t ​ ( s , a ) − V ∗ ​ ( s ) ) 2 = C \frac{1}{m}\sum_{a}(Q_{t}(s,a)-V_{*}(s))^{2}=C for some C > 0 C>0 , where m ≥ 2 m\geq 2 is the number of actions in s s . Under these conditions, max a ⁡ Q t ​ ( s , a ) ≥ V ∗ ​ ( s ) + C m − 1 \max_{a}Q_{t}(s,a)\geq V_{*}(s)+\sqrt{\frac{C}{m-1}} . This lower bound is tight. Under the same conditions, the lower bound on the absolute error of the Double Q-learning estimate is zero.

###### Proof of Theorem 1.