基于蒙特卡羅方法的理論

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

本章我們學(xué)習(xí)無模型的強(qiáng)化學(xué)習(xí)算法。

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

圖4.1 強(qiáng)化學(xué)習(xí)方法分類

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

在動態(tài)規(guī)劃的方法中，值函數(shù)的計算方法如圖4.2所示。

圖4.2值函數(shù)計算方法

動態(tài)規(guī)劃方法計算狀態(tài) s處的值函數(shù)時利用了模型，而在無模型強(qiáng)化學(xué)習(xí)中，模型是未知的。無模型的強(qiáng)化學(xué)習(xí)算法要想利用策略評估和策略改善的框架，必須采用其他的方法評估當(dāng)前策略（計算值函數(shù)）。

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

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

首先來看下什么是“經(jīng)驗”。

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

圖4.3 蒙特卡羅中的經(jīng)驗

再來看什么是“平均”。

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

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

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

，

根據(jù)大數(shù)定律：。

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

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

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

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

蒙特卡羅方法利用經(jīng)驗平均估計策略值函數(shù)。估計出值函數(shù)后，對于每個狀態(tài)s，它通過最大化動作值函數(shù)來進(jìn)行策略的改善。即

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

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

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

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

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

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

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

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

答：精心設(shè)計你的探索策略，以保證每個狀態(tài)都能被訪問到。

可是如何精心地設(shè)計探索策略？符合要求的探索策略應(yīng)該是什么樣的？

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

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

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

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

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

（1）同策略。

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

圖4.5 同策略蒙特卡羅強(qiáng)化學(xué)習(xí)方法

圖4.5中產(chǎn)生數(shù)據(jù)的策略以及評估和要改善的策略都是策略。

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

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

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

產(chǎn)生的行為。利用式子表示：滿足的任何均滿足。

利用行為策略產(chǎn)生的數(shù)據(jù)評估目標(biāo)策略需要利用重要性采樣方法。下面，我們介紹重要性采樣。

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

圖4.6 重要性采樣

如圖4.6所示，當(dāng)隨機(jī)變量z的分布非常復(fù)雜時，無法利用解析的方法產(chǎn)生用于逼近期望的樣本，這時，我們可以選用一個概率分布很簡單，很容易產(chǎn)生樣本的概率分布，比如正態(tài)分布。原來的期望可變?yōu)?/p>

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

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

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

在異策略方法中，行動策略即用來產(chǎn)生樣本的策略，所產(chǎn)生的軌跡概率分布相當(dāng)于重要性采樣中的，用來評估和改進(jìn)的策略所對應(yīng)的軌跡概率分布為，因此利用行動策略所產(chǎn)生的累積函數(shù)返回值來評估策略時，需要在累積函數(shù)返回值前面乘以重要性權(quán)重。

在目標(biāo)策略下，一次試驗的概率為

在行動策略下，相應(yīng)的試驗的概率為

因此重要性權(quán)重為

(4.10)

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

（4.11）

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

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

如圖4.8所示，t是狀態(tài)s訪問的時刻，T(t)是訪問狀態(tài)s相對應(yīng)的試驗的終止?fàn)顟B(tài)所對應(yīng)的時刻。T(s)是狀態(tài)s發(fā)生的所有時刻集合。在該例中，

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

加權(quán)重要性采樣值函數(shù)估計為

（4.12）

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

圖4.9 蒙特卡羅方法偽代碼

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

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

▌4.2 統(tǒng)計學(xué)基礎(chǔ)知識

為什么要講統(tǒng)計學(xué)？

我們先看一下統(tǒng)計學(xué)的定義。統(tǒng)計學(xué)是關(guān)于數(shù)據(jù)的科學(xué)，它提供的是一套有關(guān)數(shù)據(jù)收集、處理、分析、解釋并從數(shù)據(jù)中得出結(jié)論的方法。

聯(lián)系我們關(guān)于強(qiáng)化學(xué)習(xí)算法的概念：強(qiáng)化學(xué)習(xí)是智能體通過與環(huán)境交互產(chǎn)生數(shù)據(jù)，并把從中學(xué)到的知識內(nèi)化為自身行為的過程。學(xué)習(xí)的過程其實就是數(shù)據(jù)的處理和加工過程。尤其是值函數(shù)的估計，更是利用數(shù)據(jù)估計真實值的過程，涉及樣本均值，方差，有偏估計等，這些都是統(tǒng)計學(xué)的術(shù)語。下面做些簡單介紹。

總體：包含所研究的全部數(shù)據(jù)的集合。

樣本：從總體中抽取的一部分元素的集合。在episode強(qiáng)化學(xué)習(xí)中，一個樣本是指一幕數(shù)據(jù)。

統(tǒng)計量：用來描述樣本特征的概括性數(shù)字度量。如樣本均值，樣本方差，樣本標(biāo)準(zhǔn)差等。在強(qiáng)化學(xué)習(xí)中，我們用樣本均值衡量狀態(tài)值函數(shù)。

樣本均值：

設(shè)為樣本容量為n的隨機(jī)樣本，它們是獨立同分布的隨機(jī)變量，則樣本均值為

，

樣本均值也是隨機(jī)變量。

樣本方差：

設(shè)為樣本容量為n的隨機(jī)樣本，它們是獨立同分布的隨機(jī)變量，則樣本方差為

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

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

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

（4.13）

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

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

（4.14）

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

問題一：如何取樣本點？

答：因為是一個分布，所以可根據(jù)該分布進(jìn)行隨機(jī)采樣，得到采樣點。

問題二：如何求平均？

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

（4.15）

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

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

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

然而，當(dāng)目標(biāo)分布非常復(fù)雜或未知時，我們無法得到目標(biāo)分布的采樣點，無法得到采樣點就無法計算（4.15）式，也就無法計算平均值。這時，我們需要利用統(tǒng)計學(xué)中的各種采樣技術(shù)。

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

（1）拒絕采樣。

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

（2）重要性采樣。

重要性采樣我們已經(jīng)在4.1節(jié)做了比較詳細(xì)的介紹。

（3）MCMC方法。

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

如何通過當(dāng)前樣本點產(chǎn)生下一個樣本點，并保證如此產(chǎn)生的樣本服從原目標(biāo)分布呢？

它背后的定理是：目標(biāo)分布為馬氏鏈平穩(wěn)分布。那么，何為馬氏鏈平穩(wěn)分布？

簡單說就是該目標(biāo)分布存在一個轉(zhuǎn)移概率矩陣，且該轉(zhuǎn)移概率滿足：

是方程的唯一非負(fù)解。

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

現(xiàn)在問題轉(zhuǎn)化為尋找與目標(biāo)分布相對應(yīng)的轉(zhuǎn)移概率，那么如何構(gòu)造轉(zhuǎn)移概率呢？

轉(zhuǎn)移概率和分布應(yīng)該滿足細(xì)致平穩(wěn)條件。所謂細(xì)致平穩(wěn)條件，即

接下來，如何利用細(xì)致平衡條件構(gòu)造轉(zhuǎn)移概率呢？

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

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

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

其中被稱為接受率。

MCMC采樣算法可總結(jié)為以下步驟。

①初始化馬氏鏈初始狀態(tài)；

②對，循環(huán)以下第③~⑥步，不斷采樣；

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

④從均勻分布中采樣；

⑤如果，則接受轉(zhuǎn)移，即下一時刻的狀態(tài)；

⑥否則不接受轉(zhuǎn)移，即。

為了提高接受率，使得樣本多樣化，MCMC的第5行接受率通?？筛膶憺?img src="http://file.elecfans.com/web1/M00/4E/91/pIYBAFrB0ziAbp3BAAANlIUb5W8580.png" />，采樣這種接受率的算法稱為Metropolis- Hastings算法。

▌4.3 基于Python的編程實例

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

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

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

1．隨機(jī)策略的樣本產(chǎn)生：模擬

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

圖4.10 蒙特卡羅樣本采集

圖4.11為蒙特卡羅方法進(jìn)行策略評估的Python代碼實現(xiàn)。該函數(shù)需要說明的地方有三處。

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

第二處：正向計算每個狀態(tài)所對應(yīng)的累積函數(shù)，計算公式為。

第三處：求均值，即累積和對該狀態(tài)出現(xiàn)的次數(shù)求均值。相應(yīng)于第1節(jié)中的每次訪問蒙特卡羅方法。

圖（4.10）和圖（4.11）中的Python代碼合起來組成了基于蒙特卡羅方法的評估方法。下面，我們實現(xiàn)基于蒙特卡羅的強(qiáng)化學(xué)習(xí)算法。

如圖4.12和圖4.13所示為蒙特卡羅方法的偽代碼，其中關(guān)鍵代碼在圖4.13中實現(xiàn)。比較圖4.13和蒙特卡羅策略評估圖4.11，我們不難發(fā)現(xiàn)，蒙特卡羅強(qiáng)化學(xué)習(xí)每次迭代評估的都是策略。

圖4.11 蒙特卡羅策略評估

如圖4.12和圖4.13所示是蒙特卡羅強(qiáng)化學(xué)習(xí)算法的Python實現(xiàn)。

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

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