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

1.蒙特卡洛

成都創新互聯專業提供成都主機托管四川主機托管成都服務器托管四川服務器托管，支持按月付款！我們的承諾：貴族品質、平民價格，機房位于中國電信/網通/移動機房，西部信息服務器租用服務有保障！

Monte-Carlo算法：

1.將agent放入環境的任意狀態

2.從這個狀態開始選擇action, 并進入下一個狀態

3.重復第二步直到達到最終狀態

4.從最終狀態回溯，計算每一個狀態的G值

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

關于G值：

第一步：根據策略使agent做出動作并進入下一動作，直到到達最終狀態，需要記錄每一個狀態的轉移，得到獎勵r

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

G值就是從某個狀態到最終狀態的獎勵總和

G就是V的更新目標，關于MC的更新：

兩種方法：

2.時序差分(TD)算法

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

蒙特卡洛算法是什么？

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

與它對應的是確定性算法。蒙特·卡羅方法在金融工程學，宏觀經濟學，計算物理學（如粒子輸運計算、量子熱力學計算、空氣動力學計算）等領域應用廣泛。

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

1．使用隨機數發生器產生一個隨機的分子構型。

2．對此分子構型的其中粒子坐標做無規則的改變，產生一個新的分子構型。

3．計算新的分子構型的能量。

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

蒙特卡洛樹是什么算法

蒙特卡羅樹搜索(MCTS)會逐漸的建立一顆不對稱的樹。可以分為四步并反復迭代：

(1)選擇

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

(2)拓展

對于此時存在于內存中的局面c，添加一個它的子節點。這個子節點由局面c執行招式m而得到，也就是T。

(3)模擬

從局面T出發，雙方開始隨機的落子。最終得到一個結果(win/lost)，以此更新T節點的勝利率。

(4)反向傳播

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

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

一、定義：

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

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

二、場景舉例

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

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

三、結論

?蒙特卡羅算法???

：采樣越多，越近似最優解；

?拉斯維加斯算法：采樣越多，越有機會找到最優解；

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

你也可以算出圓周率的 - 隨機落點算法 - 致即將到來的圓周率日

一年一度的圓周率日就要到了，是的，就是3月14日，因為它與圓周率π的前幾位3.14的數字一樣。

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

這個方法源自概率論的基礎，叫做蒙特卡洛法，形象一點的話我們也可以把它稱為隨機落點法，我們先說說它的原理：

我們先看看下面這張圖

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

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

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

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

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

這時候，概率論可以出場發揮作用了，以及有了計算機之后，我們有的“隨機數”這個武器！

假設我們隨機在正方形范圍內畫一個點，那么這個點有可能落在圓形之中，也有可能落在圓形之外；然后我們重復這個動作，從概率論上來說，如果進行無限多次，那么落在圓形中的點的個數與所有已經畫的點的個數之比，就應該是圓形的面積和正方形的面積之比。看看下面這張圖是不是就好理解了？

想想當里面的點數足夠多的時候，就可以覆蓋滿整個原型和正方形。俗話說：“以點帶面”，這時候就可以理解成無數多的點組成了圓形和正方形的面積。

好了，那么下面我們看看用計算機程序來實現這種方法計算圓周率的效果吧！我們這次選用Go語言（Golang）來實現這個算法，因為Go語言相對速度較快（比Python和Java等解釋型語言要快得多），編寫起來又比C語言更容易看懂。

這段程序的運行結果是：

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

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

蒙特卡洛方法的詳細過程

在控制方面，蒙特卡洛方法就是通過大量隨機過程，類似于窮舉法，驗證控制系統的性能，主要是檢驗系統的魯棒性，比方說：PID控制器參數已經整定完畢，但是被控對象的參數在某個范圍內發生變化，這時，將系統的輸出，比方說調整時間和超調亮在坐標圖上以點的形式畫出，那么如果進行100次試驗，就會在圖上形成一百個點，如果這些點排列相對集中，那么系統的魯棒性就相對較好，并且，如果這些點離坐標原點的距離都很近，那么，這個PID控制器的調節時間和超調量性能也就比較好，這是我在控制領域見到的一種蒙特卡洛方法的運用，在經濟領域，蒙特卡洛也有運用，可以簡化過去的算法，將積分變為直接的隨機試驗，這樣可以降低系統的運行時間，提高效率。