《強(qiáng)化學(xué)習(xí)理論與應(yīng)用》蒙特卡洛法

目錄

蒙特卡洛法的基本概念3

蒙特卡洛評估5.2

蒙特卡洛預(yù)測4

蒙特卡洛控制5

小結(jié)

5.15.25.35.45.52023/10/91動態(tài)規(guī)劃法：基于模型的MDP問題求解方法；當(dāng)環(huán)境模型已知，動態(tài)規(guī)劃法無需環(huán)境采樣，只需通過迭代計(jì)算，就可以得到問題的最優(yōu)策略；無模型強(qiáng)化學(xué)習(xí)狀態(tài)轉(zhuǎn)移概率是未知的，無法利用動態(tài)規(guī)劃方法求解值函數(shù)。通過值函數(shù)的原始定義來求解無模型強(qiáng)化學(xué)習(xí)問題：引言2023/10/92經(jīng)驗(yàn)方法通過大量采樣獲取數(shù)據(jù)來進(jìn)行學(xué)習(xí)

MC方法

MC正是基于經(jīng)驗(yàn)方法，在環(huán)境模型未知的情況下，采用時(shí)間步有限的、完整的情節(jié)，根據(jù)經(jīng)驗(yàn)進(jìn)行學(xué)習(xí)，并通過平均采樣回報(bào)來解決強(qiáng)化學(xué)習(xí)問題。5.1蒙特卡洛法的基本概念（1）2023/10/935.1.1MC的核心要素

5.1蒙特卡洛法的基本概念（2）經(jīng)驗(yàn)：

從環(huán)境交互中獲得的

序列，它是情節(jié)的集合，也就是樣本集。真實(shí)經(jīng)驗(yàn)?zāi)M經(jīng)驗(yàn)

模擬經(jīng)驗(yàn)是通過模擬模型得到的，這里的模擬模型只需生成狀態(tài)轉(zhuǎn)移的一些樣本，無需像DP那樣需要環(huán)境中所有可能的狀態(tài)轉(zhuǎn)移概率。2023/10/94情節(jié)：

一段經(jīng)驗(yàn)可以分為多個(gè)情節(jié)，每一情節(jié)都是一個(gè)完整的

，即必有終止?fàn)顟B(tài)，形如：

經(jīng)常與情節(jié)混淆的是軌跡，軌跡可以不存在終止?fàn)顟B(tài)，形如：2023/10/955.1蒙特卡洛法的基本概念（3）

完整回報(bào)與目標(biāo)值：

因?yàn)橹挥械竭_(dá)終止?fàn)顟B(tài)才能計(jì)算回報(bào)，所以將情節(jié)的回報(bào)

稱為完整回報(bào)，也稱為MC的目標(biāo)值。2023/10/965.1蒙特卡洛法的基本概念（4）5.1.2MC的特點(diǎn)

5.1蒙特卡洛法的基本概念（5）無需知道狀態(tài)轉(zhuǎn)移概率

，直接從環(huán)境中進(jìn)行采樣來處理無模型任務(wù)；利用情節(jié)進(jìn)行學(xué)習(xí)，并采用情節(jié)到情節(jié)（episode-by-episode）的離線學(xué)習(xí)（off-line）方式來求解最優(yōu)策略。DP和后續(xù)介紹的時(shí)序差分算法則采用步到步（step-by-step）的在線學(xué)習(xí)（on-line）方式來求解最優(yōu)策略；2023/10/975.1蒙特卡洛法的基本概念（6）離線學(xué)習(xí)：先完整地采集數(shù)據(jù)，然后以離線方式優(yōu)化學(xué)習(xí)目標(biāo)；在線學(xué)習(xí)：邊采集數(shù)據(jù)邊優(yōu)化學(xué)習(xí)目標(biāo)。

MC是一個(gè)非平穩(wěn)問題，其表現(xiàn)在：某個(gè)狀態(tài)采取動作之后的回報(bào)，取決于在同一個(gè)情節(jié)內(nèi)后續(xù)狀態(tài)所采取的動作，而這些動作通常是不確定的。如果說DP是在MDP模型中計(jì)算值函數(shù)，那么MC就是學(xué)習(xí)值函數(shù)。2023/10/985.1蒙特卡洛法的基本概念（7）在MC中，對每個(gè)狀態(tài)的值函數(shù)估計(jì)都是獨(dú)立的。對狀態(tài)的值函數(shù)估計(jì)不依賴于其他任何狀態(tài)，這也說明了MC不是自舉過程；

MC在估計(jì)每個(gè)狀態(tài)的值函數(shù)時(shí)，其計(jì)算成本與狀態(tài)總數(shù)無直接關(guān)，因?yàn)樗恍枰?jì)算指定狀態(tài)的回報(bào)，無需考慮所有的狀態(tài)。2023/10/995.1蒙特卡洛法的基本概念（8）實(shí)際上，MC泛指任何包含大量隨機(jī)成分的估計(jì)方法，通常利用采樣數(shù)據(jù)來估算某一事件的發(fā)生概率。在數(shù)學(xué)領(lǐng)域中，它的應(yīng)用可以用例5.1來說明。例5.1在邊長為1米的正方形內(nèi)構(gòu)建一個(gè)扇形，利用扇形面積計(jì)算公式，可以計(jì)算出?，F(xiàn)在利用MC方法計(jì)算的面積。均勻地向內(nèi)撒

個(gè)黃豆，經(jīng)統(tǒng)計(jì)得知：有個(gè)黃豆在內(nèi)部，那么有，即，且

越大，計(jì)算得到的面積越精確。2023/10/9105.1蒙特卡洛法的基本概念（9）在程序中分別設(shè)置

、

和共3組數(shù)據(jù)，統(tǒng)計(jì)結(jié)果如表所示。由實(shí)驗(yàn)數(shù)據(jù)可知，當(dāng)值越大時(shí)，得到的扇形面積越精確，即接近0.785。由此獲得的MC采樣公式為：2023/10/911目錄

蒙特卡洛法的基本概念3

蒙特卡洛評估5.2

蒙特卡洛預(yù)測4

蒙特卡洛控制5

小結(jié)

5.15.25.35.45.52023/10/912根據(jù)狀態(tài)值函數(shù)的初始定義，MC預(yù)測算法以情節(jié)中初始狀態(tài)

的回報(bào)期望作為其值函數(shù)的估計(jì)值，對策略進(jìn)行評估。在求解狀態(tài)

的值函數(shù)時(shí)，先利用策略產(chǎn)生

個(gè)情節(jié)，然后計(jì)算每個(gè)情節(jié)中狀態(tài)

的折扣回報(bào)：

這里，表示在第

個(gè)情節(jié)中，從

時(shí)刻到終點(diǎn)時(shí)刻

的回報(bào)。該回報(bào)是基于某一策略下的狀態(tài)值函數(shù)的無偏估計(jì)（由于是真實(shí)獲得的，所以屬于無偏估計(jì)，但是存在高方差）。

5.2蒙特卡洛法預(yù)測（1）2023/10/913

在MC中，每個(gè)回報(bào)都是對獨(dú)立同分布的估計(jì)，通過對這些折扣回報(bào)求期望（均值）來評估策略：

在一組采樣（一個(gè)情節(jié)）中狀態(tài)

可能多次出現(xiàn)，以更新圖的方式表示，如下圖所示。對同一情節(jié)中重復(fù)出現(xiàn)的狀態(tài)

，有如下兩種處理方法：

5.2蒙特卡洛法預(yù)測（2）2023/10/914首次訪問（first-visit）：在對狀態(tài)

的回報(bào)進(jìn)行估計(jì)時(shí)，只對每個(gè)情節(jié)中第1次訪問到狀態(tài)

的回報(bào)值作以統(tǒng)計(jì)：

每次訪問（every-visit）：在對狀態(tài)

的回報(bào)進(jìn)行估計(jì)時(shí)，對所有訪問到狀態(tài)

的回報(bào)值都作以統(tǒng)計(jì)：

5.2蒙特卡洛法預(yù)測（3）2023/10/915其中，表示第

個(gè)情節(jié)，

表示第

次訪問到狀態(tài)

；表示狀態(tài)

被訪問過的總次數(shù)。根據(jù)大數(shù)定理，當(dāng)MC采集的樣本足夠多時(shí)，計(jì)算出來的狀態(tài)值函數(shù)估計(jì)值就會逼近真實(shí)狀態(tài)值函數(shù)。

5.2蒙特卡洛法預(yù)測（4）從右圖中可以看出，MC更新圖只顯示在當(dāng)前情節(jié)中，采樣得到的狀態(tài)轉(zhuǎn)移，且包

含了到該情節(jié)結(jié)束為止的所有狀態(tài)轉(zhuǎn)移；而DP更新圖顯示在當(dāng)前狀態(tài)下所有可能的狀態(tài)轉(zhuǎn)移，且僅包含單步轉(zhuǎn)移。

2023/10/9165.2蒙特卡洛法預(yù)測（5）基于首次訪問的MC預(yù)測算法，如算法5.1所示。2023/10/9175.2蒙特卡洛法預(yù)測（6）例5.2以例3.1掃地機(jī)器人為例。給出機(jī)器人經(jīng)過下圖的每條軌跡后，相對應(yīng)的狀態(tài)值。如圖所示，選取了5個(gè)經(jīng)過狀態(tài)16的情節(jié)，5個(gè)情節(jié)依次設(shè)置為情節(jié)1、情節(jié)2、情節(jié)3、情節(jié)4和情節(jié)5。2023/10/9185.2蒙特卡洛法預(yù)測（7）情節(jié)1：情節(jié)2：情節(jié)3：2023/10/9195.2蒙特卡洛法預(yù)測（8）也可以直接利用關(guān)于回報(bào)的定義計(jì)算：情節(jié)4：2023/10/9205.2蒙特卡洛法預(yù)測（9）2023/10/921情節(jié)5：

首次訪問狀態(tài)16：第2次訪問狀態(tài)16：5.2蒙特卡洛法預(yù)測（10）在情節(jié)5中狀態(tài)16被訪問了兩次。利用首次訪問的MC預(yù)測方法時(shí)，計(jì)算累計(jì)回報(bào)值只使用該情節(jié)中第一次訪問狀態(tài)16的回報(bào)，即。所以使用這5條情節(jié)，利用首次訪問方式計(jì)算狀態(tài)16的估計(jì)值為：而利用每次訪問方式計(jì)算狀態(tài)16的估計(jì)值為：

2023/10/922目錄

蒙特卡洛法的基本概念3

蒙特卡洛評估5.2

蒙特卡洛預(yù)測4

蒙特卡洛控制5

小結(jié)

5.15.25.35.45.52023/10/923

5.3蒙特卡洛評估（1）由最優(yōu)策略的兩種求解方式可知，利用動作值函數(shù)是一種更適合于無模型求解最優(yōu)策略的方法。將估計(jì)狀態(tài)值函數(shù)的MC預(yù)測問題轉(zhuǎn)化為估計(jì)動作值函數(shù)的MC評估問題，對狀態(tài)-動作對進(jìn)行訪問而不是對狀態(tài)

進(jìn)行訪問。根據(jù)策略進(jìn)行采樣，記錄情節(jié)中的回報(bào)，并對的回報(bào)求期望，得到策略下的動作值函數(shù)的估計(jì)值。MC評估方法對每一組狀態(tài)-動作對的評估方法也分為首次訪問和每次訪問兩種。

2023/10/924

5.3蒙特卡洛評估（2）為了保證算法中值函數(shù)和策略的收斂性，DP算法會對所有狀態(tài)進(jìn)行逐個(gè)掃描。在MC評估方法中，根據(jù)動作值函數(shù)計(jì)算的性質(zhì)，必須保證每組狀態(tài)-動作對都能被訪問到，即得到所有的回報(bào)值，才能保證樣本的完備性。針對該問題，我們設(shè)定探索始點(diǎn)（exploringstarts）：每一組都有非0的概率作為情節(jié)的起始點(diǎn)。2023/10/925

5.3蒙特卡洛評估（3）實(shí)際上，探索始點(diǎn)在實(shí)際應(yīng)用中是難以達(dá)成的，需要配合無限采樣才能保證樣本的完整性。通常的做法是采用那些在每個(gè)狀態(tài)下所有動作都有非0概率被選中的隨機(jī)策略。這里我們先從簡單的滿足探索始點(diǎn)的MC控制算法開始討論，然后引出基于同策略和異策略方法的MC控制算法。2023/10/926目錄

蒙特卡洛法的基本概念3

蒙特卡洛評估5.2

蒙特卡洛預(yù)測4

蒙特卡洛控制5

小結(jié)

5.15.25.35.45.52023/10/9275.4蒙特卡洛控制（1）

預(yù)測和控制的思想是相同的，它們都是基于帶獎(jiǎng)勵(lì)過程的馬爾可夫鏈來對目標(biāo)進(jìn)行更新，其區(qū)別在于：MC預(yù)測：求解在給定策略下，狀態(tài)

的狀態(tài)值函數(shù)。MC控制：基于GPI，包含策略評估和策略改進(jìn)兩部分。這里的策略評估是求解在給定策略下，狀態(tài)-動作對的動作值函數(shù)。其策略迭代過程如下所示：2023/10/9285.4蒙特卡洛控制（2）

當(dāng)采樣過程滿足探索始點(diǎn)時(shí)，對任意策略，MC算法都可以準(zhǔn)確地計(jì)算出指定的動作值函數(shù)。一旦得到了動作值函數(shù)，可以直接利用基于動作值函數(shù)的貪心策略來對策略進(jìn)行更新。此時(shí)對于所有，任意策略以及更新后的都將滿足策略改進(jìn)原理：5.4.1基于探索始點(diǎn)的蒙特卡洛控制

2023/10/9295.4蒙特卡洛控制（3）

上式表明，采用基于動作值函數(shù)的貪心策略，改進(jìn)后的策略一定優(yōu)于或等價(jià)于。這一過程保證了MC控制算法能夠收斂到最優(yōu)動作值函數(shù)和最優(yōu)策略。

無窮采樣假設(shè)，使用基于探索始點(diǎn)的蒙特卡洛（MonteCarlobasedonExploringStarts，MCES）控制算法來進(jìn)行規(guī)避。MCES控制算法通過情節(jié)到情節(jié)的方式對策略進(jìn)行評估和更新，每一情節(jié)結(jié)束后，使用觀測到的回報(bào)進(jìn)行策略評估，然后在該情節(jié)訪問到的每一個(gè)狀態(tài)上進(jìn)行策略改進(jìn)。2023/10/9305.4蒙特卡洛控制（4）

MC控制算法主要分為以下兩個(gè)階段：策略評估：根據(jù)當(dāng)前策略進(jìn)行采樣，得到一條完整情節(jié)，估計(jì)每一組的動作值函數(shù)；策略改進(jìn)：基于動作值函數(shù)，直接利用貪心策略對策略進(jìn)行改進(jìn)。2023/10/9315.4蒙特卡洛控制（5）算法5.2：基于探索始點(diǎn)的蒙特卡洛控制——MCES算法。2023/10/9325.4

蒙特卡洛控制（6）雖然可以通過探索性始點(diǎn)來彌補(bǔ)無法訪問到所有狀態(tài)-動作對的缺陷，但這一方法并不合理，唯一普遍的解決方法就是保證Agent能夠持續(xù)不斷地選擇所有可能的動作，這也稱為無探索始點(diǎn)方法，該方法分為同策略方法與異策略方法兩種。2023/10/9335.4蒙特卡洛控制（7）在同策略MC控制算法中，策略通常是軟性的（soft），即對于所有的、，均有。策略都必須逐漸變得貪心，以逐漸逼近一個(gè)確定性策略。同策略方法使用-貪心策略（-greedypolicy），其公式為：5.4.2同策略蒙特卡洛控制2023/10/9345.4蒙特卡洛控制（8）GPI并沒有要求必須使用貪心策略，只要求采用的優(yōu)化方法逐漸逼近貪心策略即可。根據(jù)策略改進(jìn)定理，對于一個(gè)-軟性策略，任何根據(jù)生成的-貪心策略都是對其所做的改進(jìn)。下面對-軟性策略改進(jìn)定理進(jìn)行證明。

2023/10/9355.4蒙特卡洛控制（9）假設(shè)為-greedy策略，對任意狀態(tài)有：所以，根據(jù)策略改進(jìn)定理，。2023/10/9365.4蒙特卡洛控制（10）基于同策略首次訪問-greedy策略的MC算法，如算法5.3所示。2023/10/9375.4蒙特卡洛控制（11）2023/10/9385.4蒙特卡洛控制（12）例5.3利用同策略首次訪問

-貪心策略MC算法，給出掃地機(jī)器人的最優(yōu)策略。掃地機(jī)器人通過多次實(shí)驗(yàn)，不斷的更新

值，最終收斂到最優(yōu)策略，并得到一條回報(bào)最大的路徑。同策略蒙特卡洛首次訪問控制算法中，對動作值函數(shù)

的計(jì)算，也是通過對每一情節(jié)中第一次訪問到的該狀態(tài)-動作對的回報(bào)進(jìn)行平均，然后選擇使該動作值函數(shù)

最大的動作，作為該狀態(tài)下應(yīng)該采取的動作。2023/10/9395.4蒙特卡洛控制（13）表5.1基于同策略首次訪問MC算法的掃地機(jī)器人最優(yōu)策略計(jì)算過程（）2023/10/9405.4蒙特卡洛控制（14）2023/10/9415.4蒙特卡洛控制（15）另外，常用-柔性策略公式還有以下4種：隨機(jī)貪心策略：基于隨機(jī)數(shù)，用一個(gè)較小的閾值來控制策略的探索性：當(dāng)隨機(jī)數(shù)大于時(shí)，選擇最大動作值函數(shù)對應(yīng)的動作；當(dāng)隨機(jī)數(shù)小于或等于時(shí)，隨機(jī)地選擇動作。2023/10/9425.4蒙特卡洛控制（15）Boltzmann探索：定義時(shí)刻選擇動作的概率，其公式為：2023/10/943其中，表示溫度參數(shù)，控制探索的隨機(jī)性。當(dāng)時(shí)，選擇貪心動作；當(dāng)時(shí)，隨機(jī)選擇動作。5.4蒙特卡洛控制（16）最大置信上界法：在選擇動作時(shí)，一方面要考慮其估計(jì)值最大，另外一方面也要考慮探索長時(shí)間沒有訪問到的動作，以免錯(cuò)過更好的動作。2023/10/944其中，表示的自然對數(shù)，表示當(dāng)前狀態(tài)，在時(shí)刻之前動作被選擇的次數(shù)。是一個(gè)大于0的數(shù)，用來控制探索的程度。如果，則動作就被認(rèn)為是當(dāng)前狀態(tài)下滿足最大化條件的動作。5.4

蒙特卡洛控制（17）樂觀初始值方法。給值函數(shù)賦予一個(gè)比實(shí)際價(jià)值大得多些的樂觀初始值。這種樂觀估計(jì)會鼓勵(lì)不斷地選取收益接近估計(jì)值的動作。但無論選取哪一種動作，收益都比最初始的估計(jì)值小，因此在估計(jì)值收斂之前，所有動作都會被多次嘗試。既使每一次都按照貪心法選擇動作，系統(tǒng)也會進(jìn)行大量的探索。2023/10/9455.4蒙特卡洛控制（18）異策略MC方法：常用的無探索始點(diǎn)蒙特卡洛方法。重要性采樣，因?yàn)閹缀跛械漠惒呗苑椒ǘ际褂玫街匾圆蓸?。重要性采樣：利用來自其他分布的樣本，估?jì)當(dāng)前某種分布期望值的通用方法。5.4.3異策略與重要性采樣2023/10/9465.4蒙特卡洛控制（19）重要性采樣以離散型數(shù)據(jù)為例，假設(shè)是一個(gè)服從分布的函數(shù)，其期望公式為：2023/10/947其中，表示

服從分布，也可記為。通常情況下，可以在服從分布的離散型數(shù)據(jù)中進(jìn)行采樣，得到樣本集，則在分布下的期望為：

2023/10/95.4蒙特卡洛控制（20）

在有些任務(wù)中，為了得到分布函數(shù)，需要采集大量的樣本才能擬合原期望，或存在部分極端、無法代表分布的樣本。針對這些任務(wù)，在服從分布的數(shù)據(jù)中采樣存在2023/10/948困難的問題，根據(jù)重要性采樣原則，可以將該任務(wù)轉(zhuǎn)化為從服從簡單分布的數(shù)據(jù)中進(jìn)行采樣，得到的樣本集為。此時(shí)在分布下的期望為：其中，表示函數(shù)在分布下的期望。

5.4蒙特卡洛控制（21）根據(jù)MC采樣思想，在采樣數(shù)據(jù)足夠多時(shí)，在分布下的期望近似為：2023/10/949這里為重要性采樣比率（importance-samplingratio），有。由此，我們將求解在分布下的函數(shù)期望問題，轉(zhuǎn)換為求解包含重要性采樣比率的在分布下的函數(shù)期望。5.4蒙特卡洛控制（22）2023/10/950重要性采樣的特點(diǎn)：

與具有相同的定義域。采樣概率分布與原概率分布越接近，方差越小；反之，方差越大。通常采用加權(quán)重要性采樣來減小方差，即用替換

：普通重要性采樣的函數(shù)估計(jì)為：

加權(quán)重要性采樣的函數(shù)估計(jì)為：5.4蒙特卡洛控制（23）基于重要性采樣的異策略方法異策略方法目標(biāo)策略和行為策略是不同的。這里假設(shè)目標(biāo)策略為，行為策略為

，所有情節(jié)都遵循行為策略

，并利用行為策略

產(chǎn)生的情節(jié)來評估目標(biāo)策略。這樣需要滿足覆蓋條件，即目標(biāo)策略中的所有動作都會在行為策略中被執(zhí)行。也就是說，所有滿足的均有。根據(jù)軌跡在兩種策略下產(chǎn)生的相對概率來計(jì)算目標(biāo)策略的回報(bào)值，該相對概率稱為重要性采樣比率，2023/10/9515.4蒙特卡洛控制（24）記為。以作為初始狀態(tài)，其采樣得到的后續(xù)狀態(tài)-動作對序列為：。在任意目標(biāo)策略下發(fā)生的概率如下所示：在任意行為策略

下發(fā)生后的概率如下所示：2023/10/9525.4蒙特卡洛控制（25）其中，

表示狀態(tài)轉(zhuǎn)移概率，是該情節(jié)的終止時(shí)刻。注意：公式累乘符號的上標(biāo)為，因?yàn)樽詈笠粋€(gè)動作發(fā)生在時(shí)刻。表示該情節(jié)服從目標(biāo)策略。這樣某一情節(jié)在目標(biāo)策略和行為策略下發(fā)生的相對概率為：2023/10/9535.4蒙特卡洛控制（26）其中，表示某一情節(jié)從

到

時(shí)刻的重要性采樣比率，也就是基于兩種策略采取動作序列的相對概率，與重要性采樣比率相對應(yīng)。從上式可以看出，盡管情節(jié)的形成依賴于狀態(tài)轉(zhuǎn)移概率

，但由于分子分母中同時(shí)存在

，可以被消去，所以重要性采樣比率僅僅依賴于兩個(gè)策略，而與狀態(tài)轉(zhuǎn)移概率無關(guān)。行為策略中的回報(bào)期望是不能直接用于評估目標(biāo)策略的。根據(jù)重要性采樣原則，需要使用比例系數(shù)對回報(bào)進(jìn)行調(diào)整，使其矯正為正確的期望值：2023/10/9545.4蒙特卡洛控制（27）假設(shè)遵循行為策略

采樣得到了一系列情節(jié)。為方便計(jì)算，將這些情節(jié)首位相連，并按時(shí)刻狀態(tài)出現(xiàn)的順序進(jìn)行編號。例如第1個(gè)情節(jié)在時(shí)刻100狀態(tài)結(jié)束，則第2個(gè)情節(jié)的編號就在時(shí)刻101狀態(tài)開始，以此類推。在每次訪問方法中，存儲所有訪問過狀態(tài)

的時(shí)間步，記為，并以表示狀態(tài)

被訪問過的總次數(shù)。在首次訪問方法中，只包括這些情節(jié)中第一次訪問到

的時(shí)間步。此外，以表示在

時(shí)刻后的第一個(gè)終止時(shí)刻，以表示從

到時(shí)刻的回報(bào)，2023/10/9555.4蒙特卡洛控制（28）以表示回報(bào)的重要性采樣比率（在增量式計(jì)算中常簡寫為）。根據(jù)重要性采樣思想，狀態(tài)值函數(shù)的計(jì)算方法分為兩種：普通重要性采樣（ordinaryimportancesampling）將回報(bào)按照權(quán)重縮放后進(jìn)行平均。屬于無偏估計(jì)，具有方差無界的特點(diǎn)。其計(jì)算如下所示：2023/10/9565.4

蒙特卡洛控制（29）加權(quán)重要性采樣（weightedimportancesampling）將回報(bào)進(jìn)行加權(quán)平均。屬于有偏估計(jì)，具有方差較小的特點(diǎn)。其計(jì)算如下所示：分母為0時(shí)，。兩種方法的主要差異在于偏差和方差的不同。2023/10/9575.4蒙特卡洛控制（30）普通重要性采樣的偏差與方差采用某種方法估計(jì)值函數(shù)，當(dāng)估計(jì)結(jié)果的期望恒為時(shí)，該方法是無偏估計(jì)，但其方差可能是無界的。當(dāng)時(shí)，表明該軌跡在目標(biāo)策略下發(fā)生的可能性是行為策略下的10倍，，根據(jù)普通重要性采樣得到的估計(jì)值是回報(bào)值的10倍，這就存在了高方差。

2023/10/9585.4蒙特卡洛控制（31）加權(quán)重要性采樣的偏差與方差由于比例系數(shù)被消去，所以加權(quán)重要性采樣的估計(jì)值就等于回報(bào)值，與重要性采樣比例無關(guān)。因?yàn)樵摶貓?bào)值是僅有的觀測結(jié)果，所以是一個(gè)合理的估計(jì)，但它的期望是2023/10/959而非，所以該方法屬于有偏估計(jì)。此外，由于加權(quán)估計(jì)中回報(bào)的最大權(quán)重是1，所以其方差會明顯低于普通估計(jì)。由于重要性采樣比率涉及到所有狀態(tài)的轉(zhuǎn)移概率，因此有很高的方差，從這一點(diǎn)來說，MC算法不太適合于處理異策略問題。異策略MC只有理論研究價(jià)值，實(shí)際應(yīng)用的效果并不明顯，難以獲得最優(yōu)動作值函數(shù)。5.4蒙特卡洛控制（32）

經(jīng)典的增量式計(jì)算

假設(shè)有一組實(shí)數(shù)數(shù)據(jù)，其形式為：。令為第個(gè)數(shù)據(jù)的數(shù)值，為前個(gè)數(shù)據(jù)的平均值，即有：

根據(jù)數(shù)學(xué)中的迭代思想，引入增量式計(jì)算方法，以簡化求解過程。增量式推導(dǎo)如下所示：

2023/10/9605.4蒙特卡洛控制（33）

根據(jù)上式的規(guī)律，構(gòu)建經(jīng)典增量式公式：

將Target稱為目標(biāo)值，從單次更新過程來看，OldEstimate是朝著Target移動的。從整個(gè)更新結(jié)果來看，OldEstimate是朝著真實(shí)目標(biāo)值移動的。在自舉方法中，Target也常被稱為自舉估計(jì)值。增量式計(jì)算方法是一種基于樣本Target的隨機(jī)近似過程，拆分了均值求解過程，減少了存儲消耗，簡化了計(jì)算過程。

2023/10/9615.4蒙特卡洛控制（34）

MC的增量式同策略MC：使用傳統(tǒng)增量式計(jì)算公式，不涉及重要性采樣，

時(shí)刻狀態(tài)的狀態(tài)值函數(shù)更新遞歸式為：公式右側(cè)的為歷史狀態(tài)值函數(shù)的均值，表示估計(jì)值，即OldEstimate；2023/10/962為

時(shí)刻的回報(bào)，表示目標(biāo)值，即Target；為步長，當(dāng)是固定步長時(shí)，該式稱為恒定-MC。5.4蒙特卡洛控制（35）異策略MC：假設(shè)已經(jīng)獲得了狀態(tài)

的回報(bào)序列，每個(gè)回報(bào)都對應(yīng)一個(gè)隨機(jī)重要性權(quán)重。當(dāng)獲得新的回報(bào)值時(shí)，希望以增量式的方式，在狀態(tài)值函數(shù)估計(jì)值的基礎(chǔ)上估計(jì)。在普通重要性采樣中，僅僅需要對回