第二篇文章是整個(gè)強(qiáng)化學(xué)習(xí)基礎(chǔ)知識(shí)中最重要的，請(qǐng)大家保持警惕。前面系列一我把馬爾科夫獎(jiǎng)賞過程的全部?jī)?nèi)容講完了，下面開始分析馬爾科夫決策過程，寫作思路依然是參考Divad Silver強(qiáng)化學(xué)習(xí)課程ppt,由于本人水平有限，如有問題，歡迎指正，我即時(shí)修改，謝謝！ 
       本文思路：

馬爾科夫獎(jiǎng)賞過程是在馬爾科夫過程基礎(chǔ)上增加了獎(jiǎng)勵(lì)和衰減因子，從而引入了狀態(tài)值函數(shù)，而馬爾科夫決策過程MDP是在馬爾科夫獎(jiǎng)賞過程基礎(chǔ)上引入了action或者說決策，從而將問題徹底轉(zhuǎn)化為了決策問題，這才真正進(jìn)入了強(qiáng)化學(xué)習(xí)路線！MDP問題雖然是加了決策，但是優(yōu)化對(duì)象依然是值函數(shù)(當(dāng)然還可以其他方式，例如最優(yōu)策略)，當(dāng)最優(yōu)的值函數(shù)求出后，最優(yōu)決策其實(shí)也就確定了，后面會(huì)細(xì)說。
       MDP的官方定義如下：

可以明顯看出，和MRP的不同就是多引入了一個(gè)A，代表一系列動(dòng)作集。同時(shí)需要注意了：相應(yīng)的P和R都已經(jīng)改變了，都是需要考慮A的，也就是說由于action的引入會(huì)影響狀態(tài)轉(zhuǎn)移矩陣P和相應(yīng)的回報(bào)R，這是非常容易理解的，比如說平時(shí)我罵你，你可能不會(huì)轉(zhuǎn)移到生氣這個(gè)狀態(tài)，但是如果我打你一下，再罵你的話，那么你就很可能會(huì)轉(zhuǎn)移到生氣這個(gè)狀態(tài)了。當(dāng)然回報(bào)也是有影響的。依然以學(xué)生為例，現(xiàn)在學(xué)生的狀態(tài)轉(zhuǎn)移圖變成了如下圖：

作為對(duì)比，可以看下以前的圖：

大家發(fā)現(xiàn)區(qū)別了吧。同一個(gè)狀態(tài)下采取不同的行為得到的即時(shí)獎(jiǎng)勵(lì)是不一樣的。MRP里面的狀態(tài)現(xiàn)在變成了MDP里面的ation，而MDP里面的狀態(tài)就直接用空心圓圈代替了，也就是說MDP和MRP即使都是求最優(yōu)值函數(shù)，但是意義是不一樣的，MDP求出的最優(yōu)值函數(shù)其實(shí)就直接表征了最優(yōu)決策。大家要習(xí)慣這種轉(zhuǎn)變。

既然引入了動(dòng)作，那么就需要引入新的概念了。策略是概率的集合或分布，其元素 為對(duì)過程中的某一狀態(tài)s采取可能的行為a的概率,用表示?？赡艽蠹視?huì)很疑惑這個(gè)東西，其實(shí)它的意思是動(dòng)作action是一個(gè)關(guān)于狀態(tài)的布，以上圖為例：在MRP圖的class2狀態(tài)處，我執(zhí)行action{sleep，study}是有概率的，我有0.8的概率去執(zhí)行study，有0.2的概率去執(zhí)行sleep,這就是一個(gè)；在執(zhí)行去酒吧pub的action后，學(xué)生有{0.2,0.4,0.4}的概率轉(zhuǎn)向三個(gè)狀態(tài)，這就是狀態(tài)轉(zhuǎn)移概率，可以看出和action有關(guān)，又或者舉例：小型無人機(jī)特技表演，現(xiàn)在我發(fā)出一個(gè)往上飛的action，但是飛機(jī)就一定會(huì)進(jìn)入往上飛的狀態(tài)嗎？其實(shí)不一定，因?yàn)檫€有風(fēng)向、風(fēng)速、干擾的影響，所以說我在某個(gè)狀態(tài)下，采取的action是一個(gè)分布（policy），采用某個(gè)action后，進(jìn)入某個(gè)狀態(tài)也是一個(gè)分布(P)，如果我能夠把風(fēng)向、風(fēng)速、干擾的影響完全考慮進(jìn)去，那么這個(gè)MDP問題的最優(yōu)決策就比較完美了，但是實(shí)際上是不可能的。
       policy的定義是：

有了上面的分析，看這個(gè)公式應(yīng)該非常好理解了吧。其實(shí)可以直接理解為在每一個(gè)狀態(tài)和狀態(tài)中插入了一個(gè)實(shí)心黑點(diǎn)而已，這個(gè)黑點(diǎn)就是action，后面會(huì)細(xì)說。

剛才說過引入了策略后，狀態(tài)轉(zhuǎn)移概率P和回報(bào)R都和action有關(guān)了，那么公式肯定也要稍微修改一下了。

按照ppt中標(biāo)準(zhǔn)寫法是：當(dāng)給和一個(gè)策略，那么狀態(tài)序列是一個(gè)馬爾科夫過程；同樣，狀態(tài)和獎(jiǎng)勵(lì)序列 是一個(gè)馬爾科夫獎(jiǎng)勵(lì)過程，并且在這個(gè)獎(jiǎng)勵(lì)過程中滿足下面兩個(gè)方程:

      舉上圖例子來說明：為了方便表述，將MRP中{facebook,class1,class2,class3,pass,pub,sleep}狀態(tài)順序?qū)?yīng)的MDP中的空心圓圈狀態(tài){s1,s2,s3,s4,s5},我沒有畫圖，大家應(yīng)該知道哪個(gè)對(duì)應(yīng)哪個(gè)吧？假設(shè)要計(jì)算

的值，按照公式，因?yàn)樵趕3狀態(tài)下，執(zhí)行study的概率是0.8，而在study動(dòng)作下，由s3轉(zhuǎn)移到s4是必然的，所以概率是1。再寫一個(gè)復(fù)雜點(diǎn)的，計(jì)算，不好意思，我算不出了，因?yàn)槁窂綄?shí)在是太多了，可以是sleep,s3->s5；可以是study,s3-s4，然后study,s4->s5；可以是stduy,s3->s4,然后pub,s4->s3,sleep,s3->s5，這里面還有l(wèi)oop，要把這些所有路徑的概率求和才算完成(ps:那實(shí)際上該如何計(jì)算呢？還是迭代法求解)。同樣的對(duì)于回報(bào)R，算法是完全一致的。

前面算了一大堆的其實(shí)本質(zhì)就是為了值函數(shù)服務(wù)的，因?yàn)榍懊嬲f過強(qiáng)化學(xué)習(xí)目的就是最大化值函數(shù)。好的，現(xiàn)在引入了策略，有些地方就得改改了，這就引入了兩個(gè)值函數(shù)：狀態(tài)值函數(shù)state-value function和動(dòng)作值函數(shù)action-value funtion。完整定義如下：

狀態(tài)值函數(shù)的定義沒變，只不過多了一個(gè)動(dòng)作值函數(shù)或者行為值函數(shù)，表示在執(zhí)行策略π時(shí)，對(duì)當(dāng)前狀態(tài)s執(zhí)行某一具體行為a所能的到的收獲的期望；或者說在遵循當(dāng)前策略π時(shí)，衡量對(duì)當(dāng)前狀態(tài)執(zhí)行行為a的價(jià)值大小。這樣看感覺不好理解，下面看具體例子：

       例如要求2.7那個(gè)狀態(tài)下的值函數(shù)那個(gè)狀態(tài)），直接算你會(huì)發(fā)現(xiàn)算不了，因?yàn)楹罄m(xù)路徑非常多，而要求那個(gè)狀態(tài)，a=study)發(fā)現(xiàn)也不好算，因?yàn)槁窂竭€是很多，那么真正解決該問題的辦法依然是迭代法，那么依然要引入牛逼的貝爾曼期望方程，一切問題就都不是問題。關(guān)于上圖中的狀態(tài)值函數(shù)具體數(shù)值，大家學(xué)到這里是肯定不知道如何算出來的，需要用到后面的貝爾曼期望方程。

前面只是定義了MDP下的狀態(tài)值函數(shù)和行為值函數(shù)，但是直接算是算不出來的，這是貝爾曼期望方程就出場(chǎng)了。貝爾曼期望方程是用于將值函數(shù)轉(zhuǎn)化為迭代求解方程，使得問題更容易求解。大家如果理解了MRP中的貝爾曼方程，那么這里也非常好理解了。首先是狀態(tài)值函數(shù):

同樣，動(dòng)作值函數(shù):

，是不是感覺很亂，看到下面的圖你就會(huì)豁然開朗了：

圖中，空心白圓圈是狀態(tài)-狀態(tài)值函數(shù)對(duì)；黑心實(shí)圓圈是動(dòng)作-動(dòng)作值函數(shù)對(duì)

可以看出，狀態(tài)值函數(shù)v和動(dòng)作值函數(shù)q是有關(guān)系的

如果不打算顯視的求動(dòng)作值函數(shù)，那么可以使用上圖形式。

如果不打算顯示的求狀態(tài)值函數(shù)，那么可以使用上圖形?？吹搅藳]，通過貝爾曼期望方程，這樣就轉(zhuǎn)化為了迭代形式了，求解就容易多了。
       依然以學(xué)生為例：

好了，現(xiàn)在我們已經(jīng)能算任意給定策略action下，每個(gè)狀態(tài)的值函數(shù)取值了，不管你是采用迭代法還是線性代數(shù)法。但是現(xiàn)在又有一個(gè)問題了：那么哪種策略下，能夠使得狀態(tài)s的值函數(shù)最大呢？因?yàn)橐坏┪覀冋页鰜碜顑?yōu)值函數(shù)，也就是找出來最優(yōu)策略，然后一直執(zhí)行該策略就好了。舉例說明：假設(shè)要訓(xùn)練一個(gè)機(jī)器人快速走迷宮，現(xiàn)在我給定一些策略，該策略可以使得機(jī)器人走出去，在該策略下，我通過迭代法可以求出每個(gè)狀態(tài)的值函數(shù)，然后依據(jù)累積回報(bào)最大化原則，就可以選出一條當(dāng)前最優(yōu)的策略了，但是你確定你給的就是最優(yōu)策略了嗎？假設(shè)我再給其他一些策略，它得到的狀態(tài)值函數(shù)更大呢，那么說明我給的策略是更優(yōu)的?，F(xiàn)在有一個(gè)疑問：既然我自己知道最優(yōu)路徑是哪個(gè)，那我就直接給定最優(yōu)策略就好了嘛，還強(qiáng)化學(xué)習(xí)啥呀？其實(shí)不是的，對(duì)于特別復(fù)雜問題，我們自己也不知道最優(yōu)策略是啥，只能通過機(jī)器人自己探索和開發(fā)出來，不需要人為的干擾，這就涉及到后面的策略估計(jì)和策略提升步驟了。上面我們舉的學(xué)生例子，他的策略是已經(jīng)給定了，雖然策略也是一個(gè)概率分布。
       上面是一些補(bǔ)充說明，下面是正式定義：

最優(yōu)狀態(tài)價(jià)值函數(shù) 指的是在從所有策略產(chǎn)生的狀態(tài)價(jià)值函數(shù)中，選取使?fàn)顟B(tài)s價(jià)值最大的函數(shù)，同理，最優(yōu)動(dòng)作價(jià)值函數(shù) 指的是從所有策略產(chǎn)生的動(dòng)作價(jià)值函數(shù)中，選取是狀態(tài)行為對(duì) 價(jià)值最大的函數(shù)，最優(yōu)價(jià)值函數(shù)確定了MDP的最優(yōu)可能表現(xiàn)，當(dāng)我們知道了最優(yōu)價(jià)值函數(shù)，也就知道了每個(gè)狀態(tài)的最優(yōu)價(jià)值，那么此時(shí)該MDP的所有量我們已經(jīng)知道，MDP問題就解決了。所以說最優(yōu)值函數(shù)表達(dá)式只是給出了一個(gè)結(jié)論，具體如何算最優(yōu)值函數(shù)，目前還沒有說。依然以學(xué)生為例子，其最優(yōu)狀態(tài)值函數(shù)和最優(yōu)行為值函數(shù)如圖所示：

最優(yōu)狀態(tài)值函數(shù)如上圖

最優(yōu)行為值函數(shù)如上圖，后面在進(jìn)行分析。對(duì)于上面兩幅圖中的數(shù)字具體是如何算出來的，暫時(shí)可以不用管，其實(shí)可以通過后面的貝爾曼最優(yōu)方程解出來的。

最優(yōu)策略的定義如下：

關(guān)于MDP的最優(yōu)策略，有如下定理：
1. 對(duì)于任何MDP問題，存在一個(gè)最優(yōu)策略，好于（至少相等）任何其他策略
2. 所有的最優(yōu)策略下都有相同的最優(yōu)價(jià)值函數(shù)
3. 所有的最優(yōu)策略下都具有相同的行為價(jià)值函數(shù)
既然有上述定理，那么尋找最優(yōu)策略就可以通過最大化最優(yōu)行為價(jià)值函數(shù)來得到。同時(shí)如果我們知道最優(yōu)行為價(jià)值函數(shù)，則表明我們找到了最優(yōu)策略，也就是說尋找最優(yōu)策略可以通過尋找最優(yōu)狀態(tài)值函數(shù)得到。尋找最優(yōu)策略的定義如下：

以學(xué)生為例子，其最優(yōu)策略如下(紅色的弧代表在該狀態(tài)下最優(yōu)的動(dòng)作，所有的狀態(tài)和相應(yīng)的動(dòng)作組合起來也就是最優(yōu)的策略):

這幅圖是告訴我們：如果已經(jīng)求出了最優(yōu)值函數(shù)，那么最優(yōu)策略是非常容易求出來的；當(dāng)然我也可以使用其他辦法不求最優(yōu)值函數(shù)，而是直接求最優(yōu)策略。

在最優(yōu)值函數(shù)中，如果求出了最優(yōu)狀態(tài)值函數(shù)，其實(shí)也就求出了最優(yōu)行為值函數(shù)，反之同理；在最優(yōu)策略中，如果求出了最優(yōu)值函數(shù)，那么最優(yōu)策略就求出來了，反之同理；這樣就把最優(yōu)策略、最優(yōu)狀態(tài)值函數(shù)、最優(yōu)行為值函數(shù)聯(lián)系起來了。好的，前面假設(shè)了一大堆前提，那么如何求最優(yōu)狀態(tài)值函數(shù)或者最優(yōu)行為值函數(shù)呢？這就需要使用本節(jié)的貝爾曼最優(yōu)方程了。針對(duì)，一個(gè)狀態(tài)的最優(yōu)價(jià)值等于從該狀態(tài)出發(fā)采取的所有行為而產(chǎn)生的行為價(jià)值中最大的那個(gè)行為價(jià)值

上圖表示左邊的action可以產(chǎn)生最大的價(jià)值，所以應(yīng)該選擇左邊的策略。
       針對(duì) ，在某個(gè)狀態(tài)s下，采取某個(gè)行為的最優(yōu)價(jià)值由2部分組成，一部分是離開狀態(tài) s 的即時(shí)獎(jiǎng)勵(lì)，另一部分則是所有能到達(dá)狀態(tài)的最優(yōu)狀態(tài)價(jià)值按出現(xiàn)概率求和

同理，把他們合并就可以得到

以上兩個(gè)方程是最重要的兩個(gè)貝爾曼最優(yōu)化方程，請(qǐng)牢記。依然以學(xué)生為例，如圖所示：

圖片中標(biāo)注的數(shù)值是根據(jù)貝爾曼最優(yōu)值函數(shù)算出來的。
       可以看出，貝爾曼最優(yōu)方程含有max，他是非線性的，沒有固定的解決方案，但是一般通過一些迭代方法來解決：價(jià)值迭代；策略迭代；Q學(xué)習(xí)；Sarsa等。只要采用這些方法把最優(yōu)狀態(tài)值函數(shù)、最優(yōu)行為值函數(shù)或者最優(yōu)策略求出來了，那么MDP就完全解決了。

 好的，MDP的所有基礎(chǔ)知識(shí)全部講完了，這里來總結(jié)一下序列一和序列二：

(1) 說明了強(qiáng)化學(xué)習(xí)是什么？和常用的機(jī)器學(xué)習(xí)算法有啥區(qū)別？

(2) 針對(duì)馬爾科夫過程進(jìn)行分析，如果模型是已知的(模型的意思可以理解為對(duì)實(shí)際環(huán)境的理解，簡(jiǎn)單來說就是狀態(tài)轉(zhuǎn)移概率是已知的)，那么就是馬爾科夫鏈；如果模型是未知的，那就是隱馬爾科夫模型；

(3) 在馬爾科夫過程基礎(chǔ)上，添加reward，就變成了馬爾科夫獎(jiǎng)賞過程。由于reward的引入，就出現(xiàn)了值函數(shù)的概念，表征各狀態(tài)下累積回報(bào)大小；

(4) 針對(duì)值函數(shù)求解困難問題，引入了貝爾曼期望方程，其將值函數(shù)轉(zhuǎn)化為迭代方程，可以方便求解；

(5) 在馬爾科夫獎(jiǎng)賞過程基礎(chǔ)上，引入動(dòng)作action，就變成了馬爾科夫決策過程；

(6) 由于action的引入，并且其也是一個(gè)關(guān)于狀態(tài)的分布，故而引入policy的概念，同時(shí)狀態(tài)轉(zhuǎn)移概念和reward也會(huì)發(fā)生改變，都和action有關(guān)了；

(7) 由于action的引入，我們需要評(píng)估在不同狀態(tài)下執(zhí)行某一action后得到的累計(jì)回報(bào)大小，故而引入動(dòng)作值函數(shù)；

(8) 狀態(tài)值函數(shù)和動(dòng)作值函數(shù)直接求解也非常困難，所以依然要引入貝爾曼期望方程，將其轉(zhuǎn)化為迭代形式，方便求解；

(9) 貝爾曼期望方程雖然可以求解出某一策略下值函數(shù)的取值，但是還沒有求解出最優(yōu)決策，所以根據(jù)決策問題的定義，首先分析了最優(yōu)值函數(shù)和最優(yōu)策略一定要滿足的關(guān)系式，或者說只有在達(dá)到最優(yōu)策略的時(shí)候才會(huì)滿足等式，即最優(yōu)值函數(shù)和最優(yōu)策略為我們強(qiáng)化學(xué)習(xí)提供了優(yōu)化方向，而貝爾曼最優(yōu)方程則提供了實(shí)際的解決思路。

(10) 后面的內(nèi)容是：如何真正利用貝爾曼期望方程和貝爾曼最優(yōu)方程解決實(shí)際問題，這就又分為兩個(gè)研究分支了，如果model(P,R)已知，那么貝爾曼期望方程和貝爾曼最優(yōu)方程就是用于解決規(guī)劃planning問題，如果model(P,R)未知，那就是貝爾曼期望方程和貝爾曼最優(yōu)方程就是用于解決Rl問題了。

由于水平有限，如有疑問，歡迎加群交流678455658。

1. David Silvr強(qiáng)化學(xué)習(xí)課程，b站有視頻