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

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

# Deep Reinforcement Learning with Double Q-learning

###### Abstract

The popular Q-learning algorithm is known to overestimate action values under certain conditions. It was not previously known whether, in practice, such overestimations are common, whether they harm performance, and whether they can generally be prevented. In this paper, we answer all these questions affirmatively. In particular, we first show that the recent DQN algorithm, which combines Q-learning with a deep neural network, suffers from substantial overestimations in some games in the Atari 2600 domain. We then show that the idea behind the Double Q-learning algorithm, which was introduced in a tabular setting, can be generalized to work with large-scale function approximation. We propose a specific adaptation to the DQN algorithm and show that the resulting algorithm not only reduces the observed overestimations, as hypothesized, but that this also leads to much better performance on several games.

The goal of reinforcement learning ( Sutton and Barto, 1998 ) is to learn good policies for sequential decision problems, by optimizing a cumulative future reward signal. Q-learning ( Watkins, 1989 ) is one of the most popular reinforcement learning algorithms, but it is known to sometimes learn unrealistically high action values because it includes a maximization step over estimated action values, which tends to prefer overestimated to underestimated values.

In previous work, overestimations have been attributed to insufficiently flexible function approximation ( Thrun and Schwartz, 1993 ) and noise ( van Hasselt, 2010 ; van Hasselt, 2011 ) . In this paper, we unify these views and show overestimations can occur when the action values are inaccurate, irrespective of the source of approximation error. Of course, imprecise value estimates are the norm during learning, which indicates that overestimations may be much more common than previously appreciated.

It is an open question whether, if the overestimations do occur, this negatively affects performance in practice. Overoptimistic value estimates are not necessarily a problem in and of themselves. If all values would be uniformly higher then the relative action preferences are preserved and we would not expect the resulting policy to be any worse. Furthermore, it is known that sometimes it is good to be optimistic: optimism in the face of uncertainty is a well-known exploration technique ( Kaelbling et al., 1996 ) . If, however, the overestimations are not uniform and not concentrated at states about which we wish to learn more, then they might negatively affect the quality of the resulting policy. Thrun and Schwartz (1993) give specific examples in which this leads to suboptimal policies, even asymptotically.

To test whether overestimations occur in practice and at scale, we investigate the performance of the recent DQN algorithm ( Mnih et al., 2015 ) . DQN combines Q-learning with a flexible deep neural network and was tested on a varied and large set of deterministic Atari 2600 games, reaching human-level performance on many games. In some ways, this setting is a best-case scenario for Q-learning, because the deep neural network provides flexible function approximation with the potential for a low asymptotic approximation error, and the determinism of the environments prevents the harmful effects of noise. Perhaps surprisingly, we show that even in this comparatively favorable setting DQN sometimes substantially overestimates the values of the actions.

We show that the idea behind the Double Q-learning algorithm ( van Hasselt, 2010 ) , which was first proposed in a tabular setting, can be generalized to work with arbitrary function approximation, including deep neural networks. We use this to construct a new algorithm we call Double DQN. We then show that this algorithm not only yields more accurate value estimates, but leads to much higher scores on several games. This demonstrates that the overestimations of DQN were indeed leading to poorer policies and that it is beneficial to reduce them. In addition, by improving upon DQN we obtain state-of-the-art results on the Atari domain.

## Background

To solve sequential decision problems we can learn estimates for the optimal value of each action, defined as the expected sum of future rewards when taking that action and following the optimal policy thereafter. Under a given policy π \pi , the true value of an action a a in a state s s is Q π ( s , a ) ≡ 𝔼 [ R 1 + γ R 2 + … ∣ S 0 = s , A 0 = a , π ] , Q_{\pi}(s,a)\equiv\mathbb{E}\left[R_{1}+\gamma R_{2}+\ldots\mid S_{0}=s,A_{0}=a,\pi\right]\,, where γ ∈ [ 0 , 1 ] \gamma\in[0,1] is a discount factor that trades off the importance of immediate and later rewards. The optimal value is then Q ∗ ​ ( s , a ) = max π ⁡ Q π ​ ( s , a ) Q_{*}(s,a)=\max_{\pi}Q_{\pi}(s,a) . An optimal policy is easily derived from the optimal values by selecting the highest-valued action in each state.

Estimates for the optimal action values can be learned using Q-learning ( Watkins, 1989 ) , a form of temporal difference learning ( Sutton, 1988 ) . Most interesting problems are too large to learn all action values in all states separately. Instead, we can learn a parameterized value function Q ⁡ ( s , a , 𝜽 t ) Q(s,a;\bm{\theta}_{t}) . The standard Q-learning update for the parameters after taking action A t A_{t} in state S t S_{t} and observing the immediate reward R t + 1 R_{t+1} and resulting state S t + 1 S_{t+1} is then 𝜽 t + 1 = 𝜽 t + α ⁡ ( Y t Q − Q ⁡ ( S t , A t , 𝜽 t ) ) ​ ∇ 𝜽 t Q ​ ( S t , A t , 𝜽 t ) . \bm{\theta}_{t+1}=\bm{\theta}_{t}+\alpha(Y^{\text{Q}}_{t}-Q(S_{t},A_{t};\bm{\theta}_{t}))\nabla_{\bm{\theta}_{t}}Q(S_{t},A_{t};\bm{\theta}_{t})\,. (1) where α \alpha is a scalar step size and the target Y t Q Y^{\text{Q}}_{t} is defined as Y t Q ≡ R t + 1 + γ ​ max a ⁡ Q ⁡ ( S t + 1 , a , 𝜽 t ) . Y^{\text{Q}}_{t}\equiv R_{t+1}+\gamma\max_{a}Q(S_{t+1},a;\bm{\theta}_{t})\,. (2) This update resembles stochastic gradient descent, updating the current value Q ⁡ ( S t , A t , 𝜽 t ) Q(S_{t},A_{t};\bm{\theta}_{t}) towards a target value Y t Q Y^{\text{Q}}_{t} .

### Deep Q Networks

A deep Q network (DQN) is a multi-layered neural network that for a given state s s outputs a vector of action values Q ⁡ ( s , ⋅ , 𝜽 ) Q(s,\cdot\,;\bm{\theta}) , where 𝜽 \bm{\theta} are the parameters of the network. For an n n -dimensional state space and an action space containing m m actions, the neural network is a function from ℝ n \mathbb{R}^{n} to ℝ m \mathbb{R}^{m} . Two important ingredients of the DQN algorithm as proposed by Mnih et al. (2015) are the use of a target network, and the use of experience replay. The target network, with parameters 𝜽 − \bm{\theta}^{-} , is the same as the online network except that its parameters are copied every τ \tau steps from the online network, so that then 𝜽 t − = 𝜽 t \bm{\theta}^{-}_{t}=\bm{\theta}_{t} , and kept fixed on all other steps. The target used by DQN is then Y t DQN ≡ R t + 1 + γ ​ max a ⁡ Q ⁡ ( S t + 1 , a , 𝜽 t − ) . Y^{\text{DQN}}_{t}\equiv R_{t+1}+\gamma\max_{a}Q(S_{t+1},a;\bm{\theta}^{-}_{t})\,. (3) For the experience replay ( Lin, 1992 ) , observed transitions are stored for some time and sampled uniformly from this memory bank to update the network. Both the target network and the experience replay dramatically improve the performance of the algorithm ( Mnih et al., 2015 ) .

### Double Q-learning

The max operator in standard Q-learning and DQN, in ( 2 ) and ( 3 ), uses the same values both to select and to evaluate an action. This makes it more likely to select overestimated values, resulting in overoptimistic value estimates. To prevent this, we can decouple the selection from the evaluation. This is the idea behind Double Q-learning ( van Hasselt, 2010 ) .

In the original Double Q-learning algorithm, two value functions are learned by assigning each experience randomly to update one of the two value functions, such that there are two sets of weights, 𝜽 \bm{\theta} and 𝜽 ′ \bm{\theta}^{\prime} . For each update, one set of weights is used to determine the greedy policy and the other to determine its value. For a clear comparison, we can first untangle the selection and evaluation in Q-learning and rewrite its target ( 2 ) as Y t Q = R t + 1 + γ ​ Q ​ ( S t + 1 , arg ⁡ max a ⁡ Q ​ ( S t + 1 , a , 𝜽 t ) , 𝜽 t ) . Y^{\text{Q}}_{t}=R_{t+1}+\gamma Q(S_{t+1},\argmax_{a}Q(S_{t+1},a;\bm{\theta}_{t});\bm{\theta}_{t})\,. The Double Q-learning error can then be written as Y t DoubleQ ≡ R t + 1 + γ ​ Q ​ ( S t + 1 , arg ⁡ max a ⁡ Q ​ ( S t + 1 , a , 𝜽 t ) , 𝜽 t ′ ) . Y^{\text{DoubleQ}}_{t}\!\equiv R_{t+1}+\gamma Q(S_{t+1},\argmax_{a}Q(S_{t+1},a;\bm{\theta}_{t});\bm{\theta}^{\prime}_{t})\,. (4) Notice that the selection of the action, in the arg ⁡ max \argmax , is still due to the online weights 𝜽 t \bm{\theta}_{t} . This means that, as in Q-learning, we are still estimating the value of the greedy policy according to the current values, as defined by 𝜽 t \bm{\theta}_{t} . However, we use the second set of weights 𝜽 t ′ \bm{\theta}_{t}^{\prime} to fairly evaluate the value of this policy. This second set of weights can be updated symmetrically by switching the roles of 𝜽 \bm{\theta} and 𝜽 ′ \bm{\theta}^{\prime} .

## Overoptimism due to estimation errors

Q-learning’s overestimations were first investigated by Thrun and Schwartz (1993) , who showed that if the action values contain random errors uniformly distributed in an interval [ − ϵ , ϵ ] [-\epsilon,\epsilon] then each target is overestimated up to γ ​ ϵ ​ m − 1 m + 1 \gamma\epsilon\frac{m-1}{m+1} , where m m is the number of actions. In addition, Thrun and Schwartz give a concrete example in which these overestimations even asymptotically lead to sub-optimal policies, and show the overestimations manifest themselves in a small toy problem when using function approximation. Later van Hasselt (2010) argued that noise in the environment can lead to overestimations even when using tabular representation, and proposed Double Q-learning as a solution.

In this section we demonstrate more generally that estimation errors of any kind can induce an upward bias, regardless of whether these errors are due to environmental noise, function approximation, non-stationarity, or any other source. This is important, because in practice any method will incur some inaccuracies during learning, simply due to the fact that the true values are initially unknown.

The result by Thrun and Schwartz (1993) cited above gives an upper bound to the overestimation for a specific setup, but it is also possible, and potentially more interesting, to derive a lower bound.

###### 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 correct, 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 in appendix.)

Note that we did not need to assume that estimation errors for different actions are independent. This theorem shows that even if the value estimates are on average correct, estimation errors of any source can drive the estimates up and away from the true optimal values.

The lower bound in Theorem 1 decreases with the number of actions. This is an artifact of considering the lower bound, which requires very specific values to be attained. More typically, the overoptimism increases with the number of actions as shown in Figure 1 .

Q-learning’s overestimations there indeed increase with the number of actions, while Double Q-learning is unbiased. As another example, if for all actions Q ∗ ​ ( s , a ) = V ∗ ​ ( s ) Q_{*}(s,a)=V_{*}(s) and the estimation errors Q t ​ ( s , a ) − V ∗ ​ ( s ) Q_{t}(s,a)-V_{*}(s) are uniformly random in [ − 1 , 1 ] [-1,1] , then the overoptimism is m − 1 m + 1 \frac{m-1}{m+1} . (Proof in appendix.)

We now turn to function approximation and consider a real-valued continuous state space with 10 discrete actions in each state. For simplicity, the true optimal action values in this example depend only on state so that in each state all actions have the same true value. These true values are shown in the left column of plots in Figure 2 (purple lines) and are defined as either Q ∗ ​ ( s , a ) = sin ⁡ ( s ) Q_{*}(s,a)=\sin(s) (top row) or Q ∗ ​ ( s , a ) = 2 ​ exp ⁡ ( − s 2 ) Q_{*}(s,a)=2\exp(-s^{2}) (middle and bottom rows). The left plots also show an approximation for a single action (green lines) as a function of state as well as the samples the estimate is based on (green dots). The estimate is a d d -degree polynomial that is fit to the true values at sampled states, where d = 6 d=6 (top and middle rows) or d = 9 d=9 (bottom row). The samples match the true function exactly: there is no noise and we assume we have ground truth for the action value on these sampled states. The approximation is inexact even on the sampled states for the top two rows because the function approximation is insufficiently flexible. In the bottom row, the function is flexible enough to fit the green dots, but this reduces the accuracy in unsampled states. Notice that the sampled states are spaced further apart near the left side of the left plots, resulting in larger estimation errors. In many ways this is a typical learning setting, where at each point in time we only have limited data.

The middle column of plots in Figure 2 shows estimated action value functions for all 10 actions (green lines), as functions of state, along with the maximum action value in each state (black dashed line). Although the true value function is the same for all actions, the approximations differ because we have supplied different sets of sampled states. 1 1 1 Each action-value function is fit with a different subset of integer states. States − 6 -6 and 6 6 are always included to avoid extrapolations, and for each action two adjacent integers are missing: for action a 1 a_{1} states − 5 -5 and − 4 -4 are not sampled, for a 2 a_{2} states − 4 -4 and − 3 -3 are not sampled, and so on. This causes the estimated values to differ. The maximum is often higher than the ground truth shown in purple on the left. This is confirmed in the right plots, which shows the difference between the black and purple curves in orange. The orange line is almost always positive, indicating an upward bias. The right plots also show the estimates from Double Q-learning in blue 2 2 2 We arbitrarily used the samples of action a i + 5 a_{i+5} (for i ≤ 5 i\leq 5 ) or a i − 5 a_{i-5} (for i > 5 i>5 ) as the second set of samples for the double estimator of action a i a_{i} . , which are on average much closer to zero. This demonstrates that Double Q-learning indeed can successfully reduce the overoptimism of Q-learning.