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

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

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

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

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

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

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

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

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

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

首先來(lái)看下什么是“經(jīng)驗(yàn)”。

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

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

再來(lái)看什么是“平均”。

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

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

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

，

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

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

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

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

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

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

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

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

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

第二，第3步完成策略評(píng)估，第4步完成策略改善。

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

我們?cè)賮?lái)討論一下探索性初始化。

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

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

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

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

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

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

若行動(dòng)策略和評(píng)估及改善的策略是同一個(gè)策略，我們稱為on-policy，可翻譯為同策略。

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

接下來(lái)我們重點(diǎn)理解這on-policy方法和off-policy方法。

（1）同策略。

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

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

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

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

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

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

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

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

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

圖4.6 重要性采樣

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

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

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

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

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

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

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

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

(4.10)

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

（4.11）

圖4.7 普通重要性采樣計(jì)算公式

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

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

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

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

（4.12）

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

圖4.9 蒙特卡羅方法偽代碼

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

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

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

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

我們先看一下統(tǒng)計(jì)學(xué)的定義。統(tǒng)計(jì)學(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í)是智能體通過(guò)與環(huán)境交互產(chǎn)生數(shù)據(jù)，并把從中學(xué)到的知識(shí)內(nèi)化為自身行為的過(guò)程。學(xué)習(xí)的過(guò)程其實(shí)就是數(shù)據(jù)的處理和加工過(guò)程。尤其是值函數(shù)的估計(jì)，更是利用數(shù)據(jù)估計(jì)真實(shí)值的過(guò)程，涉及樣本均值，方差，有偏估計(jì)等，這些都是統(tǒng)計(jì)學(xué)的術(shù)語(yǔ)。下面做些簡(jiǎn)單介紹。

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

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

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

樣本均值：

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

，

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

樣本方差：

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

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

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

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

（4.13）

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

針對(duì)這兩個(gè)問(wèn)題，我們可以將（4.13）式等價(jià)變換為

（4.14）

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

問(wèn)題一：如何取樣本點(diǎn)？

答：因?yàn)?img src="http://file.elecfans.com/web1/M00/4E/90/pIYBAFrB0yqAdh_lAAAB9xurti0548.png" />是一個(gè)分布，所以可根據(jù)該分布進(jìn)行隨機(jī)采樣，得到采樣點(diǎn)。

問(wèn)題二：如何求平均？

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

（4.15）

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

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

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

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

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

（1）拒絕采樣。

當(dāng)目標(biāo)分布非常復(fù)雜或未知時(shí)，無(wú)法利用目標(biāo)分布給出采樣點(diǎn)，那么怎么辦呢？一種方法是采用一個(gè)易于采樣的提議分布，如高斯分布進(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ù)比較高時(shí)，拒絕采樣和重要性采樣都不實(shí)用。MCMC采樣的方法原理與拒絕采樣、重要性采樣的原理有本質(zhì)的區(qū)別。拒絕采樣和重要性采樣利用提議分布產(chǎn)生樣本點(diǎn)，當(dāng)維數(shù)很高時(shí)難以找到合適的提議分布，采樣效率差。MCMC的方法則不需要提議分布，只需要一個(gè)隨機(jī)樣本點(diǎn)，下一個(gè)樣本會(huì)由當(dāng)前的隨機(jī)樣本點(diǎn)產(chǎn)生，如此循環(huán)源源不斷地產(chǎn)生很多樣本點(diǎn)。最終，這些樣本點(diǎn)服從目標(biāo)分布。

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

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

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

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

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

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

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

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

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

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

問(wèn)題是如何取呢？一個(gè)簡(jiǎn)單的想法是利用式子的對(duì)稱性，即

其中被稱為接受率。

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

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

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

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

④從均勻分布中采樣；

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

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

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

▌4.3 基于Python的編程實(shí)例

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

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

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

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

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

圖4.10 蒙特卡羅樣本采集

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

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

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

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

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

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

圖4.11 蒙特卡羅策略評(píng)估

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

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

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