DQN系列(1)：Double Q-learning

• 2020 年 1 月 14 日
• 筆記

深度強化學習實驗室報道

作者：DeepRL

論文地址： https://papers.nips.cc/paper/3964-double-q-learning.pdf

本論文由DeepMind發表於2015年NIPS的一篇論文，作者Hasselt。

前言： Q-Learning演算法由於受到大規模的動作值過估計(overestimation)而出現不穩定和效果不佳等現象的存在，而導致overestimation的主要原因來自於最大化值函數(max)逼近，該過程目標是為了最大的累計期望獎勵，而在這個過程中產生了正向偏差。而本文章作者巧妙的是使用了兩個估計器(double estimator)去計算Q-learning的值函數，作者將這種方法定義了一個名字叫「Double Q-learning」（本質上一個off-policy演算法），並對其收斂過程進行了證明(缺點：當然double Q-learning演算法有時會低估動作值，但不會像Q學習那樣遭受過高估計）

1. 問題及原因

"過估計" (overestimate) 過估計是指對一系列數先求最大值再求平均，通常比先求平均再求最大值要大（或相等，數學表達為：

一般來說Q-learning方法導致overestimation的原因歸結於其更新過程，其表達為：

其中的 表示為最大化action-value, 而更新最優化過程如下：

對於任意的 來說，最優值函數 的更新依賴於 , 從公式中可以看出，我們把N個Q值先通過取max操作之後，然後求平均(期望)，會比我們先算出N個Q值取了期望之後再max要大。這就是overestimate的原因。

註： 一般用於加速Q-learning演算法的方法有：Delayed Q-learning, Phased Q-learning, Fitted Q-iteration等

2. Estimator原理與思想

通常情況下對於一個集合中的變數 來說，獎勵的最大化累計期望表示為：

那麼在實際的過程中，對於每個 ，我們定義 為取樣，其中的 表示為對於所有取樣的一個子集，假設 滿足獨立同分布情況， 那麼期望值的「無偏估計」可以通過計算每個變數的樣本平均值來獲得，其計算方法如下：

註： 是 的估計器

這個過程是一個無偏估計，因為每一個取樣 是一個對 的無偏估計，因此，近似中的誤差僅由估計中的 「方差「 組成，當我們獲得更多樣本時會減小。

為了後面方便理解，這裡我們定義兩個函數：「概率密度函數」(Probability Density Function, PDF)和「累積分布函數」(Cumulative Distribution Function, CDF)，概率密度函數表示個 ，則累積分布函數表示為： ，同樣的道理，對於PDF和CDF來說估計器分別表示為和。

補充1. 概率密度函數， 其實就是給定一個值, 判斷這個值在該正態分布中所在的位置後, 獲得其他數據高於該值或低於該值的比例，其中的曲線就是概率密度函數(PDF)，通常情況下pdf的曲線下面積(AUC)總和為1，且曲線末端不會接觸到x軸(換句話說, 我們不可能100%的確定某件事)。

2. 累積分布函數累積分布函數 (CDF) 計算給定 x 值的累積概率。可使用 CDF 確定取自總體的隨機觀測值將小於或等於特定值的概率。還可以使用此資訊來確定觀測值將大於特定值或介於兩個值之間的概率。

例如，罐裝蘇打水的填充重量服從正態分布，且均值為 12 盎司，標準差為 0.25 盎司。概率密度函數 (PDF) 描述了填充重量的可能值的可能性。CDF 提供每個 x 值的累積概率。此處參考PDF-CDF指導

（1）單估計器方法（Single Estimator）

所謂的單估計就是使用一組估計量的最大值作為近似值，

即近似的最好的方式就是最大化估計器,表示為：

表示為估計器，而此處對於最大的估計器來說，它是依賴於 的，若要求取PDF，首先需要考慮CDF，但它的概率分布中最大的估計器小於等於，這等同於所有的估計均小於等於，數學表示為：

那麼是對的無偏估計，詳細表示為：

（2）雙估計器方法（Double Estimator）

對每個變數使用兩個估計器，並將估計器的選擇與其值解耦。

問題：單一估計器方法導致過高估計可能會對使用此方法的演算法（例如Q學習）產生很大的負面影響。為了解決這個問題，double estimator方法用來解決過高估計。

那麼對於原來的 來說，此處我們需要定義兩個估計器：和，他們分別表示為：，，然後兩個估計器都使用取樣的樣本子集來更新，其規則表示為:

那麼像單估計器一樣，如果我們假設樣本以適當的方式（例如隨機地）分布在兩組估計器上，則和也都是無偏的。設 為 中最大估計值集合，由於是一個獨立的無偏估計值，那麼 對於任何都成立，包括

此處有疑問，為什麼包括？？

設 是最大化 的估計器，表示為：，如果存在多個最大化的 是最大化估計量，我們可以例如隨機選擇一個，然後我們可以將用作的估計值，那麼對於可以近似為：

隨著我們獲得更多的樣本，估計量的方差減小，在極限情況下，

具體證明過程部分如下：

3. Double Q-learning演算法

我們可以解釋為 Q-learning學習其實使用單估計器(single estimate)去估計下一個狀態：那麼是 的一個估計，一般的，將期望理解為對同一實驗的所有可能運行的平均，而不是（通常在強化學習環境中使用）對下一個狀態的期望，根據原理部分，Double Q-learning將使用兩個函數 和（對應兩個估計器），並且每個函數都會使用另一個函數的值更新下一個狀態。兩個函數都必須從不同的經驗集中學習，這一點很重要，但是要選擇要執行的動作可以同時使用兩個值函數。 因此，該演算法的數據效率不低於Q學習。 在實驗中作者為每個動作計算了兩個Q值的平均值，然後對所得的平均Q值進行了貪婪探索。演算法偽程式碼如下：

為了區分Double Q-learning演算法和Q-learning的區別，本文同樣Q-learning演算法偽程式碼貼出來了。

對比：此處對於Q-learning演算法和double Q-learning 演算法來說，double使用了B網路來更新A網路，同樣的道理對於B網路則使用A網路的值來更新。

4. 實驗過程於結果

在這裡插入圖片描述

5. 附錄：收斂性證明過程

對於Double Q-learning收斂性的證明過程如下：

原文部落格地址：

https://blog.csdn.net/gsww404/article/details/103413124