1. 馬爾科夫決策過(guò)程
馬爾科夫決策過(guò)程(Markov Decision Process) 是一個(gè)由4個(gè)元素組成的元祖)
組成。
為狀態(tài); 
為動(dòng)作; 
為概率轉(zhuǎn)移腌零，指定%7D)
; R為獎(jiǎng)勵(lì)函數(shù)梯找，指定)
；也可以指定為)
益涧。
很容易定義狀態(tài)函數(shù))
為折扣獎(jiǎng)勵(lì)的累計(jì)期望初肉，折扣比例
。
![V^\pi(s)= E[\sum_{t=0}^{\infty} \gamma^t R(s_t) | s_0=s, a_t=\pi(s_t)]](https://math.jianshu.com/math?formula=V%5E%5Cpi(s)%3D%20E%5B%5Csum_%7Bt%3D0%7D%5E%7B%5Cinfty%7D%20%5Cgamma%5Et%20R(s_t)%20%7C%20s_0%3Ds%2C%20a_t%3D%5Cpi(s_t)%5D)
從后向傳播的觀點(diǎn)——當(dāng)前的價(jià)值函數(shù)為及時(shí)獎(jiǎng)勵(lì)和未來(lái)獎(jiǎng)勵(lì)的期望之和饰躲，有：
%3D%20R(s)%20%2B%20%5Cgamma%5Csum_%7Bs%5E%5Cprime%7D%5CPr(s%5E%5Cprime%7Cs%2C%20a)V%5E%5Cpi(s%5E%5Cprime))
寫(xiě)成矩陣的形式牙咏，求解)
即為求解線(xiàn)性方程組：
%20%26%3D%20R(s)%20%2B%20%5Cgamma%20%5CPr(s%5E%5Cprime%7Cs%2C%20a)V%5E%5Cpi(s%5E%5Cprime)%20%5C%5C%20(I_%7B%7CS%7C%7D%20-%20%5Cgamma%20%5CPr(s%5E%5Cprime%7Cs%2Ca))%20V%5E%7B%5Cpi%7D(s)%20%26%3D%20R(s)%20%5Cend%7Balign*%7D)
最優(yōu)的價(jià)值函數(shù)%20%3D%20%5Cmax_%5Cpi%20V%5E%5Cpi(s))
， 滿(mǎn)足：
%3D%20R(s)%20%2B%20%5Cgamma%5Cmax_a%5Csum_%7Bs%5E%5Cprime%7D%5CPr(s%5E%5Cprime%7Cs%2C%20a)V%5E%5Cstar(s%5E%5Cprime))
2. 價(jià)值迭代算法
價(jià)值迭代的算法如下：
- 初始化
%3D0)
- 不斷迭代更新
%5Cleftarrow%20R(s)%2B%5Cgamma%20%5Cmax_a%5Csum_%7Bs%5E%5Cprime%7D%5CPr(s%5E%5Cprime%7Cs%2C%20a)V%5E%5Cpi(s%5E%5Cprime)%20%5Cquad%20%5Cforall%20s%5Cin%20S)
理解價(jià)值迭代嘹裂，需要理解
最優(yōu)算子是個(gè)壓縮映射妄壶。 定義最優(yōu)算子
如下，
%20%3D%20R(s)%20%2B%20%5Cgamma%20%5Cmax_a%5Csum_%7Bs%5E%5Cprime%7D%5CPr(s%5E%5Cprime%7Cs%2C%20a)V%5E%5Cpi(s%5E%5Cprime))
由于
是壓縮映射寄狼，存在唯一的不動(dòng)點(diǎn))
丁寄。這就是上述價(jià)值迭代算法的收斂原理，對(duì)進(jìn)行多次迭代后泊愧，會(huì)收斂到最優(yōu)價(jià)值函數(shù)伊磺。
壓縮映射具有如下性質(zhì): 對(duì)任意)
和)
，有
%20-%20B%5C%2C%20V_2(s)%7C%20%5Cleq%20%5Cgamma%20%5Cmax_%7Bs%20%5Cin%20S%7D%7CV_1(s)-V_2(s)%7C%7D)
上述性質(zhì)說(shuō)明了這樣一個(gè)事情: 對(duì)于)
進(jìn)行迭代后删咱，更新后的%20%3D%20B%5C%2CV%5E%7Bk%7D(s))
與原來(lái)的屑埋，最大誤差不超過(guò)-V_2(s)%7C%20%3C%20%5Cmax_%7Bs%20%5Cin%20S%7D%7CV_1(s)-V_2(s)%7C)
（因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Cgamma%20%3C%201" alt="\gamma < 1" mathimg="1">）。也就是每次迭代后痰滋，誤差以比例
減小摘能。
利用上面壓縮性質(zhì)，可以證明價(jià)值迭代算法的收斂性敲街。(下面方框中的內(nèi)容团搞，可以暫時(shí)跳過(guò))
首先，假設(shè)馬爾科夫決策過(guò)程中的獎(jiǎng)勵(lì)
是有界的多艇，即
逻恐。根據(jù)等比數(shù)列性質(zhì)，那么也是有上界的峻黍。
%3D%20%5Csum_%7Bt%3D0%7D%5E%7B%5Cinfty%7D%20%5Cgamma%5Et%20R(s_t)%20%5Cleq%20%5Csum_%7Bt%3D0%7D%5E%7B%5Cinfty%7D%20%5Cgamma%5Et%20R_%7Bmax%7D%20%3D%20%5Cfrac%7BR_%7Bmax%7D%7D%7B1-%5Cgamma%7D)
那么复隆，任意一次迭代過(guò)程中的值與)
之間的差最大為
。利用壓縮性質(zhì)有奸披，
%20-%20V%5E%7B%5Cstar%7D(s)%20%7C%20%5Cleq%20%5Cgamma%20%5Cfrac%7BR_%7Bmax%7D%7D%7B1-%5Cgamma%7D)
對(duì)初值)
進(jìn)行一次迭代后昏名，
%20-%20V%5E%5Cstar(s)%7C%20%26%5Cleq%20%5Cmax_%7Bs%20%5Cin%20S%7D%7CB%5C%2C%20V%5E0(s)%20-%20V%5E%5Cstar(s)%7C%20%5C%5C%20%26%5Cleq%20%5Cgamma%20%5Cmax_%7Bs%20%5Cin%20S%7D%20%7C%20V%5E0(s)%20-%20V%5E%7B%5Cstar%7D(s)%7C%20(%E5%8E%8B%E7%BC%A9%E6%80%A7%E8%B4%A8)%20%5C%5C%20%26%5Cleq%20%5Cgamma%5E2%20%5Cfrac%7BR_%7Bmax%7D%7D%7B1-%5Cgamma%7D%20(%E6%9C%80%E5%A4%A7%E8%AF%AF%E5%B7%AE)%20%5Cend%7Balign*%7D)
可以看到，每次迭代后阵面，最大誤差以比例
減小。
3. 策略迭代算法
策略迭代算法如下：
- 初始化.
- 策略評(píng)估：(一般而言，下式中
)
為固定策略由于策略更新)
%7D(s)%20%5Cleftarrow%20%5Csum_%7Ba%20%5Cin%20A%7D%20%5Cpi(s%2C%20a)%20%5Csum_%7Bs%5E%5Cprime%20%5Cin%20S%7D%5CPr(s%5E%5Cprime%20%7C%20s%2C%20a)(r(s%2Ca)%20%2B%20V%5E%7Bk%7D(s%5E%5Cprime))%20%5Cquad%20%5Cforall%20s%20%5Cin%20S)
- 策略更新：
%20%5Cleftarrow%20%5Carg%20%5Cmax_%7Ba%7D%20(R(s)%20%2B%20%5Cgamma%20%5Csum_%7Bs%5E%5Cprime%20%5Cin%20S%7D%20%5CPr(s%5E%5Cprime%7Cs%2C%20a)%20V%5E%5Cpi(s))%20%5Cquad%20%5Cforall%20s%20%5Cin%20S)
- 如果
)
與上次迭代相比沒(méi)有變化样刷，則停止仑扑；否則，轉(zhuǎn)回2置鼻。
更多關(guān)于策略迭代的分析镇饮，請(qǐng)看這里。
4. 線(xiàn)性規(guī)劃算法
線(xiàn)性規(guī)劃算法如下：
%20%5C%5C%20subject%20%5C%2C%5C%2C%5C%2C%20to%20%5Cquad%20%26%20V(s)%20%5Cge%20R(s)%20%2B%20%5Cgamma%20%5Csum_%7Bs%5E%5Cprime%20%5Cin%20S%7D%20%5CPr(s%5E%5Cprime%20%7C%20s%2C%20a)%20V(s%5E%5Cprime)%20%5Cquad%20%5Cquad%20%5Cforall%20s%20%5Cin%20S%2C%20a%20%5Cin%20A%20%5Cend%7Balign*%7D)
理解如下箕母，假設(shè)不等式約束以等式成立储藐，那么滿(mǎn)足最優(yōu)算子；如果存在某個(gè)使得不等式約束存在嚴(yán)格大于嘶是，優(yōu)化目標(biāo)一定會(huì)使得這個(gè)繼續(xù)減小钙勃，直至不等式約束以等式存在。所以最終的目標(biāo)聂喇，使得滿(mǎn)足方程最優(yōu)解辖源。
5. 附錄
-
最優(yōu)算子收縮性質(zhì)證明
![\begin{align*} |B V_1(s) - B V_2(s)| &= |R(s) + \gamma\max_a\sum_{s^\prime}\Pr(s'|s,a) V_1(s^\prime)- R(s) - \gamma\max_a \sum_{s^\prime}\Pr({s^\prime}|s, a)V_2(s^\prime) | \\ &= \gamma|\max_a\sum_{s^\prime}[\Pr(s^\prime|s,a)(V_1(s^\prime) - V_2(s^\prime))]| \\ &\leq \gamma \max_s| V_1(s) - V_2(s)| \quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \forall s \in S \end{align*}](https://math.jianshu.com/math?formula=%5Cbegin%7Balign*%7D%20%7CB%20V_1(s)%20-%20B%20V_2(s)%7C%20%26%3D%20%7CR(s)%20%2B%20%5Cgamma%5Cmax_a%5Csum_%7Bs%5E%5Cprime%7D%5CPr(s'%7Cs%2Ca)%20V_1(s%5E%5Cprime)-%20R(s)%20-%20%5Cgamma%5Cmax_a%20%5Csum_%7Bs%5E%5Cprime%7D%5CPr(%7Bs%5E%5Cprime%7D%7Cs%2C%20a)V_2(s%5E%5Cprime)%20%7C%20%5C%5C%20%26%3D%20%5Cgamma%7C%5Cmax_a%5Csum_%7Bs%5E%5Cprime%7D%5B%5CPr(s%5E%5Cprime%7Cs%2Ca)(V_1(s%5E%5Cprime)%20-%20V_2(s%5E%5Cprime))%5D%7C%20%5C%5C%20%26%5Cleq%20%5Cgamma%20%5Cmax_s%7C%20V_1(s)%20-%20V_2(s)%7C%20%5Cquad%20%5Cquad%5Cquad%5Cquad%5Cquad%5Cquad%5Cquad%5Cquad%5Cquad%5Cquad%5Cquad%5Cquad%5Cquad%20%5Cforall%20s%20%5Cin%20S%20%5Cend%7Balign*%7D)
Thus,
%20-%20BV_2(s)%7C%20%5Cleq%20%5Cgamma%20%5Cmax_s%7C%20V_1(s)%20-%20V_2(s)%7C)
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
