蒙特卡洛方法求解：
由于動態(tài)規(guī)劃法需要在每一次回溯更新某一個狀態(tài)的價值時，回溯到該狀態(tài)的所有可能的后續(xù)狀態(tài)。導(dǎo)致對于復(fù)雜問題計算量很大。同時很多時候，我們連環(huán)境的狀態(tài)轉(zhuǎn)化模型PP都無法知道，這時動態(tài)規(guī)劃法根本沒法使用。這時需要使用蒙特卡洛方法
動態(tài)規(guī)劃法中，強(qiáng)化學(xué)習(xí)的兩個問題里模型狀態(tài)轉(zhuǎn)化概率矩陣P始終是已知的，即MDP已知，對于這樣的強(qiáng)化學(xué)習(xí)問題，我們一般稱為基于模型的強(qiáng)化學(xué)習(xí)問題。
不基于模型的強(qiáng)化學(xué)習(xí)問題了。它的兩個問題一般的定義是：
預(yù)測問題，即給定強(qiáng)化學(xué)習(xí)的5個要素：狀態(tài)集S, 動作集A, 即時獎R，衰減因子γ,? 給定策略π， 求解該策略的狀態(tài)價值函數(shù)v(π)
控制問題，也就是求解最優(yōu)的價值函數(shù)和策略。給定強(qiáng)化學(xué)習(xí)的5個要素：狀態(tài)集S, 動作集A, 即時獎勵R，衰減因子γ, 探索率?, 求解最優(yōu)的動作價值函q?和最優(yōu)策略π?
蒙特卡羅法通過采樣若干經(jīng)歷完整的狀態(tài)序列(episode)來估計狀態(tài)的真實價值。所謂的經(jīng)歷完整，就是這個序列必須是達(dá)到終點的。比如下棋問題分出輸贏，駕車問題成功到達(dá)終點或者失敗。有了很多組這樣經(jīng)歷完整的狀態(tài)序列，我們就可以來近似的估計狀態(tài)價值，進(jìn)而求解預(yù)測和控制問題了。
從特卡羅法法的特點來說，一是和動態(tài)規(guī)劃比，它不需要依賴于模型狀態(tài)轉(zhuǎn)化概率。二是它從經(jīng)歷過的完整序列學(xué)習(xí)，完整的經(jīng)歷越多，學(xué)習(xí)效果越好。
蒙特卡羅法求解強(qiáng)化學(xué)習(xí)預(yù)測：
一個給定策略π的完整有T個狀態(tài)的狀態(tài)序列如下：
每個狀態(tài)的價值函數(shù)等于所有該狀態(tài)收獲的期望，同時這個收獲是通過后續(xù)的獎勵與對應(yīng)的衰減乘積求和得到。那么對于蒙特卡羅法來說，如果要求某一個狀態(tài)的狀態(tài)價值，只需要求出所有的完整序列中該狀態(tài)出現(xiàn)時候的收獲再取平均值即可近似求解，也就是：
有幾個點可以優(yōu)化考慮。
第一個點是同樣一個狀態(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)歷樣本序列少的場景下會比第一種方法適用。
第二個點是累進(jìn)更新平均值（incremental mean)。在上面預(yù)測問題的求解公式里，我們有一個average的公式，意味著要保存所有該狀態(tài)的收獲值之和最后取平均。這樣浪費(fèi)了太多的存儲空間。一個較好的方法是在迭代計算收獲均值，即每次保存上一輪迭代得到的收獲均值與次數(shù)，當(dāng)計算得到當(dāng)前輪的收獲時，即可計算當(dāng)前輪收獲均值和次數(shù)。通過下面的公式就很容易理解這個過程：
有時候，尤其是海量數(shù)據(jù)做分布式迭代的時候，我們可能無法準(zhǔn)確計算當(dāng)前的次數(shù)N(St),這時我們可以用一個系數(shù)α來代替，即
蒙特卡羅法求解強(qiáng)化學(xué)習(xí)控制問題：
蒙特卡羅法求解控制問題的思路和動態(tài)規(guī)劃價值迭代的的思路類似，和動態(tài)規(guī)劃比，蒙特卡羅法不同之處體現(xiàn)在三點：一是預(yù)測問題策略評估的方法不同，這個第三節(jié)已經(jīng)講了。第二是蒙特卡羅法一般是優(yōu)化最優(yōu)動作價值函數(shù)q?，而不是狀態(tài)價值函數(shù)v?。三是動態(tài)規(guī)劃一般基于貪婪法更新策略。而蒙特卡羅法一般采用??貪婪法更新。
???貪婪法通過設(shè)置一個較小的?值，使用1??的概率貪婪地選擇目前認(rèn)為是最大行為價值的行為，而用?的概率隨機(jī)的從所有m 個可選行為中選擇行為。用公式可以表示為：
可以避免動態(tài)規(guī)劃求解過于復(fù)雜，同時還可以不事先知道環(huán)境轉(zhuǎn)化模型，因此可以用于海量數(shù)據(jù)和復(fù)雜模型。但是它也有自己的缺點，這就是它每次采樣都需要一個完整的狀態(tài)序列。如果我們沒有完整的狀態(tài)序列，或者很難拿到較多的完整的狀態(tài)序列，這時候蒙特卡羅法就不太好用了， 也就是說，我們還需要尋找其他的更靈活的不基于模型的強(qiáng)化問題求解方法
時序差分（TD）方法：
蒙特卡羅法中計算狀態(tài)收獲的方法是：
對于時序差分法來說，我們沒有完整的狀態(tài)序列，只有部分的狀態(tài)序列，回顧貝爾曼方程：
這樣我們只需要兩個連續(xù)的狀態(tài)與對應(yīng)的獎勵，就可以嘗試求解強(qiáng)化學(xué)習(xí)問題了
時序差分TD的預(yù)測問題求解：
和蒙特卡羅法類似，但是主要有兩個不同點。一是收獲Gt的表達(dá)式不同
二是迭代的式子系數(shù)稍有不同
由于在時序差分我們沒有完整的序列，也就沒有對應(yīng)的次數(shù)NSt),一般就用一個[0,1]的系數(shù)α代替。這樣時序差分的價值函數(shù)迭代式子是：
一是時序差分法在知道結(jié)果之前就可以學(xué)習(xí)，也可以在沒有結(jié)果時學(xué)習(xí)，還可以在持續(xù)進(jìn)行的環(huán)境中學(xué)習(xí)，而蒙特卡羅法則要等到最后結(jié)果才能學(xué)習(xí)，時序差分法可以更快速靈活的更新狀態(tài)的價值估計，這在某些情況下有著非常重要的實際意義。
二是時序差分法在更新狀態(tài)價值時使用的是TD 目標(biāo)值，即基于即時獎勵和下一狀態(tài)的預(yù)估價值來替代當(dāng)前狀態(tài)在狀態(tài)序列結(jié)束時可能得到的收獲，是當(dāng)前狀態(tài)價值的有偏估計，而蒙特卡羅法則使用實際的收獲來更新狀態(tài)價值，是某一策略下狀態(tài)價值的無偏估計，這一點蒙特卡羅法占優(yōu)。
三是雖然時序差分法得到的價值是有偏估計，但是其方差卻比蒙特卡羅法得到的方差要低，且對初始值敏感，通常比蒙特卡羅法更加高效。
從上面的描述可以看出時序差分法的優(yōu)勢比較大，因此現(xiàn)在主流的強(qiáng)化學(xué)習(xí)求解方法都是基于時序差分的。后面的文章也會主要基于時序差分法來擴(kuò)展討論。
n步時序差分：
能不能向前兩步呢，這時我們的收獲GT的近似表達(dá)式為：
n步時序差分收獲
n到底是多少步好呢？如何衡量n的好壞呢？
n步時序差分選擇多少步數(shù)作為一個較優(yōu)的計算參數(shù)是需要嘗試的超參數(shù)調(diào)優(yōu)問題。為了能在不增加計算復(fù)雜度的情況下綜合考慮所有步數(shù)的預(yù)測，我們引入了一個新[0,1]的參數(shù)λ，定義λ?收獲是n從1到∞所有步的收獲乘以權(quán)重的和。每一步的權(quán)重是(1?λ)λn?1，這樣λ?收獲的計算公式表示為：
進(jìn)而
當(dāng)λ=0?時,就是第二節(jié)講到的普通的時序差分法，當(dāng)λ=1?時,就是蒙特卡羅法。
