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

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

Define the errors for each action a a as ϵ a = Q t ​ ( s , a ) − V ∗ ​ ( s ) \epsilon_{a}=Q_{t}(s,a)-V_{*}(s) . Suppose that there exists a setting of { ϵ a } \{\epsilon_{a}\} such that max a ⁡ ϵ a < C m − 1 \max_{a}\epsilon_{a}<\sqrt{\frac{C}{m-1}} . Let { ϵ i + } \{\epsilon^{+}_{i}\} be the set of positive ϵ \epsilon of size n n , and { ϵ j − } \{\epsilon^{-}_{j}\} the set of strictly negative ϵ \epsilon of size m − n m-n (such that { ϵ } = { ϵ i + } ∪ { ϵ j − } \{\epsilon\}=\{\epsilon^{+}_{i}\}\cup\{\epsilon^{-}_{j}\} ). If n = m n=m , then ∑ a ϵ a = 0 ⟹ ϵ a = 0 ​ ∀ a \sum_{a}\epsilon_{a}=0\implies\epsilon_{a}=0\;\forall a , which contradicts ∑ a ϵ a 2 = m ​ C \sum_{a}\epsilon_{a}^{2}=mC . Hence, it must be that n ≤ m − 1 n\leq m-1 . Then, ∑ i = 1 n ϵ i + ≤ n ​ max i ​ ϵ i + < n ​ C m − 1 \sum_{i=1}^{n}\epsilon^{+}_{i}\leq n\max_{i}\epsilon^{+}_{i}<n\sqrt{\frac{C}{m-1}} , and therefore (using the constraint ∑ a ϵ a = 0 \sum_{a}\epsilon_{a}=0 ) we also have that ∑ j = 1 m − n | ϵ j − | < n ​ C m − 1 \sum_{j=1}^{m-n}|\epsilon^{-}_{j}|<n\sqrt{\frac{C}{m-1}} . This implies max j ⁡ | ϵ j − | < n ​ C m − 1 \max_{j}|\epsilon^{-}_{j}|<n\sqrt{\frac{C}{m-1}} . By Hölder’s inequality, then ∑ j = 1 m − n ( ϵ j − ) 2 \displaystyle\sum_{j=1}^{m-n}(\epsilon^{-}_{j})^{2} ≤ ∑ j = 1 m − n | ϵ j − | ⋅ max j ⁡ | ϵ j − | \displaystyle\leq\sum_{j=1}^{m-n}|\epsilon^{-}_{j}|\cdot\max_{j}|\epsilon^{-}_{j}| < n ​ C m − 1 ​ n ​ C m − 1 . \displaystyle<n\sqrt{\frac{C}{m-1}}n\sqrt{\frac{C}{m-1}}\,. We can now combine these relations to compute an upper-bound on the sum of squares for all ϵ a \epsilon_{a} : ∑ a = 1 m ( ϵ a ) 2 \displaystyle\sum_{a=1}^{m}(\epsilon_{a})^{2} = ∑ i = 1 n ( ϵ i + ) 2 + ∑ j = 1 m − n ( ϵ j − ) 2 \displaystyle=\sum_{i=1}^{n}(\epsilon^{+}_{i})^{2}+\sum_{j=1}^{m-n}(\epsilon^{-}_{j})^{2} < n ​ C m − 1 + n ​ C m − 1 ​ n ​ C m − 1 \displaystyle<n\frac{C}{m-1}+n\sqrt{\frac{C}{m-1}}n\sqrt{\frac{C}{m-1}} = C ​ n ⁡ ( n + 1 ) m − 1 \displaystyle=C\frac{n(n+1)}{m-1} ≤ m ​ C . \displaystyle\leq mC. This contradicts the assumption that ∑ a = 1 m ϵ a 2 < m ​ C \sum_{a=1}^{m}\epsilon_{a}^{2}<mC , and therefore max a ⁡ ϵ a ≥ C m − 1 \max_{a}\epsilon_{a}\geq\sqrt{\frac{C}{m-1}} for all settings of ϵ \epsilon that satisfy the constraints. We can check that the lower-bound is tight by setting ϵ a = C m − 1 \epsilon_{a}=\sqrt{\frac{C}{m-1}} for a = 1 , … , m − 1 a=1,\dots,m-1 and ϵ m = − ( m − 1 ) ​ C \epsilon_{m}=-\sqrt{(m-1)C} . This verifies ∑ a ϵ a 2 = m ​ C \sum_{a}\epsilon_{a}^{2}=mC and ∑ a ϵ a = 0 \sum_{a}\epsilon_{a}=0 .

The only tight lower bound on the absolute error for Double Q-learning | Q t ′ ​ ( s , arg ⁡ max a ⁡ Q t ​ ( s , a ) ) − V ∗ ​ ( s ) | |Q^{\prime}_{t}(s,\argmax_{a}Q_{t}(s,a))-V_{*}(s)| is zero. This can be seen by because we can have Q t ​ ( s , a 1 ) = V ∗ ​ ( s ) + C ​ m − 1 m , Q_{t}(s,a_{1})=V_{*}(s)+\sqrt{C\frac{m-1}{m}}\,, and Q t ​ ( s , a i ) = V ∗ ​ ( s ) − C ​ 1 m ⁡ ( m − 1 ) ​ , for i > 1 . Q_{t}(s,a_{i})=V_{*}(s)-\sqrt{C\frac{1}{m(m-1)}}\,\text{, for $i>1$.} Then the conditions of the theorem hold. If then, furthermore, we have Q t ′ ​ ( s , a 1 ) = V ∗ ​ ( s ) Q^{\prime}_{t}(s,a_{1})=V_{*}(s) then the error is zero. The remaining action values Q t ′ ​ ( s , a i ) Q^{\prime}_{t}(s,a_{i}) , for i > 1 i>1 , are arbitrary. ∎

###### Theorem 2 .

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) . Suppose that the estimation errors Q t ​ ( s , a ) − Q ∗ ​ ( s , a ) Q_{t}(s,a)-Q_{*}(s,a) are independently distributed uniformly randomly in [ − 1 , 1 ] [-1,1] . Then, 𝔼 ⁡ [ max a ⁡ Q t ​ ( s , a ) − V ∗ ​ ( s ) ] = m − 1 m + 1 \displaystyle\mathbb{E}\left[\max_{a}Q_{t}(s,a)-V_{*}(s)\right]=\frac{m-1}{m+1}\,

###### Proof.

Define ϵ a = Q t ​ ( s , a ) − Q ∗ ​ ( s , a ) \epsilon_{a}=Q_{t}(s,a)-Q_{*}(s,a) ; this is a uniform random variable in [ − 1 , 1 ] [-1,1] . The probability that max a ⁡ Q t ​ ( s , a ) ≤ x \max_{a}Q_{t}(s,a)\leq x for some x x is equal to the probability that ϵ a ≤ x \epsilon_{a}\leq x for all a a simultaneously. Because the estimation errors are independent, we can derive P ⁡ ( max a ⁡ ϵ a ≤ x ) \displaystyle P(\max_{a}\epsilon_{a}\leq x) = P ⁡ ( X 1 ≤ x ∧ X 2 ≤ x ∧ … ∧ X m ≤ x ) \displaystyle=P(X_{1}\leq x\land X_{2}\leq x\land\ldots\land X_{m}\leq x) = ∏ a = 1 m P ⁡ ( ϵ a ≤ x ) . \displaystyle=\prod_{a=1}^{m}P(\epsilon_{a}\leq x)\,. The function P ⁡ ( ϵ a ≤ x ) P(\epsilon_{a}\leq x) is the cumulative distribution function (CDF) of ϵ a \epsilon_{a} , which here is simply defined as P ⁡ ( ϵ a ≤ x ) = { 0 if x ≤ − 1 1 + x 2 if x ∈ ( − 1 , 1 ) 1 if x ≥ 1 P(\epsilon_{a}\leq x)=\left\{\begin{array}[]{ll}0&\text{if $x\leq-1$}\\ \frac{1+x}{2}&\text{if $x\in(-1,1)$}\\ 1&\text{if $x\geq 1$}\\ \end{array}\right. This implies that P ⁡ ( max a ⁡ ϵ a ≤ x ) \displaystyle P(\max_{a}\epsilon_{a}\leq x) = ∏ a = 1 m P ⁡ ( ϵ a ≤ x ) \displaystyle=\prod_{a=1}^{m}P(\epsilon_{a}\leq x) = { 0 if x ≤ − 1 ( 1 + x 2 ) m if x ∈ ( − 1 , 1 ) 1 if x ≥ 1 \displaystyle=\left\{\begin{array}[]{ll}0&\text{if $x\leq-1$}\\ \left(\frac{1+x}{2}\right)^{m}&\text{if $x\in(-1,1)$}\\ 1&\text{if $x\geq 1$}\\ \end{array}\right. This gives us the CDF of the random variable max a ⁡ ϵ a \max_{a}\epsilon_{a} . Its expectation can be written as an integral 𝔼 ⁡ [ max a ⁡ ϵ a ] = ∫ − 1 1 x ​ f max ​ ( x ) ​ d ​ x , \mathbb{E}\left[\max_{a}\epsilon_{a}\right]=\int_{-1}^{1}\!xf_{\max}(x)\,\text{d}x\,, where f max f_{\max} is the probability density function of this variable, defined as the derivative of the CDF: f max ​ ( x ) = d d ​ x ​ P ​ ( max a ⁡ ϵ a ≤ x ) f_{\max}(x)=\frac{\text{d}}{\text{d}x}P(\max_{a}\epsilon_{a}\leq x) , so that for x ∈ [ − 1 , 1 ] x\in[-1,1] we have f max ​ ( x ) = m 2 ​ ( 1 + x 2 ) m − 1 f_{\max}(x)=\frac{m}{2}\left(\frac{1+x}{2}\right)^{m-1} . Evaluating the integral yields 𝔼 ⁡ [ max a ⁡ ϵ a ] \displaystyle\mathbb{E}\left[\max_{a}\epsilon_{a}\right] = ∫ − 1 1 x ​ f max ​ ( x ) ​ d ​ x \displaystyle=\int_{-1}^{1}\!xf_{\max}(x)\,\text{d}x = [ ( x + 1 2 ) m ​ m ​ x − 1 m + 1 ] − 1 1 \displaystyle=\left[\left(\frac{x+1}{2}\right)^{m}\frac{mx-1}{m+1}\right]_{-1}^{1} = m − 1 m + 1 . ∎ \displaystyle=\frac{m-1}{m+1}\,.\qed

## Experimental Details for the Atari 2600 Domain

We selected the 49 games to match the list used by Mnih et al. (2015) , see Tables below for the full list. Each agent step is composed of four frames (the last selected action is repeated during these frames) and reward values (obtained from the Arcade Learning Environment ( Bellemare et al., 2013 ) ) are clipped between -1 and 1.

### Network Architecture

The convolution network used in the experiment is exactly the one proposed by proposed by Mnih et al. (2015) , we only provide details here for completeness. The input to the network is a 84x84x4 tensor containing a rescaled, and gray-scale, version of the last four frames. The first convolution layer convolves the input with 32 filters of size 8 (stride 4), the second layer has 64 layers of size 4 (stride 2), the final convolution layer has 64 filters of size 3 (stride 1). This is followed by a fully-connected hidden layer of 512 units. All these layers are separated by Rectifier Linear Units (ReLu). Finally, a fully-connected linear layer projects to the output of the network, i.e., the Q-values. The optimization employed to train the network is RMSProp (with momentum parameter 0.95 0.95 ).

### Hyper-parameters

In all experiments, the discount was set to γ = 0.99 \gamma=0.99 , and the learning rate to α = 0.00025 \alpha=0.00025 . The number of steps between target network updates was τ = 10,000 \tau=10,000 . Training is done over 50M steps (i.e., 200M frames). The agent is evaluated every 1M steps, and the best policy across these evaluations is kept as the output of the learning process. The size of the experience replay memory is 1M tuples. The memory gets sampled to update the network every 4 steps with minibatches of size 32. The simple exploration policy used is an ϵ \epsilon -greedy policy with the ϵ \epsilon decreasing linearly from 1 to 0.1 0.1 over 1M steps.

## Supplementary Results in the Atari 2600 Domain

The Tables below provide further detailed results for our experiments in the Atari domain.

## Instructions for reporting errors

We are continuing to improve HTML versions of papers, and your feedback helps enhance accessibility and mobile support. To report errors in the HTML that will help us improve conversion and rendering, choose any of the methods listed below:

Click the "Report Issue" ( ) button, located in the page header.

Tip: You can select the relevant text first, to include it in your report.

Our team has already identified the following issues . We appreciate your time reviewing and reporting rendering errors we may not have found yet. Your efforts will help us improve the HTML versions for all readers, because disability should not be a barrier to accessing research. Thank you for your continued support in championing open access for all.

Have a free development cycle? Help support accessibility at arXiv! Our collaborators at LaTeXML maintain a list of packages that need conversion , and welcome developer contributions .