作者：劉建平           

編輯：陳人和           

在強(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í)問題定義

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

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

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

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

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

不基于模型的強(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í)獎(jiǎng)勵(lì)R，衰減因子，給定策略，求解該策略的狀態(tài)價(jià)值函數(shù)。

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

可見, 模型狀態(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í)獎(jiǎng)勵(lì)R，衰減因子，給定策略，求解該策略的狀態(tài)價(jià)值函數(shù)。

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

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

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

蒙特卡羅這個(gè)詞之前的博文也討論過，尤其是在之前的MCMC系列中。它是一種通過采樣近似求解問題的方法。這里的蒙特卡羅法雖然和MCMC不同，但是采樣的思路還是一致的。那么如何采樣呢？

蒙特卡羅法通過采樣若干經(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è)給定策略的完整有T個(gè)狀態(tài)的狀態(tài)序列如下：

回憶下強(qiáng)化學(xué)習(xí)（二）馬爾科夫決策過程(MDP)中對于價(jià)值函數(shù)

的定義：

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

可以看出，預(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è)過程：

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

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

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

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

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

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

蒙特卡羅法求解控制問題的思路和動態(tài)規(guī)劃價(jià)值迭代的的思路類似?；貞浵聞討B(tài)規(guī)劃價(jià)值迭代的的思路， 每輪迭代先做策略評估，計(jì)算出價(jià)值，然后基于據(jù)一定的方法（比如貪婪法）更新當(dāng)前策略。最后得到最優(yōu)價(jià)值函數(shù)和最優(yōu)策略。和動態(tài)規(guī)劃比，蒙特卡羅法不同之處體現(xiàn)在三點(diǎn)：一是預(yù)測問題策略評估的方法不同，這個(gè)第三節(jié)已經(jīng)講了。第二是蒙特卡羅法一般是優(yōu)化最優(yōu)動作價(jià)值函數(shù)，而不是狀態(tài)價(jià)值函數(shù)。三是動態(tài)規(guī)劃一般基于貪婪法更新策略。而蒙特卡羅法一般采用貪婪法更新。這個(gè)就是我們在強(qiáng)化學(xué)習(xí)（一）模型基礎(chǔ)中講到的第8個(gè)模型要素。貪婪法通過設(shè)置一個(gè)較小的值，使用的概率貪婪地選擇目前認(rèn)為是最大行為價(jià)值的行為，而用的概率隨機(jī)的從所有m 個(gè)可選行為中選擇行為。用公式可以表示為：的概率隨機(jī)的從所有m 個(gè)可選行為中選擇行為。用公式可以表示為：的概率隨機(jī)的從所有m 個(gè)可選行為中選擇行為。用公式可以表示為：

在實(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í)獎(jiǎng)勵(lì)R，衰減因子，探索

輸出：最優(yōu)的動作價(jià)值函數(shù)和最優(yōu)策

1. 初始化所有的動作價(jià)值，狀態(tài)次數(shù)，采樣次數(shù)k=0，隨機(jī)初始化一個(gè)策略

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

3. 對于該狀態(tài)序列里出現(xiàn)的每一狀態(tài)行為對，計(jì)算其收獲，更新其計(jì)數(shù)和行為價(jià)值函數(shù)：        

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

5.如果所有的收斂，則對應(yīng)的所有即為最優(yōu)的動作價(jià)值函數(shù)。對應(yīng)的策略即為最優(yōu)策略。否則轉(zhuǎn)到第二步。

蒙特卡羅法求解強(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)化問題求解方法。

END