1. 策略迭代算法：
- 初始化
%3D0)
.
- 策略評(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)
- 如果
)
與上次迭代相比沒有變化奢浑，則停止饮焦；否則琼掠，轉(zhuǎn)回2拒垃。
2. 策略改進(jìn)分析
(Lemma 1)策略更新可以使得)
單調(diào)遞增，最終收斂于)
瓷蛙。
假設(shè)第k次迭代前的策略為
, 迭代后的策略為
. 而為)
下的貪婪策略悼瓮。所以需要證明，%20%5Cgeq%20V%5Ek(s)%20%5Cquad%20%5Cforall%20s%20%5Cin%20S.)
下面證明更加通用的定理：
(Lemma 2)對(duì)任意的
和
艰猬，并且對(duì)于任意的
,
![V^{\pi'}(s) - V^\pi (s) = \frac{1}{1-\gamma} \mathbb{E}_{s' \sim \eta^{\pi'}_{s'}}[A^\pi(s', \pi')] \geq 0.](https://math.jianshu.com/math?formula=V%5E%7B%5Cpi'%7D(s)%20-%20V%5E%5Cpi%20(s)%20%3D%20%5Cfrac%7B1%7D%7B1-%5Cgamma%7D%20%5Cmathbb%7BE%7D_%7Bs'%20%5Csim%20%5Ceta%5E%7B%5Cpi'%7D_%7Bs'%7D%7D%5BA%5E%5Cpi(s'%2C%20%5Cpi')%5D%20%5Cgeq%200.)
這里
是折扣的state occupancy横堡，由從起始狀態(tài)
引入。
Proof:
考慮一個(gè)策略序列
, 其中
對(duì)于任意中間的
是一個(gè)隨時(shí)間變化的策略命贴，前
個(gè)時(shí)間步采用策略而后面的時(shí)間步采用策略。
根據(jù)差分求和食听，有胸蛛，
![V^{\pi'}(s) - V^\pi (s) = \sum_{i=0}^{\infty}[V^{\pi_{i+1}}(s) - V^{\pi_i}(s)]](https://math.jianshu.com/math?formula=V%5E%7B%5Cpi'%7D(s)%20-%20V%5E%5Cpi%20(s)%20%3D%20%5Csum_%7Bi%3D0%7D%5E%7B%5Cinfty%7D%5BV%5E%7B%5Cpi_%7Bi%2B1%7D%7D(s)%20-%20V%5E%7B%5Cpi_i%7D(s)%5D)
可見
和
僅在
上的動(dòng)作選擇有差異，所以兩者的值函數(shù)差異就體現(xiàn)在%20%3D%20%5Carg%5Cmax_%7Ba%7D%20Q%5E%5Cpi(s%3Ds_%7Bi%2B1%7D%2C%20a))
所以
)-Q^\pi(s', \pi(s))) \\ &= \sum_{i=0}^{\infty} \gamma^i \sum_{s' \in S} \mathbb{P}[s_i=s'|s_1=s, \pi']A^\pi(s', \pi') \\ &= \frac{1}{1-\gamma} \eta^{\pi'}_s(s') A^\pi(s', \pi') \\ &= \frac{1}{1-\gamma} \mathbb{E}_{s' \sim \eta^{\pi'}_{s'}}[A^\pi(s', \pi')] \\ &\geq 0 . \end{align*}](https://math.jianshu.com/math?formula=%5Cbegin%7Balign*%7D%20V%5E%7B%5Cpi'%7D(s)%20-%20V%5E%5Cpi%20(s)%20%26%3D%20%5Csum_%7Bi%3D0%7D%5E%7B%5Cinfty%7D%20%5Cgamma%5Ei%20%5Csum_%7Bs'%20%5Cin%20S%7D%20%5Cmathbb%7BP%7D%5Bs_i%3Ds'%7Cs_1%3Ds%2C%20%5Cpi'%5D(Q%5E%5Cpi(s'%2C%20%5Cpi'(s'))-Q%5E%5Cpi(s'%2C%20%5Cpi(s)))%20%5C%5C%20%26%3D%20%5Csum_%7Bi%3D0%7D%5E%7B%5Cinfty%7D%20%5Cgamma%5Ei%20%5Csum_%7Bs'%20%5Cin%20S%7D%20%5Cmathbb%7BP%7D%5Bs_i%3Ds'%7Cs_1%3Ds%2C%20%5Cpi'%5DA%5E%5Cpi(s'%2C%20%5Cpi')%20%5C%5C%20%26%3D%20%5Cfrac%7B1%7D%7B1-%5Cgamma%7D%20%5Ceta%5E%7B%5Cpi'%7D_s(s')%20A%5E%5Cpi(s'%2C%20%5Cpi')%20%5C%5C%20%26%3D%20%5Cfrac%7B1%7D%7B1-%5Cgamma%7D%20%5Cmathbb%7BE%7D_%7Bs'%20%5Csim%20%5Ceta%5E%7B%5Cpi'%7D_%7Bs'%7D%7D%5BA%5E%5Cpi(s'%2C%20%5Cpi')%5D%20%5C%5C%20%26%5Cgeq%200%20.%20%5Cend%7Balign*%7D)
綜上樱报，策略提升得證葬项。
