作者：劉建平

編輯：黃俊嘉

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

MDP這一篇對應Sutton書的第三章和UCL強化學習課程的第二講。

強化學習引入MDP的原因

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

這兩個轉化過程也可以從下圖中直觀的看出：

把上面兩個式子互相結合起來，我們可以得到：

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

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

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

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

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

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

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

實 例

上面的公式有點多，需要一些時間慢慢消化，這里給出一個UCL講義上實際的例子，首先看看具體我們如何利用給定策略來計算價值函數(shù)。

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

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

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

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

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

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

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

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

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

MDP小結

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

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

END