滴柬采！小李久違上線了~原來這周要寫個(gè)年終總結(jié)的…上周比完賽 喪到現(xiàn)在似乎情緒還是不好就拖到下周吧…補(bǔ)一個(gè)強(qiáng)化學(xué)習(xí)的知識(shí)魂务。
——————
蒙特卡羅
基本思想
蒙特卡羅方法又叫統(tǒng)計(jì)模擬方法，它使用隨機(jī)數(shù)（或偽隨機(jī)數(shù)）來解決計(jì)算的問題，是以概率為基礎(chǔ)的方法。
簡(jiǎn)單的例子：
假設(shè)我們需要計(jì)算一個(gè)不規(guī)則圖形的面積蹋半，那么圖形的不規(guī)則程度和分析性計(jì)算（比如積分）的復(fù)雜程度是成正比的。采用蒙特卡羅方法是怎么計(jì)算的呢充坑？
首先你把圖形放到一個(gè)已知面積的方框內(nèi)减江，然后假想你有一些豆子染突，把豆子均勻地朝這個(gè)方框內(nèi)撒，之后數(shù)這個(gè)圖形之中有多少顆豆子辈灼，再根據(jù)圖形內(nèi)外豆子的比例來計(jì)算面積份企。當(dāng)你的豆子越小，撒的越多的時(shí)候茵休，結(jié)果就越精確薪棒。上述的思想是一種通過采樣近似求解問題的方法手蝎，在強(qiáng)化學(xué)習(xí)里面的蒙特卡羅的采樣思路也大體如此榕莺。下面來看一下在強(qiáng)化學(xué)習(xí)它如何采樣？
蒙特卡羅法通過采樣若干經(jīng)歷完整的狀態(tài)序列(episode)來估計(jì)狀態(tài)的真實(shí)價(jià)值棵介。所謂的經(jīng)歷完整钉鸯，就是這個(gè)序列必須是達(dá)到終點(diǎn)的。
比如下棋問題分出輸贏邮辽，駕車問題成功到達(dá)終點(diǎn)或者失敗唠雕。有了很多組這樣經(jīng)歷完整的狀態(tài)序列，我們就可以來近似的估計(jì)狀態(tài)價(jià)值吨述，進(jìn)而求解預(yù)測(cè)和控制問題了岩睁。區(qū)別比較
VS 強(qiáng)化學(xué)習(xí)的動(dòng)態(tài)規(guī)劃
在動(dòng)態(tài)規(guī)劃中，會(huì)假設(shè)智能體已經(jīng)知道關(guān)于該環(huán)境的所有信息揣云，即完全了解 MDP（馬爾可夫決策過程）捕儒，而不需要和環(huán)境互動(dòng)后才知道。
所以智能體知道該環(huán)境是如何決定下一狀態(tài)以及如何決定獎(jiǎng)勵(lì)的邓夕。動(dòng)態(tài)規(guī)劃所要解決的問題就是智能體知道了環(huán)境的所有信息后刘莹，如何利用這些信息找出最優(yōu)策略。
然而焚刚，蒙特卡羅法点弯，智能體是不知道環(huán)境的動(dòng)態(tài)信息的，需要和環(huán)境進(jìn)行一系列的互動(dòng)后才了解矿咕。它不需要對(duì)環(huán)境有完整的知識(shí)抢肛，僅僅需要經(jīng)驗(yàn)就可以求解最優(yōu)策略，這些經(jīng)驗(yàn)可以在線獲得或者根據(jù)某種模擬機(jī)制獲得碳柱。
故雌团，準(zhǔn)確的來說，動(dòng)態(tài)規(guī)劃可以是一種有模型的學(xué)習(xí)士聪，而蒙特卡羅是基于采樣的模型無關(guān)的學(xué)習(xí)锦援。蒙特卡羅法→預(yù)測(cè)問題
預(yù)測(cè)：狀態(tài)值、預(yù)測(cè)值
智能體與環(huán)境進(jìn)行一系列互動(dòng)的過程中剥悟，會(huì)有一系列的狀態(tài)灵寺，包括動(dòng)作和獎(jiǎng)勵(lì)（反饋）曼库。此處重點(diǎn)探討階段性任務(wù)，即智能體在時(shí)間 T 遇到最終狀態(tài)時(shí)略板，互動(dòng)結(jié)束毁枯。在任何階段，智能體的目標(biāo)都是最大化期望積累獎(jiǎng)勵(lì)叮称。在給定一個(gè)策略后种玛，智能體如何估算該策略的狀態(tài)值和動(dòng)作值？有兩種方式：
1.離線策略方法(Off-Policy Method)：
用一個(gè)策略進(jìn)行評(píng)估瓤檐，用另一個(gè)策略來與環(huán)境進(jìn)行互動(dòng)赂韵。
2.異同策略方法(On-Policy Method)：
智能體通過某個(gè)策略與環(huán)境進(jìn)行互動(dòng)，并計(jì)算該策略的值函數(shù)挠蛉。狀態(tài)值
在每個(gè)階段中祭示，分別計(jì)算出現(xiàn)某一狀態(tài)（一個(gè)階段中只出現(xiàn)一次）后的（折扣）回報(bào)，最后基于所有階段取均值谴古。該算法將狀態(tài)值定義為某一狀態(tài)之后的預(yù)期回報(bào)质涛。
如果在一個(gè)階段中，一個(gè)狀態(tài)出現(xiàn)多次掰担，此時(shí)有兩種處理方法：
1.對(duì)所有階段中該狀態(tài)的首次經(jīng)歷的回報(bào)取平均值
（first MC methods）
2.對(duì)所有階段中該狀態(tài)的所有經(jīng)歷之后的回報(bào)取平均值
（every-visit MC methods）
舉個(gè)例子：這里汇陆，我們考慮first MC methods，即在一個(gè)episode內(nèi)带饱，我們只記錄s的第一次訪問毡代，并對(duì)它取平均回報(bào)。
現(xiàn)在我們假設(shè)有如下一些樣本纠炮，取折扣因子γ=1月趟，即直接計(jì)算累積回報(bào)，則有根據(jù)first MC methods恢口，對(duì)出現(xiàn)過狀態(tài)s的episode的累積回報(bào)取均值孝宗，有Vπ(s)≈ (2 + 1 – 5 + 4)/4 = 0.5
容易知道，當(dāng)我們經(jīng)過無窮多的episode后耕肩，Vπ(s)的估計(jì)值將收斂于其真實(shí)值因妇。
參考：Reinforcement Learning筆記(2)--動(dòng)態(tài)規(guī)劃與蒙特卡洛方法動(dòng)作值
在每個(gè)階段中，先查看狀態(tài)動(dòng)作對(duì)的經(jīng)歷猿诸，然后計(jì)算每個(gè)狀態(tài)動(dòng)作對(duì)之后的回報(bào)婚被，再取平均值。如果在一個(gè)階段中梳虽，某一狀態(tài)動(dòng)作對(duì)出現(xiàn)多次址芯，則處理方法與上面一樣，分為只考慮首次經(jīng)歷和考慮所有經(jīng)歷。蒙特卡羅法→控制問題（策略改進(jìn)）
前面我們講到谷炸，我們通過一些樣本來估計(jì)動(dòng)作值函數(shù)Q和狀態(tài)值函數(shù)V北专，并且在未來執(zhí)行估值最大的動(dòng)作。
這里就存在問題旬陡，假設(shè)在某個(gè)確定狀態(tài)s0下拓颓，能執(zhí)行a0, a1, a2這三個(gè)動(dòng)作，如果智能體已估計(jì)了兩個(gè)Q函數(shù)值描孟，如Q(s0,a0), Q(s0,a1)驶睦，Q(s0,a0)>Q(s0,a1)，那么它在未來將只會(huì)執(zhí)行一個(gè)確定的動(dòng)作a0匿醒。
這樣我們就無法更新Q(s0,a1)的估值和獲得Q(s0,a2)的估值了场航，無法保證Q(s0,a0)就是s0下最大的Q函數(shù)。
為了解決這個(gè)問題青抛，我們需要對(duì)策略進(jìn)行改進(jìn)旗闽。和動(dòng)態(tài)規(guī)劃對(duì)比酬核，動(dòng)態(tài)規(guī)劃中的更新策略是通過最大化動(dòng)作值函數(shù)獲得的蜜另，這種方法稱為貪婪策略。在蒙特卡洛方法中仍然使用貪婪策略的話嫡意，會(huì)使智能體很容易掉入眼前的陷阱中举瑰，而忽略其他最大化獎(jiǎng)勵(lì)的可能。所以要修改算法蔬螟，使得智能體能夠探究每種策略背后最大化獎(jiǎng)勵(lì)的可能此迅。
這時(shí)候的方法是采用隨機(jī)性策略，隨機(jī)策略中以高概率選擇貪婪策略旧巾，低概率選擇某個(gè)非貪婪策略耸序，即不再始終采用貪婪策略。
該算法稱為? 貪婪策略鲁猩。? 的范圍為 [0,1]
ε-greedy policy（?- 貪婪策略）坎怪，即在所有的狀態(tài)下，用1-ε的概率來執(zhí)行當(dāng)前的最優(yōu)動(dòng)作a0廓握，ε的概率來執(zhí)行其他動(dòng)作a1, a2搅窿。這樣我們就可以獲得所有動(dòng)作的估計(jì)值，然后通過慢慢減少ε值隙券，最終使算法收斂男应，并得到最優(yōu)策略。具體的流程
以下版本用的是every-visit,即個(gè)狀態(tài)序列中每次出現(xiàn)的相同狀態(tài)娱仔，都會(huì)計(jì)算對(duì)應(yīng)的收獲值沐飘。
友情參考：強(qiáng)化學(xué)習(xí)（四）用蒙特卡羅法（MC）求解總結(jié)
蒙特卡羅法可以避免動(dòng)態(tài)規(guī)劃求解過于復(fù)雜，同時(shí)還可以不事先知道環(huán)境轉(zhuǎn)化模型，因此可以用于海量數(shù)據(jù)和復(fù)雜模型耐朴。
但是它也有自己的缺點(diǎn)众弓，這就是它每次采樣都需要一個(gè)完整的狀態(tài)序列。如果我們沒有完整的狀態(tài)序列隔箍，或者很難拿到較多的完整的狀態(tài)序列谓娃。
Ending 吃飯啦！周末愉快蜒滩！
友情鏈接： 增強(qiáng)學(xué)習(xí)（四） ----- 蒙特卡羅方法(Monte Carlo Methods)
