作者：劉建平
編輯：黃俊嘉
前 言
在強(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這一篇對(duì)應(yīng)Sutton書的第三章和UCL強(qiáng)化學(xué)習(xí)課程的第二講。
01
強(qiáng)化學(xué)習(xí)的8個(gè)要素我們在第一節(jié)已經(jīng)講了。其中的第七個(gè)是環(huán)境的狀態(tài)轉(zhuǎn)化模型，它可以表示為一個(gè)概率模型，即在狀態(tài)ss下采取動(dòng)作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)。這一會(huì)導(dǎo)致我們的環(huán)境轉(zhuǎn)化模型非常復(fù)雜，復(fù)雜到難以建模。因此我們需要對(duì)強(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)。用公式表示就是：
對(duì)于馬爾科夫性本身，我之前講過的隱馬爾科夫模型HMM（一）HMM模型，條件隨機(jī)場CRF(一)從隨機(jī)場到線性鏈條件隨機(jī)場以及MCMC(二)馬爾科夫鏈都有講到。它本身是一個(gè)比較簡單的假設(shè)，因此這里就不專門對(duì)“馬爾可夫性”做專門的講述了。
除了對(duì)于環(huán)境的狀態(tài)轉(zhuǎn)化模型這個(gè)因素做馬爾科夫假設(shè)外，我們還對(duì)強(qiáng)化學(xué)習(xí)第四個(gè)要素個(gè)體的策略(policy)π也做了馬爾科夫假設(shè)。即在狀態(tài)s時(shí)采取動(dòng)作a的概率僅與當(dāng)前狀態(tài)s有關(guān)，與其他的要素?zé)o關(guān)。用公式表示就是：
對(duì)于第五個(gè)要素，價(jià)值函數(shù)
其中，
02
根據(jù)價(jià)值函數(shù)的表達(dá)式，我們可以推導(dǎo)出價(jià)值函數(shù)基于狀態(tài)的遞推關(guān)系，比如對(duì)于狀態(tài)價(jià)值函數(shù)
也就是說，在t時(shí)刻的狀態(tài)
這個(gè)遞推式子我們一般將它叫做貝爾曼方程。這個(gè)式子告訴我們，一個(gè)狀態(tài)的價(jià)值由該狀態(tài)的獎(jiǎng)勵(lì)以及后續(xù)狀態(tài)價(jià)值按一定的衰減比例聯(lián)合組成。
同樣的方法，我們可以得到動(dòng)作價(jià)值函數(shù)
03
根據(jù)動(dòng)作價(jià)值函數(shù)
也就是說，狀態(tài)價(jià)值函數(shù)是所有動(dòng)作價(jià)值函數(shù)基于策略π的期望。通俗說就是某狀態(tài)下所有狀態(tài)動(dòng)作價(jià)值乘以該動(dòng)作出現(xiàn)的概率，最后求和，就得到了對(duì)應(yīng)的狀態(tài)價(jià)值。
反過來，利用上貝爾曼方程，我們也很容易從狀態(tài)價(jià)值函數(shù)
通俗說就是狀態(tài)動(dòng)作價(jià)值有兩部分相加組成，第一部分是即時(shí)獎(jiǎng)勵(lì)，第二部分是環(huán)境所有可能出現(xiàn)的下一個(gè)狀態(tài)的概率乘以該下一狀態(tài)的狀態(tài)價(jià)值，最后求和，并加上衰減。
這兩個(gè)轉(zhuǎn)化過程也可以從下圖中直觀的看出：
把上面兩個(gè)式子互相結(jié)合起來，我們可以得到：
04
最優(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)劣呢？一般是通過對(duì)應(yīng)的價(jià)值函數(shù)來比較的，也就是說，尋找較優(yōu)策略可以通過尋找較優(yōu)的價(jià)值函數(shù)來完成?？梢远x最優(yōu)狀態(tài)價(jià)值函數(shù)是所有策略下產(chǎn)生的眾多狀態(tài)價(jià)值函數(shù)中的最大者，即：
同理也可以定義最優(yōu)動(dòng)作價(jià)值函數(shù)是所有策略下產(chǎn)生的眾多動(dòng)作狀態(tài)價(jià)值函數(shù)中的最大者，即：
對(duì)于最優(yōu)的策略，基于動(dòng)作價(jià)值函數(shù)我們可以定義為：
反過來的最優(yōu)價(jià)值函數(shù)關(guān)系也很容易得到：
利用上面的兩個(gè)式子也可以得到和第三節(jié)末尾類似的式子：
05
實(shí) 例
上面的公式有點(diǎn)多，需要一些時(shí)間慢慢消化，這里給出一個(gè)UCL講義上實(shí)際的例子，首先看看具體我們?nèi)绾卫媒o定策略來計(jì)算價(jià)值函數(shù)。
例子是一個(gè)學(xué)生學(xué)習(xí)考試的MDP。里面左下那個(gè)圓圈位置是起點(diǎn)，方框那個(gè)位置是終點(diǎn)。上面的動(dòng)作有study, pub, facebook, quit, sleep，每個(gè)狀態(tài)動(dòng)作對(duì)應(yīng)的即時(shí)獎(jiǎng)勵(lì)R已經(jīng)標(biāo)出來了。我們的目標(biāo)是找到最優(yōu)的動(dòng)作價(jià)值函數(shù)或者狀態(tài)價(jià)值函數(shù)，進(jìn)而找出最優(yōu)的策略。
為了方便，我們假設(shè)衰減因子r = 1，π（a|s）= 0.5。
對(duì)于終點(diǎn)方框位置，由于其沒有下一個(gè)狀態(tài)，也沒有當(dāng)前狀態(tài)的動(dòng)作，因此其狀態(tài)價(jià)值函數(shù)為0。對(duì)于其余四個(gè)狀態(tài)，我們依次定義其價(jià)值為v1、v2、v3、v4， 分別對(duì)應(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ù)
我們這次以動(dòng)作價(jià)值函數(shù)
接著我們就可利用
從而我們的最優(yōu)決策路徑是走6->6->8->10->結(jié)束。
06
MDP小結(jié)
MDP是強(qiáng)化學(xué)習(xí)入門的關(guān)鍵一步，如果這部分研究的比較清楚，后面的學(xué)習(xí)就會(huì)容易很多。因此值得多些時(shí)間在這里。雖然MDP可以直接用方程組來直接求解簡單的問題，但是更復(fù)雜的問題卻沒有辦法求解，因此我們還需要尋找其他有效的求解強(qiáng)化學(xué)習(xí)的方法。
下一篇討論用動(dòng)態(tài)規(guī)劃的方法來求解強(qiáng)化學(xué)習(xí)的問題。
END
聯(lián)系客服
