




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
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的初
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 產(chǎn)品總經(jīng)銷服務(wù)協(xié)議書
- 領(lǐng)取丈夫遺產(chǎn)協(xié)議書
- 退休軍人移交協(xié)議書
- 遺產(chǎn)財產(chǎn)分配協(xié)議書
- 購買表演服務(wù)協(xié)議書
- 輕松掌握MS Office試題及答案
- 理解MySQL存儲類型分類試題及答案
- 經(jīng)濟法知識普及試題及答案
- 應(yīng)試策略2025年計算機二級MySQL試題及答案
- 數(shù)據(jù)庫管理與維護策略MySQL試題及答案
- 2024年安徽省初中(八年級)學(xué)業(yè)水平考試初二會考生物+地理試卷真題
- 2024年江西省中考生物·地理合卷試卷真題(含答案)
- 專題12 電功率圖像的四種類型(原卷版)-2023-2024學(xué)年九年級物理全一冊學(xué)優(yōu)生期中期末復(fù)習(xí)難點題型專項突破(人教版)
- DZ/T 0462.5-2023 礦產(chǎn)資源“三率”指標要求 第5部分:金、銀、鈮、鉭、鋰、鋯、鍶、稀土、鍺(正式版)
- 垃圾分類臺賬制度
- (高清版)JTG 3370.1-2018 公路隧道設(shè)計規(guī)范 第一冊 土建工程
- 《產(chǎn)生氣體的變化》小學(xué)科學(xué)六年級下冊課件
- 團隊境內(nèi)旅游合同2014版
- 二年級數(shù)學(xué)三位數(shù)加減三位數(shù)計算題同步作業(yè)練習(xí)題
- 中國藝術(shù)史智慧樹知到期末考試答案2024年
- 2024年天津市專業(yè)技術(shù)人員繼續(xù)教育公需課考試題+答案 (四套全)
評論
0/150
提交評論