一、一些概念

馬爾科夫性質(zhì)：當(dāng)前時(shí)刻狀態(tài)僅僅與前一個(gè)時(shí)刻相關(guān)。

狀態(tài)轉(zhuǎn)移矩陣，表明了任意狀態(tài)a到狀態(tài)b的條件概率。

馬爾科夫過程（馬爾科夫鏈）：一個(gè)具有馬爾科夫性質(zhì)的無記憶的隨機(jī)過程，包含n個(gè)狀態(tài)。

馬爾科夫激勵(lì)過程(S,P,R,γ)是一個(gè)帶有value的馬爾科夫鏈。

用GtGt來表示t時(shí)刻會(huì)得到的總的return。出于數(shù)學(xué)計(jì)算、防止NaN無窮大的return等原因，引入折扣因子γ∈[0,1]γ∈[0,1]來對下一時(shí)刻的獎(jiǎng)勵(lì)和更遠(yuǎn)的獎(jiǎng)勵(lì)之間進(jìn)行取舍。（若所有序列都會(huì)在有限步終結(jié)，而且策略上合適，γ也可以取1。）

Gt=Rt+1+γRt+2+...=∑k=0∞γkRt+k+1Gt=Rt+1+γRt+2+...=∑k=0∞γkRt+k+1

價(jià)值函數(shù)v(s)，在馬爾科夫激勵(lì)過程（MRP）中表征指定狀態(tài)下，獲得的return的期望。是由所有包含該狀態(tài)的樣本Sample序列計(jì)算出來的。其中RsRs是立即獎(jiǎng)勵(lì)，可以認(rèn)為是離開狀態(tài)s時(shí)獲得的獎(jiǎng)勵(lì)。

v(s)=E[Gt|St=s]=E[Rt+1+γ(v(st+1)|St=s)]=Rs+γ∑s′∈SPss′v(s′)v(s)=E[Gt|St=s]=E[Rt+1+γ(v(st+1)|St=s)]=Rs+γ∑s′∈SPss′v(s′)

上面的公式可以向量化的表示為：

V=R+γPVV=R+γPV

而這個(gè)公式是有解析解的，MRP每個(gè)狀態(tài)的價(jià)值可以直接被解出來。

二、MDP

馬爾科夫決策過程(S,A,P,R,γ)，在MRP基礎(chǔ)上增加了有限的action集合。

策略，給定狀態(tài)時(shí)，關(guān)于行為的概率分布，用π來表示。決定了agent的行為。

MDP和馬爾科夫過程、MRP內(nèi)在的聯(lián)系。

狀態(tài)價(jià)值函數(shù)vπ(s)vπ(s)定義了在狀態(tài)s下，采用策略π，所能獲得的期望return。

行為價(jià)值函數(shù)qπ(s,a)qπ(s,a)定義了在狀態(tài)s下，采取行為a，并在之后采用策略π所能獲得的期望return。

這兩個(gè)價(jià)值函數(shù)之間密切相關(guān)。狀態(tài)的價(jià)值，就等于這個(gè)狀態(tài)下所有行為a產(chǎn)生的行為價(jià)值q，乘以做出該行為的概率（策略）π。反之，行為的價(jià)值，就等于這個(gè)行為所能產(chǎn)生的立即獎(jiǎng)勵(lì)immediate reward加上折扣因子乘以下一個(gè)狀態(tài)（到達(dá)這個(gè)狀態(tài)的概率由動(dòng)態(tài)轉(zhuǎn)移矩陣來確定）乘以這個(gè)狀態(tài)的狀態(tài)價(jià)值。

在MDP中，你能夠控制你的行為（通過策略），但是你無法控制環(huán)境（做出行為之后會(huì)發(fā)生什么），這個(gè)要靠動(dòng)態(tài)轉(zhuǎn)移矩陣來計(jì)算。

最佳價(jià)值函數(shù)v?(s)v?(s)和q?(s,a)q?(s,a)。最佳策略π?π?，就是在每個(gè)狀態(tài)下選擇最大的行為價(jià)值函數(shù)q*。

如何計(jì)算這個(gè)Q呢，Bellman Optimality Equation。也就是對每個(gè)狀態(tài)，其價(jià)值等于價(jià)值最大的行為的價(jià)值，而這個(gè)行為的價(jià)值又由直接獎(jiǎng)勵(lì)和行為*可能會(huì)導(dǎo)致的狀態(tài)價(jià)值有關(guān)。

v?(s)=maxaq?(s,a)v?(s)=maxaq?(s,a) q?(s,a)=Ras+γ∑s′∈SPass′v?(s′)q?(s,a)=Rsa+γ∑s′∈SPss′av?(s′)

而這個(gè)公式就無法直接解析求解了，求解的方法有：

• Value iteration
• Policy iteration
• Q-learning
• Sarsa

最后，對MDP的擴(kuò)展模型和其他一些概念進(jìn)行了簡介，如infinite/continuous/POMDP/belief states。

參考

• https://zhuanlan.zhihu.com/p/21378532

原文地址：http://cairohy.github.io/2017/08/29/deeplearning/%E3%80%8ADavid%20Silver%E5%BC%BA%E5%8C%96%E5%AD%A6%E4%B9%A0%E5%85%AC%E5%BC%80%E8%AF%BE%E3%80%8B-2%EF%BC%9AMDP/

總結(jié)

以上是生活随笔為你收集整理的David Silver强化学习公开课】-2：MDP的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。