▌4.1 基于蒙特卡羅方法的理論

本章我們學習無模型的強化學習算法。

強化學習算法的精髓之一是解決無模型的馬爾科夫決策問題。如圖4.1所示，無模型的強化學習算法主要包括蒙特卡羅方法和時間差分方法。本章我們闡述蒙特卡羅方法。

圖4.1 強化學習方法分類

學習蒙特卡羅方法之前，我們先梳理強化學習的研究思路。首先，強化學習問題可以納入馬爾科夫決策過程中，這方面的知識已在第2章闡述。在已知模型的情況下，可以利用動態規劃的方法（動態規劃的思想是無模型強化學習研究的根源，因此重點闡述）解決馬爾科夫決策過程。第3章，闡述了兩種動態規劃的方法：策略迭代和值迭代。這兩種方法可以用廣義策略迭代方法統一：即先進行策略評估，也就是計算當前策略所對應的值函數，再利用值函數改進當前策略。無模型的強化學習基本思想也是如此，即：策略評估和策略改善。

在動態規劃的方法中，值函數的計算方法如圖4.2所示。

圖4.2值函數計算方法

動態規劃方法計算狀態 s處的值函數時利用了模型，而在無模型強化學習中，模型是未知的。無模型的強化學習算法要想利用策略評估和策略改善的框架，必須采用其他的方法評估當前策略（計算值函數）。

我們回到值函數最原始的定義公式（參見第2章）：

狀態值函數和行為值函數的計算實際上是計算返回值的期望（參見圖4.2），動態規劃的方法是利用模型計算該期望。在沒有模型時，我們可以采用蒙特卡羅的方法計算該期望，即利用隨機樣本估計期望。在計算值函數時，蒙特卡羅方法是利用經驗平均代替隨機變量的期望。此處，我們要理解兩個詞：經驗和平均。

首先來看下什么是“經驗”。

當要評估智能體的當前策略時，我們可以利用策略產生很多次試驗，每次試驗都是從任意的初始狀態開始直到終止，比如一次試驗（an episode）為計算一次試驗中狀態處的折扣回報返回值為，那么“經驗”就是指利用該策略做很多次試驗，產生很多幕數據（這里的一幕是一次試驗的意思），如圖4.3所示。

圖4.3 蒙特卡羅中的經驗

再來看什么是“平均”。

這個概念很簡單，平均就是求均值。不過，利用蒙特卡羅方法求狀態處的值函數時，又可以分為第一次訪問蒙特卡羅方法和每次訪問蒙特卡羅方法。

第一次訪問蒙特卡羅方法是指在計算狀態處的值函數時，只利用每次試驗中第一次訪問到狀態s時的返回值。如圖4.3中第一次試驗所示，計算狀態s處的均值時只利用，因此第一次訪問蒙特卡羅方法的計算公式為

每次訪問蒙特卡羅方法是指在計算狀態s處的值函數時，利用所有訪問到狀態s時的回報返回值，即

，

根據大數定律：。

由于智能體與環境交互的模型是未知的，蒙特卡羅方法是利用經驗平均來估計值函數，而能否得到正確的值函數，則取決于經驗——因此，如何獲得充足的經驗是無模型強化學習的核心所在。

在動態規劃方法中，為了保證值函數的收斂性，算法會逐個掃描狀態空間中的狀態。無模型的方法充分評估策略值函數的前提是每個狀態都能被訪問到，因此，在蒙特卡洛方法中必須采用一定的方法保證每個狀態都能被訪問到，方法之一是探索性初始化。

探索性初始化是指每個狀態都有一定的幾率作為初始狀態。在學習基于探索性初始化的蒙特卡羅方法前，我們還需要先了解策略改善方法，以及便于進行迭代計算的平均方法。下面我們分別介紹蒙特卡羅策略改善方法和可遞增計算均值的方法。

（1）蒙特卡羅策略改善。

蒙特卡羅方法利用經驗平均估計策略值函數。估計出值函數后，對于每個狀態s，它通過最大化動作值函數來進行策略的改善。即

（2）遞增計算均值的方法如（4.4）式所示。

如圖4.4所示是探索性初始化蒙特卡羅方法的偽代碼，需要注意的是：

第一，第2步中，每次試驗的初始狀態和動作都是隨機的，以保證每個狀態行為對都有機會作為初始狀態。在評估狀態行為值函數時，需要對每次試驗中所有的狀態行為對進行估計；

第二，第3步完成策略評估，第4步完成策略改善。

圖4.4探索性初始化蒙特卡羅方法

我們再來討論一下探索性初始化。

探索性初始化在迭代每一幕時，初始狀態是隨機分配的，這樣可以保證迭代過程中每個狀態行為對都能被選中。它蘊含著一個假設：假設所有的動作都被無限頻繁選中。對于這個假設，有時很難成立，或無法完全保證。

我們會問，如何保證在初始狀態不變的同時，又能保證每個狀態行為對可以被訪問到？

答：精心設計你的探索策略，以保證每個狀態都能被訪問到。

可是如何精心地設計探索策略？符合要求的探索策略應該是什么樣的？

答：策略必須是溫和的，即對所有的狀態s和a滿足：。也就是說，溫和的探索策略是指在任意狀態下，采用動作集中每個動作的概率都大于零。典型的溫和策略是策略：

根據探索策略（行動策略）和評估的策略是否為同一個策略，蒙特卡羅方法又分為on-policy和off-policy兩種方法。

若行動策略和評估及改善的策略是同一個策略，我們稱為on-policy，可翻譯為同策略。

若行動策略和評估及改善的策略是不同的策略，我們稱為off-policy，可翻譯為異策略。

接下來我們重點理解這on-policy方法和off-policy方法。

（1）同策略。

同策略（on-policy）是指產生數據的策略與評估和要改善的策略是同一個策略。比如，要產生數據的策略和評估及要改善的策略都是策略。其偽代碼如圖4.5所示。

圖4.5 同策略蒙特卡羅強化學習方法

圖4.5中產生數據的策略以及評估和要改善的策略都是策略。

（2）異策略。異策略（off-policy）是指產生數據的策略與評估和改善的策略不是同一個策略。我們用表示用來評估和改善的策略，用表示產生樣本數據的策略。

異策略可以保證充分的探索性。例如用來評估和改善的策略是貪婪策略，用于產生數據的探索性策略為探索性策略，如策略。

用于異策略的目標策略和行動策略并非任意選擇的，而是必須滿足一定的條件。這個條件是覆蓋性條件，即行動策略產生的行為覆蓋或包含目標策略

產生的行為。利用式子表示：滿足的任何均滿足。

利用行為策略產生的數據評估目標策略需要利用重要性采樣方法。下面，我們介紹重要性采樣。

我們用圖4.6描述重要性采樣的原理。重要性采樣來源于求期望，如圖4.6所示：

圖4.6 重要性采樣

如圖4.6所示，當隨機變量z的分布非常復雜時，無法利用解析的方法產生用于逼近期望的樣本，這時，我們可以選用一個概率分布很簡單，很容易產生樣本的概率分布，比如正態分布。原來的期望可變為

定義重要性權重：，普通的重要性采樣求積分如方程（4.7）所示為

由式（4.7）可知，基于重要性采樣的積分估計為無偏估計，即估計的期望值等于真實的期望。但是，基于重要性采樣的積分估計的方差無窮大。這是因為原來的被積函數乘了一個重要性權重，改變了被積函數的形狀及分布。盡管被積函數的均值沒有發生變化，但方差明顯發生改變。

在重要性采樣中，使用的采樣概率分布與原概率分布越接近，方差越小。然而，被積函數的概率分布往往很難求得、或很奇怪，因此沒有與之相似的簡單采樣概率分布，如果使用分布差別很大的采樣概率對原概率分布進行采樣，方差會趨近于無窮大。一種減小重要性采樣積分方差的方法是采用加權重要性采樣：

在異策略方法中，行動策略即用來產生樣本的策略，所產生的軌跡概率分布相當于重要性采樣中的，用來評估和改進的策略所對應的軌跡概率分布為，因此利用行動策略所產生的累積函數返回值來評估策略時，需要在累積函數返回值前面乘以重要性權重。

在目標策略下，一次試驗的概率為

在行動策略下，相應的試驗的概率為

因此重要性權重為

(4.10)

普通重要性采樣的值函數估計如圖4.7所示：

（4.11）

圖4.7 普通重要性采樣計算公式

現在舉例說明公式（4.11）中各個符號的具體含義。

如圖4.8所示，t是狀態s訪問的時刻，T(t)是訪問狀態s相對應的試驗的終止狀態所對應的時刻。T(s)是狀態s發生的所有時刻集合。在該例中，

圖4.8 重要性采樣公式舉例解釋

加權重要性采樣值函數估計為

（4.12）

最后，我們給出異策略每次訪問蒙特卡羅算法的偽代碼，如圖4.9所示。

圖4.9 蒙特卡羅方法偽代碼

注意：此處的軟策略為策略，需要改善的策略為貪婪策略。

總結一下：本節重點講解了如何利用MC的方法估計值函數。與基于動態規劃的方法相比，基于MC的方法只是在值函數估計上有所不同，在整個框架上則是相同的，即評估當前策略，再利用學到的值函數進行策略改善。本節需要重點理解on-policy 和off-policy的概念，并學會利用重要性采樣來評估目標策略的值函數。

▌4.2 統計學基礎知識

為什么要講統計學？

我們先看一下統計學的定義。統計學是關于數據的科學，它提供的是一套有關數據收集、處理、分析、解釋并從數據中得出結論的方法。

聯系我們關于強化學習算法的概念：強化學習是智能體通過與環境交互產生數據，并把從中學到的知識內化為自身行為的過程。學習的過程其實就是數據的處理和加工過程。尤其是值函數的估計，更是利用數據估計真實值的過程，涉及樣本均值，方差，有偏估計等，這些都是統計學的術語。下面做些簡單介紹。

總體：包含所研究的全部數據的集合。

樣本：從總體中抽取的一部分元素的集合。在episode強化學習中，一個樣本是指一幕數據。

統計量：用來描述樣本特征的概括性數字度量。如樣本均值，樣本方差，樣本標準差等。在強化學習中，我們用樣本均值衡量狀態值函數。

樣本均值：

設為樣本容量為n的隨機樣本，它們是獨立同分布的隨機變量，則樣本均值為

，

樣本均值也是隨機變量。

樣本方差：

設為樣本容量為n的隨機樣本，它們是獨立同分布的隨機變量，則樣本方差為

無偏估計：若樣本的統計量等于總體的統計量，則稱該樣本的統計量所對應的值為無偏估計。如總體的均值和方差分別為和時，若，則和稱為無偏估計。

蒙特卡羅積分與隨機采樣方法[3]：

蒙特卡羅方法常用來計算函數的積分，如計算下式積分。

（4.13）

如果f(x)的函數形式非常復雜，則（4.13）式無法應用解析的形式計算。這時，我們只能利用數值的方法計算。利用數值的方法計算（4.13）式的積分需要取很多樣本點，計算f(x)在這些樣本點處的值，并對這些值求平均。那么問題來了：如何取這些樣本點？如何對樣本點處的函數值求平均呢？

針對這兩個問題，我們可以將（4.13）式等價變換為

（4.14）

其中為已知的分布。將（4.13）式變換為等價的（4.14）式后，我們就可以回答上面的兩個問題了。

問題一：如何取樣本點？

答：因為是一個分布，所以可根據該分布進行隨機采樣，得到采樣點。

問題二：如何求平均？

答：根據分布采樣后，在樣本點處計算，并對所有樣本點處的值求均值：

（4.15）

以上就是利用蒙特卡羅方法計算積分的原理。

我們再來看看期望的計算。設X表示隨機變量，且服從概率分布，計算函數的期望。函數的期望計算公式為

利用蒙特卡羅的方法計算該式很簡單，即不斷地從分布中采樣，然后對這些取平均便可近似的期望。這也是4.1節中估計值函數的方法。只不過那里的一個樣本是一個episode，每個episode 產生一個狀態值函數，蒙特卡羅的方法估計狀態值函數就是把這些樣本點處的狀態值函數加起來求平均，也就是經驗平均。

然而，當目標分布非常復雜或未知時，我們無法得到目標分布的采樣點，無法得到采樣點就無法計算（4.15）式，也就無法計算平均值。這時，我們需要利用統計學中的各種采樣技術。

常用的采樣方法有兩類。第一類是指定一個已知的概率分布用于采樣，指定的采樣概率分布稱為提議分布。這類采樣方法包括拒絕采樣和重要性采樣。此類方法只適用于低維情況，針對高維情況常采用第二類采樣方法，即馬爾科夫鏈蒙特卡羅的方法。該方法的基本原理是從平穩分布為的馬爾科夫鏈中產生非獨立樣本。下面我們簡單介紹這些方法。

（1）拒絕采樣。

當目標分布非常復雜或未知時，無法利用目標分布給出采樣點，那么怎么辦呢？一種方法是采用一個易于采樣的提議分布，如高斯分布進行采樣。可是，如果用提議分布采樣，那么所產生的樣本服從提議分布而不服從目標分布。所以，為了得到符合目標分布的樣本，需要加工由提議分布得到的樣本。接收符合目標分布的樣本，拒絕不符合目標分布的樣本。

（2）重要性采樣。

重要性采樣我們已經在4.1節做了比較詳細的介紹。

（3）MCMC方法。

MCMC方法被視為二十世紀Top 10的算法。MCMC方法全稱為馬爾科夫鏈蒙特卡羅方法。當采樣空間的維數比較高時，拒絕采樣和重要性采樣都不實用。MCMC采樣的方法原理與拒絕采樣、重要性采樣的原理有本質的區別。拒絕采樣和重要性采樣利用提議分布產生樣本點，當維數很高時難以找到合適的提議分布，采樣效率差。MCMC的方法則不需要提議分布，只需要一個隨機樣本點，下一個樣本會由當前的隨機樣本點產生，如此循環源源不斷地產生很多樣本點。最終，這些樣本點服從目標分布。

如何通過當前樣本點產生下一個樣本點，并保證如此產生的樣本服從原目標分布呢？

它背后的定理是：目標分布為馬氏鏈平穩分布。那么，何為馬氏鏈平穩分布？

簡單說就是該目標分布存在一個轉移概率矩陣，且該轉移概率滿足：

是方程的唯一非負解。

當轉移矩陣滿足上述條件時，從任意初始分布出發，經過一段時間迭代，分布都會收斂到目標分布。因此，假設我們已經知道了滿足條件的狀態轉移概率矩陣，那么我們只要給出任意一個初始狀態，則可以得到一個轉移序列。如果該馬氏鏈在第n步已經收斂到目標分布，那么我們就得到了服從目標分布的樣本。

現在問題轉化為尋找與目標分布相對應的轉移概率，那么如何構造轉移概率呢？

轉移概率和分布應該滿足細致平穩條件。所謂細致平穩條件，即

接下來，如何利用細致平衡條件構造轉移概率呢？

我們可以這樣考慮：加入已有的一個轉移矩陣為Q的馬氏鏈，這樣任意選的轉移矩陣通常情況下并不滿足細致平衡條件，也就是

既然不滿足，我們就可以改造，使之滿足。改造的方法是加入一項使得

問題是如何取呢？一個簡單的想法是利用式子的對稱性，即

其中被稱為接受率。

MCMC采樣算法可總結為以下步驟。

①初始化馬氏鏈初始狀態；

②對，循環以下第③~⑥步，不斷采樣；

③第t時刻的馬氏鏈狀態為，采樣；

④從均勻分布中采樣；

⑤如果，則接受轉移，即下一時刻的狀態；

⑥否則不接受轉移，即。

為了提高接受率，使得樣本多樣化，MCMC的第5行接受率通常可改寫為，采樣這種接受率的算法稱為Metropolis- Hastings算法。

▌4.3 基于Python的編程實例

在這一節中，我們用Python和蒙特卡羅方法解決機器人找金幣的問題。

蒙特卡羅方法解決的是無模型的強化學習問題，基本思想是利用經驗平均代替隨機變量的期望。因此，利用蒙特卡羅方法評估策略應該包括兩個過程：模擬和平均。

模擬就是產生采樣數據，平均則是根據數據得到值函數。下面我們以利用蒙特卡羅方法估計隨機策略的值函數為例做詳細說明。

1．隨機策略的樣本產生：模擬

圖4.10為蒙特卡羅方法的采樣過程。該采樣函數包括兩個大循環，第一個大循環表示采樣多個樣本序列，第二個循環表示產生具體的每個樣本序列。需要注意的是，每個樣本序列的初始狀態都是隨機的。因為評估的是隨機均勻分布的策略，所以在采樣的時候，動作都是根據隨機函數產生的。每個樣本序列包括狀態序列，動作序列和回報序列。

圖4.10 蒙特卡羅樣本采集

圖4.11為蒙特卡羅方法進行策略評估的Python代碼實現。該函數需要說明的地方有三處。

第一處：對于每個模擬序列逆向計算該序列的初始狀態處的累積回報，也就是說從序列的最后一個狀態開始往前依次計算，最終得到初始狀態處的累積回報為，計算公式為

第二處：正向計算每個狀態所對應的累積函數，計算公式為。

第三處：求均值，即累積和對該狀態出現的次數求均值。相應于第1節中的每次訪問蒙特卡羅方法。

圖（4.10）和圖（4.11）中的Python代碼合起來組成了基于蒙特卡羅方法的評估方法。下面，我們實現基于蒙特卡羅的強化學習算法。

如圖4.12和圖4.13所示為蒙特卡羅方法的偽代碼，其中關鍵代碼在圖4.13中實現。比較圖4.13和蒙特卡羅策略評估圖4.11，我們不難發現，蒙特卡羅強化學習每次迭代評估的都是策略。

圖4.11 蒙特卡羅策略評估

如圖4.12和圖4.13所示是蒙特卡羅強化學習算法的Python實現。

圖4.12 蒙特卡羅方法偽代碼及Python代碼

圖4.13 蒙特卡羅方法偽代碼及Python代碼