公式及圖片正常顯示的精美排版版請(qǐng)移步http:///2015/11/17/Master-Reinforcement-Learning-MDP.html

寫(xiě)在前面

現(xiàn)有的機(jī)器學(xué)習(xí)算法根據(jù)模型的學(xué)習(xí)過(guò)程大致可以分為四類(lèi)：監(jiān)督式學(xué)習(xí)，無(wú)監(jiān)督式學(xué)習(xí)，半監(jiān)督式學(xué)習(xí)和增強(qiáng)學(xué)習(xí)。

① 監(jiān)督式學(xué)習(xí)：從標(biāo)記好的訓(xùn)練數(shù)據(jù)中進(jìn)行模型的訓(xùn)練，常用來(lái)做分類(lèi)和回歸，例如邏輯回歸、反向神經(jīng)網(wǎng)絡(luò)；

② 無(wú)監(jiān)督式學(xué)習(xí)：根據(jù)數(shù)據(jù)的特征直接對(duì)數(shù)據(jù)的結(jié)構(gòu)和數(shù)值進(jìn)行歸納，常用來(lái)做聚類(lèi)，例如周知的K-均值，譜聚類(lèi)；

③ 半監(jiān)督式學(xué)習(xí)：根據(jù)部分標(biāo)記的和部分沒(méi)有標(biāo)記的訓(xùn)練數(shù)據(jù)進(jìn)行模型的學(xué)習(xí)，常用來(lái)做回歸和分類(lèi)；

④ 增強(qiáng)式學(xué)習(xí)：作為今天要討論的主角，是機(jī)器學(xué)習(xí)中最酷的分支之一，其通過(guò)不斷的試錯(cuò)、反饋進(jìn)行學(xué)習(xí)，常用來(lái)做序列決策或者控制問(wèn)題，算法例子有Q-Learning、TD-Learning（Tempora Difference Learning）。

增強(qiáng)學(xué)習(xí)和人類(lèi)學(xué)習(xí)的機(jī)制非常相近，在實(shí)際應(yīng)用中也有這很Cool的表現(xiàn)，如直升機(jī)自動(dòng)飛行、各種通過(guò)增強(qiáng)學(xué)習(xí)實(shí)現(xiàn)的打敗人類(lèi)最強(qiáng)選手的棋牌博弈機(jī)器，包括最近非?；鸬腄eepMind將深度學(xué)習(xí)和增強(qiáng)學(xué)習(xí)融合實(shí)現(xiàn)的玩Atari游戲的超強(qiáng)程序。下面將結(jié)合一個(gè)實(shí)例，從增強(qiáng)學(xué)習(xí)的數(shù)學(xué)本質(zhì)——馬爾科夫決策過(guò)程進(jìn)行闡述。

一個(gè)栗子

假設(shè)一個(gè)智能體處于下圖（a）中所示的4x3的環(huán)境中。從初始狀態(tài)開(kāi)始，它需要每個(gè)時(shí)間選擇一個(gè)行動(dòng)（上、下、左、右）。在智能體到達(dá)標(biāo)有+1或-1的目標(biāo)狀態(tài)時(shí)與環(huán)境的交互終止。如果環(huán)境是確定的，很容易得到一個(gè)解:[上，上，右，右，右]?？上е悄荏w的行動(dòng)不是可靠的（類(lèi)似現(xiàn)實(shí)中對(duì)機(jī)器人的控制不可能完全精確），環(huán)境不一定沿這個(gè)解發(fā)展。下圖（b）是一個(gè)環(huán)境轉(zhuǎn)移模型的示意，每一步行動(dòng)以0.8的概率達(dá)到預(yù)期，0.2的概率會(huì)垂直于運(yùn)動(dòng)方向移動(dòng)，撞到（a）圖中黑色模塊后會(huì)無(wú)法移動(dòng)。兩個(gè)終止?fàn)顟B(tài)分別有+1和-1的回報(bào)，其他狀態(tài)有-0.4的回報(bào)?，F(xiàn)在智能體要解決的是通過(guò)增強(qiáng)學(xué)習(xí)（不斷的試錯(cuò)、反饋、學(xué)習(xí)）找到最優(yōu)的策略（得到最大的回報(bào)）。

上述問(wèn)題可以看作為一個(gè)馬爾科夫決策過(guò)程，最終的目標(biāo)是通過(guò)一步步?jīng)Q策使整體的回報(bào)函數(shù)期望最優(yōu)。下面介紹馬爾科夫決策過(guò)程。

馬爾科夫決策過(guò)程

一個(gè)馬爾科夫決策過(guò)程（Markov Decision Processes, MDP）有一個(gè)五個(gè)關(guān)鍵元素組成{S,A,{Psa},γ,R},其中：

S：表示狀態(tài)集合，例如上例中4x3的每個(gè)環(huán)境{(i,j)|i=1,2,3,4,j=1,2,3}。自動(dòng)直升機(jī)系統(tǒng)中的所有可能的位置、方向等。

A：表示一組動(dòng)作集合，例如上例中的（上、下、左、右），自動(dòng)直升機(jī)系統(tǒng)中的讓飛機(jī)向前，向后等。

Psa：狀態(tài)轉(zhuǎn)移概率，表示在當(dāng)前s∈S狀態(tài)下，通過(guò)執(zhí)行動(dòng)作a∈A后轉(zhuǎn)移到其他狀態(tài)的概率分布。例如上例中，P(1,1)上表示智能體在狀態(tài)(1,1)執(zhí)行向上的動(dòng)作后轉(zhuǎn)移到狀態(tài)(1,2)，(2,1)的概率分布。

γ∈[0,1)：阻尼系數(shù)，表示的是隨著時(shí)間的推移回報(bào)率的折扣。

R:S×AR：回報(bào)函數(shù)，有時(shí)回報(bào)函數(shù)是只與S有關(guān)的函數(shù)，R重寫(xiě)為R:SR。相當(dāng)于上例中對(duì)每個(gè)狀態(tài)上賦予的回報(bào)值。

MDP的動(dòng)態(tài)過(guò)程如下：智能體在狀態(tài)s0選擇某個(gè)動(dòng)作a0∈A，智能體根據(jù)概率Ps0a0轉(zhuǎn)移到狀態(tài)s1，然后執(zhí)行動(dòng)作a1，…如此下去我們可以得到這樣的過(guò)程：

經(jīng)過(guò)上面的轉(zhuǎn)移路徑，我們可以得到相應(yīng)的回報(bào)函數(shù)和如下：

如果回報(bào)函數(shù)R只與S有關(guān)，我們上式可重新寫(xiě)作

我們的目標(biāo)是選擇一組最佳的動(dòng)作，使得全部的回報(bào)加權(quán)和期望最大：

從上式可以發(fā)現(xiàn)，在t時(shí)刻的回報(bào)值是被打了γt倍折扣的，注意到γ<1，則越靠后的狀態(tài)對(duì)回報(bào)和影響越小，為了得到最大期望回報(bào)，智能體將會(huì)盡量最先拿最大回報(bào)。

下圖是上述內(nèi)容的一個(gè)直觀示意

下一部分將對(duì)上述過(guò)程進(jìn)行進(jìn)一步數(shù)學(xué)表示，以方便求解。

進(jìn)一步數(shù)學(xué)表示

首先我們來(lái)定義策略，一個(gè)策略π就是一個(gè)從狀態(tài)到動(dòng)作的映射函數(shù)π:SA。也就是，給定了當(dāng)前狀態(tài)s，根據(jù)策略π，也就確定了下一步應(yīng)該執(zhí)行的動(dòng)作a=π(s)。

為每一個(gè)策略π我們頂一個(gè)相應(yīng)的值函數(shù)（Value Function）

即給定初始狀態(tài)s0和策略π后的累積折扣回報(bào)期望（Expected Sum Of Discounted Rewards）。

對(duì)于一個(gè)固定的策略，它的值函數(shù)Vπ滿足貝爾曼等式（Bellman Equations）：

其中s′表示狀態(tài)s執(zhí)行動(dòng)作π(s)后的下一個(gè)可能狀態(tài)，其服從Psπ(s)分布。上式由兩部分構(gòu)成：即時(shí)回報(bào)R(s)及未來(lái)累積折扣回報(bào)期望Es′～Psπ(s)[Vπ(s′)]。

利用貝爾曼等式能夠有效的解出Vπ（給定的策略π的回報(bào)值）。尤其，對(duì)于一個(gè)有限狀態(tài)的MDP（|S|<∞），對(duì)每一個(gè)狀態(tài)s我們都能寫(xiě)出這樣的等式Vπ(s)，求解變?yōu)榱私庖粋€(gè)|S|個(gè)方程，|S|個(gè)未知數(shù)的線性方程組。

當(dāng)然，我們求解Vπ的目的是為找到一個(gè)當(dāng)前狀態(tài)s下最優(yōu)的行動(dòng)策略π服務(wù)的（最優(yōu)的策略下得到最優(yōu)的值函數(shù)）。定義最優(yōu)的值函數(shù)為：

其貝爾曼等式的形式為：

也可表示為增強(qiáng)學(xué)習(xí)中的Q函數(shù)形式：

其中Q(s,a)≡R(S)+γPsa(s′)V(s′)，表示在s狀態(tài)下執(zhí)行動(dòng)作a作為第一個(gè)動(dòng)作時(shí)的最大累計(jì)折扣回報(bào)。

對(duì)應(yīng)最優(yōu)值函數(shù)的最優(yōu)的策略為：

需要注意的是，π有一個(gè)有趣的特性，即π是針對(duì)的是所有的狀態(tài)s的，確定了每一個(gè)狀態(tài)s的下一個(gè)動(dòng)作a，不管初始狀態(tài)是哪一個(gè)狀態(tài)，通過(guò)策略π都會(huì)取得最大回報(bào)。

現(xiàn)在我們有了優(yōu)化目標(biāo)的數(shù)學(xué)表達(dá)（最優(yōu)值函數(shù)，最優(yōu)策略），下一部分討論兩種求解方法（針對(duì)有限狀態(tài)、有限動(dòng)作的MDP）。

值迭代方法和策略迭代方法

值迭代方法

算法步驟：

1 講每一個(gè)狀態(tài)s的值函數(shù)V(s)初始化為0

2 循環(huán)直至收斂{

  對(duì)于每一個(gè)狀態(tài)s，對(duì)V(s)做更新

  V(s):=R(s)+maxa∈Aγ∑s′V(s′)

}

值迭代方法里面的內(nèi)循環(huán)又有兩種策略：同步迭代，異步迭代。同步迭代就是得到V(s)后不立即更新，等所有的狀態(tài)s的V(s)都完成計(jì)算后統(tǒng)一更新。異步迭代就是對(duì)每個(gè)狀態(tài)s得到新的V(s)后立即更新。兩種都會(huì)使得V(s)收斂于V(s)。求得最優(yōu)的V(s)后，可使用公式π(s)=argmaxa∈A∑s′∈SPsa(s′)V(s′)來(lái)求出相應(yīng)的最優(yōu)策略π。

策略迭代方法

于值迭代方法不同，策略迭代法之間關(guān)注π，使π收斂到π。

算法步驟：

1 隨機(jī)初始化話一個(gè)S到A的映射π

2 循環(huán)直至收斂{

  2.1 令V:=Vπ

  2.2 對(duì)每一個(gè)狀態(tài)s,對(duì)π(s)做更新

  π(s):=argmaxa∈A∑s′Psa(s′)V(s′)

}

其中2.1步即為上述對(duì)于一個(gè)給定策略π利用貝爾曼等式求解Vπ的過(guò)程（求解|S|個(gè)方程，|S|個(gè)未知數(shù)的線性方程組）。

2.2是根據(jù)2.1步的結(jié)果，挑選出當(dāng)前狀態(tài)s下最優(yōu)的動(dòng)作a來(lái)更新π(s)。

兩者比較

對(duì)于規(guī)模較小的MDP，策略迭代一般能夠更快的收斂；但對(duì)于規(guī)模較大的MDP（狀態(tài)多），值迭代更容易些（沒(méi)有線性方程組的計(jì)算）。

MDP中的參數(shù)估計(jì)

到目前為止，我們討論的MDP和MDP求解算法都是在已知狀態(tài)轉(zhuǎn)移概率Psa和回報(bào)函數(shù)R(s)的。在許多實(shí)際問(wèn)題中，狀態(tài)轉(zhuǎn)移概率和回報(bào)函數(shù)不能顯式的得到，本部分講如何從數(shù)據(jù)中估計(jì)這些參數(shù)（通常S,A,γ是已知的）。

假設(shè)我們已知很多條狀態(tài)轉(zhuǎn)移路徑如下：

其中s(j)i是i時(shí)刻第j條轉(zhuǎn)移路徑對(duì)應(yīng)的狀態(tài)，aji是sji狀態(tài)要執(zhí)行的動(dòng)作。每條轉(zhuǎn)移路徑中的狀態(tài)數(shù)都是有限的，在實(shí)際操作中每個(gè)轉(zhuǎn)移路徑要么進(jìn)入終結(jié)狀態(tài)，要不達(dá)到規(guī)定的步數(shù)后終結(jié)。

當(dāng)我們獲得了很多類(lèi)似上面的轉(zhuǎn)移路徑后（樣本），我們可以用最大似然估計(jì)來(lái)估計(jì)狀態(tài)轉(zhuǎn)移概率。

上式分子表示在狀態(tài)s通過(guò)執(zhí)行動(dòng)作a后到達(dá)狀態(tài)s′的次數(shù)，分母表示在狀態(tài)s我們執(zhí)行動(dòng)作的次數(shù)。為避免分母為0的情況，當(dāng)分母為0使，令Psa(s′)=1|S|。

對(duì)于未知的回報(bào)函數(shù)，我們令R(s)為在狀態(tài)s下觀察到的回報(bào)均值。

得到狀態(tài)轉(zhuǎn)移概率和回報(bào)函數(shù)的估值后，就簡(jiǎn)化為了前面部分講述的問(wèn)題，用第三部分將的值迭代或者策略迭代方法即可解決。例如我們將值迭代和參數(shù)估計(jì)結(jié)合到一塊：

算法流程如下：

1 隨機(jī)初始化話一個(gè)S到A的映射π

2 循環(huán)直至收斂{

  2.1 在MDP中執(zhí)行策略π一定次數(shù)

  2.2 通過(guò)2.1得到的樣本估計(jì)Psa（和R，需要的話）

  2.3 使用上一節(jié)提到的值迭代方法和估計(jì)得到的參數(shù)來(lái)更新V

  2.4 對(duì)于得到的V更新得到更優(yōu)的策略π

}

其中2.3步，是一個(gè)循環(huán)迭代的過(guò)程。上一節(jié)中我們通過(guò)將V初始化為0然后進(jìn)行迭代，當(dāng)嵌套上述過(guò)程中后，如果每次都將V初始化為0然后迭代更新，速度回很慢。一個(gè)加速的方法是將V初始化我上次大循環(huán)中得到的V。

小結(jié)

至此我們討論完了增強(qiáng)學(xué)習(xí)的數(shù)學(xué)本質(zhì)————馬爾科夫決策過(guò)程（MDP）的數(shù)學(xué)表示及求解過(guò)程（這里的MDP是非確定的MDP，即狀態(tài)轉(zhuǎn)移函數(shù)和回報(bào)函數(shù)是有概率的,，對(duì)于確定性的，求解會(huì)更簡(jiǎn)單些，感興趣可參考[3]最后一章：增強(qiáng)學(xué)習(xí)）。全文很大部分是對(duì)Andrew Ng講義[1]的翻譯，加上了部分自己的理解。推薦大家根據(jù)參考文獻(xiàn)進(jìn)行進(jìn)一步理解和學(xué)習(xí)。

參考文獻(xiàn)

[1] 機(jī)器學(xué)習(xí)公開(kāi)課-講義-馬爾科夫決策過(guò)程.Andrew Ng

[2] 機(jī)器學(xué)習(xí)公開(kāi)課-視頻-馬爾科夫決策過(guò)程.Andrew Ng

[3] 人工智能：一種現(xiàn)代方法

[4] 機(jī)器學(xué)習(xí).Tom M.Mitchell

[5] 看DeepMind如何用Reinforcement learning玩游戲