深度強化學習專欄（三）

• 2019 年 10 月 4 日
• 筆記

作者 | 小猴鍋

編輯 | 安可

出品 | 磐創AI團隊出品

【磐創AI導讀】：本篇文章是深度強化學習專欄的第三篇，講了第四節無模型的強化學習方法，希望對大家有所幫助。查看上篇關於本專欄的介紹：深度強化學習（DRL）專欄開篇。

目錄：

1. 引言

• 專欄知識結構
• 從AlphaGo看深度強化學習

2. 強化學習基礎知識

• 強化學習問題
• 馬爾科夫決策過程
• 最優價值函數和貝爾曼方程

3. 有模型的強化學習方法

• 價值迭代
• 策略迭代

4. 無模型的強化學習方法

• 蒙特卡洛方法
• 時序差分學習
• 值函數近似
• 策略搜索

5. 實戰強化學習算法

• Q-learning 算法
• Monte Carlo Policy Gradient 算法
• Actor Critic 算法

6. 深度強化學習算法

• Deep Q-Networks(DQN)
• Deep Deterministic Policy Gradient(DDPG)

7. 專欄小結

4 無模型的強化學習方法

在有模型（model-based）的強化學習方法中，我們擁有環境的完整描述（例如狀態轉移概率P和獎勵R），所以可以使用動態規劃的方法求解策略。然而在實際情況中，我們很少會擁有這麼詳細的環境信息（例如「Frozen Lake」遊戲），這時就需要agent自己去探索環境，並尋找策略。我們稱這種情況為無模型（model-free）的強化學習方法。這也是強化學習問題中最常使用的方法。

4.1 蒙特卡洛方法

蒙特卡洛方法（Monte Carlo Methods）又稱為統計模擬方法，通過前面的學習，我們知道實際上Q值函數（動作-價值函數）其實就是一個期望，所以我們可以直接使用採樣來代替期望。

蒙特卡洛方法的思想是：對於某個隨機事件，如果我們想要得到該隨機事件發生的概率，可以通過重複實驗的方式，以該事件發生的頻率來近似替代該事件發生的概率。

無模型的強化學習方法和上一節里介紹的策略迭代的方法思路很像，也同樣由兩部分組成：策略估計和策略改進。

1.策略估計和策略改進

在策略迭代方法中的策略估計部分，由於中間動作（或狀態）的獎勵R是已知的，所以只要按照當前策略走一遍，就可以得到當前狀態的價值。而在無模型的強化學習方法中，由於不知道中間動作（或狀態）的獎勵，所以如果想要知道某個狀態的價值，就需要從這個狀態出發，按照當前策略，走完多個回合併得到多個累積獎勵，然後計算這多個累積獎勵的平均值作為當前狀態的價值，即用採樣去逼近真實的值，以「Frozen Lake」遊戲為例，如下圖所示：

圖1 從S_2狀態出發的多條路線的累積獎勵

如圖1所示，假設以S_2狀態為例，從S_2狀態出發直到終止狀態，可以有多條路徑，每條路徑都可以得到一個累積獎勵，我們將所有累積獎勵的平均值作為當前狀態S_2的狀態價值，即：

仔細觀察圖1我們會發現，例如第二條路徑，S_2狀態和S_3狀態都被訪問了兩次。根據計算每條路徑的累積獎勵的方式不同，蒙特卡洛方法可以分為兩種：First-Visit Monte Carlo和Every-Visit Monte Carlo。在First-Visit Monte Carlo方法中，不管一個狀態被訪問了多少次，在計算累積獎勵的時候只考慮第一次的訪問。而在Every-Visit Monto Carlo方法中，如果一個狀態被多次訪問，則在計算累積獎勵的時候，每一次的訪問都會被考慮在內。

目前我們只考慮了狀態的價值，同樣的方法可以得到狀態-動作價值（Q值）：在狀態S下採取動作a，之後遵循當前策略π獲得的累計期望獎勵就是Q^π (s,a)的價值。

在得到Q值函數後，策略改進的方法就和前面策略迭代方法中的策略改進方法一樣，即：利用當前的Q值函數更新策略（策略就是採取具有Q值最大的按個動作），如果更新後的策略與之前的策略一致，則說明已經收斂，策略求解結束，否則繼續執行策略估計。

Initialization：  Initial a polic π  For s in S:      For a in A:          Initial Q(s,a) and Return(s,a)          c(s,a)=0  For i in range(k):  Generate an episode using π  For each state s appearing in the episode:  G ← the return that follows the first occurrence of s  Q(s_t,a_t)=(c(s_t,a_t)*Q(s_t,a_t)+G)/(c(s_t,a_t)+1)  c(s_t,a_t)++  end for  update policy π(s)=argmaxQ(s,a)  end for

蒙特卡洛算法

2.環境探索

在策略估計的時候還存在一個問題，我們是想通過計算策略π下，從狀態S出發的多個路徑的平均累積獎勵，然而，一但確定了這個策略π，那麼每次採取的動作必然有a_t=π(s_t)。即一但策略確定後，能夠採取的動作也就確定了，所以不管走多少個回合，路徑都是一樣的，如此一來就沒法進行策略估計了。所以我們需要有一個探索環境的辦法。一種常用的方法是ε貪心（ε-greedy）搜索。

ε貪心搜索方法：首先初始一個概率ε，在進行策略估計的時候，以ε的概率隨機選擇一個動作，以1-ε的概率去根據當前的策略選擇動作。考慮到剛開始進行策略估計的時候，應該更注重對環境的探索，而隨着策略慢慢地改進，則應該更注重策略的利用。所以，初始的ε值較大，隨着策略的不斷改進，慢慢減小ε的值。

3.確定性的和非確定性的環境狀態

「Frozen Lake」遊戲有「無風」和「有風」兩種遊戲模式。「無風」模式下，遊戲環境是確定的，即agent執行一個動作（例如右移或下移）後，到達的下一個狀態是確定的，並且得到的獎勵也是確定的，而在「有風」模式下，環境狀態則不確定了。圖6-10中的蒙特卡洛算法考慮的是非確定性的環境狀態，所以採用取平均值的方式，希望能夠近似替代真實的狀態價值。如果是確定性的環境狀態的話，就可以省去取平均值的操作，直接賦值為：Q(s_t,a_t)=G。

4.在策略（on-policy）和離策略（off-policy）

在策略（on-policy）和離策略（off-policy）是強化學習問題中常見的兩個概念。在agent進行策略估計的時候，我們需要使用一些辦法進行環境的探索，例如ε貪心搜索。在這種情況下，我們學到的策略π其實是帶有探索的策略，如果我們在進行策略改進的時候，也使用該策略的話，則會導致我們最終得到的策略也是帶有探索的策略。策略估計和策略改進都是用這種帶有探索的策略的情況稱為在策略（on-policy）。

然而我們更希望最終agent學到的策略是不帶探索的，雖然在策略評估的時候我們避免不了使用探索策略，但是在策略改進的時候，我們可以有一些方法抵消掉探索對策略的影響，這種只在策略估計的時候使用帶探索的策略，而在策略改進的時候只考慮不帶探索的策略的方式稱為離策略（off-policy）。在蒙特卡洛方法中我們可以使用重要性採樣（importance sampling）技術實現離策略的算法。

4.2 時序差分學習

時序差分學習（Temporal-Difference Learning）是另一種無模型（model-free）的強化學習方法。蒙特卡洛方法不足的地方是它只能應用於回合步數有限的情況（因為蒙特卡洛方法只有在一個回合結束並得到一個獎勵後，才能去更新一個狀態的價值），然而現實問題中，很多問題並不能在有限的步數里結束，例如無人駕駛和機械人控制，而時序差分學習則可以應用於這類回合持續時間很長的任務。

1. 蒙特卡洛更新和時序差分更新

在蒙特卡洛方法里我們都是利用一個回合結束後得到的獎勵來更新當前的Q值，這種更新的方式稱為蒙特卡洛更新。我們希望可以儘早的更新Q值，而不是只有等到一個回合結束之後才能更新，這就是時序差分更新。

在蒙特卡洛算法中，更新Q值的公式為：

式1

公式1是將所有的累積獎勵取平均值，假設c(s_t,a_t )=k,並用G_i表示第i次得到的獎勵的話，公式1可以表示為：

式2

我們將公式2中的1/(k+1)看做一個參數α，我們稱之為學習率，學習率的存在是為了Q值最終收斂，並且該參數的值隨着時間遞減。現在我們將公式2改寫為一個更常用的形式：

式3

上式中的G-Q(s_t,a_t )稱為蒙特卡洛誤差。事實上，Q(s_t,a_t )的值其實就是agent在狀態s_t下，執行動作a_t後，沿着當前策略走下去後所能得到的累積獎勵的期望，是對獎勵的一個估計值，而蒙特卡洛算法中走完一個回合後得到的G是真實的獎勵值，時序差分學習希望用這個估計的獎勵值替代真實的獎勵值。因此，時序差分方法更新Q值的公式為：

式4

公式4中的

稱為時序差分誤差（TD誤差），r_(t+1)+γQ(s_(t+1),a_(t+1))是公式3中G的近似值，公式4中的折扣因子γ(0≤γ≤1)在本專欄的2.1節中介紹過。如果去掉折扣因子γ，則有：

在介紹蒙特卡洛方法的時候，我們說到了確定性的和非確定性的環境狀態，在時序差分學習方法中，如果環境狀態是確定的，則Q值的更新公式為：

式5

2. Sarsa算法

Sarsa算法是時序差分學習的在策略版本，Sarsa算法的偽代碼如下：

For s in S:  For a in A:      Initialize Q(s,a)  For i in range(k):  Initialize S  Choose a using policy derived from Q (e.g.ε-greedy)  Repeat (for each step of episode):  Take action a,observe r and s  Choose a^' using policy derived from Q (e.g.ε-greedy)  Q(s, a) ← Q(s, a) + α[R + γQ(s^', a^') − Q(s, a)]  s ←s^'; a ←a^'  until s is terminal  End for

Sarsa算法

3. Q-Learning算法

Q-Learning算法是時序差分學習方法的離策略版本，Q-Learning算法的偽代碼如下：

For s in S:  For a in A:      Initialize Q(s,a)  For i in range(k):  Initialize S  Repeat (for each step of episode):  Choose a using policy derived from Q (e.g.ε-greedy)  Take action a,observe r and s  Q(s, a) ← Q(s, a) + α[R + γmax(Q(s^', a^')) − Q(s, a)]  s ←s^'  until s is terminal  End for

Q-Learning算法

在時序差分學習方法中，在策略的Sarsa算法使用估計的策略採取動作，而離策略的Q-Learning算法選擇所有可能的下一動作中Q值最大的動作（即Q-Learning有一個專門用來產生行為的策略）。

如果是在確定性的環境狀態下，Q-Learning的Q值的更新方式可以簡化為：

式6

這裡我們介紹的Sarsa算法和Q-Learning算法均為單步更新算法，即時序差分誤差都只用來更新前一個值，我們可以通過使用資格跡（eligibility trace）來實現多步的更新，有關資格跡的討論不在本專欄的範圍。

4.3 值函數近似

在前面介紹的所有強化學習方法中，我們所有的狀態-動作價值（Q值）或狀態價值（V值）都是存放在表中的，這種方法在狀態空間和動作空間都不大的情況下還很適用，一旦狀態空間和動作空間變得很大，那麼表格的尺寸也會變得很大，有時甚至大到無法存儲（例如圍棋），即使能夠存儲，算法的效率也會受到很大影響。而且如果是連續的狀態和動作（例如無人駕駛），使用表格勢必會將狀態和動作離散化，這可能會導致誤差。因此，我們想用一個函數來近似表示Q值表（或V值表），這種方法稱為值函數近似（Value Function Approximation）。

利用函數去逼近Q值表（或V值表）的問題可以看作一個回歸問題，以Q-Learning為例，我們定義一個回歸器Q(s,a|θ),其中θ是一個參數向量。我們輸入的數據是狀態-動作對(s_t,a_t)，希望輸出的是

的值，因此，我們可以定義誤差函數為：

具體這個回歸器的選擇，可以是一個線性的模型，也可以是一個非線性的模型，例如神經網絡。

4.4 策略搜索

1. 基於值函數（value-based）和基於策略函數（policy-based）

前面介紹的所有方法都是先把V值或者Q值估計出來，然後再從中推導出策略，我們稱這一類方法為基於值函數（value-based）的方法。使用基於值函數的方法可以採用表格的形式，如果使用函數近似的話會出現策略退化問題。為了解決這個問題，我們可以直接去尋找策略，而不是通過值函數來導出策略，這種直接學習策略的方法稱為基於策略函數（policy-based）的方法。我們一般是直接在策略空間中搜索得到最優策略，該方法稱為策略搜索（policy search）。

2.策略梯度（Policy Gradient）

在策略搜索中，我們可以使用基於梯度的方式來優化策略，這種方法稱為策略梯度。假設我們的策略函數為π_θ (a|s),θ為這個函數的參數，我們定義目標函數為：

式7

有了目標函數J(θ)，我們可以使用梯度上升的方法來優化參數θ使得目標函數J(θ)增大，梯度就是函數J(θ)關於參數θ的導數，即：

式8

上式中

是從時刻t作為起始時刻，直至結束後得到的累積獎勵。

3. Monte Carlo Policy Gradient算法

在前面介紹蒙特卡洛方法的時候介紹過，期望可以通過採樣的方法近似，對於當前的策略π_θ，我們可以通過讓agent在環境中運行，得到多個運動軌跡，對於每一條軌跡，我們可以計算每個時刻的梯度，將得到的梯度乘以一個學習率用來更新參數，這就是Monte Carlo Policy Gradient算法（或稱REINFORCE算法）。

Input: a differentiable policy parameterization π_θ (a|s)  Initialize policy parameter θ  Repeat:  Generate an episode τ: S_0,A_0,R_1,…, S_(T-1), A_(T-1), R_T, following π_θ (a|s)  For each step of the episode t = 0,…,T-1:  G ← return from step t                    θ← θ+ 〖αγ〗^t G(τ_(t:T) ) ∂/∂θ logπ_θ (a_t |s_t)      End  Until θ is converged  Output: π_θ

Monte Carlo Policy Gradient算法

4. Actor Critic算法

在Monte Carlo Policy Gradient算法中，我們每次都要走完一條完整的軌跡才能得到累積獎勵，我們希望像時序差分方法一樣，可以實現單步更新。演員-評論家（actor-critic）算法是一種結合了策略梯度和時序差分的強化學習方法。

在actor-critic算法中，我們既要學習策略π_θ (s,a)，同時還要學習值函數V_ϕ (s)。

Input: a differentiable policy parameterization π_θ (a|s)  Input: a differentiable state-value parameterization V_∅ (s)  Repeat:  Initialize state s           ℷ=1    Repeat:        On state s, choose an action a=π_θ (a|s)        Execute a, get reward r and new state s^'        δ←r+γV_∅ (s^' )-V_∅ (s)        ∅←∅+βλδ ∂/(∂∅) V_∅ (s) #更新值函數的參數        θ←θ+αλδ ∂/∂θ logπ_θ (a|s) #更新策略函數的參數        λ←γλ        s←s^'    until s is terminal  until θ is converged  Output: π_θ

actor-critic算法