本文來自加州大學洛杉磯分校計算機科學專業的本科生OneRaynyDay，他喜歡用清晰易懂且不失幽默的方式講述機器學習概念，尤其是其中的數學概念。相比作者這個“數學怪胎”，小編能力有限，只能盡力去計算驗證和補齊文中未介紹的概念。如果內容有誤，歡迎在留言中指出。

蒙特卡洛是座賭城

目錄

簡介

蒙特卡洛動作值

初識蒙特卡洛

蒙特卡洛控制

Monte Carlo ES On-Policy：? -Greedy Policies Off-policy：重要性抽樣

Python里的On-Policy Model

在強化學習問題中，我們可以用馬爾可夫決策過程（MDP）和相關算法找出最優行動值函數 q?(s,a)和v?(s)，它通過策略迭代和值迭代找出最佳策略。

這是個好方法，可以解決強化學習中隨機動態系統中的許多問題，但它還有很多限制。比如，現實世界中是否真的存在那么多明確知道狀態轉移概率的問題？我們可以隨時隨地用MDP嗎？

那么，有沒有一種方法既能對一些復雜度過高的計算進行近似求解，又能處理動態系統中的所有問題？

這就是我們今天要介紹的內容——蒙特卡洛方法。

簡介

蒙特卡洛是摩納哥大公國的一座知名賭城，里面遍布輪盤賭、擲骰子和老虎機等游戲，類似的，蒙特卡洛方法的建模機制也基于隨機數和統計概率。

和一般動態規劃算法不同，蒙特卡洛方法（MC）以一個全新的視角來看待問題。簡而言之，它關注的是：我需要從環境中進行多少次采樣，才能從不良策略中辨別出最優策略？

論智注：關于動態規劃算法和MC的視角差異，我們可以舉這兩個例子：

問：1+1+1+1+1+1+1+1 =？ 答：（掰手指）8。 問：在上式后再+1呢？ 答：9！ 問：怎么這么快？ 答：因為8+1=9。 ——動態規劃：記住求過的解來節省時間！

問：我有一個半徑為R的圓和一把豆子，怎么計算圓周率？ 答：在圓外套一個邊長為2R的正方形，往里面隨機扔豆子。 問：此話怎講？ 答：如果扔了N顆豆，落入圓里的豆子有n顆。N越大，n/N就越接近πR2/4R2。 ——MC：手工算完全比不過祖沖之，我好氣！

為了從數學角度解釋MC，這里我們先引入強化學習中的“return”（R），也就是“回報”概念，計算agent的長期預期收益（G）：

有時候，當前策略的狀態概率在這個episode內是非零的，它在之后連續多個episode里也是非零的，我們就要綜合考慮當前回報和未來回報的重要程度。

這不難理解，強化學習的回報往往有一定滯后性。比如下圍棋時，當前下的子可能目前看來沒有多大用處，但它在之后的局勢中可能會顯示出巨大的優勢或劣勢，因此我們的圍棋agent需要考量長期回報。這個衡量標準就是折扣因子γ：

γ一般在[0,1]之間。當γ=0時，只考慮當前回報；當γ=1時，均衡看待當前回報和未來回報。

有了收益Gt和概率At，我們就能計算當前策略下，狀態s的函數值V(s)：

根據大數定律，當N逼近∞時，我們可以得到確切的函數期望值。我們對第i次模擬進行索引。可以發現，如果使用的是MDP（可以解決99%的強化學習問題），由于它有很強的馬爾可夫性，即確信系統下個狀態只與當前狀態有關，與之前的信息無關：

我們可以推導出這樣一個事實：t和期望值完全沒有關系。所以我們可以直接用Gs來表示從某個狀態開始的期望回報（將狀態前移到t = 0時）。

初識蒙特卡洛

計算值函數最經典的方法是對狀態s的每個first visit進行采樣，然后計算平均值，也就是first-visit MC prediction。下面是找到最優V的算法：

pi = init_pi()

returns = defaultdict(list)

for i in range(NUM_ITER):

episode = generate_episode(pi) # (1)

G = np.zeros(|S|)

prev_reward = 0

for (state, reward) in reversed(episode):

reward += GAMMA * prev_reward

# backing up replaces s eventually,

# so we get first-visit reward.

G[s] = reward

prev_reward = reward

for state in STATES:

returns[state].append(state)

V = { state : np.mean(ret) for state, ret in returns.items() }

另一種方法則是every-visit MC prediction，即計算s的所有visit的平均值。雖然兩者有輕微不同，但同樣的，如果visit次數夠大，它們最后會收斂到相似值。

蒙特卡洛動作值

如果我們有一個完整的模型，我們只需知道當前狀態值，就能選擇一個可以獲得最高回報的動作。但如果不知道模型信息呢？蒙特卡洛的特色是無需知道完整的環境知識，只需經驗就能學習。因此當我們不知道什么動作會導致什么狀態，或者環境內部會存在什么互動性時，我們用的是動作值q*，而不是MDP中的狀態值。

這就意味著我們估計的是qπ(s,a)，而不是vπ(s)，回報G[s]也應該是G[s,a]。如果原來G的空間維數是S，現在就成了S×A，這是個很大的空間，但我們還是得繼續對其抽樣，以找出每個狀態動作元組（state?action pair）的預期回報。

正如上一節提到的，蒙特卡洛計算值函數的方法有兩種：first-visit MC和every-visit MC。因為搜索空間過大，如果策略過于貪婪，我們就無法遍歷每個state?action pair，做不到兼顧exploration和exploitation。關于這個問題的解決方法，我們會在下一節具體講述。

蒙特卡洛控制

我們先來回顧一下MDP的策略迭代方式：

對于蒙特卡洛方法，它的迭代方式并沒有我們想象中的不同，也是先從π開始，然后是qπ0，再是π′……

論智注：從π到q的過程代表的是一個完整的策略評估過程，而從q到π則代表一個完整的策略過程。其中策略評估過程會產生很多episode，得到很多接近真實函數的action-value函數。和vπ0一樣，雖然這里我們估計出的每個動作值都是一個近似值，但通過用值函數的近似值進行迭代，經過多輪迭代后，我們還是可以收斂到最優策略。

既然qπ0和vπ0并沒有那么不同，MDP可以用動態規劃法求解，那么我們也可以繼續套用貝爾曼最優性方程（Bellman optimality equation），即：

如果不理解，這里有一份中文介紹：增強學習（三）——MDP的動態規劃解法。

下面就是exploration vs. exploitation。

Monte Carlo ES

面對這么大一個搜索空間，一個補救方法是假定我們每個episode都會從一個特定的狀態開始，并采取特定的行動，也就是exploring start，然后從所有可能回報中抽樣。它背后的思想是認定我們能從任意狀態開始，并在每個episode之初采取所有動作，同時策略評估過程可以利用無限個episode完成。這在很多情況下是不合常理的，但在環境未知問題中卻有奇效。

在實際操作中，我們只需在之前的代碼塊里添加如下內容：

# Before (Start at some arbitrary s_0, a_0)

episode = generate_episode(pi)

# After (Start at some specific s, a)

episode = generate_episode(pi, s, a) # loop through s, a at every iteration.

On-Policy：? -Greedy策略

那么，如果我們不能假設自己能從任意的狀態開始并采取任意的動作呢？不再貪婪，不再存在無限個episode，我們是否還能擬合最優策略？

這就是On-Policy的思想。所謂On-Policy，指的是評估、優化現在正在做決策的那個策略；而off-policy改進的則是和現在正在做決策的那個策略不同的策略。

因為我們要“不再貪婪”，最簡單的方法就是用ε-greedy：對于任何時刻t的執行“探索”小概率ε<1，我們會有ε的概率會進行exploration，有1-ε的概率會進行exploitation。相比貪婪策略，?-Greedy隨機選擇策略（不貪婪）的概率是ε/|A(s)|。

現在的問題是，這是否會收斂到蒙特卡洛方法的最優策略π*？——答案是會，但只是個近似值。

?-Greedy收斂

讓我們從q和一個?-greedy策略π′(s)開始：

?-greedy策略像貪婪策略一樣對vπ做單調改進。如果回到每一步細看，就是：

（1）

這是我們的收斂目標。

這只是理論上的結果，它真的能擬合嗎？顯然不行，因為最優策略是固定的，而我們選擇的策略是被迫隨機的，所以它不能保證收斂到π*——我們來重構我們的問題：

假設我們不用概率ε在隨機選擇策略，而是無視規則，真正做到了完全隨機選擇策略，那么我們就能保證得到至少一個最優策略。即，如果（1）里的等式成立，那么我們就有π=π'，因此vπ=vπ'，受環境約束，這時我們獲得的策略是隨機情況下最優的。

Off-policy：重要性抽樣

Off-policy注釋

我們先來看一些定義：

π：目標策略，我們希望能優化這些策略已獲得最高回報；

b：動作策略，我們正在用b生成π之后會用到的各種數據；

π(a|s)>0?b(a|s)>0?a∈A：整體概念。

Off-policy策略通常涉及多個agent，其中一個agent一直在生成另一個agent試圖優化的數據，我們分別稱它們為行為策略和目標策略。就像神經網絡比線性模型更“有趣”，同樣的，Off-policy策略一般也比On-Policy策略更好玩，也更強大。當然，它也更容易出現高方差，更難收斂。

重要性采樣則是統計學中估計某一分布性質時使用的一種方法。它在這里充當的角色是回答“給定Eb[G]，Eπ[G]是什么”？換句話說，就是我們如何使用從b抽樣得到的信息來確定π的預期回報？

直觀來看，如果b選了很多a，π也選了很多a，那b在π中應該發揮著重要作用；相反地，如果b選了很多a，π并不總是跟著b選a，那b因a產生的狀態不會對π因a產生的狀態產生過大影響。

以上就是重要性采樣的基礎思想。給定從t到T的策略迭代軌跡(Si,Ai)Ti=t，策略π擬合這個軌跡的可能性是：

簡單地說，π和b之間的比率就是：

一般重要性采樣

現在我們有很多方法可以用ρt:T?1計算Eπ[G]的最優解，比如一般重要性采樣（ordinary importance sampling）。設我們采樣了N個episode：

s的首次出現時間是：

因為要估計vπ(s)，所以我們可以用之前提到的first-visit方法計算均值來估計值函數。

這里用first-visit只是為了簡便，我們也可以把它擴展到every-visit。事實上，我們應該結合不同方法來衡量每個episode的回報，因為如果π能擬合最優策略的軌跡，我們應該給它更多權重。

這種重要性抽樣方法是一種無偏差估計，它可能存在嚴重的方差問題。想想那個重要性比率，如果在第k輪的某個episode之中，ρT(s):Tk?1=1000，這就太大了，但它完全有可能存在。那這個1000會造成多大影響？如果我們只有一個episode，它的影響可想而知，但因為強化學習任務往往很長，再加上里面有很多乘法計算，這個比例會存在爆炸和消失兩種結果。

加權重要性采樣

為了降低方差，一種可行的方法是加入權重來計算總和：

這被稱為加權重要性采樣（weighted importance sampling）。它是一個有偏差的估計（偏差趨于0），但與此同時方差降低了。如果是實踐，強烈建議加權！

增量式實現

蒙特卡洛預測方法也可以采用增量式的實現方式，假設我們使用上節中的加權重要性采樣，那么我們可以得到如下形式的一些抽樣算法：

其中Wk是我們的權重。

假設我們有了估計值Vn和當前獲得的回報Gn，要利用Vn與Gn來估計 Vn+1，同時，我們用∑nkWk表示前幾輪回報的權重之和Cn。那么這個等式就是：

權重：Cn+1=Cn+Wn+1

現在，這個Vn就是我們的值函數，同樣的方法也適用于求動作值函數Qn。

在我們更新價函數的同時，我們也可以更新我們的策略π—— argmaxaQπ(s,a)。

注：這里涉及很多數學知識，但已經很基礎了，確切地說，最前沿的也和這個非常接近。

下面還有針對折扣因子、獎勵的抽樣簡介，具體請看原文，小編動不了了。

Python里的On-Policy Model

由于蒙特卡洛方法的代碼通常具有相似的結構，作者已經在python中創建了一個可以直接使用的蒙特卡洛模型類，感興趣的讀者可以在Github上找到代碼。

他還在原文中做了示例：用? -greedy policy解決Blackjack問題。

總而言之，蒙特卡洛方法利用episode的采樣學習最佳值函數和最佳策略，它無需建立對環境的充分認知，在不符合馬爾可夫性時性能穩定，是一種值得嘗試的好方法，也是新人接觸強化學習的一塊良好基石。

本文參考閱讀：

[1]增強學習（二）——馬爾可夫決策過程MDP：https://www.cnblogs.com/jinxulin/p/3517377.html

[2]增強學習（四）——蒙特卡羅方法(Monte Carlo Methods)：http://www.cnblogs.com/jinxulin/p/3560737.html

[3]算法-動態規劃 Dynamic Programming--從菜鳥到老鳥：https://blog.csdn.net/u013309870/article/details/75193592

[4]蒙特卡羅用于計算圓周率pi：http://gohom.win/2015/10/05/mc-forPI/

[5]蒙特卡洛方法 （Monte Carlo Method）：https://blog.csdn.net/coffee_cream/article/details/66972281