(for pursue, do accumulation)
个人笔记，纯属佛系分享，如有错误，万望赐教。
动态规划(Dynamic Programming, DP)是在给定一个利用MDP描述的完备的环境模型下可以计算出最优策略的优化算法。
1. 策略评估(Policy Evalution)
策略评估也被称为“预测问题”，就是计算任意一个随机策略(pi) 的状态价值函数(v_pi) 的问题。((2.11)) 最终得到了状态价值函数的贝尔曼方程：(v_ pi(s)=displaystyle sum_api(a|s) sum_{s^prime.r} p(s^prime,r|s,a) [r+gamma v_pi(s^prime)]) ，该方程可以通过迭代法求解，方法如下：(left{ v_0,v_1,...,v_kright}) (v_0) 作为初始状态价值函数，任意取值（在终止状态时，取值必须为0）(left{v_kright}) 在(k rightarrow infty) 时将收敛于(v_pi) 。该方法需要两个数组：一个用于存储旧的(v_k(s)) ，另一个用于存储新的(v_{k+1}(s)) 。也可以每次直接用新状态价值函数替换旧状态价值函数，这就是"in-place"更新。
2. 价值迭代(Value Iteration)
上述的策略评估方法是一个多次遍历状态集合的迭代过程，因此，可以通过价值迭代来缩短策略评估的步骤，公式如下：
[begin{aligned}
v_{k+1}(s)
& doteq max_a mathbb{E}[R_{t+1}+ gamma v_k(S_{t+1}|S_t=s,A_t=a)] \
&=max_a displaystyle sum_{s^prime,r}p(s^prime,r|s,a)[r+gamma v_k(s^prime)]
end{aligned} tag{3.2}
]
通过公式((3.2)) 可以在一次遍历后立即停止策略评估，只需要对每个状态更新一次，从而提升计算效率。
3. 策略改进(Policy Improvement)
通过策略评估得出策略的状态价值函数，可以根据策略改进定理(policy improvement theoroem)选择出贪心策略:
对于任意两个确定策略(pi) 和(pi^prime) ，(forall s in mathcal{S},q_pi(s,pi^prime(s)) geq v_pi(s)) ，则策略(pi^prime) 不劣于(pi) 。
在这种情况下，(v_{pi^prime}(s) geq v_pi(s)) 。证明过程如下
[begin{aligned}
v_{pi}(s)
& leq q_{pi}left(s, pi^{prime}(s)right) \
&=mathbb{E}left[R_{t+1}+gamma v_{pi}left(S_{t+1}right) | S_{t}=s, A_{t}=pi^{prime}(a)right] \
&=mathbb{E}_{pi^{prime}}left[R_{t+1}+gamma v_{pi}left(S_{t+1}right) | S_{t}=sright] \
& leq mathbb{E}_{pi^{prime}}left[R_{t+1}+gamma q_{pi}left(S_{t+1}, pi^{prime}left(S_{t+1}right)right) | S_{t}=sright] \
&=mathbb{E}_{pi^{prime}}left[R_{t+1}+gamma mathbb{E}_{pi^{prime}}left[R_{t+2}+gamma v_{pi}left(S_{t+2}right)right] | S_{t}=sright] \
&=mathbb{E}_{pi^{prime}}left[R_{t+1}+gamma R_{t+2}+gamma^{2} v_{pi}left(S_{t+2}right) | S_{t}=sright] \
& leq mathbb{E}_{pi^{prime}}left[R_{t+1}+gamma R_{t+2}+gamma^{2} R_{t+3}+gamma^{3} v_{pi}left(S_{t+3}right) | S_{t}=sright] \
& qquad vdots \
& leq mathbb{E}_{pi^{prime}}left[R_{t+1}+gamma R_{t+2}+gamma^{2} R_{t+3}+gamma^{3} R_{t+4}+cdots | S_{t}=sright] \
&=v_{pi^{prime}}(s)
end{aligned} tag{3.3}
]
由此，可以推出贪心策略(pi^prime) ，满足
[begin{aligned}
pi^{prime}(s)
& doteq underset{a}{arg max } q_{pi}(s, a) \
&=underset{a}{operatorname{argmax}} mathbb{E}left[R_{t+1}+gamma v_{pi}left(S_{t+1}right) | S_{t}=s, A_{t}=aright] \
&=underset{a}{operatorname{argmax}} sum_{s^{prime}, r} pleft(s^{prime}, r | s, aright)left[r+gamma v_{pi}left(s^{prime}right)right]
end{aligned} tag{3.4}
]
同时，可以写出它的状态价值函数：
[begin{aligned}
v_{pi^{prime}}(s)
&=max _{a} mathbb{E}left[R_{t+1}+gamma v_{pi^{prime}}left(S_{t+1}right) | S_{t}=s, A_{t}=aright] \
&=max _{a} sum_{s^{prime}, r} pleft(s^{prime}, r | s, aright)left[r+gamma v_{pi^{prime}}left(s^{prime}right)right] \
&=v_*(s)
end{aligned} tag{3.5}
]
4. 策略迭代(Policy Iteration)
[pi_{0} stackrel{E}{longrightarrow} v_{pi_{0}} stackrel{1}{longrightarrow} pi_{1} stackrel{E}{longrightarrow} v_{pi_{1}} stackrel{1}{longrightarrow} pi_{2} stackrel{E}{longrightarrow} cdots stackrel{I}{longrightarrow} pi_{*} stackrel{E}{longrightarrow} v_{*}
]
(stackrel{E}{longrightarrow}) 表示策略评估，(stackrel{I}{longrightarrow}) 表示策略改进，每一次的策略评估都是一个迭代计算的过程，需要基于前一个策略的状态价值函数开始计算。
由上图可知，策略迭代是通过策略评估和策略改进不断交互，使策略和状态价值函数最终收敛为最优。
5. 异步动态规划
上述的都是同步动态规划，它们的缺点是需要对MDP的整个状态集进行遍历。异步动态规划使使用任意可用的状态值，以任意规则进行更新，为了确保能够正确收敛，异步动态规划必须不断更新所有状态的值。
（转载请标明出处：https://www.cnblogs.com/HughCai/p/12770811.html ）
Reference
Richard S. Sutton and Andrew G. Barto (2017). Reinforcement Learning: An Introduction (Second Edition). Cambridge, Massachusetts London, England : The MIT Press.
Csaba Szepesvari (2009). Algorithms for Reinforcement Learning. Morgan & Claypool Publisers.
内容来源于网络如有侵权请私信删除
客服
