當前位置:
首頁 > 最新 > 強化學習——蒙特卡洛方法介紹

強化學習——蒙特卡洛方法介紹

來源:OneRaynyDay

編譯:Bot

編者按:本文來自加州大學洛杉磯分校計算機科學專業的本科生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的演算法:

另一種方法則是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完成。這在很多情況下是不合常理的,但在環境未知問題中卻有奇效。

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

On-Policy:? -Greedy策略

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

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

因為我們要「不再貪婪」,最簡單的方法就是用ε-greedy:對於任何時刻t的執行「探索」小概率ε

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

?-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的採樣學習最佳值函數和最佳策略,它無需建立對環境的充分認知,在不符合馬爾可夫性時性能穩定,是一種值得嘗試的好方法,也是新人接觸強化學習的一塊良好基石。

原文地址:oneraynyday.github.io/ml/2018/05/24/Reinforcement-Learning-Monte-Carlo/

本文參考閱讀:

[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


喜歡這篇文章嗎?立刻分享出去讓更多人知道吧!

本站內容充實豐富,博大精深,小編精選每日熱門資訊,隨時更新,點擊「搶先收到最新資訊」瀏覽吧!


請您繼續閱讀更多來自 論智 的精彩文章:

用遷移學習創造的通用語言模型ULMFiT,達到了文本分類的最佳水平
如何改進梯度下降演算法

TAG:論智 |