Deep Reinforcement Learning with Double Q-learning
Google DeepMind
Abstract
主流的 Q-learning 算法過高的估計在特定條件下的動作值。實際上，之前是不知道是否這樣的過高估計是 common的，是否對性能有害，以及是否能從主體上進行組織。本文就回答了上述的問題，特别的，本文指出最近的 DQN 算法，的确存在在玩 Atari 2600 時會 suffer from substantial overestimations。本文提出了 double Q-learning algorithm 可以很好的降低觀測到的 overestimation 問題，而且在幾個遊戲上取得了更好的效果。
Introduction
強化學習的目标是對序列決策問題能夠學習到一個好的政策，通過優化一個累計未來獎勵信号。Q-learning 是最著名的 RL 學習算法之一，但是由于其在預測動作值的時候包含一個最大化的步驟，是以導緻會出現過高的預測值，使得學習到不實際的高動作值。
在之前的工作中，将 overestimation 的問題歸咎于 不夠靈活的函數估計 以及 noise。本文統一了這些觀點，并且表明 當動作值預測的不準确的時候，就會出現 overestimation，而不管估計誤差的來源。當然，在學習的過程中，出現不準确的值估計也是正常的，這也說明 overestimation 可能比之前所看的情況更加普遍。
如果overestimation 的确出現，那麼這個開放的問題的确會影響實際的性能。過于優化的值估計在一個問題中是不必要的，如果所有的值都比相對動作參考要均勻的高被儲存了，那麼我們就不會相信得到的結果政策會更差了。此外，有時候 optimistic 是一件好事情：optimistic in the face of uncertainty is a well-known exploration technique. 然而，如果當預測并且均勻，不集中在 state上，那麼他們可能對結果的政策産生壞的影響。Thrun 等人給出了特定的例子，即：導緻次優的政策。
為了測試在實際上是否會出現 overestimation，我們探讨了最近 DQN 算法的性能。關于 DQN 可以參考相關文章，此處不贅述了。可能比較奇怪的是，這種 DQN設定 仍然存在過高的估計動作的 value 這種情況。
作者表明，在 Double Q-learning算法背後的idea，可以很好的和任意的函數估計相結合，包括神經網絡，我們利用此建構了新的算法，稱: Double DQN。本文算法不但可以産生更加精确的 value estimation，而且在幾個遊戲上得到了更高的分數。這樣表明，在 DQN上的确存在 overestimation 的問題，并且最好将其降低或者說消除。
Background
為了解決序列決策問題，我們學習對每一個動作的最優值的估計，定義為：當采取該動作，并且以後也采用最優的政策時，期望得到的将來獎勵的總和。在給定一個政策 $\pi$ 之後，在狀态 s下的一個動作 a 的真實值為：
$Q_{\pi}(s, a) = E[R_1 + \gamma R_2 + ... | S_0 =s, A_0 = a, \pi]$，
最優的值就是 $Q_*(s, a) = max_{\pi} Q_{\pi}(s, a)$。一個優化的政策就是從每一個狀态下選擇最高值動作。
預測最優動作值 可以利用 Q-learning算法。大部分有意思的問題都無法在所有狀态下都計算出其動作值。相反，我們學習一個參數化的動作函數 Q(s, a; \theta_t)。在狀态St下，采取了動作 $A_t$之後标準的 Q-learning 更新，然後觀測到獎勵 $R_{t+1}$以及得到轉換後的狀态 $S_{t+1}$：
其中，目标 $Y_t^Q$ 的定義為：
這個更新非常類似于随機梯度下降，朝向 target value $Y^Q_t$ 更新目前值 Q（S_t, A_t; \theta_t）。
Deep Q-Networks.
一個DQN是一個多層的神經網絡，給定一個狀态 s，輸出一個動作值的向量 $Q(s, *; \theta)$，其中，$\theta$ 是網絡的參數。對于一個 n維 的狀态空間，動作空間是 m 個動作，神經網絡是一個函數将其從 n維空間映射到 m維。兩個重要的點分别是 target network 的使用 以及 experience replay的使用。target network，參數為 $\theta^-$，和 online的網絡一樣，除了其參數是從 online network 經過 某些 steps之後拷貝下來的。目标網絡是：
對于 experience replay，觀測到的 transitions 都被存貯起來，并且随機的從其中進行采樣，用來更新網絡。target network 和 experience replay 都明顯的改善了最終的 performance。
Double Q-learning
在标準的 Q-learning 以及 DQN 上的 max operator，用相同的值來選擇和評價一個 action。這使得其更偏向于選擇 overestimated values，導緻次優的估計值。為了防止此現象，我們可以從評價中将選擇獨立出來，這就是 Double Q-learning 背後的 idea。
在最開始的 Double Q-learning算法中，通過随機的賦予每一個 experience 來更新兩個 value functions 中的一個 來學習兩個value function，如此，就得到兩個權重的集合，$\theta$ 以及 $\theta '$。對于每一次更新，其中一個權重集合用來決定貪婪政策，另一個用來決定其 value。做一個明确的對比，我們可以首先排解 selection 和 evaluation，重寫公式2，得到：
那麼， Double Q-learning error可以寫為：
注意到 action 的選擇，在 argmax，仍然屬于 online weights $\theta_t$。這意味着，像 Q-learning一樣，我們仍然可以根據目前值，利用貪婪政策進行 value 的估計。然而，我們利用第二個權重 $\theta _t '$來更加公平的評價該政策。第二個權重的集合，可以通過交換 兩個權重的角色進行更新。
OverOptimism due to estimation errors: