馬爾可夫決策

1、Markov Decision 馬 爾 可 夫 決 策第九組： 史文祥 曹海歌設(shè)計一個回報函數(shù)，如果learning agent在決定一步后，獲得了較好的結(jié)果，那么我們給agent一些回報（比如回報函數(shù)結(jié)果為正），若得到較差的結(jié)果，那么回報函數(shù)為負。比如，四足機器人，如果他向前走了一步（接近目標），那么回報函數(shù)為正，后退為負。如果我們能夠?qū)γ恳徊竭M行評價，得到相應(yīng)的回報函數(shù)，那么就好辦了，我們只需要找到一條回報值最大的路徑（每步的回報之和最大），就認為是最佳的路徑。馬爾可夫決策過程（MDP,Markov decision processes）是基于馬爾可夫過程理論的隨機動態(tài)系統(tǒng)的最優(yōu)決策過程。

2、它是馬爾可夫過程與確定性的動態(tài)規(guī)劃相結(jié)合的產(chǎn)物，又稱馬爾可夫型隨機動態(tài)規(guī)劃。研究一類可周期地或連續(xù)地進行觀察的隨機動態(tài)系統(tǒng)的最優(yōu)化問題。在各個時刻根據(jù)觀察到的狀態(tài)，從它的馬爾可夫決策相關(guān)書籍允許決策（控制、行動、措施等） 集合中選用一個決策而決定了系統(tǒng)下次的轉(zhuǎn)移規(guī)律與相應(yīng)的運行效果。并假設(shè)這兩者都不依賴于系統(tǒng)過去的歷史。在各個時刻選取決策的目的，是使系統(tǒng)運行的全過 程達到某種最優(yōu)運行效果，即選取控制（影響）系統(tǒng)發(fā)展的最優(yōu)策略。MDP五元組（S,A,Psa,，R）S:狀態(tài)集（states）A:一組動作（actions）Psa:狀態(tài)轉(zhuǎn)移概率：阻尼系數(shù)（discount factor）R: 回報函數(shù)

3、（reward function）S中一個狀態(tài)到另一個狀態(tài)的轉(zhuǎn)變，需要A來參與。Psa表示在當(dāng)前sS狀態(tài)下，經(jīng)過aA作用后，會轉(zhuǎn)移到的其它狀態(tài)的概率分布情況一個較小的MDP模型（機器人導(dǎo)航任務(wù)）S:11 statesA=N,S,W,E PSN(s)P(3,1)N(3,2)=0.8P(3,1)N(4,1)=0.1P(3,1)N(2,1)=0.1RR(4,3)=+1R(4,2)=-1R(s)=-0.02（S,A,Psa,，R）MDP是如何工作的時間0，從狀態(tài)S0出發(fā). . .取出你在哪個地方at state S0選擇一個動作A0決定action a0得到一個新狀態(tài)S1PS0a0循環(huán)S0S2S1S3

4、a0a1a2. . . . . .R(S0)R(S1)R(S2)R(S3). . . . . .+R(S0)R(S1)2R(S2)3R(S3). . . . . . 0,1)+目標：目標：ER(S0)R(S1)2R(S2)3R(S3)+. . .+Policy(策略)已經(jīng)處于某個狀態(tài)s時,我們會以一定的策略來選擇下一個動作a的執(zhí)行，然后轉(zhuǎn)換到另一個狀態(tài)。：SAa=（s）值函數(shù)（value function ）V（s）= ER(S0)+R(S1)+2R(S2)+3R(S3)+. . . | s0=s , 值函數(shù)是回報的加權(quán)和期望，給定也就給定了一條未來的行動方案，這個行動方案會經(jīng)過一個個狀態(tài)，而

5、到達每個狀態(tài)都會有一定回報值，距離當(dāng)前狀態(tài)越近的其它狀態(tài)對方案的影響越大，權(quán)重越高。遞推 V（s）= ER(S0)+R(S1)+2R(S2)+3R(S3)+. . . V（s1）S)(s s s)()(VssVPRss）（）（下一個狀態(tài)值函數(shù)的期望值然而我們需要注意的是：給定給定后，在給定狀態(tài)后，在給定狀態(tài)s下，下，a是唯一是唯一的，但的，但AS可能不是多到一的映射可能不是多到一的映射 立即回報= R(S0)+（ER(S1)+2R(S2)+3R(S3)+. . . ）= R(S0)+V（s）(s: 下一個狀態(tài))給定一個固定的策略，我們怎么解這個等式 V（s）=？S)(sss)()(VssVPR

6、ss）（）（)1 , 2(1 . 0)1 , 4(1 . 0)2 , 3(8 . 0 )1 , 3(R)1 , 3(VVVV(3,1)(3,2)(4,1)(2,1)0.80.10.1.|S|個方程，個方程，|S|個未知數(shù)個未知數(shù)一個具體的例子對于給定的策略，我們可以寫下這一策略的價值函數(shù)這是一個策略，但這不是一個偉大的策略V（策略的價值函數(shù)）S)(s s s)()(VssVPRss）（）（目的：找到一個當(dāng)前狀態(tài)找到一個當(dāng)前狀態(tài)s下，最優(yōu)的行動策略下，最優(yōu)的行動策略。定義最優(yōu)的V*如下：）（s)(Vmax*sVS*sA* s s)()(maxVsaaVPRss）（）（Bellman等式：（2）

7、第二項是一個就決定了每個狀態(tài)s的下一步動作，執(zhí)行a后，s按概率分布的回報概率和的期望定義了最優(yōu)的V*，我們再定義最優(yōu)的策略*： SASs*A*) () ( maxargssVsPsaa）（*：實際上是最佳策略，最大化我們的收益。 選擇最優(yōu)的*，也就確定了每個狀態(tài)s的下一步動作a。（3）注意： 如果我們能夠求得每一個如果我們能夠求得每一個s下最優(yōu)的下最優(yōu)的a，那么從全局來看，那么從全局來看，SA的映射即可生成，并且是最優(yōu)映射的映射即可生成，并且是最優(yōu)映射*。*針對全局的針對全局的s，確定了每一個確定了每一個s的下一個行動的下一個行動a,不會因為初始狀態(tài)不會因為初始狀態(tài)s選取的不同選取的不同而不同

8、。而不同。如何計算最優(yōu)策略？（MDP是有限狀態(tài)，有限動作時）值迭代法1、將每一個s的V(s)初始化為0 2、循環(huán)直到收斂 對于每一個狀態(tài)s,對V(s)做更新 A) () (max)(: )(ssaasVsPsRsVi）同步迭代法初始狀態(tài)所有的v(s)都為0.對s都計算新的V(s)=R(s)+0=R(s)。在計算每一個狀態(tài)時，得到V(s)后，先存下來，不立即更新。待所有s的新值v(s)都計算完后，再統(tǒng)一更新。ii)異步迭代法對于每一個狀態(tài)s,得到新的v(s)后，不存儲，直接更新。V(s)V*(s)知道了V*(s)后，再用（3）求出相應(yīng)的最優(yōu)策略=0.9974. 071. 0*1 . 069. 0

9、*1 . 075. 0*8 . 0) () (:*ssasVsPW676. 071. 0*1 . 075. 0*1 . 069. 0*8 . 0) () (:*ssasVsPNSs*A*) () ( maxargssVsPsaa）（策略迭代法（*）1、隨機指定一個S到A的映射。2、循環(huán)直到收斂 （a）令V:=V （b）對于每一個狀態(tài)s,對（s）做更新 Aa) () (maxarg: )(ssasVsPsV可以通過之前的bellmand等式求得這一步會求出所有狀態(tài)的V（s）根據(jù)（a）歩的結(jié)果挑選出當(dāng)前狀態(tài)s下最優(yōu)的a,然后對a做更新。MDP中的參數(shù)估計 之前討論的MDP中，狀態(tài)轉(zhuǎn)移概率Psa和回

10、報函數(shù)R(s)是已知的。 實際中，我們需要從數(shù)據(jù)中估計出這些參數(shù)（S,A,已知）S10S12S11S13a10a11a12. . . . . .S20S22S21S23a20a21a22. . . . . .aij是sij狀態(tài)時要執(zhí)行的動作12.最大似然估計來估計狀態(tài)轉(zhuǎn)移概率（）sstateinaactiontookwetimesstogotandsstateinaactionweotimessPsa#okt#) (（從s狀態(tài)執(zhí)行動作a后到達s的次數(shù)）（在狀態(tài)s時，執(zhí)行a的次數(shù)）如果分母為0，則令Psa(s)=1/|s|將參數(shù)估計和值迭代結(jié)合起來（在不知道狀態(tài)轉(zhuǎn)移概率的情況下）1、隨機初始化2、循環(huán)直到收斂(a)在樣本上統(tǒng)計中每個狀態(tài)轉(zhuǎn)移次數(shù)，更新Psa和R(b)使用估計到的參數(shù)來更新V(值迭代)(c)根據(jù)跟新的V來重新得出 V的初