【强化学习】DQN及其延伸算法
目錄
- DQN算法
- 價值函數的近似表示
- 提出背景：
- 近似表示：
- 狀態價值函數
- 動作價值函數
- 概述
- 經驗回放（experience replay）
- 算法流程
- 小結
- Nature DQN算法
- 概述
- Nature DQN的優化點：
- Nature DQN 建模——雙網絡結構：
- 算法流程
- 小結
- Double DQN算法
- 概述
- DDQN的優化點：
- DDQN建模——Q值與動作解耦:
- 算法流程
- Prioritized Replay DQN算法
- 概述
- Prioritized Replay DQN的優化點：
- Prioritized Replay DQN建模:
- 算法流程（集成了DDQN）
- Dueling DQN算法
- 概述
- Dueling DQN的優化點：
- Dueling DQN網絡結構:
- 總結
強化學習筆記，內容來自 劉建平老師的博客
DQN算法
價值函數的近似表示
提出背景：
? 動態規劃DP、蒙特卡羅MC、時序差分TD這些求解MDP問題的算法，使用的狀態都是有限個離散狀態，問題規模小時易求解。而 當問題規模龐大，或者狀態是連續的且離散化后依然規模龐大時，無法將Q表存在有限的內存中。因此用價值函數的近似表示來修改模 型。
?
近似表示：
狀態價值函數
? ，其中w是參數
動作價值函數
? ，其中w是參數
? 具體的近似有很多，比如：線性表示法、決策樹、最近鄰、傅里葉變換等，但是最常用的是神經網絡（DNN、CNN、RNN）。
? 對于狀態價值函數，神經網絡的輸入是狀態s的特征向量，輸出是狀態價值v(s,w)。
? 對于動作價值函數，有兩種方法，一種是輸入狀態s的特征向量和動作a，輸出對應的動作價值q(s,a,w)，另一種是只輸入狀態s的特征 向量，動作集合有多少個動作就有多少個輸出q(s,ai,w)。這里隱示了動作是有限個的離散動作。
?
概述
? 基本思路來源于Q-Learning，但是和Q-Learning不同的地方在于，它的Q值的計算不是直接通過狀態值S 和動作A 來計算，而是通過上面講到的Q網絡來計算的，這個Q網絡是一個神經網絡。
經驗回放（experience replay）
? 將每次和環境交互得到的獎勵與狀態更新情況都保存起來，用于后面目標Q值的更新。Q-Learning是有一張Q表來保存所有的Q 值的當前結果的，而DQN在做動作價值函數更新時靠的就是經驗回放。從經驗池查詢得到的S、A用神經網絡結合公式計算得到的目 標Q值和直接通過Q網絡直接計算得到的Q估計值肯定是不等的（經驗池里的是之前神經網絡算出來的，其網絡參數與當前網絡的不 同，這個差值作為神經網絡的損失函數Loss Function，那么可以通過梯度的反向傳播來更新神經網絡的參數w，當w收斂后就得到的 近似的Q值計算方法，進而貪婪策略也就求出來了。
?
算法流程
輸入：迭代輪數T、狀態特征維度n、動作集A、步長α、衰減因子γ、探索率?、Q網絡結構、批量梯度下降的樣本數m
輸出：Q網絡參數w
? 1. 隨機初始化Q網絡的所有參數w，基于w初始化所有的狀態和動作對應的價值Q，清空經驗池D
? 2. for i in [ 1, T ]：
? a）初始化S為當前狀態序列的第一個狀態，拿到其特征向量?(S)
? b）把?(S)輸入Q網絡，得到所有動作對應的Q值輸出，用ε-greedy策略從中選擇出動作A
? c）執行動作A，由環境得到新狀態S‘ 對應的特征向量?(S‘)、獎勵R’、終止標志is_end
? d）將 { ?(S)，A，R，?(S‘)，is_end } 這個五元組存入經驗池D
? e）前進一步：S = S’
? f）從經驗池中采集m個樣本 { ?(Sj)，Aj，Rj，?(Sj‘)，is_endj }，j = 1,2,3…，把S‘ 和A’ 輸入神經網絡結合貪婪策略計算當前目標Q 值 yj：
?
? g）把S‘ 和A’ 輸入Q網絡直接求Q估計值，由目標Q值和Q估計值求損失函數Loss Function，然后梯度反向傳播更新Q網絡參數w
? h）if S’是終止狀態，break；else 跳回步驟b
? （注意，f步和g步的Q值計算都需要用到Q網絡。另外，實際應用中為了算法較好的收斂，探索率?需要隨著迭代的進行而變小 ）
?
小結
? DQN由于對價值函數做了近似表示，因此有了解決大規模強化學習問題的能力。但是DQN有個問題，就是它并不一定能保證Q網絡的收斂，也就是說不一定可以得到收斂后的Q網絡參數。這會導致訓練出的模型效果很差。針對這個問題衍生出了DQN的很多變種，比如Nature DQN(NIPS 2015)、Double DQN、Dueling DQN等。
?
?
?
?
Nature DQN算法
概述
Nature DQN的優化點：
? 目標Q值的計算用到了當前要訓練的網絡參數w：
?
? 用來計算損失函數的目標Q值和Q估計值，二者相關性太強，不利于算法收斂。因此提出Nature DQN使用兩個Q網絡來分別計 算目標Q值和Q估計值，從而減少二者間的依賴關系。
Nature DQN 建模——雙網絡結構：
? 相較于普通DQN，Nature DQN使用了兩個Q網絡，當前Q網絡用來選擇動作，更新模型參數，目標Q網絡用于計算目標Q值。 目標Q網絡的網絡參數不需要迭代更新，而是每隔一段時間從當前Q網絡復制過來，即延時更新，這樣可以減少目標Q值和當前 Q值的相關性。二者其余部分基本是完全相同的。（要注意的是，兩個Q網絡的結構是一模一樣的。這樣才可以復制網絡參數 ）
?
算法流程
輸入：迭代輪數T、狀態特征維度n、動作集A、步長α、衰減因子γ、探索率?、當前Q網絡Q、目標Q網絡Q′、批量梯度下降的樣本數m、 目標Q網絡參數更新頻率C
輸出：當前Q網絡參數（目標Q網絡只是輔助工具）
? 1. 隨機初始化所有狀態和動作對應的價值Q，隨機初始化當前Q網絡的所有參數w，初始化目標Q網絡Q′的參數w′=w，清空經驗池D
? 2. for i in [ 1, T ]:
? a）初始化S為當前序列的第一個狀態，求其特征向量 ?(S)
? b）把 ?(S) 輸入當前Q網絡，得到所有動作對應的Q值輸出，用 ε-greedy 策略從中選擇出動作 A
? c）執行動作 A，由環境得到新狀態 S‘ 對應的特征向量 ?(S’)、獎勵 R、終止標志 is_end
? d）將 { ?(S)，A，R，?(S‘)，is_end } 這個五元組存入經驗池 D
? e）前進一步：S = S’
? f）從經驗池中采集m個樣本 { ?(Sj)，Aj，Rj，?(Sj‘)，is_endj }，j = 1,2,3…，把S‘ 和A’ 輸入目標Q網絡結合貪婪策略計算當前目 標Q值 yj：
? （注意：公式里的是Q’ 不是Q )
? g）把S‘ 和A’ 輸入當前Q網絡求Q估計值，由目標Q值和Q估計值求損失函數Loss Function，然后梯度反向傳播更新當前Q 網絡參數w
? h）if i%C == 0：更新目標Q網絡參數w’ = w
? i）if S’是終止狀態，break；else 跳回步驟b
? （注意，f步用的是目標Q網絡、g步用的是當前Q網絡。另外，實際應用中為了算法較好的收斂，探索率?需要隨著迭代變小 ）
?
小結
? Nature DQN 對 普通DQN 做了相關性方面的改進，這個改進雖然不錯，但是仍然沒有解決DQN的 很多問題，比如：
1） 目標Q值的計算是否準確？全部通過max Q來計算有沒有問題？
2） 從經驗池隨機采樣的方法好嗎？按道理不同樣本的重要性是不一樣的。
3） Q值代表狀態動作的價值，那么單獨動作價值的評估會不會更準確？
第一個問題對應的改進是Double DQN, 第二個問題的改進是Prioritised Replay DQN，第三個問題的改進是Dueling DQN。
?
?
?
?
Double DQN算法
概述
DDQN的優化點：
? 在DDQN之前，基本上所有的目標Q值都是通過貪婪法直接得到的，無論是Q-Learning、普通DQN 還是 Nature DQN。比如對 于Nature DQN，雖然用了兩個Q網絡并使用目標Q網絡計算目標Q值，其第 j 個樣本的目標Q值的計算還是貪婪法得到的：
?
? 使用max雖然可以快速讓Q值向可能的優化目標靠攏，但是很容易過猶不及，導致過度估計(Over Estimation)。所謂過度估計就 是最終得到的算法模型有很大的偏差(bias)。而DDQN通過解耦目標Q值動作的選擇和目標Q值的計算這兩步，來達到消除過度估計的 問題。
DDQN建模——Q值與動作解耦:
? DDQN 和 Nature DQN一樣，也有一樣的兩個Q網絡結構。在 Nature DQN 的基礎上，通過解耦目標Q值動作的選擇和目標Q值的計算這兩步，來消除過度估計的問題。
? Nature DQN對于非終止狀態，其目標Q值的計算式子是：
?
? 在DDQN這里，不再是直接在目標Q網絡里面找各個動作中最大Q值，而是先把S‘ 輸入當前Q網絡中找出最大Q值對應的動作amax(S′j,w)，即：
?
? 然后利用這個選擇出來的動作amax(S′j,w)在目標網絡里面去計算目標Q值。即：
?
? 綜合起來寫就是：
?
? 動作A’ 是在當前Q網絡對經驗池樣本S‘ 的輸出中選擇，然后用目標Q網絡對A‘ 和S’ 算目標Q值。
?
算法流程
輸入：迭代輪數T、狀態特征維度n、動作集A、步長α、衰減因子γ、探索率?、當前Q網絡、目標Q網絡、批量梯度下降的樣本數m、目標Q網絡參數更新頻率C
輸出：當前Q網絡參數
? 1. 隨機初始化所有狀態和動作對應的價值Q，隨機初始化當前Q網絡的所有參數w，初始化目標Q網絡Q′的參數w′=w，清空經驗池D
? 2. for i in [ 1, T ]:
? a）初始化S為當前狀態序列的第一個狀態, 拿到其特征向量 ?(S)
? b）把?(S)輸入當前Q網絡，得到所有動作對應的Q值輸出，用ε-greedy策略從中選擇出動作 A
? c）執行動作 A，由環境得到新狀態 S‘ 對應的特征向量 ?(S’)、獎勵 R、終止標志 is_end
? d）將 { ?(S)，A，R，?(S‘)，is_end } 這個五元組存入經驗池 D
? e）前進一步：S = S’
? f）從經驗池中采集m個樣本 { ?(Sj)，Aj，Rj，?(Sj‘)，is_endj }，j = 1,2,3…，用Q值與動作解耦的思想計算目標Q值：
?
? g）用當前Q網絡求Q估計值，由目標Q值和Q估計值求損失函數 Loss Function，然后梯度反向傳播更新當前Q網絡參數 w
? h）if i%C == 0：更新目標Q網絡參數w’ = w
? i）if S’是終止狀態，break；else 跳回步驟b
? （注意，f步兩個網絡都用了、g步只用到了當前Q網絡。另外，實際應用中為了算法較好的收斂，探索率?需要隨著迭代變小 ）
?
?
?
?
Prioritized Replay DQN算法
概述
Prioritized Replay DQN的優化點：
? 普通DQN、Nature DQN、DDQN等都是通過經驗回放來采樣，進而做目標Q值的計算的。在采樣時經驗池里的所有樣本都有相 同的被采樣概率。但是注意到在經驗池里面的不同的樣本由于TD誤差的不同，對反向傳播的作用是不一樣的。TD誤差越大，對反向 傳播的作用越大。而TD誤差小的樣本對反向梯度的計算影響不大。在Q網絡中，TD誤差就是目標Q網絡計算的目標Q值和當前Q網絡 計算的Q值之間的差距。這樣如果TD誤差的絕對值|δ(t)|較大的樣本更容易被采樣，則算法會比較容易收斂。
Prioritized Replay DQN建模:
? 1. 經驗池優化：
? Prioritized Replay DQN的經驗池中每個樣本的優先級正比于TD誤差絕對值|δ(t)|。由于引入了經驗回放的優先級，Prioritized Replay DQN的經驗池和之前的其他DQN算法的經驗池不一樣，因為這個優先級大小會影響它被采樣的概率。在實際使用中，通常使 用SumTree這樣的二叉樹結構來做帶優先級的經驗回放池樣本的存儲：
?
? 所有的經驗回放樣本只保存在最下面的葉子節點上面，一個節點一個樣本，內部節點不保存樣本數據。葉子節點除了保存數據 以外，還要保存該樣本的優先級數值（TD誤差）。對于內部節點每個節點只保存自己的兒子節點的優先級值之和。以上面的樹結構 為例，根節點是42，如果要采樣一個樣本，可以在[0,42]之間做均勻采樣，采樣到哪個區間，就是哪個樣本。
? （注意：當Q網絡參數進行了梯度更新后，需要重新計算TD誤差，并將TD誤差更新到SunTree上面 ）
? 2. Loss Function優化：
? 通常使用的損失函數：
?
? 考慮了樣本優先級的損失函數要加上優先權重因子：
?
? 其中wj是第j個樣本的優先級權重，由TD誤差|δ(t)|歸一化得到
?
算法流程（集成了DDQN）
輸入：迭代輪數T、狀態特征維度n、動作集A、步長α、采樣權重系數β、衰減因子γ、探索率?、當前Q網絡、目標Q網絡、批量梯度下降的樣本數m、目標Q網絡參數更新頻率C、SumTree的葉子節點數S
輸出：當前Q網絡參數
? 1. 隨機初始化所有狀態和動作對應的價值Q，隨機初始化當前Q網絡的所有參數w，初始化目標Q網絡Q′的參數w′=w
? 2. 初始化經驗池SumTree的默認數據結構，SumTree的S個葉子節點的優先級pj都初始化為1
? 3. for i in [ 1, T ]:
? a）初始化S為當前狀態序列的第一個狀態, 拿到其特征向量 ?(S)
? b）把?(S)輸入當前Q網絡，得到所有動作對應的Q值輸出，用ε-greedy策略從中選擇出動作 A
? c）執行動作 A，由環境得到新狀態 S‘ 對應的特征向量 ?(S’)、獎勵 R、終止標志 is_end
? d）將 { ?(S)，A，R，?(S‘)，is_end } 這個五元組存入SumTree
? e）前進一步：S = S’
? f）從SumTree中依概率 P(j) = pj / ∑(pi) 采集m個樣本 { ?(Sj)，Aj，Rj，?(Sj‘)，is_endj }，j = 1,2,3…，用Q值與動作解耦的 思想計算目標Q值：
?
? g）用當前Q網絡求Q估計值，由目標Q值和Q估計值求帶優先權重因子wj的損失函數 Loss Function，然后梯度反向傳播更新當 前Q網絡參數 w，其中優先權重因子的公式為：
?
? h）用更新參數后的當前Q網絡重新計算經驗池中每個樣本的Q估計值，然后用目標Q值和新的Q估計值算出新的TD誤差作為優先 級更新SumTree
? i）if i%C == 0：更新目標Q網絡參數w’ = w
? j）if S’是終止狀態，break；else 跳回步驟b
? （注意，f步兩個網絡都用了、g步只用到了當前Q網絡。另外，實際應用中為了算法較好的收斂，探索率?需要隨著迭代變小 ）
?
?
?
?
Dueling DQN算法
概述
Dueling DQN的優化點：
? DDQN中通過優化目標Q值的計算來優化算法，Prioritized Replay DQN中通過優化經驗回放池按權重采樣來優化算法，而在 Dueling DQN中通過優化神經網絡的結構來優化算法。
Dueling DQN網絡結構:
? Dueling DQN將Q網絡分成兩部分。第一部分僅與狀態S有關，與具體要采用的動作A無關，叫做價值函數部分，記做V(S,w,α)。 第二部分同時與狀態狀態S和動作A有關，這部分叫做**優勢函數(Advantage Function)**部分，記為A(S,A,w,β)。
?
? 最終價值函數可以重新 表示為：
?
? （其中，w是公共部分的網絡參數，而α是價值函數部分獨有的網絡參數，β是優勢函數部分獨有的網絡參數 ）
? 考慮到這個式子無法辨識最終輸出里面V(S,w,α)和A(S,A,w,β)各自的作用，為了可以體現這種可辨識性(identifiability),實際使用的 組合公式如下：
?
? （其實就是對優勢函數部分做了中心化的處理 ）
?
?
?
?
總結
? 這里一共總結了5種DQN算法：普通DQn、Nature DQN、DDQN、Prioritized Replay DQN、Dueling DQN，目前使用的比較主流的是后面三種算法思路，這三種算法思路也是可以混著一起使用的，相互并不排斥。
? 當然DQN家族的算法遠遠不止這些，還有一些其他的DQN算法沒有總結，比如使用一些較復雜的CNN和RNN網絡來提高DQN的表達能力，又比如改進探索狀態空間的方法等，主要是在DQN的基礎上持續優化。
? DQN算是深度強化學習的中的主流流派，代表了Value-Based這一大類深度強化學習算法。但是它也有自己的一些問題，就是絕大多數DQN只能處理離散的動作集合，不能處理連續的動作集合。雖然NAF DQN可以解決這個問題，但是方法過于復雜了。而深度強化學習的另一個主流流派Policy-Based而可以較好的解決這個問題。
總結
以上是生活随笔為你收集整理的【强化学习】DQN及其延伸算法的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 【强化学习】Q-Learning
- 下一篇： 【强化学习】策略梯度Policy-Gra