編者按：本文節(jié)選自《深度學(xué)習(xí)理論與實(shí)戰(zhàn)：提高篇 》一書，原文鏈接http://fancyerii./2019/03/14/dl-book/ 。作者李理，環(huán)信人工智能研發(fā)中心vp，有十多年自然語言處理和人工智能研發(fā)經(jīng)驗(yàn)，主持研發(fā)過多款智能硬件的問答和對(duì)話系統(tǒng)，負(fù)責(zé)環(huán)信中文語義分析開放平臺(tái)和環(huán)信智能機(jī)器人的設(shè)計(jì)與研發(fā)。

以下為正文。

本文介紹蒙特卡羅方法，詳細(xì)介紹蒙特卡羅預(yù)測(cè)。接著會(huì)通過多臂老虎機(jī)和UCB來介紹探索-利用困境（exploration-exploitation dilemma），然后會(huì)介紹On-Policy和Off-Policy的蒙特卡羅預(yù)測(cè)，最后會(huì)簡(jiǎn)單的比較一下蒙特卡羅方法與動(dòng)態(tài)規(guī)劃的區(qū)別。每一個(gè)算法都會(huì)有相應(yīng)的示例代碼，通過一個(gè)簡(jiǎn)單的21點(diǎn)游戲來比較On-Policy和Off-Policy算法。

目錄

• 蒙特卡羅預(yù)測(cè) (Monte Carlo Prediction)

• 21 點(diǎn)游戲 (Blackjack)

• 蒙特卡羅預(yù)測(cè)代碼示例

  Blackjack 環(huán)境

  蒙特卡羅預(yù)測(cè)代碼

• 蒙特卡羅控制

• 多臂老虎機(jī)和 UCB

• On-Policy 蒙特卡洛控制

• On-Policy 蒙特卡羅控制代碼示例

• Off-Policy 蒙特卡羅預(yù)測(cè)

• Off-Policy 蒙特卡羅控制

• Off-Policy 蒙特卡羅控制代碼示例

• 動(dòng)態(tài)規(guī)劃和蒙特卡羅方法的比較

接下來我們介紹解決 MDP 問題的另外一種方法——蒙特卡羅方法。前面的動(dòng)態(tài)規(guī)劃方法，我們需要完全的環(huán)境動(dòng)力學(xué) ??(??′,??|??,??) 。而蒙特卡羅方法只需要經(jīng)驗(yàn) (Experience)——通過與真實(shí)環(huán)境交互或者模擬得到的狀態(tài)、行為和獎(jiǎng)勵(lì)的序列。如果從模擬學(xué)習(xí)，那么需要一個(gè)模型來建模環(huán)境，但是這個(gè)模型不需要完整的環(huán)境動(dòng)力學(xué)，它只需要能采樣即可。有的時(shí)候顯示的定義一個(gè)概率分布是很困難的，但是從中獲取樣本卻比較容易。

蒙特卡羅方法通過平均采樣的回報(bào)(return)來解決強(qiáng)化學(xué)習(xí)問題。它要求任務(wù)是 Episodic 的，并且一個(gè) Episode 進(jìn)入終止?fàn)顟B(tài)后才能開始計(jì)算（后面介紹的 Temporal Difference 不需要任務(wù)是 Episodic，即使 Episodic 的任務(wù)也不用等到一個(gè) Episode 介紹才能計(jì)算）。

蒙特卡羅預(yù)測(cè)(Monte Carlo Prediction)

首先我們來使用蒙特卡羅方法解決預(yù)測(cè)問題——給定策略，計(jì)算狀態(tài)價(jià)值函數(shù)的問題?；貞浺幌?，狀態(tài)的價(jià)值是從這個(gè)狀態(tài)開始期望的回報(bào)——也就是期望的所有未來 Reward 的打折累加。因此很直觀的想法就是從經(jīng)驗(yàn)中估計(jì)——所有經(jīng)過這個(gè)狀態(tài)的回報(bào)的平均。我們的目標(biāo)是估計(jì) ???? ，但是我們有的只是一些經(jīng)驗(yàn)的 Episode，這些 Episode 是采樣策略 ?? 得到的。也就是Episode??1,??1,??2,…,????～?? 。而 t 時(shí)刻狀態(tài)是 s 的回報(bào)是如下定義的：

????=????+??????+1+...+?????1????

而狀態(tài)價(jià)值函數(shù)是采樣策略 ?? 時(shí)期望的回報(bào)：

????(??)=????[????|????=??]

蒙特卡羅方法的思想是使用(采樣的)平均回報(bào)來估計(jì)期望回報(bào)，根據(jù)大數(shù)定律，如果采樣的次數(shù)趨于無窮，那么估計(jì)是無偏的。

比如我們要估計(jì) ????(??) ，我們用很多 Episodic 的經(jīng)驗(yàn)，這些經(jīng)驗(yàn)是使用策略 ?? 獲得的。一個(gè)Episode里 s 的每次出現(xiàn)都叫做 s 的一次 visit。當(dāng)然在一個(gè) Episode 里 s 可能多次出現(xiàn)，一種方法只考慮 s 的第一次 visit，這就叫 First-Visit 蒙特卡羅方法；而另外一種就是每次 visit 都算，這就是 Every-Visit 蒙特卡羅方法。這兩者的收斂在理論上有一些細(xì)微區(qū)別，我們這里不討論，這里我們使用 First-Visit 蒙特卡羅方法。算法偽代碼如下：

圖：First-Visit蒙特卡羅方法偽代碼

21 點(diǎn)游戲 (Blackjack)

在介紹蒙特卡羅預(yù)測(cè)的代碼之前，我們來學(xué)習(xí)一下 21 點(diǎn)游戲的玩法，并且說明為什么之前的動(dòng)態(tài)規(guī)劃很難解決這個(gè)問題，后面我們會(huì)使用蒙特卡羅方法來估計(jì)狀態(tài)的價(jià)值函數(shù)。

這個(gè)游戲有一個(gè)莊家和一個(gè)玩家(我們這里假設(shè)只有一個(gè)玩家)，有一副撲克牌，他們的目標(biāo)是使得手中所有的牌加起來盡可能大，但是不能超過 21（可能等于），最終誰的大誰獲勝，如果一樣大就是平均 (Draw)。所有的花牌 (Face，也就是J、Q、K)都算作 10，Ace 可以算 1 也可以算11。游戲開始時(shí)莊家和玩家都會(huì)發(fā)到兩張牌，莊家的一張牌是亮出來的，而玩家的兩張牌是不亮的。如果這兩張牌是 21 點(diǎn)(一個(gè) Ace 和一個(gè)花牌或者一個(gè) 10)，那么就叫一個(gè) natural，如果對(duì)手不是 natural，那就獲勝，否則是平局。如果都不是 natural，那么玩家可以有兩種選擇，繼續(xù)要牌(hit)或者不要(stick)。如果繼續(xù)要牌之后超過21點(diǎn)，就叫爆了(goes bust)，那么莊家獲勝。如果沒有爆就停止要牌，那就輪到莊家要牌，莊家如果爆了，那就玩家獲勝，否則就比最終的大小來區(qū)分勝負(fù)或者平局。

讀者可以在繼續(xù)閱讀之前上網(wǎng)“搜索21點(diǎn)在線”來試玩一下，這樣對(duì)這個(gè)游戲更加熟悉。進(jìn)入網(wǎng)站點(diǎn)擊”Try it free”可以免費(fèi)單人試玩，請(qǐng)不要賭博?。?/p>

從游戲的技巧來看（作者在學(xué)習(xí)強(qiáng)化學(xué)習(xí)之前也沒玩過，所有總結(jié)的不一定正確），玩家需要根據(jù)莊家亮的牌以及自己牌的和來決定是否繼續(xù)要牌。同樣莊家可能需要根據(jù)自己的點(diǎn)數(shù)以及玩家的牌的張數(shù)以及玩家要牌的快慢表情等(如果是跟機(jī)器玩可能就無表情了？機(jī)器能像人那樣使用表情騙人嗎？——明明分不高故意裝得很有信心，從而引導(dǎo)對(duì)手爆掉)來決定是否繼續(xù)要牌。另外就是Ace的使用，如果把 Ace 算成 11 也沒有超過 21 點(diǎn)，那么在要牌肯定不會(huì)爆掉，但是有可能分變小，比如現(xiàn)在是3+Ace，我們可以認(rèn)為是 4 點(diǎn)或者 14 點(diǎn)，但似乎都有點(diǎn)少，那么我們?cè)僖粡?。如果?，那么Ace只能算成1，否則就爆了(22)，這樣的結(jié)果就是 12 點(diǎn)。

由于有兩個(gè)角色——莊家和玩家，玩的好的 Agent 可能還要對(duì)對(duì)手建模，甚至還要利用對(duì)手的表情這樣的信息，包括用表情來騙人。這里為了簡(jiǎn)單，我們假設(shè)看不到表情，而且我們的 Agent 是玩家，而莊家使用一個(gè)固定的策略：如果得分達(dá)到或者超過 17 就 stick，否則就一直 hit。

我們可以用 MDP 來對(duì)這個(gè)游戲進(jìn)行建模，這是個(gè)有限的 MDP，而且是 Episodic 的，游戲肯定會(huì)結(jié)束。對(duì)于結(jié)束狀態(tài)，獲勝、失敗和平局，Reward分別是 +1、-1 和 0。沒有結(jié)束的狀態(tài)的Reward 都是 0,打折因子是 1。玩家的 Action 只有 stick 和 hit 兩種。狀態(tài)是玩家的牌和莊家亮出來的那種牌（這部分信息是玩家可以獲得的所有信息）。此外為了簡(jiǎn)單，我們假設(shè)發(fā)牌的牌堆是無限的（也就是每種牌都可能無限張，因此記住已經(jīng)發(fā)過的牌是沒有什么意義的，但實(shí)際的情況是有區(qū)別的，如果拿過一張Ace，那么再拿到 Ace 的概率會(huì)變化）

玩家的狀態(tài)有多少種呢？首先是自己的當(dāng)前得分，因?yàn)槿绻?dāng)前不超過11點(diǎn)，那么必然可以要牌而不爆掉，因此狀態(tài)是12-21共10種可能。而另外的信息就是莊家亮牌 ace-10 共十種（花牌和10 沒區(qū)別）。還有一點(diǎn)就是Ace，如果玩家有一個(gè)Ace而且可以把它算作 11而不爆，那么這個(gè) Ace就叫可用(Usable)的 Ace。如果 Ace 算作 11 就爆了，那么它只能算 11，也就是不能再（根據(jù)不同情況）變化了，也就不“可用”了。如果Ace可以算11，那么我們一定把它算成11，因?yàn)槿绻愠?，那么分就一定小于等于11（否則就爆了），那么我們一定會(huì)繼續(xù)要牌，這個(gè)狀態(tài)是不需要決策的，直接變成一個(gè)新的狀態(tài)。

關(guān)于“可用”的Ace算11可能有些難以理解，我們通過一個(gè)例子來說明。假設(shè)現(xiàn)在玩家手里的牌是2+3+Ace，這個(gè)Ace是“可用”的，我們現(xiàn)在的狀態(tài)是16點(diǎn)并且有一個(gè)“可用”的Ace。如果我們把Ace當(dāng)成1，那么也可以增加一個(gè)狀態(tài)，2+3+Ace，但是這個(gè)狀態(tài)我們一定會(huì)hit。所以我們不需要任務(wù)這種狀態(tài)存在。因此這個(gè)MDP一共有 10102=200個(gè)狀態(tài)。

為什么這個(gè)問題很難用動(dòng)態(tài)規(guī)劃來解決呢？因?yàn)閯?dòng)態(tài)規(guī)劃需要知道 ??(??′,??|??,??) ，比如現(xiàn)在的牌是 3+8+2，如果我們采取 hit (要牌)，我們也許還能計(jì)算變成 3+8+2+4 的概率，但是 reward 是多少呢？此外如果我們 stick，那么我們的狀態(tài)會(huì)取決于莊家的行為并且最終進(jìn)入終止?fàn)顟B(tài)，這個(gè)是很難計(jì)算的（因?yàn)槲覀儾恢罌]有亮的牌是多少）。而使用蒙特卡羅方法就很簡(jiǎn)單，我們不需要知道這些概率，只需要根據(jù)某個(gè)策略來采取行為就可以了，而環(huán)境動(dòng)力學(xué)我們只需要隨機(jī)模擬就可以了。

蒙特卡羅預(yù)測(cè)代碼示例

完整代碼在這里。

Blackjack環(huán)境

首先我們來簡(jiǎn)單的閱讀一些Blackjack環(huán)境代碼。代碼在 envs/blackjack.py 里。要點(diǎn)都在注釋里了，請(qǐng)讀者仔細(xì)閱讀注釋。

玩家的牌存在 self.player 里，而莊家的牌存在 self.dealer 里，狀態(tài)是 3 元組。3 元組的第一個(gè)是 spaces.Discrete(32)，Discrete(32) 的范圍是 0-31。游戲中沒有 0 的牌，1-31 表示玩家的牌的和，注意如果玩家到了 21 點(diǎn)肯定不會(huì)再要牌，因此即使爆了最大和也最多是 20+11=31，其實(shí)根據(jù)我們的分析 12 以下也沒必要有，不過有也沒關(guān)系。3 元組的第二個(gè)是spaces.Discrete(10)，1-10 表示莊家亮牌的點(diǎn)數(shù)。3 元組的第三個(gè)元素用 0 和 1 表示是否有可用的 Ace。

蒙特卡羅預(yù)測(cè)代碼

代碼如下，非常直觀，請(qǐng)讀者對(duì)照前面的偽代碼閱讀代碼和注釋。

最后我們測(cè)試簡(jiǎn)單的策略——不到 20 就要牌，否則就停止的策略，看看它在不同狀態(tài)下的價(jià)值函數(shù)：

如果我們運(yùn)行 jupyter notebook 的代碼，可以得到下圖的結(jié)果。可以看到經(jīng)過 500k 次迭代后價(jià)值函數(shù)非常平滑，而10k次迭代還是不平滑的，也就是誤差比較大。我們發(fā)現(xiàn)(驗(yàn)證)這個(gè)策略并不好：從圖中可以看出，只有一上來我們 (agent) 的點(diǎn)數(shù)大于 20 點(diǎn)才會(huì)贏，事實(shí)上如果我們知道莊家的策略，我們一上來到了 18 點(diǎn)就可以停止要牌了，但是我們很激進(jìn)的要超過 19 才停止，這顯然很容易爆掉。所以這個(gè)策略基本就是輸?shù)摹?/p>

圖：10k 迭代沒有 Ace

圖：10k 迭代有 Ace

圖：500k 迭代沒有 Ace

圖：500k 迭代有 Ace

前面介紹的是使用蒙特卡羅方法來求解一個(gè)策略的狀態(tài)價(jià)值函數(shù)，而行為狀態(tài)函數(shù)也是類似的算法，只不過采樣后累加的 key 是 s-a 而不是 s 而已。這里就不贅述了。

蒙特卡羅控制

和之前的策略迭代類似，我們可以用蒙特卡羅預(yù)測(cè)替代基于動(dòng)態(tài)規(guī)劃的策略評(píng)估，然后不斷提升策略。這里我們計(jì)算的是行為價(jià)值函數(shù)q(s,a)而不是狀態(tài)v(s)。

??0→????0→??1→????1→??2→...→???→??? 

這里使用的策略提升是貪婪的方法：

為什么這個(gè)方法可以提升策略呢？我們?nèi)匀豢梢允褂们懊娴牟呗蕴嵘ɡ韥碜C明：

這個(gè)算法有兩個(gè)假設(shè)：蒙特卡羅迭代的次數(shù)是無窮的（才能逼近真實(shí)的價(jià)值函數(shù)）；Exploring Start。前者我們可以忽略，因?yàn)榈銐蚨啻螖?shù)一般就夠了，而且我們之前也討論過價(jià)值迭代，我們不需要精確的估計(jì)策略的價(jià)值就可以使用價(jià)值提升了。這里的關(guān)鍵問題是 Exploring Start，初始狀態(tài) ??0 因?yàn)橛螒蚴请S機(jī)初始化的，因此所有可能的初始狀態(tài)我們都可能遍歷到，而且隨著采樣趨于無窮，每種可能初始狀態(tài)的采樣都是趨于無窮。與 ??0 對(duì)應(yīng)的 ??0 可能有很多，但是有可能我們的策略會(huì)只選擇其中一部分，那么有可能我們搜索的空間是不完整的。一種辦法就是Exploring Start，就是強(qiáng)制隨機(jī)的選擇所有可能的(??0S 和??(??0) )，但這樣有問題——我們的策略探索過 (??0,??0) 之后發(fā)現(xiàn)它不好，正常的話，它碰到??0S0后就避免 ??0 了，但是我們強(qiáng)迫它隨機(jī)(平均)的探索 (??0,??0) 和 (??0,??1) ，其實(shí)是浪費(fèi)的。這個(gè)問題我們留到后面來解決，我們首先假設(shè)是 Exploring Start 的，看看蒙特卡羅預(yù)測(cè)的偽代碼。

圖：蒙特卡羅控制算法偽代碼

通過上面的算法，我們就可以得到最優(yōu)的策略如下圖所示。

圖：使用 Exploring Start 的蒙特卡羅控制求解結(jié)果

這里學(xué)到的策略大致是：如果有可用的 Ace，那么一直要牌直到 18 點(diǎn)，這顯然是有道理的，因?yàn)槲覀冎狼f家是要到 17 點(diǎn)為止。如果沒有 Ace，如果莊家亮出來的牌很小，那么我們到 11 或者 12 點(diǎn)就停止要牌了。為什么這是最優(yōu)的？作者也不清楚，知道的讀者可以留言告訴我。

這一節(jié)我們不會(huì)實(shí)現(xiàn) Exploring Start 的算法，原因前面我們講過了，這個(gè)算法并不高效和通用，我們之后的內(nèi)容會(huì)介紹沒有 Explroing Start 的算法并用它們來解決 21 點(diǎn)游戲。

多臂老虎機(jī)和 UCB

上一節(jié)遇到的一個(gè)問題就是 Exploring Start 的問題，如果我們不“探索”所有可能的 (??0,??0) ，那么就可能“錯(cuò)過”好的策略。但是如果不“利用”以往的知識(shí)而把過多的時(shí)間浪費(fèi)在明顯不好的狀態(tài)也似乎不明智，這就需要權(quán)衡“探索”(Explore)和“利用”(Exploit)。我們下面通過一個(gè)多臂老虎機(jī)的例子來介紹一下探索和利用的矛盾。

這是很簡(jiǎn)單的一個(gè)問題，但在很多地方都有應(yīng)用，比如互聯(lián)網(wǎng)廣告，游戲廳有一個(gè) K 臂的老虎機(jī)，你可以選擇其中的一個(gè)投幣，每個(gè)手臂都是一個(gè)產(chǎn)生一個(gè)隨機(jī)的獎(jiǎng)勵(lì)，它們的均值是固定的（也有 Nonstationary 的多臂老虎機(jī)，我這里只考慮 Stationary 的）。你有 N 次投幣的機(jī)會(huì)，需要想辦法獲得最大的回報(bào) (reward)。

當(dāng)然如果我們知道這個(gè) K 個(gè)手臂的均值，那么我們每次都選擇均值最大的那個(gè)投幣，那么獲得的期望回報(bào)應(yīng)該是最大的。

可惜我們并不知道。那么我們可能上來每個(gè)都試一下，然后接下來一直選擇最大的那個(gè)。不過這樣可能也有問題，因?yàn)楠?jiǎng)勵(lì)是隨機(jī)的，所以一次回報(bào)高不代表真實(shí)的均值回報(bào)高。當(dāng)然你可以每個(gè)都試兩次，估計(jì)一下獎(jiǎng)勵(lì)的均值。如果還不放心，你可以每個(gè)都試三次，或者更多。根據(jù)大數(shù)定律，試的次數(shù)越多，估計(jì)的就越準(zhǔn)。最極端的一種做法就是每個(gè)手臂都投一樣多的次數(shù)；另外一種極端就是碰運(yùn)氣，把所有的機(jī)會(huì)都放到一個(gè)手臂上。后一種如果運(yùn)氣好是最優(yōu)的，但是很可能你抽到的是回報(bào)一般的甚至很差的手臂，期望的回報(bào)其實(shí)就是K個(gè)手臂的平均值。前一種呢？回報(bào)也是K個(gè)手臂的平均值！我們實(shí)際的做法可能是先每個(gè)手臂都試探幾次，然后估計(jì)出比較好的手臂（甚至幾個(gè)手臂），然后后面重點(diǎn)嘗試這個(gè)(些)手臂，當(dāng)然偶爾也要試試不那么好的手臂，太差的可能就不怎么去試了。但這個(gè)“度”怎么控制就是一個(gè)很復(fù)雜的問題了。這就是 exploit-explore 的困境 (dilemma)。利用之前的經(jīng)驗(yàn)，優(yōu)先“好”的手臂，這就是 exploit；嘗試目前看不那么“好”的手臂，挖掘“潛力股”，這就是 explore。

一種策略 (Policy) 的 Regret (損失)為：

不要被數(shù)學(xué)公式嚇到了，用自然語言描述就是：最理想的情況是 n 次都是均值最大的那個(gè)手臂 ( ??? )，不過我們并不知道，??????[????(??)] 是這個(gè)策略下選擇第 j 個(gè)手臂的期望。那么 R 就是期望的損失，如果我們的策略非常理想，這個(gè)策略只嘗試最好的手臂，其它不試，那么 R 就是 0。

但是這樣的理想情況存在嗎？很明顯不太可能存在（存在的一種情況是 k 個(gè)手臂的均值一樣）。那么我們的策略應(yīng)該盡量減少這個(gè)損失。Lai and Robbins 證明了這個(gè)損失的下界是 logn，也就是說不存在更好的策略，它的損失比 logn ?。ㄟ@類似于算法的大 O 表示法）。所以我們的目標(biāo)是尋找一種算法，它的損失是 logn 的。UCB 就是其中的一種算法：

每次決策之前，它都用上面的公式計(jì)算每個(gè)手臂的 UCB 值，然后選中最大的那個(gè)手臂。公式右邊的第一項(xiàng)是 exploit 項(xiàng)，是第j個(gè)手臂的平均回報(bào)的估計(jì)。這個(gè)值越大我們就越有可能再次選中它。第二項(xiàng)是 explore 項(xiàng)，???? 是第 j 個(gè)手臂的嘗試次數(shù)，???? 越小這個(gè)值就越大，也就是說嘗試次數(shù)越少的我們就越應(yīng)該多嘗試。當(dāng) ????=0 時(shí)，第二項(xiàng)為無窮大，所以這個(gè)算法會(huì)首先嘗試完所有的手臂（explore），然后才會(huì)選擇回報(bào)最大的那個(gè)(exploit)，試了之后這個(gè)手臂的平均值可能變化，而且 ???? 增加，explore 值變小，接著可能還是試最大的那個(gè)，也可能是第二大的，這要看具體情況。

我們來分析一些極端的情況，一種情況是最好的（假設(shè)下標(biāo)是 k)比第二好的要好很多，那么第一項(xiàng)占主導(dǎo)，那么穩(wěn)定了之后大部分嘗試都是最好的這個(gè)，當(dāng)然隨著 ???? 的增加 explore 項(xiàng)在減少(其它手表不變)，所以偶爾也試試其它手臂，但其它手臂的回報(bào)很少，所以很快又會(huì)回到第 k 個(gè)手臂。但是不管怎么樣，即使 n 趨于無窮大，偶爾也會(huì)嘗試一下其它的手臂的。不過因?yàn)榇蟛糠謺r(shí)間都在第 k 個(gè)手臂上，所以這個(gè)策略還是可以的。

另一種極端就是k個(gè)手臂都差不多（比如都是一樣的回報(bào)），那么 exploit 項(xiàng)大家都差不多，起決定作用的就是 explore 項(xiàng)，那么就是平均的嘗試這些手臂，由于 k 各手臂回報(bào)差不多，所以這個(gè)策略也還不錯(cuò)。處于中間的情況就是有一些好的和一些差的，那么根據(jù)分析，大部分嘗試都是在好的手臂上，偶爾也會(huì)試一試差的，所以策略的結(jié)果也不會(huì)太差。

當(dāng)然這個(gè)只是簡(jiǎn)單的直覺的分析，事實(shí)上可以證明這個(gè)算法的 regret 是 logn 的，具體證明細(xì)節(jié)請(qǐng)參看論文Finite-time Analysis of the Multiarmed Bandit Problem。

On-Policy蒙特卡洛控制

我們?cè)倩氐角懊婷商乜蹇刂频膯栴}，需要 Exploring Start，有什么辦法可以避免嗎？從理論上講，如果蒙特卡洛實(shí)驗(yàn)的次數(shù)趨于無窮，那么所有的 Action 我們也需要嘗試無窮次才能保證無偏的估計(jì)。我們這里先介紹 On-Policy 的方法，它的基本思想和 UCB 類似，把大多數(shù)時(shí)間花在當(dāng)前策略認(rèn)為好的 Action 上，但是也要花一些時(shí)間探索所有其它的 Action。為什么叫 On-Policy 呢？這是和 Off-Policy 相對(duì)的，On-Policy 指的是生成 Episode 的策略和最后使用來決策的策略是同一個(gè)策略；而 Off-Policy 有兩個(gè)策略：一個(gè)策略用于生成 Episode，而另一個(gè)策略是最終用了決策的策略。

On-Policy 的策略通常是 soft 的，也就是  ?s∈S, a∈A(s), π(a|s)>0。因此 soft 的策略在狀態(tài) s 時(shí)對(duì)于所有的 Action 都有一定的概率去嘗試，但是最終會(huì)有某個(gè)(些) Action 的概率會(huì)比較大從而形成比較固定的策略。為什么蒙特卡羅控制要求策略是 soft 而之前的動(dòng)態(tài)規(guī)劃不需要呢（還記得之前的策略提升都是用到固定的貪婪的策略嗎）？

圖：動(dòng)態(tài)規(guī)劃的 backup 圖

圖：蒙特卡羅方法的 backup 圖

我們看一下這兩種方法的 backup 圖，從圖中我們可以看出，在動(dòng)態(tài)規(guī)劃的時(shí)候，我們是“遍歷”一個(gè)狀態(tài)所有 Action，以及 Action 的所有新狀態(tài)。通過這種類似廣度優(yōu)先的方式遞歸的方式，我們遍歷了所有空間。而蒙特卡羅方法我們是通過采樣的方法一次訪問一條“路徑”，如果策略是固定的，那么我們每次都是訪問相同的路徑。

這一節(jié)我們會(huì)介紹 ε-貪婪算法，它在大部分情況下(1-ε的概率)會(huì)使用貪婪的策略選擇 a 使得 q(s,a) 最大，但是也會(huì)有 ε 的概率隨機(jī)的選擇策略。因此對(duì)于“最優(yōu)”行為的概率是 1-ε+ε/|A|（因?yàn)殡S機(jī)也可能隨機(jī)到最優(yōu)的行為），而其它行為的概率是 ε/|A|。算法的偽代碼如下：

圖：On-Policy蒙特卡洛控制算法

假設(shè)策略 ?? 是一個(gè) ε-soft 的策略，它的行為價(jià)值函數(shù)是 ????(??,??) ，而 ??′ 是對(duì) ???? 進(jìn)行 ε- 貪婪之后得到的新策略（當(dāng)然它也是一個(gè) ε-soft 的策略），那么這個(gè)新策略 ??′ 相對(duì)于 ?? 是有提升的（新的策略比老的好）。下面我們來證明一下， ?s∈S，我們有：

這個(gè)證明難點(diǎn)是第二行到第三行的不等式，它利用了這樣一個(gè)結(jié)論：n個(gè)數(shù)的“線性組合”小于等于最大的那個(gè)數(shù)。所謂的線性組合就是n個(gè)數(shù)分別乘以n個(gè)系數(shù)在加起來，這n個(gè)系數(shù)是大于等于0小于等于1并且和為1的。我們以兩個(gè)數(shù)為例，假設(shè)??1≤??2 ：

同樣三個(gè)數(shù)的情況可以用類似的方法證明。我們?cè)倩剡^頭來看上面的不等式，假設(shè)狀態(tài)s下有n種行為，那么第三行就是n個(gè)數(shù)(????(??,??)aπ(s,a))的線性組合，因?yàn)檫@n個(gè)數(shù)的系數(shù)都是大于0小于1的，而且其和是1：

我們?cè)诿商乜_方法（包括后面的TD）使用的不是狀態(tài)價(jià)值函數(shù) V(s) 而是行為價(jià)值函數(shù) Q(s,a)，為什么呢？我們首先回顧一下 GPI，參考下圖。假設(shè)使用 V(s)，我們首先有個(gè)初始的策略 ?? ，我們用蒙特卡羅預(yù)測(cè)來估計(jì) ????(??) ，然后我們使用 ε- 貪婪獲得一個(gè)更好的策略，然后再估計(jì)這個(gè)新的策略的價(jià)值函數(shù)，不斷的迭代。這里我們需要根據(jù) V(s) 來計(jì)算這個(gè) ε-貪婪的策略如下：

如下圖所示，蒙特卡羅控制是這樣優(yōu)化的，注意和動(dòng)態(tài)規(guī)劃不同，蒙特卡羅控制一上來 是有 Q，然后做 ε- 貪婪的提升，然后計(jì)算新的 Q，不過因?yàn)槊商乜_是采樣的近似，所以圖中的蒙特卡羅的預(yù)測(cè)不是精確的預(yù)測(cè) ????(??,??) ，而是它的近似，所以圖中的線沒有接近上端。

圖：蒙特卡羅控制的 GPI

On-Policy 蒙特卡羅控制代碼示例

代碼在這里。首先我們定義函數(shù) make_epsilon_greedy_policy，它的輸入是一個(gè) Q 函數(shù)和epsilon，輸出一個(gè)實(shí)現(xiàn) ε- 貪婪的策略的函數(shù)。

然后是實(shí)現(xiàn)ε-貪婪策略的蒙特卡羅控制函數(shù)mc_control_epsilon_greedy：

注意和偽代碼比，我們沒有“顯式”定義新策略??′π′，而是把當(dāng)前策略定義為Q(s,a)的一個(gè)函數(shù)policy = make_epsilon_greedy_policy(Q, epsilon, env.action_space.n)，因此Q(s,a)發(fā)生變化時(shí)，對(duì)于的函數(shù)就會(huì)發(fā)生變化。

運(yùn)行后我們把V(s)畫出來，如下圖所示。

圖：無Ace時(shí)最佳值函數(shù)

圖：有Ace時(shí)最佳值函數(shù)

我們可以看出，如果一上來手上的牌就大于 18，我們最優(yōu)的勝率是大于 0 的(當(dāng)然也會(huì)可能輸，因?yàn)榍f家大于 17 就停止要牌，仍然有一定概率比我們大)。

Off-Policy蒙特卡羅預(yù)測(cè)

前面的 ε- 貪婪策略可以解決 Exploring Start的問題，但是帶來一個(gè)新的問題，它永遠(yuǎn)只能學(xué)到 ε-soft 的策略，用于決策的時(shí)候還去“探索”其實(shí)是不好的。本節(jié)我們介紹 Off-Policy 的蒙特卡羅預(yù)測(cè)，和前面的 On-Policy 策略相比，Off-Policy 有兩個(gè)不同策略：目標(biāo)策略 (target policy)和行為策略 (behavior policy)。目標(biāo)策略就是我們解決問題需要學(xué)習(xí)的策略；而行為策略是用來生成 Episode 的策略。如果目標(biāo)策略和行為策略相同，那就是 On-Policy 策略了。

本節(jié)我們解決預(yù)測(cè)問題，假設(shè)目標(biāo)策略和行為策略都已知的情況下計(jì)算其價(jià)值函數(shù)。假設(shè)目標(biāo)策略是 ?? ，而行為策略是 b，我們的目的是根據(jù) b 生成的 Episode 采樣來計(jì)算 ????(??) 或????(??,??) 。為了通過 b 生成的 Episode 能夠用來估計(jì) ?? ，我們要求如果 ??(??|??)>0 則 ??(??|??)>0 ，這叫做 b 是?? 的 coverage。為什么要有 coverage 的要求？因?yàn)槿绻覀円烙?jì)的策略 ??(??|??)>0 ，而??(??|??)=0 ，那么就不可能有 Episode 會(huì)在狀態(tài) s 是采取行為 a，那么就無法估計(jì) ??(??|??) 了。

coverage 的另外一種說法就是：如果 ??(??|??)=0 那么一定有 ??(??|??)=0 。因此策略 b 一定是隨機(jī)的策略，為什么？因?yàn)?b 如果是確定的策略，對(duì)于任何狀態(tài) ???? ，只有一個(gè)???? 使得??(????|????)=1 ，其余的都是 0。因?yàn)?b 是 ?? 的 coverage，所以除了 j，其余所有的 ??(????|????)=0 ，因此只有 ??(????|????)>0 ，因此它必須是 ??(????|????)=1 ，這樣 ?? 和 b 就是相同的策略，這顯然不是 Off-Policy 策略。

因此在 Off-Policy 控制里，行為策略通常是隨機(jī)的，它會(huì)“探索”，而目標(biāo)策略通常是固定的貪心的策略，它更多的是“利用”。幾乎所有的 Off-Policy 策略都使用重要性采樣 (Importance Sampling) 方法，這是根據(jù)一個(gè)概率分布來估計(jì)另外一個(gè)不同的概率分布的常見方法。我們希望估計(jì)的是策略 ?? ，而實(shí)際采樣用的是 b 生成的 Episode。因此我們?cè)谟?jì)算平均的回報(bào)時(shí)需要對(duì)它乘以一個(gè)采樣重要性比例 (importance-sampling ratio) 來加權(quán)。通俗的解釋就是：??(??|??) 的概率是0.2，而??(??|??)=0.4 ，那么我們需要乘以 2。給定初始狀態(tài) ???? 和策略 ?? ，再給定任意狀態(tài)-行為軌跡 (trajectory)，我們可以就是其條件概率——在給定策略下出現(xiàn)這個(gè)軌跡的概率。

雖然軌跡的概率是和 MDP 的轉(zhuǎn)移概率 ??(??′|??,??) 有關(guān)，但是兩個(gè)策略的重要性比例是和它無關(guān)的，它只跟兩個(gè)策略相關(guān)。

為了介紹后面的算法，我們先介紹一個(gè)數(shù)學(xué)記號(hào)，請(qǐng)讀者在繼續(xù)閱讀之前熟悉這些記號(hào)。首先我們把很多的 Episode 使用統(tǒng)一的時(shí)刻來標(biāo)志，也就是把所有的 Episode 順序的串起來。比如有兩個(gè)Episode，??1 是 105 個(gè)時(shí)間單位，??2 是 50 個(gè)。那么我們用 1 到 155 來標(biāo)識(shí)這過兩個(gè)Episode。??2 的第一個(gè)時(shí)刻是 106，??2 的最后一個(gè)時(shí)刻是 155。我們介紹一個(gè)記號(hào) τ(s)，如果是 every-visit 的方法，它代表狀態(tài) s 在同樣時(shí)間里的下標(biāo)集合；如果是 first-visit 的方法，那么每個(gè) Episode 只算第一次的出現(xiàn)。舉例來說：比如兩個(gè) Episode 是 {??1,??1,??2,??3} 和{??2,??3,??2,??1} 。如果是 every-visit 的方法，則 ??(??1)={1,2,8} ；如果是 first-visit 方法，則??(??1)={1,8} 。然后是記號(hào)T(t)，它表示 t 時(shí)刻之后的第一個(gè)結(jié)束時(shí)刻。對(duì)于上面的例子 T(2)=4, T(5)=8，表示第 2 個(gè)時(shí)刻之后的第一個(gè)結(jié)束時(shí)刻是 4，第 5 個(gè)時(shí)刻之后的第一個(gè)結(jié)束時(shí)刻是 8。其實(shí)就是這個(gè)時(shí)刻所在 Episode 的結(jié)束時(shí)刻。再就是記號(hào) G(t)，它表示從 t 時(shí)刻到 T(t) 時(shí)刻的回報(bào) (Return)，也就是 t 時(shí)刻的回報(bào)。因此記號(hào) {??(??)}??∈??(??) 表示所有這些 Episode 里狀態(tài) s 的回報(bào)的集合。{????:??(??)?1}??∈??(??) 表示與之對(duì)應(yīng)的采樣重要性比例。

為了估計(jì) ????(??) ，我們可以簡(jiǎn)單的用重要性比例加權(quán)平均回報(bào)：

這種平均方法加普通重要性采樣 (ordinary importance sampling)，另外一種叫加權(quán)重要性采樣 (weighted importance sampling):

普通重要性采樣是無偏的估計(jì)，而加權(quán)重要性采樣是有偏的估計(jì)；前者的方差很大，而后者較小。Off-Policy預(yù)測(cè)的偽代碼如下：

圖：Off-Policy蒙特卡羅預(yù)測(cè)

Off-Policy 蒙特卡羅控制

有了 Off-Policy 預(yù)測(cè)之后，我們很容易得到 Off-Policy 蒙特卡羅控制。偽代碼如下：

圖：Off-Policy 蒙特卡羅控制

注意這個(gè)代碼和上面代碼最后兩行的差別。首先因?yàn)槲覀兊牟呗??? 是確定的策略，因此只有一個(gè)Action 的概率是 1，其余的是 0。因此如果狀態(tài)是 ???? ，那么策略 ?? 會(huì)選擇 Q 最大的那個(gè) a，也就是 ??????max????(????,??) ，如果 ????≠??(????) ，則說明 ??(????|????)=0 ，因此和上面算法的條件一樣，可以退出 for 循環(huán)，否則就更新 W，如果執(zhí)行到最后一行代碼，說明 ??(????|????)=1 ，所以分子是 1。

Off-Policy蒙特卡羅控制代碼示例

完整代碼在這里。

核心的函數(shù)是 mc_control_importance_sampling，代碼和偽代碼幾乎一樣，請(qǐng)讀者參考偽代碼閱讀：

運(yùn)行后我們把V(s)畫出來，如下圖所示。

圖：Off-Policy算法無Ace時(shí)最佳值函數(shù)

圖：Off-Policy算法有Ace時(shí)最佳值函數(shù)

我們可以看出結(jié)果和前面的 On-Policy 算法差不多，但是運(yùn)算速度會(huì)快很多，讀者可以自行比較一下。

動(dòng)態(tài)規(guī)劃和蒙特卡羅方法的比較

• 是否有模型

動(dòng)態(tài)規(guī)劃需要模型 p(s’,r|s,a)；而蒙特卡羅方法不需要，它只需要能獲得采樣的 Episode 就行。因此動(dòng)態(tài)規(guī)劃也稱為基于模型的 (model based) 方法；而蒙特卡羅方法被稱為無模型的 (model free) 方法?；谀Ｐ偷姆椒ㄐ枰拉h(huán)境的動(dòng)力系統(tǒng)，有些問題我們很容易知道環(huán)境動(dòng)力系統(tǒng)，但是還有很多問題我們無法直接獲得。如果我們還想使用動(dòng)態(tài)規(guī)劃，我們就必須用一個(gè)模型來建模環(huán)境，這本身就是一個(gè)很復(fù)雜的問題。比如前面我們的21點(diǎn)游戲，想完全建模其動(dòng)力系統(tǒng)是很困難的。

• bootstrapping

動(dòng)態(tài)規(guī)劃是有 bootstrapping 的，??(??) 和 ??(??,??) 都需要先有估計(jì)(初始值)，然后通過迭代的方法不斷改進(jìn)這個(gè)估計(jì)。

• online/offline

蒙特卡羅方法是 offline 的，需要一個(gè) Episode 結(jié)束之后才能計(jì)算回報(bào)。等介紹過 TD(λ) 之后，與 constant-α MC (一種后面我們會(huì)介紹的蒙特卡羅方法)等價(jià)的 TD(1) 可以實(shí)現(xiàn) online 計(jì)算。這樣如果不是 Episode 的任務(wù)（比如用于不結(jié)束狀態(tài)的連續(xù)的任務(wù)），或者有些任務(wù)如果策略不對(duì)可能永遠(yuǎn)無法結(jié)束，比如后面我們會(huì)介紹的 Windy Gridworld。

注意動(dòng)態(tài)規(guī)劃并沒有 online/offline 只說，因?yàn)樗皇遣蓸拥姆椒ā＿@是蒙特卡羅方法的一個(gè)缺點(diǎn)，后面的時(shí)間差分學(xué)習(xí)能解決這個(gè)問題。

• full/sampling backup

如下圖所示，動(dòng)態(tài)規(guī)劃會(huì)”遍歷”所有的子樹，而蒙特卡羅方法只采樣一條路徑。

圖：蒙特卡羅算法只采樣一條路徑

圖：動(dòng)態(tài)規(guī)劃會(huì)遞歸的遍歷所有子樹

本文經(jīng)授權(quán)發(fā)布，不代表36氪立場(chǎng)。如若轉(zhuǎn)載請(qǐng)聯(lián)系原作者。