作者：劉建平           

編輯：陳人和           

在強(qiáng)化學(xué)習(xí)（三）用動態(tài)規(guī)劃（DP）求解中，我們討論了用動態(tài)規(guī)劃來求解強(qiáng)化學(xué)習(xí)預(yù)測問題和控制問題的方法。但是由于動態(tài)規(guī)劃法需要在每一次回溯更新某一個狀態(tài)的價值時，回溯到該狀態(tài)的所有可能的后續(xù)狀態(tài)。導(dǎo)致對于復(fù)雜問題計算量很大。同時很多時候，我們連環(huán)境的狀態(tài)轉(zhuǎn)化模型P都無法知道，這時動態(tài)規(guī)劃法根本沒法使用。這時候我們?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í)的兩個問題是這樣定義的：

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

控制問題，也就是求解最優(yōu)的價值函數(shù)和策略。給定強(qiáng)化學(xué)習(xí)的5個要素：狀態(tài)集S，動作集A，模型狀態(tài)轉(zhuǎn)化概率矩陣P， 即時獎勵R，衰減因子，求解最優(yōu)的狀態(tài)價值函數(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，這時如果仍然需要我們求解強(qiáng)化學(xué)習(xí)問題，那么這就是不基于模型的強(qiáng)化學(xué)習(xí)問題了。它的兩個問題一般的定義是：

預(yù)測問題，即給定強(qiáng)化學(xué)習(xí)的5個要素：狀態(tài)集S，動作集A，即時獎勵R，衰減因子，給定策略，求解該策略的狀態(tài)價值函數(shù)。

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

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

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

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

蒙特卡羅法通過采樣若干經(jīng)歷完整的狀態(tài)序列(episode)來估計狀態(tài)的真實(shí)價值。所謂的經(jīng)歷完整，就是這個序列必須是達(dá)到終點(diǎn)的。比如下棋問題分出輸贏，駕車問題成功到達(dá)終點(diǎn)或者失敗。有了很多組這樣經(jīng)歷完整的狀態(tài)序列，我們就可以來近似的估計狀態(tài)價值，進(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ù)測問題的方法，即策略評估。一個給定策略的完整有T個狀態(tài)的狀態(tài)序列如下：

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

的定義：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

輸入：狀態(tài)集S，動作集A，即時獎勵R，衰減因子，探索

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

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

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

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

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

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

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

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

END