蒙特卡洛，時(shí)序差分Temporal-Difference Learning(TD)算法

1.蒙特卡洛

成都創(chuàng)新互聯(lián)專業(yè)提供成都主機(jī)托管四川主機(jī)托管成都服務(wù)器托管四川服務(wù)器托管，支持按月付款！我們的承諾：貴族品質(zhì)、平民價(jià)格，機(jī)房位于中國電信/網(wǎng)通/移動(dòng)機(jī)房，西部信息服務(wù)器租用服務(wù)有保障！

Monte-Carlo算法：

1.將agent放入環(huán)境的任意狀態(tài)

2.從這個(gè)狀態(tài)開始選擇action, 并進(jìn)入下一個(gè)狀態(tài)

3.重復(fù)第二步直到達(dá)到最終狀態(tài)

4.從最終狀態(tài)回溯，計(jì)算每一個(gè)狀態(tài)的G值

5.重復(fù)1-4過程，然后平均每一次的G值，最后得到的就是V值

關(guān)于G值：

第一步：根據(jù)策略使agent做出動(dòng)作并進(jìn)入下一動(dòng)作，直到到達(dá)最終狀態(tài)，需要記錄每一個(gè)狀態(tài)的轉(zhuǎn)移，得到獎(jiǎng)勵(lì)r

第二步：從最終狀態(tài)回溯，一遍一遍計(jì)算G值。 G 等于上一狀態(tài)的G值（G‘）乘以一定的折扣（gamma）再加上r

G值就是從某個(gè)狀態(tài)到最終狀態(tài)的獎(jiǎng)勵(lì)總和

G就是V的更新目標(biāo)，關(guān)于MC的更新：

兩種方法：

2.時(shí)序差分(TD)算法

TD是對(duì)MC的改進(jìn)，即agent走到第N步就可以開始回溯更新。

蒙特卡洛算法是什么？

蒙特·卡羅方法（Monte Carlo method），也稱統(tǒng)計(jì)模擬方法，是二十世紀(jì)四十年代中期由于科學(xué)技術(shù)的發(fā)展和電子計(jì)算機(jī)的發(fā)明，而被提出的一種以概率統(tǒng)計(jì)理論為指導(dǎo)的一類非常重要的數(shù)值計(jì)算方法。是指使用隨機(jī)數(shù)（或更常見的偽隨機(jī)數(shù)）來解決很多計(jì)算問題的方法。

與它對(duì)應(yīng)的是確定性算法。蒙特·卡羅方法在金融工程學(xué)，宏觀經(jīng)濟(jì)學(xué)，計(jì)算物理學(xué)（如粒子輸運(yùn)計(jì)算、量子熱力學(xué)計(jì)算、空氣動(dòng)力學(xué)計(jì)算）等領(lǐng)域應(yīng)用廣泛。

使用蒙特·卡羅方法步驟：

1．使用隨機(jī)數(shù)發(fā)生器產(chǎn)生一個(gè)隨機(jī)的分子構(gòu)型。

2．對(duì)此分子構(gòu)型的其中粒子坐標(biāo)做無規(guī)則的改變，產(chǎn)生一個(gè)新的分子構(gòu)型。

3．計(jì)算新的分子構(gòu)型的能量。

4．比較新的分子構(gòu)型于改變前的分子構(gòu)型的能量變化，判斷是否接受該構(gòu)型。

蒙特卡洛樹是什么算法

蒙特卡羅樹搜索(MCTS)會(huì)逐漸的建立一顆不對(duì)稱的樹?？梢苑譃樗牟讲⒎磸?fù)迭代：

(1)選擇

從根節(jié)點(diǎn)，也就是要做決策的局面R出發(fā)向下選擇一個(gè)最急迫需要被拓展的節(jié)點(diǎn)T；局面R是第一個(gè)被檢查的節(jié)點(diǎn)，被檢查的節(jié)點(diǎn)如果存在一個(gè)沒有被評(píng)價(jià)過的招式m，那么被檢查的節(jié)點(diǎn)在執(zhí)行m后得到的新局面就是我們所需要展開的T；如果被檢查的局面所有可行的招式已經(jīng)都被評(píng)價(jià)過了，那么利用ucb公式得到一個(gè)擁有最大ucb值的可行招式，并且對(duì)這個(gè)招式產(chǎn)生的新局面再次進(jìn)行檢查；如果被檢查的局面是一個(gè)游戲已經(jīng)結(jié)束的游戲局面，那么直接執(zhí)行步驟4；通過反復(fù)的進(jìn)行檢查，最終得到一個(gè)在樹的最底層的最后一次被檢查的局面c和它的一個(gè)沒有被評(píng)價(jià)過的招式m，執(zhí)行步驟2。

(2)拓展

對(duì)于此時(shí)存在于內(nèi)存中的局面c，添加一個(gè)它的子節(jié)點(diǎn)。這個(gè)子節(jié)點(diǎn)由局面c執(zhí)行招式m而得到，也就是T。

(3)模擬

從局面T出發(fā)，雙方開始隨機(jī)的落子。最終得到一個(gè)結(jié)果(win/lost)，以此更新T節(jié)點(diǎn)的勝利率。

(4)反向傳播

在T模擬結(jié)束之后，它的父節(jié)點(diǎn)c以及其所有的祖先節(jié)點(diǎn)依次更新勝利率。一個(gè)節(jié)點(diǎn)的勝利率為這個(gè)節(jié)點(diǎn)所有的子節(jié)點(diǎn)的平均勝利率。并從T開始，一直反向傳播到根節(jié)點(diǎn)R，因此路徑上所有的節(jié)點(diǎn)的勝利率都會(huì)被更新。

蒙特卡洛算法和拉斯維加斯算法

一、定義：

特卡羅是一類隨機(jī)方法的統(tǒng)稱。這類方法的特點(diǎn)是，可以在隨機(jī)采樣上計(jì)算得到近似結(jié)果，隨著采樣的增多，得到的結(jié)果是正確結(jié)果的概率逐漸加大，但在（放棄隨機(jī)采樣，而采用類似全采樣這樣的確定性方法）獲得真正的結(jié)果之前，無法知道目前得到的結(jié)果是不是真正的結(jié)果。

拉斯維加斯方法是另一類隨機(jī)方法的統(tǒng)稱。這類方法的特點(diǎn)是，隨著采樣次數(shù)的增多，得到的正確結(jié)果的概率逐漸加大，如果隨機(jī)采樣過程中已經(jīng)找到了正確結(jié)果，該方法可以判別并報(bào)告，但在但在放棄隨機(jī)采樣，而采用類似全采樣這樣的確定性方法之前，不保證能找到任何結(jié)果（包括近似結(jié)果）

二、場景舉例

假如筐里有100個(gè)蘋果，讓我每次閉眼拿1個(gè)，挑出最大的。于是我隨機(jī)拿1個(gè)，再隨機(jī)拿1個(gè)跟它比，留下大的，再隨機(jī)拿1個(gè)……我每拿一次，留下的蘋果都至少不比上次的小。拿的次數(shù)越多，挑出的蘋果就越大，但我除非拿100次，否則無法肯定挑出了最大的。這個(gè)挑蘋果的算法，就屬于蒙特卡羅算法——盡量找好的，但不保證是最好的。

而拉斯維加斯算法，則是另一種情況。假如有一把鎖，給我100把鑰匙，只有1把是對(duì)的。于是我每次隨機(jī)拿1把鑰匙去試，打不開就再換1把。我試的次數(shù)越多，打開（最優(yōu)解）的機(jī)會(huì)就越大，但在打開之前，那些錯(cuò)的鑰匙都是沒有用的。這個(gè)試鑰匙的算法，就是拉斯維加斯的——盡量找最好的，但不保證能找到。

三、結(jié)論

?蒙特卡羅算法???

：采樣越多，越近似最優(yōu)解；

?拉斯維加斯算法：采樣越多，越有機(jī)會(huì)找到最優(yōu)解；

這兩類隨機(jī)算法之間的選擇，往往受到問題的局限。如果問題要求在有限采樣內(nèi)，必須給出一個(gè)解，但不要求是最優(yōu)解，那就要用蒙特卡羅算法。反之，如果問題要求必須給出最優(yōu)解，但對(duì)采樣沒有限制，那就要用拉斯維加斯算法。

你也可以算出圓周率的 - 隨機(jī)落點(diǎn)算法 - 致即將到來的圓周率日

一年一度的圓周率日就要到了，是的，就是3月14日，因?yàn)樗c圓周率π的前幾位3.14的數(shù)字一樣。

我們知道，傳說中祖沖之計(jì)算圓周率用的是“割圓術(shù)”的改進(jìn)方法，可惜我們大多數(shù)現(xiàn)代人的腦子已經(jīng)無法理解這種方法了。使用其他的復(fù)雜公式也有，但人的腦子更不容易理解，但有一個(gè)異想天開的方法你知道嗎？任何人可以簡單地去計(jì)算出Pi呢（下面我們都用Pi來代替圓周率π吧，好寫好認(rèn)，：p）。

這個(gè)方法源自概率論的基礎(chǔ)，叫做蒙特卡洛法，形象一點(diǎn)的話我們也可以把它稱為隨機(jī)落點(diǎn)法，我們先說說它的原理：

我們先看看下面這張圖

假設(shè)有圖中的一個(gè)正方形和一個(gè)剛好套在它中間的圓形，可以很直觀地看出：圓形的半徑如果是R的話，正方形的邊長就是2R。

圓形的面積根據(jù)公式是Pi乘以R的平方，也就是 Pi × R × R = PiR2

正方形的面積根據(jù)公式是邊長的平方，也就是（2R）×（2R）= 4R2

把兩個(gè)式子相除一下，可以很容易地推算出來，Pi = （圓形的面積 ÷ 正方形的面積）× 4

這樣，就巧妙地把計(jì)算Pi值的問題轉(zhuǎn)換成計(jì)算符合上面圖中條件的圓形與正方形的面積之比的計(jì)算了。

這時(shí)候，概率論可以出場發(fā)揮作用了，以及有了計(jì)算機(jī)之后，我們有的“隨機(jī)數(shù)”這個(gè)武器！

假設(shè)我們隨機(jī)在正方形范圍內(nèi)畫一個(gè)點(diǎn)，那么這個(gè)點(diǎn)有可能落在圓形之中，也有可能落在圓形之外；然后我們重復(fù)這個(gè)動(dòng)作，從概率論上來說，如果進(jìn)行無限多次，那么落在圓形中的點(diǎn)的個(gè)數(shù)與所有已經(jīng)畫的點(diǎn)的個(gè)數(shù)之比，就應(yīng)該是圓形的面積和正方形的面積之比?？纯聪旅孢@張圖是不是就好理解了？

想想當(dāng)里面的點(diǎn)數(shù)足夠多的時(shí)候，就可以覆蓋滿整個(gè)原型和正方形。俗話說：“以點(diǎn)帶面”，這時(shí)候就可以理解成無數(shù)多的點(diǎn)組成了圓形和正方形的面積。

好了，那么下面我們看看用計(jì)算機(jī)程序來實(shí)現(xiàn)這種方法計(jì)算圓周率的效果吧！我們這次選用Go語言（Golang）來實(shí)現(xiàn)這個(gè)算法，因?yàn)镚o語言相對(duì)速度較快（比Python和Java等解釋型語言要快得多），編寫起來又比C語言更容易看懂。

這段程序的運(yùn)行結(jié)果是：

可以看出來，計(jì)算出來的圓周率Pi值越來越接近于我們所熟知的數(shù)字：3.1415……

神奇吧，為什么說人也可以算出來呢？假想在地上用粉筆畫一個(gè)那樣的正方形和圓形，然后我們隨性地往里扔沙包吧！很童真的畫面吧？

蒙特卡洛方法的詳細(xì)過程

在控制方面，蒙特卡洛方法就是通過大量隨機(jī)過程，類似于窮舉法，驗(yàn)證控制系統(tǒng)的性能，主要是檢驗(yàn)系統(tǒng)的魯棒性，比方說：PID控制器參數(shù)已經(jīng)整定完畢，但是被控對(duì)象的參數(shù)在某個(gè)范圍內(nèi)發(fā)生變化，這時(shí)，將系統(tǒng)的輸出，比方說調(diào)整時(shí)間和超調(diào)亮在坐標(biāo)圖上以點(diǎn)的形式畫出，那么如果進(jìn)行100次試驗(yàn)，就會(huì)在圖上形成一百個(gè)點(diǎn)，如果這些點(diǎn)排列相對(duì)集中，那么系統(tǒng)的魯棒性就相對(duì)較好，并且，如果這些點(diǎn)離坐標(biāo)原點(diǎn)的距離都很近，那么，這個(gè)PID控制器的調(diào)節(jié)時(shí)間和超調(diào)量性能也就比較好，這是我在控制領(lǐng)域見到的一種蒙特卡洛方法的運(yùn)用，在經(jīng)濟(jì)領(lǐng)域，蒙特卡洛也有運(yùn)用，可以簡化過去的算法，將積分變?yōu)橹苯拥碾S機(jī)試驗(yàn)，這樣可以降低系統(tǒng)的運(yùn)行時(shí)間，提高效率。