Modern Deep Reinforcement Learning Algorithms

Sergey Ivanov, Alexander Dyakonov, Moscow State University, 2019.06

摘要

近年來，強化學習領域基於傳統理論與深度學習

相結合的研究範式在許多人工智慧任務中取得了明顯的突破，催生了深度強化學習（Deep Reinforcement Learning, DRL）這樣的新研究領域。這篇綜述回顧了近年來的DRL演算法並且主要關注理論證明、應用侷限以復現實驗中觀察到的特點。（這篇綜述篇幅較長，後面翻譯基礎部分從簡，基本的RL概念可以參看這裡）

1. 引言

深度強化學習在很多人工智慧領域取得與人類相當的水平，如圍棋、Dota、StartCraft II等。雖然RL一般用序列決策來建模，但是對於世界的模型假設是很少的，經常把世界作為一種黑盒，這樣模型的適應能力更強。

第二節建立基本的RL模型，涉及到探索以及延遲稀疏獎勵等概念。

第三節一部分內容介紹傳統的RL演算法，這部分是理論基石，這些演算法在小規模以及環境狀態可枚舉的問題上能較好的應用。另一部分介紹基於價值的強化學習研究這一方向，主要介紹DQN，DQN再提出後的幾年顯著地擴展和提高了DRL這一領域研究水平。

第四節介紹基於價值的DRL的分散式方法。

第五節介紹DRL的另一個主要的研究方向——策略梯度方法。策略梯度方法直接優化目標函數，並且在問題建立的時候就顯式地表達出來。策略梯度方法使用神經網路的時候需要使用一些特殊的優化方法來解決一些問題。策略方法已經成為了很有競爭力的DRL方法，主要得益於巨大的並行化潛力以及連續問題的解決能力。

第六節在標準測試環境下復現state-of-art DRL演算法，討論這些演算法在實際應用中的細微差別。目前最先進的DRL演算法人然由很多不足的地方。和神經網路訓練需要大量數據類似，DRL在一些數據產生難度大的場景下難以取得令人滿意的效果。另外，強化學習對初始化以及超參數敏感，優化過程不穩定。因此很多不同團隊觀測到的經驗有難以復現。

2. 強化學習問題的建立

2.1 兩個假設

獎勵假設：強化學習的目的是最大化累積獎勵的期望。Markov假設：轉移只依賴當前狀態和當前選擇的動作，與之前的狀態和動作無關。

2.2 環境模型的兩個定義

馬爾可夫決策（MDP）:

馬爾可夫決策可以表示為 (mathcal{S},mathcal{A},mathbb{T},r,s_0) ，其中：

  • mathcal{S} in mathbb{R}^d ——狀態空間。
  • mathcal{A} ——動作空間。離散： |mathcal{A}|<+infty ，連續： mathcal{A}=[-1,1]^m 。
  • mathbb{T} ——轉移概率 p(s|s,a) , s,s in mathcal{S} , a in mathcal{A} 。
  • r:mathcal{S} ightarrowmathbb{R} ——獎勵函數函數。
  • s_0 in mathcal{S} ——初始狀態。

狀態轉移

狀態轉移用 (s_t,a_t,r_{t+1},s_{t+1}) 來表示。觀察到的軌跡可以寫成s_0,a_0,r_1,s_1,a_1,r_2,s_2,a_2,r_3,s_3,a_3,cdots

2.3 目標

最大化累計獎勵（maximize a cumulative reward）,叫做回報（return）：

R:=sum_{t=1}^{T}r_t ag{1}

策略（policy）是智能體在某狀態下採取某動作的概率分佈 pi(a|s) 。在此基礎上可以定義軌跡 { s_0, a_0, s_1,a_1,s_2,a_2,cdots} 的概率分佈，記為 mathcal{T}_{pi} : mathcal{T}_{pi}:=prod_{t=0}p(s_{t+1}|s_t,s_t)pi(a_t|s_t) 。此時，期望獎勵最大化可寫成 mathbb{E}_{mathcal{T}_pi}sum_{t=1}^{T}r_t ightarrowmax_{pi} ，這個式要收斂的話，則要保證 |r_t|leq R^{ ext{max}} ( r_t 有界)，因此引入折扣期望獎勵模型：J(pi):=mathbb{E}_{mathcal{T}_{pi}}sum_{t=0}gamma^{t}r_{t+1} ， gamma in [0,1) 。在折扣獎勵模型下，強化學習的任務就是找到最優的策略 pi^* 使得折期望獎勵最大化：

J(pi) ightarrowmax_{pi} ag{2}

2.4 值函數

在給定策略 pi 下，狀態 s 的值函數為： V^{pi}(s):=mathbb{E}_{mathcal{T}_{pi}|s_0=s}sum_{t=0}gamma^{t}r_{t+1} ，即在策略 pi 以及智能體處於狀態 s 的條件下，它後續獲得累計獎勵的期望，最優值函數用 V^{pi^*} 表示（傳統上也用 V^* 表示）。另外一個重要的函數是Q函數： Q^{pi}(s,a):=mathbb{E}_{mathcal{T}_{pi}|s_0=s,a_0=a}sum_{t=0}gamma^{t}r_{t+1} ，以上兩個函數是相互聯繫的：

Q^{pi}(s,a)=mathbb{E}_{ssim p(s|s,a)}[r(s)+gamma V^{pi}(s)] ag{3}

V^{pi}(s)=mathbb{E}_{ain pi(a|s)}Q^{pi}(s,a) ag{4}

求解最優Q函數 Q^*(s,a) 實際上是在求解最佳策略： pi^*(s)=argmax_a Q^*(s,a) 。

2.5 強化學習演算法分類

meta-heuristics，policy gradient，value-based，model-based。（下圖為部分DRL演算法分類圖，未完全按綜述方法進行分類）

部分DRL演算法分類

2.6 性能評估

平均累計獎勵。另外，採樣效率（sample efficiency）、wall-clock time也是需要考慮的指標。

3. 基於價值的演算法（Value-based algorithms）

3.1 TD (Temporal Difference learning)

這裡直接給出Q-learning的形式化定義：

Q^*_{t+1}(s,a)=mathbb{E}_{sin p(s|s,a)}[r_{t+1}+gamma max_{a} Q_t^*(s,a)] ag{7}

注意，式子裡面用的期望( mathbb{E} )進行Q函數更新。同樣，直接給出TD演算法(TD(0))的形式化定義(在Sutton的書裡面，下面的(9)就是Q-learning，是off-policy TD（有max操作），Sarsa是on-policy TD（無max操作）)：

Q^*_{t+1}(s,a)=egin{cases}Q^*_{t}(s,a)+alpha[r_{t+1}+gamma max_{a} Q(s,a)-Q^*_{t}(s,a)]& ext{if }s=s,a=a\ Q^*_{t}(s,a)& ext{otherwise}end{cases} ag{9}

注意，這裡沒有出現求期望的過程，而是用多看一步與部分更新來代替。中括弧裡面的叫做時間差分項，在最優Q函數下，該項為0。TD實際上用下一步的最大目標值與當前值做差並部分更新代替了求期望這一步驟，但是max這種貪婪的操作有時候會比較「短視」，有些獎勵非常大但是比較遠的狀態可能永遠訪問不到。這時候就要允許智能體拋棄貪婪思想去探索，最普遍使用的就是 epsilon ext{-greedy}策略，即每次以 epsilon 的概率按照貪婪規則採取動作，以 (1-epsilon) 的概率去探索（隨機選取動作）。

TD演算法在實際中有個問題就是，必須將Q值表顯示地存儲在內存中，如果狀態空間或者動作空間非常大或者是連續的，此時就必須用近似（approximation）的方法。

3.2 Deep Q-learning (DQN)

(這部分內容參考文獻建議看2015年的DQN文章。)

用神經網路對策略或者Q函數建模其實很早就有人這麼做了(叫做NFQ, Riedmiller, 2005)。將經驗重放用於Q-learning就更早了（Long-Ji Lin, 1993）。DQN作者認為最大的特點在於可以直接使用原始高維感測器數據進行強化學習，並且使用隨機梯度下降進行訓練，並且訓練過程更加穩定。這裡面涉及目標網路(target network)、經驗重放等概念。

先說目標網路。用一個網路來近似Q函數 Q(s,a; heta)approx Q^*(s,a) ，用 y=r+gamma max_{a}Q(s,a; heta_i^-) 來近似表示目標值，其中 heta_i^- 是之前某次迭代的參數。在收斂到最優策略時，應當有 yequiv Q(s,a; heta) 。因此使用梯度下降的迭代方法求解最優貝爾曼方程。用 L_i( heta_i) 表示第 i 次迭代的損失函數

L_i( heta_i)=mathbb{E}_{s,a,r}[(mathbb{E}_{s}[y|s,a]-Q(s,a; heta_i))^2]=\{ ext{using}(7)}=mathbb{E}_{s,a,r,s}[(y-Q(s,a; heta_i))^2]+mathbb{E}_{s,a,r}[mathbb{V}_{s}[y]]

把 y 代入，並對 heta 求導，得到損失函數的梯度為

abla_{ heta_i} L( heta_i)=mathbb{E}_{s,a,r}[ig(r+gamma max_{a}Q(s,a; heta_i^-)-Q(s,a; heta_i)ig) abla_{ heta_i}Q(s,a; heta_i)]

這個式子裡面的期望不用完整的求出來，只需要使用隨機梯度下降的方法即可。值得注意的是，上面的梯度裡面，最終是對 heta_i 求導，並沒有有對 heta_i^- 採取任何操作。將 Q^*(s,a, heta) 視為 mathcal{S} imes mathcal{A} ightarrowmathbb{R} 的函數，用 heta^{s,a} 表示： heta^{s,a}=Q^*(s,a, heta)， heta^{s,a}in mathbb{R}^{|mathcal{S}||mathcal{A}|} ，則有 heta_{i+1}= heta_i-alpha_i abla_{ heta_i }L_i( heta_i) ，這就是隨機梯度下降的公式，並且這個形式與(9)是統一的。

再說經驗重放。將智能體每次與環境的交互記為 e_t=(s_t,a_t,r_{t+1},s_{t+1}) ，在2015發表DQN的論文裡面 e_t=(s_t,a_t,r_{t},s_{t+1}) ，查了一下Sutton的書（2018版16.5節），裡面寫的 (S_t,A_t,R_{t+1},S_{t+1}) 。將最近的 N 個交互存儲起來用 D_t={e_1,cdots,e_t} 表示。在演算法的內層循環裡面使用小批量（minibatch）更新， (s,a,r,s)sim U(D) ， U(D) 表示從 D_t 裡面均勻採樣。好處有三，（1）交互經驗可以用在多次權重更新上，數據利用率高；（2）降低樣本相關性，減小更新方差；（3）行為分佈被平均，避免訓練震蕩和發散。

DQN with experience replay

3.3 Double DQN

3.4 Dueling DQN

3.5 Noisy DQN

3.6 Prioritized experience replay

3.7 Multi-step DQN

4. 值分佈演算法 (Distributional approaches for value-based methods)

4.1 理論基礎

4.2 Categorical DQN

4.3 Quantile Regression DQN (QR-DQN)

4.4 Rainbow DQN

5. 策略梯度演算法 (Policy Gradient algorithms)

5.1 策略梯度理論

5.2 REINFORCE

5.3 Advantage Actor-Critic (A2C)

推薦閱讀：

相關文章