0
雷鋒網 AI 科技評論按：強化學習已經席卷了整個 AI 世界。從 AlphaGo 到 AlphaStar，由強化學習提供動力的 AI 智能體已經戰勝了越來越多由人類主導的傳統活動。通過在某一環境中對智能體行為進行優化以實現最大獎勵是強化學習的關鍵，但是絕大多數強化學習方法需要對環境有完整的了解，而現實中這是難以實現的，基于樣本的學習方法（例如蒙特卡洛）則可以解決這一痛點。本文以 21 點游戲為例，對蒙特卡洛方法進行了在強化學習中的應用進行了介紹，雷鋒網 AI 科技評論編譯如下。
強化學習已經席卷了整個 AI 世界。從 AlphaGo 到 AlphaStar，由強化學習提供動力的 AI 智能體已經戰勝了越來越多傳統上由人類主導的活動。簡而言之，這些成就通過在某一環境中對智能體行為進行優化以實現最大獎勵而取得。
此前關于 GradientCrescent 的一些文章中，我們對強化學習的各基本方面進行了研究，從基礎的強盜系統和基于策略的方法，到在馬爾可夫環境中優化基于獎勵的行為。所有這些方法都要求我們對環境有全面了解，例如，動態規劃要求我們掌握所有可能發生狀態轉換的完整概率分布。但是，實際上，我們發現大多數系統不可能完全了解完整概率分布，并且由于復雜性、固有的不確定性或計算的局限性，不能顯式地表示出概率分布。以氣象學家的工作進行類比：預測天氣背后涉及的因素非常之多，以至于要知道其中的確切概率幾乎是不可能的。
GradientCrescent 相關文章閱讀可參考：https://medium.com/gradientcrescent
圖 1：你能確定颶風形成的準確概率嗎？
對于這些情況，基于樣本的學習方法（例如蒙特卡洛）是一種解決方案。蒙特卡洛一詞通常用于描述任何依賴于隨機抽樣的估計方法。換句話說，我們并不假設我們了解環境，而是僅通過與環境交互獲得的狀態、動作和獎勵的樣本序列從經驗中學習。這些方法通過直接觀察模型在正常運行時的獎勵反饋來判斷其狀態的平均值。有趣的是，有研究表明，即使不了解環境的動態（可以認為是狀態轉換的概率分布），我們仍然可以獲得最佳行為來最大化獎勵。
例如，考慮擲 12 個骰子得到的返回值。通過將這些滾動視為單個狀態，我們可以對這些返回值進行平均以接近真正的預期返回值。隨著樣本數量的增加，我們越接近實際的期望返回值。
圖 2：擲 12 個骰子 60 次的平均期望值（阿爾伯塔大學）
我忠實的讀者可能對這種基于抽樣的估計并不陌生，我在此前的相關文章中也對 k-bandit 系統也進行了抽樣。蒙特卡洛方法不是比較不同的強盜系統，而是用來比較馬爾可夫環境中的不同策略，方法是確定一個狀態的值，同時遵循特定的策略直到終止。
在強化學習中，蒙特卡洛方法是一種通過平均樣本回報來估計模型狀態值的方法。由于終端狀態的需要，蒙特卡洛方法天生適用于偶發環境。由于這個限制，蒙特卡洛方法通常被認為是「離線」的，在這種情況下，所有更新都是在到達終端狀態之后進行的。
一個簡單的類比是在迷宮中隨機導航，它的一種離線的方法是先讓智能體到達終點，然后利用經驗進行嘗試，從而減少在迷宮中花費的時間。相反地，在線方法則是讓智能體不斷地修正其在迷宮中的行為，比如說當它注意到綠色走廊通向“死胡同”，即便依舊還置身迷宮中也會決定避開它們。我們將在下一篇文章中討論在線方法。
蒙特卡洛的處理過程可以總結如下：
圖 3：蒙特卡洛方法的狀態值估計（Sutton 等人）
為了更好地了解蒙特卡洛的工作原理，請參考下面的狀態轉換圖。每個狀態轉換的獎勵都以黑色顯示，并且采用 0.5 的貼現因子。讓我們暫時擱置實際狀態值，并專注于計算本輪的返回值。
圖 4：狀態轉換圖。狀態編號以紅色顯示，返回值以黑色顯示。
假定終端狀態的返回值為 0，那么讓我們從終端狀態（G5）開始計算每個狀態的返回值。請注意，我們已將貼現因子設置為 0.5，從而對最近的狀態進行加權。
一般化的公式表示如下：
為了避免將所有返回值都保留在列表中，我們可以逐步地執行蒙特卡洛狀態值的更新過程，其方程與傳統的梯度下降方程有一些相似之處：
圖 5：蒙特卡洛逐步更新過程。S 代表狀態，V 代表值，G 代表返回值，而 alpha 代表步長參數。
在強化學習中，蒙特卡洛方法可以進一步分為「首次訪問」和「每次訪問」。簡單地說，兩者之間的區別在于蒙特卡洛更新之前，在一輪中可以訪問一個狀態的次數。「首次訪問」蒙特卡洛方法將所有狀態的值估計為終止前每個狀態首次訪問后返回值的平均值，而「每次訪問」蒙特卡洛方法將終止前一個狀態的 n 次訪問后的返回值作為平均值。由于「首次訪問」蒙特卡洛方法相對簡單，我們將在本文中使用「首次訪問」蒙特卡洛。
如果一個模型不能提供策略，那么蒙特卡洛方法也可以用來估計狀態動作的值。這比僅使用狀態值更有用，因為給定狀態中每個動作（q）的值可使得智能體通過對未知環境的觀察自動形成策略。
更正式地說，我們可以使用蒙特卡洛方法來估計 q（s, a,pi），從狀態 s 開始，采取行動 a，然后遵循策略 pi 時的預期返回值。在蒙特卡洛方法保持不變的情況下，我們針對特定狀態額外增加了一個動作維度。如果狀態 s 被訪問并且動作 A 在其中被執行，則可以認為在該輪中的該狀態—動作對（s，a）被訪問過。類似地，可以通過「首次訪問」或「每次訪問」方法來完成狀態動作值估計。
像在動態規劃中一樣，我們可以使用廣義策略迭代（GPI）從狀態動作值的觀察中形成策略：
通過交替執行策略估計和策略改進步驟，并結合探索起點以確保所有可能的動作都得到訪問，我們可以為每個狀態實現最佳策略。對于蒙特卡洛 GPI，這種交替通常是在每輪終止后完成的。
圖 6：蒙特卡洛 GPI（Sutton 等人）
為了更好地理解蒙特卡洛在評估不同狀態值和狀態動作值時的實際工作方式，讓我們通過 21 點游戲逐步演示。首先，讓我們定義游戲的規則和條件：
我們只會和莊家對抗，而沒有其他玩家參加。這使我們可以將莊家發牌視為環境的一部分。
牌面數即為卡牌值。紙牌 J，K 和 Q 的價值均為 10。ace 的值可以為 1 或 11，玩家可以自主選擇。
雙方都有兩張卡。玩家的兩張牌面朝上，而莊家的一張牌面朝上。
目的是使手中的所有卡的總和<= 21。超過 21 則導致爆牌，而雙方都為 21 則導致平局。
玩家看到自己的牌和莊家的第一張牌后，玩家可以選擇要牌或停牌，直到對自己的總和滿意為止，之后他將停牌。
然后，莊家展示第二張牌——如果兩張牌之和少于 17，將繼續發牌，直到達到 17，之后停牌。
讓我們用 21 點游戲來演示蒙特卡洛。
1、回合 1
你取得的紙牌之和為 19，你想碰碰運氣繼續要牌，然后抽出了一張 3，則導致爆牌。爆牌時，莊家只有一張可見的卡，總和為 10。可以顯示如下：
圖 10：回合 1
當我們爆牌時，此回合的獎勵為-1。讓我們使用【智能體紙牌之和，莊家紙牌之和，是否獲勝？】的格式作為前次狀態相應的返回值，該格式如下：
本輪不太走運，讓我們進行下一輪。
2、回合 2
你取得的紙牌之和為 19，這次你決定停牌。莊家取得的紙牌之和為 13，然后繼續要牌，最終導致爆牌。前次狀態描述如下：
圖 7：回合 2
讓我們描述下這一輪發生的狀態和獎勵。
隨著本輪終止，我們現在可以使用本回合計算出的返回值來更新本輪所有狀態值。假設折現系數為 1，我們只需像以前的狀態轉換一樣，將新的獎勵加到前面的結果中。由于先前狀態 V（19，10，no）的返回值為 -1，因此我們計算出預期返回值并將其分配給我們的狀態：
圖 8：21 點演示的最終狀態值
3、實現
讓我們使用「首次訪問」的蒙特卡洛方法來實現 21 點游戲，并基于 Sudharsan 等人提出的方法采用 Python 形式對游戲中所有可能的狀態值（或不同的操作組合）進行學習 。和往常一樣，我們的代碼可以在 GradientCrescent Github上獲取，鏈接如下：
我們將使用 OpenAI Gym 環境來實現這一點。將環境看作是運行游戲的接口，使用最少的代碼，從而讓我們專注于實現強化學習。方便的是，所有收集到的關于狀態、動作和獎勵的信息都保存在「觀察」變量中，其中這些變量是通過運行游戲積累得到的。
首先讓我們導入獲取和繪制結果所需的全部開發庫。
接下來對我們的 gym 環境進行初始化，并對指導智能體行動的策略進行定義。基本上，我們會持續要牌，直至手中的紙牌之和達到 19 點或更多，然后停牌。
接下來，使用我們的策略為一輪游戲定義生成數據的方法。我們將有關狀態、采取的行動以及行動伴隨的獎勵的信息進行存儲。
最后，讓我們定義「首次訪問」的蒙特卡洛預測函數。首先，我們初始化一個空字典來存儲當前狀態值，以及另一個字典來存儲所有輪游戲中每個狀態的條目數。
對于每一輪游戲，我們都調用先前的「 generate_episode 」方法來生成有關狀態值和該狀態后獲得的獎勵的信息。我們還初始化了一個變量來存儲增量返回值。接下來，我們獲得該輪中訪問的每個狀態的獎勵和當前狀態值，并使用該步驟的獎勵來增加我們的返回值變量。
回想一下，當我們執行「首次訪問」的蒙特卡洛時，我們只訪問單輪游戲中的單個狀態。因此，我們對狀態字典執行條件檢查，以查看狀態是否已被訪問。如果滿足此條件，則可以使用先前定義的蒙特卡洛狀態值更新過程來計算新值，并將對該狀態的觀察次數增加 1。然后，對下一輪游戲重復此過程，從而最終獲得平均返回值。
讓我們執行程序看看我們的結果吧！
圖 15：輸出樣本顯示了多次 21 點游戲的狀態值
輸出樣本顯示了多次 21 點游戲的狀態值。
我們可以繼續觀察 5000 輪游戲的蒙特卡洛，并繪制狀態值分布來描述玩家和莊家的任何組合的值。
圖 16：不同 21 點游戲組合的狀態值可視化
現在讓我們總結一下我們學到的知識。
基于樣本的學習方法使我們可以簡單地通過采樣來估計狀態和狀態動作值，而無需任何遷移動態知識。
蒙特卡洛方法依賴于模型的隨機抽樣，觀察模型返回的獎勵，在正常操作期間收集信息來定義其狀態的平均值。
通過蒙特卡洛方法進行廣義策略迭代是可行的。
21 點游戲中玩家和發牌手所有可能組合的值可以通過重復的蒙特卡洛模擬來判斷，從而為優化策略開辟了道路。
對蒙特卡洛方法的介紹到此結束。在下一篇文章中，我將介紹以時序差分學習的形式繼續進行基于樣本的在線學習方法。
參考文獻
Sutton et. al, Reinforcement Learning（書籍鏈接：https://books.google.com/books?id=PwnrBwAAQBAJ&printsec=frontcover&dq=Reinforcement+Learning&hl=zh-CN&sa=X&ved=0ahUKEwjB25vcgP3lAhUUa94KHcPODyMQ6AEIKDAA#v=onepage&q=Reinforcement%20Learning&f=false）
White et. al, Fundamentals of Reinforcement Learning, University of Alberta
Silva et. al, Reinforcement Learning, UCL
Platt et. Al, Northeaster University（論文鏈接：http://www.ccs.neu.edu/home/rplatt/cs7180_fall2018/slides/monte_carlo.pdf）
論文作者：Adrian Yijie Xu. 雷鋒網雷鋒網
雷峰網原創文章，未經授權禁止轉載。詳情見轉載須知。
