馬爾可夫決策.ppt

《馬爾可夫決策.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

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

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

3、tfactor）R:回報(bào)函數(shù)（rewardfunction）S中一個(gè)狀態(tài)到另一個(gè)狀態(tài)的轉(zhuǎn)變，需要A來(lái)參與。Psa表示在當(dāng)前s∈S狀態(tài)下，經(jīng)過(guò)a∈A作用后，會(huì)轉(zhuǎn)移到的其它狀態(tài)的概率分布情況一個(gè)較小的MDP模型（機(jī)器人導(dǎo)航任務(wù)）+1-11234321S:11statesA={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是如何工作的時(shí)間0，從狀態(tài)S0出發(fā)...取出你在哪個(gè)地方ats

4、tateS0選擇一個(gè)動(dòng)作A0決定actiona0得到一個(gè)新?tīng)顟B(tài)S1~PS0a0循環(huán)S0S2S1S3a0a1a2......R(S0)R(S1)R(S2)R(S3)......+++R(S0)γR(S1)γ2R(S2)γ3R(S3)......γ∈[0,1)+++目標(biāo)：E[R(S0)γR(S1)γ2R(S2)γ3R(S3)+...]+++Policy(策略)已經(jīng)處于某個(gè)狀態(tài)s時(shí),我們會(huì)以一定的策略π來(lái)選擇下一個(gè)動(dòng)作a的執(zhí)行，然后轉(zhuǎn)換到另一個(gè)狀態(tài)。π：S→Aa=π（s）值函數(shù)（valuefunction）Vπ（s）=E[R(S0)+γR(S1)+γ2R(S2)+γ3R(S

5、3)+...

6、s0=s,π]值函數(shù)是回報(bào)的加權(quán)和期望，給定π也就給定了一條未來(lái)的行動(dòng)方案，這個(gè)行動(dòng)方案會(huì)經(jīng)過(guò)一個(gè)個(gè)狀態(tài)，而到達(dá)每個(gè)狀態(tài)都會(huì)有一定回報(bào)值，距離當(dāng)前狀態(tài)越近的其它狀態(tài)對(duì)方案的影響越大，權(quán)重越高。遞推Vπ（s）=E[R(S0)+γR(S1)+γ2R(S2)+γ3R(S3)+...]Vπ（s1）下一個(gè)狀態(tài)值函數(shù)的期望值然而我們需要注意的是：給定π后，在給定狀態(tài)s下，a是唯一的，但A→S可能不是多到一的映射立即回報(bào)=R(S0)+γ（E[R(S1)+γ2R(S2)+γ3R(S3)+...]）=R(S0)+γVπ（s'）(s':下一個(gè)狀態(tài))給定一個(gè)固定的策略π，我們

7、怎么解這個(gè)等式Vπ（s）=？(3,1)(3,2)(4,1)(2,1)0.80.10.1.....

8、S

9、個(gè)方程，

10、S

11、個(gè)未知數(shù)+1-112343210.520.330.37+1-0.09-0.82-1-0.88-0.83-0.85-1.001234321一個(gè)具體的例子對(duì)于給定的策略，我們可以寫(xiě)下這一策略的價(jià)值函數(shù)這是一個(gè)策略，但這不是一個(gè)偉大的策略Vπ（策略的價(jià)值函數(shù)）目的：找到一個(gè)當(dāng)前狀態(tài)s下，最優(yōu)的行動(dòng)策略π。定義最優(yōu)的V*如下：Bellman等式：（2）第二項(xiàng)是一個(gè)π就決定了每個(gè)狀態(tài)s的下一步動(dòng)作，執(zhí)行a后，s'按概率分布的回報(bào)概率和的期望定義了最優(yōu)的V*，我們?cè)?/p>

12、定義最優(yōu)的策略π*：S→Aπ*：實(shí)際上是最佳策略，最大化我們的收益。選擇最優(yōu)的π*，也就確定了每個(gè)狀態(tài)s的下一步動(dòng)作a。（3）注意：如果我們能夠求得每一個(gè)s下最優(yōu)的a，那么從全局來(lái)看，S→A的映射即可生成，并且是最優(yōu)映射π*。π*針對(duì)全局的s，確定了每一個(gè)s的下一個(gè)行動(dòng)a,不會(huì)因?yàn)槌跏紶顟B(tài)s選取的不同而不同。如何計(jì)算最優(yōu)策略？（MDP是有限狀態(tài)，有限動(dòng)作時(shí)）值迭代法1、將每一個(gè)s的V(s)初始化為02、循環(huán)直到收斂{對(duì)于每一個(gè)狀態(tài)s,對(duì)V(s)做更新}i）同步迭代法初始狀態(tài)所有的v(s)都為0.對(duì)s都計(jì)算新的V(s)=R(s)+0=R(s)。在計(jì)算每