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

以下為正文。

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

目錄

• 蒙特卡羅預測 (Monte Carlo Prediction)

• 21 點游戲 (Blackjack)

• 蒙特卡羅預測代碼示例

  Blackjack 環(huán)境

  蒙特卡羅預測代碼

• 蒙特卡羅控制

• 多臂老虎機和 UCB

• On-Policy 蒙特卡洛控制

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

• Off-Policy 蒙特卡羅預測

• Off-Policy 蒙特卡羅控制

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

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

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

蒙特卡羅方法通過平均采樣的回報(return)來解決強化學習問題。它要求任務是 Episodic 的，并且一個 Episode 進入終止狀態(tài)后才能開始計算（后面介紹的 Temporal Difference 不需要任務是 Episodic，即使 Episodic 的任務也不用等到一個 Episode 介紹才能計算）。

蒙特卡羅預測(Monte Carlo Prediction)

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

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

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

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

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

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

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

21 點游戲 (Blackjack)

在介紹蒙特卡羅預測的代碼之前，我們來學習一下 21 點游戲的玩法，并且說明為什么之前的動態(tài)規(guī)劃很難解決這個問題，后面我們會使用蒙特卡羅方法來估計狀態(tài)的價值函數。

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

讀者可以在繼續(xù)閱讀之前上網“搜索21點在線”來試玩一下，這樣對這個游戲更加熟悉。進入網站點擊”Try it free”可以免費單人試玩，請不要賭博??！

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

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

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

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

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

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

蒙特卡羅預測代碼示例

完整代碼在這里。

Blackjack環(huán)境

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

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

蒙特卡羅預測代碼

代碼如下，非常直觀，請讀者對照前面的偽代碼閱讀代碼和注釋。

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

如果我們運行 jupyter notebook 的代碼，可以得到下圖的結果?？梢钥吹浇涍^ 500k 次迭代后價值函數非常平滑，而10k次迭代還是不平滑的，也就是誤差比較大。我們發(fā)現(驗證)這個策略并不好：從圖中可以看出，只有一上來我們 (agent) 的點數大于 20 點才會贏，事實上如果我們知道莊家的策略，我們一上來到了 18 點就可以停止要牌了，但是我們很激進的要超過 19 才停止，這顯然很容易爆掉。所以這個策略基本就是輸的。

圖：10k 迭代沒有 Ace

圖：10k 迭代有 Ace

圖：500k 迭代沒有 Ace

圖：500k 迭代有 Ace

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

蒙特卡羅控制

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

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

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

為什么這個方法可以提升策略呢？我們仍然可以使用前面的策略提升定理來證明：

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

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

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

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

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

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

多臂老虎機和 UCB

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

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

當然如果我們知道這個 K 個手臂的均值，那么我們每次都選擇均值最大的那個投幣，那么獲得的期望回報應該是最大的。

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

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

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

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

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

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

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

當然這個只是簡單的直覺的分析，事實上可以證明這個算法的 regret 是 logn 的，具體證明細節(jié)請參看論文Finite-time Analysis of the Multiarmed Bandit Problem。

On-Policy蒙特卡洛控制

我們再回到前面蒙特卡洛控制的問題，需要 Exploring Start，有什么辦法可以避免嗎？從理論上講，如果蒙特卡洛實驗的次數趨于無窮，那么所有的 Action 我們也需要嘗試無窮次才能保證無偏的估計。我們這里先介紹 On-Policy 的方法，它的基本思想和 UCB 類似，把大多數時間花在當前策略認為好的 Action 上，但是也要花一些時間探索所有其它的 Action。為什么叫 On-Policy 呢？這是和 Off-Policy 相對的，On-Policy 指的是生成 Episode 的策略和最后使用來決策的策略是同一個策略；而 Off-Policy 有兩個策略：一個策略用于生成 Episode，而另一個策略是最終用了決策的策略。

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

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

圖：蒙特卡羅方法的 backup 圖

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

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

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

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

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

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

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

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

圖：蒙特卡羅控制的 GPI

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

代碼在這里。首先我們定義函數 make_epsilon_greedy_policy，它的輸入是一個 Q 函數和epsilon，輸出一個實現 ε- 貪婪的策略的函數。

然后是實現ε-貪婪策略的蒙特卡羅控制函數mc_control_epsilon_greedy：

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

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

圖：無Ace時最佳值函數

圖：有Ace時最佳值函數

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

Off-Policy蒙特卡羅預測

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

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

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

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

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

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

為了估計 ????(??) ，我們可以簡單的用重要性比例加權平均回報：

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

普通重要性采樣是無偏的估計，而加權重要性采樣是有偏的估計；前者的方差很大，而后者較小。Off-Policy預測的偽代碼如下：

圖：Off-Policy蒙特卡羅預測

Off-Policy 蒙特卡羅控制

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

圖：Off-Policy 蒙特卡羅控制

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

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

完整代碼在這里。

核心的函數是 mc_control_importance_sampling，代碼和偽代碼幾乎一樣，請讀者參考偽代碼閱讀：

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

圖：Off-Policy算法無Ace時最佳值函數

圖：Off-Policy算法有Ace時最佳值函數

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

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

• 是否有模型

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

• bootstrapping

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

• online/offline

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

注意動態(tài)規(guī)劃并沒有 online/offline 只說，因為它不是采樣的方法。這是蒙特卡羅方法的一個缺點，后面的時間差分學習能解決這個問題。

• full/sampling backup

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

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

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

本文經授權發(fā)布，不代表36氪立場。如若轉載請聯系原作者。