強化學習基礎篇（十五）蒙特卡洛預測

1、 Model-free方法

通過貝爾曼方程求解最優(yōu)策略 $\pi^*$ 有3種基本方法：動態(tài)規(guī)劃法、蒙特卡洛法和時間差分法。前面我們介紹了如何利用動態(tài)規(guī)劃法去求解環(huán)境知識完備（即馬爾可夫決策過程已知）的強化學習任務。簡而言之，首先通過策略評估計算給定策略 $\pi$ 的優(yōu)劣程度，然后采用策略迭代算法獲得基于策略 $\pi$ 的最優(yōu)價值函數(shù) $v_{\pi}^*(s)$ ，并根據(jù)最優(yōu)價值函數(shù) $v_{\pi}^*(s)$ 確定最優(yōu)策略 $\pi^*$ ；出于效率的考慮，也可以采用值迭代算法來獲得最優(yōu)價值函數(shù) $v_{\pi}^*(s)$ 和最優(yōu)策略 $\pi^*$ 。
在實際任務中，環(huán)境知識完備性這一先決條件較難滿足，也就意味著大量的強化學習任務難以直接采用動態(tài)規(guī)劃法進行求解。對于環(huán)境知識不完備的MDP，即轉(zhuǎn)移矩陣 $P$ 以及獎勵 $R$ 未知的研究領域稱為無模型（Model-Free）方法。Model-free方法的基本方法就是使用蒙特卡洛法（Monte Carlo，MC）和時間差分法（Temporal-difference，TD）。

此外Model-free方法可以分為兩個大方面：預測（prediction）與控制（Control）

Model-free預測是評估一個未知MDP的值函數(shù)。
Model-free控制是優(yōu)化一個未知MDP的值函數(shù)。

本文會主要介紹蒙特卡洛預測方法。

2、什么是蒙特卡洛方法

“蒙特卡洛”這一名字來源于摩納哥的城市蒙特卡洛（MonteCarlo）。該方法由著名的美國計算機科學家馮·諾伊曼和S.M.烏拉姆在20世紀40年代第二次世界大戰(zhàn)中研制原子彈（"曼哈頓計劃”）時首先提出。
蒙特卡洛法是一種基于采樣的算法名稱，依靠重復隨機抽樣來獲得數(shù)值結(jié)果的計算方法，其核心理念是使用隨機性來解決原則上為確定性的問題。通俗而言，蒙特卡洛法采樣越多，結(jié)果就越近似最優(yōu)解，即通過多次采樣逼近最優(yōu)解。
舉個簡單的例子。去果園摘蘋果，規(guī)則是每次只能摘一個蘋果，并且手中只能留下一個蘋果，最后走出果園的時候也只能帶走一個蘋果，目標是使得最后拿出果園的蘋果最大?？梢赃_成這樣一個共識：進入果園后每次摘一個大蘋果，看到比該蘋果更大的則替換原來的蘋果。基于上述共識，可以保證每次摘到的蘋果都至少不比上一次摘到的蘋果小。如果摘蘋果的次數(shù)越多，挑出來的蘋果就越大，但無法確保最后摘到的蘋果一定是最大的，除非把整個果園的蘋果都摘一遍。即盡量找較大的，但不保證是最大的。采樣次數(shù)越多，結(jié)果就越近似最優(yōu)解，這種方法就屬于蒙特卡洛法。\

蒙特卡洛法能夠處理免模型的任務，究其原因是無須依賴環(huán)境的完備知識（Environment backup），只需收集從環(huán)境中進行采樣得到的經(jīng)驗軌跡（Experience episode），基于經(jīng)驗軌跡集數(shù)據(jù)的計算，可求解最優(yōu)策略。

蒙特卡洛在強化學習中應用的核心主要包含以下幾點：

MC方法是直接從經(jīng)驗軌跡當中直接進行學習。
MC方法是一種model-free方法，即沒有MDP的轉(zhuǎn)移概率 $P$ 以及獎勵 $R$ 的先驗知識。
MC方法從完整的經(jīng)驗軌跡中學習，不使用bootstrapping方法。
MC方法簡單得使用這個思想：價值=平均回報。
缺點在于只能應用于一定有終結(jié)點的按幕分的MDP過程。

經(jīng)驗軌跡（Episodes）

經(jīng)驗軌跡是智能體通過與環(huán)境交互獲得的狀態(tài)、動作、獎勵的樣本序列。

舉個例子：

每條經(jīng)驗軌跡（episode）就是一條從起始狀態(tài)到結(jié)束狀態(tài)的經(jīng)歷。例如在走迷宮，一條episode就是從你開始進入迷宮，到最后走出迷宮的路徑。首先我們要得到的是某一個狀態(tài) $s$ 的平均收獲。所以我們說的episode要經(jīng)過狀態(tài) $s$ 。所以上圖中第二條和第五條路徑?jīng)]有經(jīng)過狀態(tài) $s$ ，對于 $s$ 來說就不能使用它了。完整的經(jīng)驗軌跡不要求起始狀態(tài)一定是某一個特定的狀態(tài)，但是要求智能體最終進入環(huán)境認可的某一個終止狀態(tài)。理論上完整的狀態(tài)序列越多，結(jié)果越準確。

有終結(jié)點的按幕分的MDP過程

無論采用哪個策略，都會在有限時間內(nèi)到達終點并獲得回報。就像上面那個圖，每條樣本都會最終到達終點。現(xiàn)實中，我們的棋類游戲，都會在有限步數(shù)以后達到輸贏或者平局的結(jié)果并獲得相應的回報。

價值=平均回報

其實從字面理解就是求均值的意思。就是狀態(tài) $s$ 在每一個樣本中收獲的回報均值。

比如，現(xiàn)評估某狀態(tài) $s$ 的價值函數(shù)。我們采樣了兩個經(jīng)驗軌跡，從一個經(jīng)驗軌跡里面得到的回報是5，然后下一個經(jīng)驗軌跡里面的得到的回報是7，我們可以從起始狀態(tài)來評估此狀態(tài)的價值函數(shù)為：
$\frac{5+7}{2}=6$

3. 蒙特卡洛策略評估

蒙特卡洛法采用時間步有限的、完整的經(jīng)驗軌跡，其所產(chǎn)生的經(jīng)驗信息可推導出每個狀態(tài)的平均獎勵，以此來代替獎勵的期望（即目標狀態(tài)值）。換言之，在給定的策略 $\pi$ 下，蒙特卡洛法從一系列完整的經(jīng)驗軌跡中學習該策略下的狀態(tài)值函數(shù) $v_{\pi}(s)$ 。
當模型環(huán)境未知（Model-free）時，智能體根據(jù)策略 $\pi$ 進行采樣，從起始狀態(tài) $s_0$ 出發(fā)，執(zhí)行該策略 $T$ 步后達到一個終止狀態(tài) $s_T$ ，從而獲得一條完整的經(jīng)驗軌跡。
$s_0,a_0,r_1,s_1,a_1,r_2,...,s_{T-1},a_{T-1},r_T,s_T \sim \pi$
對于 $t$ 時刻的狀態(tài) $s$ ，未來折扣累積獎勵為：
$G_t=r_t+\gamma r_{t+1}+...+\gamma^{T-1} r_{t+T}$
蒙特卡洛法利用經(jīng)驗軌跡的平均未來折扣累積獎勵 $G$ 作為狀態(tài)值的期望。
$G=average(G_1+G_2+...+G_T)$
而強化學習的目標是求解最優(yōu)策略 $\pi^*$ ，得到最優(yōu)策略的一個常用方法是求解狀態(tài)值函數(shù) $v_{\pi}(s)$ 的期望。如果采樣的經(jīng)驗軌跡樣本足夠多，就可以精確估計出狀態(tài) $s$ 上下遵循策略 $\pi$ 的期望，即狀態(tài)值函數(shù) $v_{\pi}(s)$ 。
$v_{\pi}(s)=\mathbb E[G | s \in S]$
當根據(jù)策略 $\pi$ 收集到的經(jīng)驗軌跡樣本趨于無窮多時，得到的狀態(tài)值 $v_{\pi}(s)$ 也就無限接近于真實的狀態(tài)值。

4.First Visit以及Every Visit蒙特卡洛評估方法

假設智能體收集了大量基于某一策略 $\pi$ 下運行到狀態(tài) $s$ 的經(jīng)驗軌跡，就可直接估計在該策略下的狀態(tài)值 $v(s)$ 。然而在狀態(tài)轉(zhuǎn)移過程中，可能發(fā)生一個狀態(tài)經(jīng)過一定的轉(zhuǎn)移后又一次或多次返回該狀態(tài)的情況，即狀態(tài)發(fā)生多次重復，這會給實際的狀態(tài)值估算帶來噪聲。
例如，羊群在A地吃草為狀態(tài) $s_A$ ，在B地吃草為狀態(tài) $s_B$ ，顯然羊群會根據(jù)草地的肥沃程度在不同的地方遷徙吃草，但是會出現(xiàn)羊群重復回到同一個地方吃草的情況，例如重新回到A地吃草，即重復返回到狀態(tài) $s_A$ 。
因此，在一個經(jīng)驗軌跡里，需要對同一經(jīng)驗軌跡中重復出現(xiàn)的狀態(tài)進行處理，主要有如下兩種方法，一種是首次訪問蒙特卡洛策略評估（First-Visit Monte-Carlo Policy Evaluation）另一種是每次訪問蒙特卡洛策略評估（Every-Visit Monte-Carlo Policy Evaluation）。

首次訪問蒙特卡洛策略評估（First-Visit Monte-Carlo Policy Evaluation）

在給定一個策略，使用一系列完整經(jīng)驗軌跡評估某一個狀態(tài) $s$ 時，對于每一個經(jīng)驗軌跡，僅當該狀態(tài) $s$ 首次出現(xiàn)的時間 $t$ 列入計算：

狀態(tài)出現(xiàn)的次數(shù)加1： $N(s) \leftarrow N(s)+1$
總回報更新： $S(s) \leftarrow S(s)+G_t$
使用平均回報更新值函數(shù)： $V(s) = S(s)/N(s)$
由大數(shù)定理可以得到，當 $N(s)$ 趨于無窮大時： $V(s) \rightarrow v_{\pi}(s)$

每次訪問蒙特卡洛策略評估（First-Visit Monte-Carlo Policy Evaluation）

在給定一個策略，使用一系列完整經(jīng)驗軌跡評估某一個狀態(tài) $s$ 時，對于每一個經(jīng)驗軌跡，僅當該狀態(tài) $s$ 每次出現(xiàn)在狀態(tài)轉(zhuǎn)移鏈時，例如，一次在時刻 $t_1$ ，一次在時刻 $t_2$ ，則兩次對應的 $G_{t_1}$ , $G_{t_2}$ 都應該納入對 $v(s)$ 的計算

狀態(tài)出現(xiàn)的次數(shù)加1： $N(s) \leftarrow N(s)+1$ (每次訪問狀態(tài) $s$ )
總回報更新： $S(s) \leftarrow S(s)+G_t$ (每次訪問狀態(tài) $s$ )
使用平均回報更新值函數(shù)： $V(s) = S(s)/N(s)$
由大數(shù)定理可以得到，當 $N(s)$ 趨于無窮大時： $V(s) \rightarrow v_{\pi}(s)$

5.累進更新平均值（Incremental Mean）

不論是First-Visit還是Every-Visit，在計算回報均值時，都是利用總回報除以狀態(tài)s的總訪問次數(shù)的，我們能否對均值進行增量式的求?。?/p>

這里假設每次的回報為 $x_j$ ，在 $k$ 次后平均回報為：
$\mu_k=\frac{1}{k}\sum_{j=1}^kx_j$
在 $k-1$ 次后平均回報為：
$\mu_{k-1}=\frac{1}{k-1}\sum_{j=1}^{k-1}x_j$
這種增量式的推導過程可以按照如下過程進行：
$\begin{aligned} \mu_k&=\frac{1}{k}\sum_{j=1}^kx_j\\ &=\frac{1}{k}（x_k+\sum_{j=1}^{k-1}x_j)\\ &=\frac{1}{k}（x_k+(k-1)\mu_{k-1})\\ &=\mu_{k-1}+\frac{1}{k}（x_k-\mu_{k-1})\\ \end{aligned}$

6. 蒙特卡洛累進更新(Incremental Monte-Carlo Updates)

對于一系列經(jīng)驗軌跡： $S_0,A_0,R_1,S_1,A_1,R_2,...,S_{T-1},A_{T-1},R_T,S_T$

按照更新平均值的方法可以進行如下累進更新響應的價值函數(shù)：
$\begin{aligned} & N(S_t) \leftarrow N(S_t)+1\\ & V(S_t) \leftarrow V(S_t)+\frac{1}{N(S_t)}(G_t-V（S_t）)\\ &w.r.t \ \ \ \ G_t=R_t+\gamma R_{t+1}+...+\gamma^{T-1} R_{t+T} \end{aligned}$
這里另外說下靜態(tài)問題和非靜態(tài)問題的概念：

靜態(tài)問題就是說我們的MDP是不變的，比如轉(zhuǎn)移矩陣，比如獎勵函數(shù)
非靜態(tài)問題即隨著時間的推移，MDP中的某些參數(shù)將會發(fā)生改變。

這里我們將MC方法變?yōu)樵隽渴剑覀兛梢詳U展開改變 $\frac{1}{N(S_t)}$ ，將他定義為一個類似于學習率的參數(shù) $\alpha$ ，在處理非靜態(tài)問題時，使用這個方法跟蹤一個實時更新的平均值是非常有用的，可以扔掉那些已經(jīng)計算過的episode信息。

引入?yún)?shù) $\alpha$ 后的狀態(tài)價值更新方法可以更改為：
$V(S_t) \leftarrow V(S_t)+\alpha(G_t-V（S_t）)$

7. 蒙特卡洛預測算法偽代碼

7.1 首次訪問型MC預測算法，用于估計 $V \approx v_\pi$

image.png

7.2 蒙特卡洛ES（試探性出發(fā)），用于估計 $\pi \approx \pi_*$

image.png

7.3 離軌策略MC預測算法（策略評估），用于估計 $Q \approx q_{\pi}$

image.png

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

強化學習基礎篇（十五）蒙特卡洛預測