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