在很多應用場景中，馬爾可夫決策過程的狀態轉移概率 \(p(s^ {\prime}|s,a)\) 和獎勵函數 \(r\left( {s,a,s^{\prime}} \right)\) 都是未知的。這種情況一般需要智能體與環境交互，然後收集一些樣本，然後再根據這些樣本來求解最優策略，這種基於採樣的學習方法稱為模型無關的強化學習 \([1]\).
1 蒙特卡羅預測 (Monte Carlo Prediction)
1.1 蒙特卡羅狀態值函數估計
蒙特卡羅法通過對若干個完整的狀態序列(episode)採樣以獲取大量的經驗數據，從而來估計真實的狀態值函數 \({v_\pi }\left( s \right)\).
在馬爾可夫決策過程中對狀態值函數 \({v_\pi }\left( s \right)\)
即它等於所有該狀態收穫的期望，而蒙特卡羅做的事是在計算值函數時，用經驗平均代替隨機變量的期望。比如我們在一次 episode 中，狀態 \(s\)
有了一次 episode 就可以有多次，所以狀態值函數 \({v_\pi }\left( s \right)\)
現在有個問題是：狀態 \(s\)
這種情況有兩種處理的方式，分別為：
- First-visit MC method：只把第一次出現該狀態 \(s\) 後產生的 return \(G_t\) 記錄下來，用於估計 \({v_\pi }\left( s \right)\)
- Every-visit MC method：把所有出現該狀態 \(s\) 後的 return 都記錄下來，用來進行估計 \({v_\pi }\left( s \right)\)
第二種方法比第一種的計算量要大一些，但是在完整的經歷樣本序列少的場景下會比第一種方法適用
圖中是用第一種方法計算的 return，所以 \(R_1(s)=1-2+0+1-3+5=2\). 最後得到的 \({v_\pi }\left( s \right)\)
很明顯生成的 episode 越多，對狀態值函數 \({v_\pi }\left( s \right)\) 的估計就越準確，具體的算法流程為\([2]\)：
First-visit MC prediction
1.2 蒙特卡羅動作值函數估計
我們在使用動態規劃方法進行策略改進時，是假設環境狀態轉移概率 \(p(s^ {\prime}|s,a)\) 是已知的，這樣我們才能評判下一步採取什麼 action 會更好。但是現在我們並不知道 \(p(s^ {\prime}|s,a)\)，也就沒辦法按以前的方法進行策略改進。
所以我們不如用相同的辦法直接對動作值函數 \({Q^\pi }\left( {s,a} \right)\)
2 Monte Carlo Control
蒙特卡羅控制(Monte Carlo Control) 首要的問題就是如何估計最優策略，我們需要產生無數的 episode 才能保證收斂到最優結果。無數的 episode 和大量的迭代導致計算量巨大，效率非常低。主要有兩種辦法解決這個問題：
- 雖説理論上必須有無限個 episode 來估計 \({Q^\pi }\left( {s,a} \right)\)，實際上我們是做不到的，我們只能盡力多產生點 episode，儘可能去接近這個收斂值。我們可以設定一個誤差，兩次估計的值小於這個誤差，差不多就行了。
- 在策略提升前放棄完全的策略評估，採用 episode by episode 的方式進行優化。即先用當前策略生成一個 episode，然後根據這個 episode 進行動作值函數的更新，同時更新策略，並利用更新後的策略繼續生成後續的 episode。
2.1 Monte Carlo with Exploring Starts
然而我們需要考慮一個嚴重的問題：在所有樣本片段集合中，很多 state-action 對並不出現，比如當我在一個確定的 policy下，有可能某個 state 下只出現有限的幾個對應的 actions，其他的 actions 都基本不出現。這樣我們根本沒有 returns 去 average，怎麼能估計到某些 \({Q^\pi }\left( {s,a} \right)\)
比如在下五子棋，機器如果使用greedy的方法的話，從直觀上來看下的每一步棋都對當前很有利。但是一些高手，看似下了一步很不相關的棋，但是從長遠來看可能是一個戰略上的佈局，這個不相關的棋從長遠來看收益可能更大，只不過我們永遠不會去走那一步棋。
為了保證策略迭代對於所有行為值有效，我們必須保證持續的探索。一種解決的方法是在狀態序列開始時，每個狀態行為對被選到的概率都不為 0，這種方法稱為探索初值假定(exploring starts)。
下面給出 Monte Carlo with Exploring Starts 算法流程：
Monte Carlo with Exploring Starts
2.3 On-Policy 蒙特卡羅控制
Exploring start 這個方案在模擬產生 episodes 也許可行，但是在從真實經驗中學習時就不可行了，因為我們無法控制 start point。
On-policy Monte Carlo Control 為了避免初始狀態假定而引入了隨機策略。也就是在決策的時候以一定的概率選擇那些不是最大回報的行為值。這樣提供了探索的可能性，保證了所有狀態能被訪問到。On-policy Monto Carlo 控制方法的大體思想還是 GPI，但是沒有探索初值假定的條件。
On-policy first-visit MC control
> 記錄一下疑問：這每一輪實驗使用的是一個新的策略$\pi$產生的，而這輪實驗在某個狀態$(s,a)$所帶來的回報$G$又加入到$Return(s,a)$去求了平均，那最後這個$Q(s,a)$豈不是由多個策略共同生成的結果？ 還是説這個$Return(s,a)$在每輪進行完會清空呢？
2.4 Off-Policy 蒙特卡羅控制
一個更直截了當的方法是 off-policy：使用兩個策略，一個策略用來學習最優策略，另一個則更具探索性地用來產生行為。 用來學習的策略我們稱之為 目標策略 ，另一個用來生成行為的稱作行為策略。
Off-policy Monte Carlo Control
3 小結
蒙特卡羅法提供了一個替代的策略評估過程。蒙特卡羅法簡單地對於從狀態開始的 return 取均值，而不是用模型去算每個狀態的值。蒙特卡羅法區別於 DP 方法主要在兩方面：
- 蒙特卡羅法基於採樣經驗，所以沒有模型也可以學習
- 蒙特卡羅法不是 bootstrap 的，因為蒙特卡羅法不基於其他狀態的值估計來更新值估計