作者：劉建平

編輯：黃俊嘉

在強(qiáng)化學(xué)習(xí)（一）模型基礎(chǔ)中，我們講到了強(qiáng)化學(xué)習(xí)模型的8個(gè)基本要素。但是僅憑這些要素還是無法使用強(qiáng)化學(xué)習(xí)來幫助我們解決問題的, 在講到模型訓(xùn)練前，模型的簡化也很重要，這一篇主要就是講如何利用馬爾科夫決策過程(Markov Decision Process，以下簡稱MDP)來簡化強(qiáng)化學(xué)習(xí)的建模。

MDP這一篇對應(yīng)Sutton書的第三章和UCL強(qiáng)化學(xué)習(xí)課程的第二講。

強(qiáng)化學(xué)習(xí)引入MDP的原因

強(qiáng)化學(xué)習(xí)的8個(gè)要素我們在第一節(jié)已經(jīng)講了。其中的第七個(gè)是環(huán)境的狀態(tài)轉(zhuǎn)化模型，它可以表示為一個(gè)概率模型，即在狀態(tài)ss下采取動作a，轉(zhuǎn)到下一個(gè)狀態(tài)s'的概率，表示為。

如果按照真實(shí)的環(huán)境轉(zhuǎn)化過程看，轉(zhuǎn)化到下一個(gè)狀態(tài)s'的概率既與上一個(gè)狀態(tài)s有關(guān)，還與上上個(gè)狀態(tài)，以及上上上個(gè)狀態(tài)有關(guān)。這一會導(dǎo)致我們的環(huán)境轉(zhuǎn)化模型非常復(fù)雜，復(fù)雜到難以建模。因此我們需要對強(qiáng)化學(xué)習(xí)的環(huán)境轉(zhuǎn)化模型進(jìn)行簡化。簡化的方法就是假設(shè)狀態(tài)轉(zhuǎn)化的馬爾科夫性，也就是假設(shè)轉(zhuǎn)化到下一個(gè)狀態(tài)s'的概率僅與上一個(gè)狀態(tài)s有關(guān)，與之前的狀態(tài)無關(guān)。用公式表示就是：

對于馬爾科夫性本身，我之前講過的隱馬爾科夫模型HMM（一）HMM模型，條件隨機(jī)場CRF(一)從隨機(jī)場到線性鏈條件隨機(jī)場以及MCMC(二)馬爾科夫鏈都有講到。它本身是一個(gè)比較簡單的假設(shè)，因此這里就不專門對“馬爾可夫性”做專門的講述了。

除了對于環(huán)境的狀態(tài)轉(zhuǎn)化模型這個(gè)因素做馬爾科夫假設(shè)外，我們還對強(qiáng)化學(xué)習(xí)第四個(gè)要素個(gè)體的策略(policy)π也做了馬爾科夫假設(shè)。即在狀態(tài)s時(shí)采取動作a的概率僅與當(dāng)前狀態(tài)s有關(guān)，與其他的要素?zé)o關(guān)。用公式表示就是：

對于第五個(gè)要素，價(jià)值函數(shù)也是一樣，現(xiàn)在僅僅依賴于當(dāng)前狀態(tài)了，那么現(xiàn)在價(jià)值函數(shù)表示為：表示為:表示為:表示為:

其中，代表收獲（return), 是一個(gè)MDP中從某一個(gè)狀態(tài)開始采樣直到終止?fàn)顟B(tài)時(shí)所有獎勵的有衰減的之和。

MDP的價(jià)值函數(shù)與貝爾曼方程

對于MDP，我們在第一節(jié)里已經(jīng)講到了它的價(jià)值函數(shù) 的表達(dá)式。但是這個(gè)表達(dá)式?jīng)]有考慮到所采用的動作a帶來的價(jià)值影響，因此我們除了這個(gè)狀態(tài)價(jià)值函數(shù)外，還有一個(gè)動作價(jià)值函數(shù)，即：

根據(jù)價(jià)值函數(shù)的表達(dá)式，我們可以推導(dǎo)出價(jià)值函數(shù)基于狀態(tài)的遞推關(guān)系，比如對于狀態(tài)價(jià)值函數(shù)，可以發(fā)現(xiàn)：

也就是說，在t時(shí)刻的狀態(tài)和t+1時(shí)刻的狀態(tài)是滿足遞推關(guān)系的，即：

這個(gè)遞推式子我們一般將它叫做貝爾曼方程。這個(gè)式子告訴我們，一個(gè)狀態(tài)的價(jià)值由該狀態(tài)的獎勵以及后續(xù)狀態(tài)價(jià)值按一定的衰減比例聯(lián)合組成。

同樣的方法，我們可以得到動作價(jià)值函數(shù)的貝爾曼方程：

狀態(tài)價(jià)值函數(shù)與動作價(jià)值函數(shù)的遞推關(guān)系

根據(jù)動作價(jià)值函數(shù) 和狀態(tài)價(jià)值函數(shù) 定義，我們很容易得到他們之間的轉(zhuǎn)化關(guān)系公式：

也就是說，狀態(tài)價(jià)值函數(shù)是所有動作價(jià)值函數(shù)基于策略π的期望。通俗說就是某狀態(tài)下所有狀態(tài)動作價(jià)值乘以該動作出現(xiàn)的概率，最后求和，就得到了對應(yīng)的狀態(tài)價(jià)值。

反過來，利用上貝爾曼方程，我們也很容易從狀態(tài)價(jià)值函數(shù)表示動作價(jià)值函數(shù) ，即：

通俗說就是狀態(tài)動作價(jià)值有兩部分相加組成，第一部分是即時(shí)獎勵，第二部分是環(huán)境所有可能出現(xiàn)的下一個(gè)狀態(tài)的概率乘以該下一狀態(tài)的狀態(tài)價(jià)值，最后求和，并加上衰減。

這兩個(gè)轉(zhuǎn)化過程也可以從下圖中直觀的看出：

把上面兩個(gè)式子互相結(jié)合起來，我們可以得到：

最優(yōu)價(jià)值函數(shù)

解決強(qiáng)化學(xué)習(xí)問題意味著要尋找一個(gè)最優(yōu)的策略讓個(gè)體在與環(huán)境交互過程中獲得始終比其它策略都要多的收獲，這個(gè)最優(yōu)策略我們可以用π*表示。一旦找到這個(gè)最優(yōu)策略π*，那么我們就解決了這個(gè)強(qiáng)化學(xué)習(xí)問題。一般來說，比較難去找到一個(gè)最優(yōu)策略，但是可以通過比較若干不同策略的優(yōu)劣來確定一個(gè)較好的策略，也就是局部最優(yōu)解。

如何比較策略的優(yōu)劣呢？一般是通過對應(yīng)的價(jià)值函數(shù)來比較的，也就是說，尋找較優(yōu)策略可以通過尋找較優(yōu)的價(jià)值函數(shù)來完成。可以定義最優(yōu)狀態(tài)價(jià)值函數(shù)是所有策略下產(chǎn)生的眾多狀態(tài)價(jià)值函數(shù)中的最大者，即：

同理也可以定義最優(yōu)動作價(jià)值函數(shù)是所有策略下產(chǎn)生的眾多動作狀態(tài)價(jià)值函數(shù)中的最大者，即：

對于最優(yōu)的策略，基于動作價(jià)值函數(shù)我們可以定義為：

反過來的最優(yōu)價(jià)值函數(shù)關(guān)系也很容易得到：

利用上面的兩個(gè)式子也可以得到和第三節(jié)末尾類似的式子：

實(shí) 例

上面的公式有點(diǎn)多，需要一些時(shí)間慢慢消化，這里給出一個(gè)UCL講義上實(shí)際的例子，首先看看具體我們?nèi)绾卫媒o定策略來計(jì)算價(jià)值函數(shù)。

例子是一個(gè)學(xué)生學(xué)習(xí)考試的MDP。里面左下那個(gè)圓圈位置是起點(diǎn)，方框那個(gè)位置是終點(diǎn)。上面的動作有study, pub, facebook, quit, sleep，每個(gè)狀態(tài)動作對應(yīng)的即時(shí)獎勵R已經(jīng)標(biāo)出來了。我們的目標(biāo)是找到最優(yōu)的動作價(jià)值函數(shù)或者狀態(tài)價(jià)值函數(shù)，進(jìn)而找出最優(yōu)的策略。

為了方便，我們假設(shè)衰減因子r = 1，π（a|s）= 0.5。

對于終點(diǎn)方框位置，由于其沒有下一個(gè)狀態(tài)，也沒有當(dāng)前狀態(tài)的動作，因此其狀態(tài)價(jià)值函數(shù)為0。對于其余四個(gè)狀態(tài)，我們依次定義其價(jià)值為v1、v2、v3、v4， 分別對應(yīng)左上，左下，中下，右下位置的圓圈。我們基于

計(jì)算所有的狀態(tài)價(jià)值函數(shù)?？梢粤谐鲆粋€(gè)方程組。

解出這個(gè)方程組可以得到v1=-2.3，v2=-1.3，v3=2.7，v4=7.4, 即每個(gè)狀態(tài)的價(jià)值函數(shù)如下圖：

上面我們固定了策略π（a|s），雖然求出了每個(gè)狀態(tài)的狀態(tài)價(jià)值函數(shù)，但是卻并不一定是最優(yōu)價(jià)值函數(shù)。那么如何求出最優(yōu)價(jià)值函數(shù)呢？這里由于狀態(tài)機(jī)簡單，求出最優(yōu)的狀態(tài)價(jià)值函數(shù)或者動作價(jià)值函數(shù)比較容易。

我們這次以動作價(jià)值函數(shù) 來為例求解。首先終點(diǎn)方框處的好求。

接著我們就可利用列方程組求出所有的。有了所有的 ,利用就可以求出所有的 。最終求出的所有 和 如下圖：

從而我們的最優(yōu)決策路徑是走6->6->8->10->結(jié)束。

MDP小結(jié)

MDP是強(qiáng)化學(xué)習(xí)入門的關(guān)鍵一步，如果這部分研究的比較清楚，后面的學(xué)習(xí)就會容易很多。因此值得多些時(shí)間在這里。雖然MDP可以直接用方程組來直接求解簡單的問題，但是更復(fù)雜的問題卻沒有辦法求解，因此我們還需要尋找其他有效的求解強(qiáng)化學(xué)習(xí)的方法。

下一篇討論用動態(tài)規(guī)劃的方法來求解強(qiáng)化學(xué)習(xí)的問題。

END