強(qiáng)化學(xué)習(xí)（四）用蒙特卡羅法求解

姓名：白子軒? ? ? ?學(xué)號：21011110229? ? ?學(xué)院：通信工程學(xué)院

轉(zhuǎn)自：https://www.cnblogs.com/pinard/p/9492980.html

【嵌牛導(dǎo)讀】本文將對蒙特卡羅法求解強(qiáng)化學(xué)習(xí)問題進(jìn)行介紹

【嵌牛鼻子】蒙特卡羅

【嵌牛提問】蒙特卡羅算法的優(yōu)缺點(diǎn)？

【嵌牛正文】

在強(qiáng)化學(xué)習(xí)（三）用動態(tài)規(guī)劃（DP）求解中山橄，我們討論了用動態(tài)規(guī)劃來求解強(qiáng)化學(xué)習(xí)預(yù)測問題和控制問題的方法人灼。但是由于動態(tài)規(guī)劃法需要在每一次回溯更新某一個(gè)狀態(tài)的價(jià)值時(shí)敛滋，回溯到該狀態(tài)的所有可能的后續(xù)狀態(tài)。導(dǎo)致對于復(fù)雜問題計(jì)算量很大厘线。同時(shí)很多時(shí)候出刷，我們連環(huán)境的狀態(tài)轉(zhuǎn)化模型 $P$ 都無法知道，這時(shí)動態(tài)規(guī)劃法根本沒法使用姨裸。這時(shí)候我們?nèi)绾吻蠼鈴?qiáng)化學(xué)習(xí)問題呢秧倾？本文要討論的蒙特卡羅(Monte-Calo, MC)就是一種可行的方法怨酝。

不基于模型的強(qiáng)化學(xué)習(xí)問題定義

在動態(tài)規(guī)劃法中傀缩，強(qiáng)化學(xué)習(xí)的兩個(gè)問題是這樣定義的：

預(yù)測問題，即給定強(qiáng)化學(xué)習(xí)的6個(gè)要素：狀態(tài)集 $S$ , 動作集 $A$ , 模型狀態(tài)轉(zhuǎn)化概率矩陣 $P$ , 即時(shí)獎勵(lì) $R$ 农猬，衰減因子 $\gamma$ ,? 給定策略 $\pi$ 赡艰，求解該策略的狀態(tài)價(jià)值函數(shù) $v(\pi)$ 。

控制問題斤葱，也就是求解最優(yōu)的價(jià)值函數(shù)和策略慷垮。給定強(qiáng)化學(xué)習(xí)的5個(gè)要素：狀態(tài)集 $S$ , 動作集 $A$ , 模型狀態(tài)轉(zhuǎn)化概率矩陣 $P$ , 即時(shí)獎勵(lì) $R$ ，衰減因子 $\gamma$ , 求解最優(yōu)的狀態(tài)價(jià)值函數(shù) $v^*$ 和最優(yōu)策略 $\pi^*$

可見, 模型狀態(tài)轉(zhuǎn)化概率矩陣 $P$ 始終是已知的揍堕，即MDP已知料身，對于這樣的強(qiáng)化學(xué)習(xí)問題，我們一般稱為基于模型的強(qiáng)化學(xué)習(xí)問題衩茸。

不過有很多強(qiáng)化學(xué)習(xí)問題芹血，我們沒有辦法事先得到模型狀態(tài)轉(zhuǎn)化概率矩陣 $P$ ，這時(shí)如果仍然需要我們求解強(qiáng)化學(xué)習(xí)問題楞慈，那么這就是不基于模型的強(qiáng)化學(xué)習(xí)問題了幔烛。它的兩個(gè)問題一般的定義是：

預(yù)測問題，即給定強(qiáng)化學(xué)習(xí)的5個(gè)要素：狀態(tài)集 $S$ , 動作集 $A$ , 即時(shí)獎勵(lì) $R$ 囊蓝，衰減因子 $\gamma$ ,? 給定策略 $\pi$ 饿悬，求解該策略的狀態(tài)價(jià)值函數(shù) $v(\pi)$

控制問題，也就是求解最優(yōu)的價(jià)值函數(shù)和策略聚霜。給定強(qiáng)化學(xué)習(xí)的5個(gè)要素：狀態(tài)集 $S$ , 動作集 $A$ , 即時(shí)獎勵(lì) $R$ 狡恬，衰減因子 $\gamma$ , 探索率 $\epsilon$ , 求解最優(yōu)的動作價(jià)值函數(shù) $q^*$ 和最優(yōu)策略 $\pi^*$

本文要討論的蒙特卡羅法就是上述不基于模型的強(qiáng)化學(xué)習(xí)問題珠叔。

蒙特卡羅法求解特點(diǎn)

蒙特卡羅法通過采樣若干經(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ù)測和控制問題了报嵌。

從特卡羅法法的特點(diǎn)來說虱咧，一是和動態(tài)規(guī)劃比，它不需要依賴于模型狀態(tài)轉(zhuǎn)化概率锚国。二是它從經(jīng)歷過的完整序列學(xué)習(xí)腕巡，完整的經(jīng)歷越多，學(xué)習(xí)效果越好血筑。

蒙特卡羅法求解強(qiáng)化學(xué)習(xí)預(yù)測問題

這里我們先來討論蒙特卡羅法求解強(qiáng)化學(xué)習(xí)預(yù)測問題的方法绘沉，即策略評估。一個(gè)給定策略 $\pi$ 的完整有T個(gè)狀態(tài)的狀態(tài)序列如下：

$S_{1}, A_{1}, R_{2}, S_{2}, A_{2}, \ldots S_{t}, A_{t}, R_{t+1}, \ldots R_{T}, S_{T}$

回憶對于價(jià)值函數(shù) $v_\pi(s)$ 的定義:

$v_{\pi}(s)=\mathbb{E}_{\pi}\left(G_{t} \mid S_{t}=s\right)=\mathbb{E}_{\pi}\left(R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\ldots \mid S_{t}=s\right)$

可以看出每個(gè)狀態(tài)的價(jià)值函數(shù)等于所有該狀態(tài)收獲的期望豺总，同時(shí)這個(gè)收獲是通過后續(xù)的獎勵(lì)與對應(yīng)的衰減乘積求和得到车伞。那么對于蒙特卡羅法來說，如果要求某一個(gè)狀態(tài)的狀態(tài)價(jià)值喻喳，只需要求出所有的完整序列中該狀態(tài)出現(xiàn)時(shí)候的收獲再取平均值即可近似求解另玖，也就是：

$\begin{gathered}G_{t}=R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\ldots \gamma^{T-t-1} R_{T} \\v_{\pi}(s) \approx \operatorname{average}\left(G_{t}\right), \text { s.t. } S_{t}=s\end{gathered}$

可以看出，預(yù)測問題的求解思路還是很簡單的表伦。不過有幾個(gè)點(diǎn)可以優(yōu)化考慮谦去。

第一個(gè)點(diǎn)是同樣一個(gè)狀態(tài)可能在一個(gè)完整的狀態(tài)序列中重復(fù)出現(xiàn)，那么該狀態(tài)的收獲該如何計(jì)算蹦哼？有兩種解決方法鳄哭。第一種是僅把狀態(tài)序列中第一次出現(xiàn)該狀態(tài)時(shí)的收獲值納入到收獲平均值的計(jì)算中；另一種是針對一個(gè)狀態(tài)序列中每次出現(xiàn)的該狀態(tài)纲熏，都計(jì)算對應(yīng)的收獲值并納入到收獲平均值的計(jì)算中妆丘。兩種方法對應(yīng)的蒙特卡羅法分別稱為：首次訪問(first visit) 和每次訪問(every visit) 蒙特卡羅法。第二種方法比第一種的計(jì)算量要大一些赤套，但是在完整的經(jīng)歷樣本序列少的場景下會比第一種方法適用飘痛。

第二個(gè)點(diǎn)是累進(jìn)更新平均值（incremental mean)。在上面預(yù)測問題的求解公式里容握，我們有一個(gè)average的公式宣脉，意味著要保存所有該狀態(tài)的收獲值之和最后取平均。這樣浪費(fèi)了太多的存儲空間剔氏。一個(gè)較好的方法是在迭代計(jì)算收獲均值塑猖，即每次保存上一輪迭代得到的收獲均值與次數(shù)竹祷，當(dāng)計(jì)算得到當(dāng)前輪的收獲時(shí)，即可計(jì)算當(dāng)前輪收獲均值和次數(shù)羊苟。通過下面的公式就很容易理解這個(gè)過程：

$\mu_{k}=\frac{1}{k} \sum_{j=1}^{k} x_{j}=\frac{1}{k}\left(x_{k}+\sum_{j=1}^{k-1} x_{j}\right)=\frac{1}{k}\left(x_{k}+(k-1) \mu_{k-1}\right)=\mu_{k-1}+\frac{1}{k}\left(x_{k}-\mu_{k-1}\right)$

這樣上面的狀態(tài)價(jià)值公式就可以改寫成：

$\begin{gathered}N\left(S_{t}\right)=N\left(S_{t}\right)+1 \\V\left(S_{t}\right)=V\left(S_{t}\right)+\frac{1}{N\left(S_{t}\right)}\left(G_{t}-V\left(S_{t}\right)\right)\end{gathered}$

這樣我們無論數(shù)據(jù)量是多還是少塑陵，算法需要的內(nèi)存基本是固定的。

有時(shí)候蜡励，尤其是海量數(shù)據(jù)做分布式迭代的時(shí)候令花，我們可能無法準(zhǔn)確計(jì)算當(dāng)前的次數(shù) $N(S_t)$ ,這時(shí)我們可以用一個(gè)系數(shù) $α$ 來代替，即：

$V(S_t)=V(S_t)+\alpha(G_t-V(S_t))$

對于動作價(jià)值函數(shù) $Q(S_t,A_t)$ ,也是類似的凉倚，比如對上面最后一個(gè)式子兼都，動作價(jià)值函數(shù)版本為：

$Q\left(S_{t}, A_{t}\right)=Q\left(S_{t}, A_{t}\right)+\alpha\left(G_{t}-Q\left(S_{t}, A_{t}\right)\right)$

以上就是蒙特卡羅法求解預(yù)測問題的整個(gè)過程，下面我們來看控制問題求解稽寒。

蒙特卡羅法求解強(qiáng)化學(xué)習(xí)控制問題

蒙特卡羅法求解控制問題的思路和動態(tài)規(guī)劃價(jià)值迭代的的思路類似扮碧。回憶下動態(tài)規(guī)劃價(jià)值迭代的的思路杏糙，每輪迭代先做策略評估慎王，計(jì)算出價(jià)值 $v_k(s)$ ，然后基于據(jù)一定的方法（比如貪婪法）更新當(dāng)前策略 $π$ 宏侍。最后得到最優(yōu)價(jià)值函數(shù) $v^?$ 和最優(yōu)策略 $π^?$ 赖淤。

和動態(tài)規(guī)劃比，蒙特卡羅法不同之處體現(xiàn)在三點(diǎn)：一是預(yù)測問題策略評估的方法不同负芋，這個(gè)第三節(jié)已經(jīng)講了漫蛔。第二是蒙特卡羅法一般是優(yōu)化最優(yōu)動作價(jià)值函數(shù) $q^?$ 嗜愈，而不是狀態(tài)價(jià)值函數(shù) $v^?$ 旧蛾。三是動態(tài)規(guī)劃一般基于貪婪法更新策略。而蒙特卡羅法一般采用??貪婪法更新蠕嫁。這個(gè)?就是我們在強(qiáng)化學(xué)習(xí)（一）模型基礎(chǔ)中講到的第8個(gè)模型要素?锨天。??貪婪法通過設(shè)置一個(gè)較小的?值，使用1??的概率貪婪地選擇目前認(rèn)為是最大行為價(jià)值的行為剃毒，而用? 的概率隨機(jī)的從所有m 個(gè)可選行為中選擇行為病袄。用公式可以表示為：

$\pi(a \mid s)= \begin{cases}\epsilon / m+1-\epsilon & \text { if } a^{*}=\arg \max _{a \in A} Q(s, a) \\ \epsilon / m & \text { else }\end{cases}$

在實(shí)際求解控制問題時(shí)，為了使算法可以收斂赘阀，一般??會隨著算法的迭代過程逐漸減小益缠，并趨于0。這樣在迭代前期基公，我們鼓勵(lì)探索幅慌，而在后期，由于我們有了足夠的探索量轰豆，開始趨于保守胰伍，以貪婪為主齿诞，使算法可以穩(wěn)定收斂。這樣我們可以得到一張和動態(tài)規(guī)劃類似的圖：

蒙特卡羅法控制問題算法流程

在這里總結(jié)下蒙特卡羅法求解強(qiáng)化學(xué)習(xí)控制問題的算法流程骂租，這里的算法是在線(on-policy)版本的,相對的算法還有離線(off-policy)版本的祷杈。在線和離線的區(qū)別我們在后續(xù)的文章里面會講。同時(shí)這里我們用的是every-visit,即個(gè)狀態(tài)序列中每次出現(xiàn)的相同狀態(tài)渗饮，都會計(jì)算對應(yīng)的收獲值但汞。

在線蒙特卡羅法求解強(qiáng)化學(xué)習(xí)控制問題的算法流程如下:

輸入：狀態(tài)集 $S$ , 動作集 $A$ , 即時(shí)獎勵(lì) $R$ ，衰減因子 $γ$ , 探索率 $?$

輸出：最優(yōu)的動作價(jià)值函數(shù) $q^?$ 和最優(yōu)策略 $π^?$

1. 初始化所有的動作價(jià)值 $Q(s,a)=0$ 互站，狀態(tài)次數(shù) $N(s,a)=0$ 特占，采樣次數(shù) $k=0$ ，隨機(jī)初始化一個(gè)策略 $\pi$

2. k=k+1, 基于策略 $π$ 進(jìn)行第k次蒙特卡羅采樣云茸，得到一個(gè)完整的狀態(tài)序列:

? ?????? $S_{1}, A_{1}, R_{2}, S_{2}, A_{2}, \ldots S_{t}, A_{t}, R_{t+1}, \ldots R_{T}, S_{T}$

3.?對于該狀態(tài)序列里出現(xiàn)的每一狀態(tài)行為對 $(S_t,A_t)$ 是目，計(jì)算其收獲 $G_t$ , 更新其計(jì)數(shù) $N(s,a)$ 和行為價(jià)值函數(shù) $Q(s,a)$ ：

? ?????? $G_{t}=R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\ldots \gamma^{T-t-1} R_{T}$

? ?????? $N\left(S_{t}, A_{t}\right)=N\left(S_{t}, A_{t}\right)+1$

? ?????? $Q\left(S_{t}, A_{t}\right)=Q\left(S_{t}, A_{t}\right)+\frac{1}{N\left(S_{t}, A_{t}\right)}\left(G_{t}-Q\left(S_{t}, A_{t}\right)\right)$

4. 基于新計(jì)算出的動作價(jià)值，更新當(dāng)前的??貪婪策略：

$\epsilon=\frac{1}{k}$

$\pi(a \mid s)= \begin{cases}\epsilon / m+1-\epsilon & \text { if } a^{*}=\arg \max _{a \in A} Q(s, a) \\ \epsilon / m & \text { else }\end{cases}$

蒙特卡羅法求解強(qiáng)化學(xué)習(xí)問題小結(jié)

蒙特卡羅法是我們第二個(gè)講到的求解強(qiáng)化問題的方法标捺，也是第一個(gè)不基于模型的強(qiáng)化問題求解方法懊纳。它可以避免動態(tài)規(guī)劃求解過于復(fù)雜，同時(shí)還可以不事先知道環(huán)境轉(zhuǎn)化模型亡容，因此可以用于海量數(shù)據(jù)和復(fù)雜模型嗤疯。但是它也有自己的缺點(diǎn)，這就是它每次采樣都需要一個(gè)完整的狀態(tài)序列闺兢。如果我們沒有完整的狀態(tài)序列茂缚，或者很難拿到較多的完整的狀態(tài)序列，這時(shí)候蒙特卡羅法就不太好用了屋谭，也就是說脚囊，我們還需要尋找其他的更靈活的不基于模型的強(qiáng)化問題求解方法。

最后編輯于：2021.12.08 21:12:59

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末桐磁，一起剝皮案震驚了整個(gè)濱河市悔耘，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌我擂，老刑警劉巖衬以，帶你破解...
沈念sama閱讀 219,270評論 6贊 508
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異校摩，居然都是意外死亡看峻，警方通過查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,489評論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門衙吩，熙熙樓的掌柜王于貴愁眉苦臉地迎上來互妓，“玉大人，你說我怎么就攤上這事〕碘” “怎么了霉猛？”我有些...
開封第一講書人閱讀 165,630評論 0贊 356
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長珠闰。經(jīng)常有香客問我惜浅，道長，這世上最難降的妖魔是什么伏嗜？我笑而不...
開封第一講書人閱讀 58,906評論 1贊 295
?港島之戀（遺憾婚禮）
正文為了忘掉前任坛悉，我火速辦了婚禮，結(jié)果婚禮上承绸，老公的妹妹穿的比我還像新娘裸影。我一直安慰自己，他們只是感情好军熏，可當(dāng)我...
茶點(diǎn)故事閱讀 67,928評論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布轩猩。她就那樣靜靜地躺著，像睡著了一般荡澎。火紅的嫁衣襯著肌膚如雪均践。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 51,718評論 1贊 305
城市分裂傳說
那天摩幔，我揣著相機(jī)與錄音彤委，去河邊找鬼。笑死或衡，一個(gè)胖子當(dāng)著我的面吹牛焦影，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播封断，決...
沈念sama閱讀 40,442評論 3贊 420
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼斯辰，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了澄港？” 一聲冷哼從身側(cè)響起椒涯，我...
開封第一講書人閱讀 39,345評論 0贊 276
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤柄沮，失蹤者是張志新（化名）和其女友劉穎回梧，沒想到半個(gè)月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體祖搓，經(jīng)...
沈念sama閱讀 45,802評論 1贊 317
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡狱意，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,984評論 3贊 337
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了拯欧。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片详囤。...
茶點(diǎn)故事閱讀 40,117評論 1贊 351
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出藏姐，到底是詐尸還是另有隱情隆箩，我是刑警寧澤，帶...
沈念sama閱讀 35,810評論 5贊 346
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布羔杨，位于F島的核電站捌臊，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏兜材。R本人自食惡果不足惜理澎，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,462評論 3贊 331
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望曙寡。院中可真熱鬧糠爬，春花似錦、人聲如沸举庶。這莊子的主人今日做“春日...
開封第一講書人閱讀 32,011評論 0贊 22
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽户侥。三九已至殴玛，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間添祸，已是汗流浹背滚粟。一陣腳步聲響...
開封第一講書人閱讀 33,139評論 1贊 272
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留刃泌，地道東北人凡壤。一個(gè)月前我還...
沈念sama閱讀 48,377評論 3贊 373
代替公主和親
正文我出身青樓，卻偏偏與公主長得像耙替，于是被迫代替她去往敵國和親亚侠。傳聞我的和親對象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 45,060評論 2贊 355