（三）动态规划
(for pursue, do accumulation)
个人笔记，纯属佛系分享，如有错误，万望赐教。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。 动态规划(Dynamic Programming, DP)是在给定一个利用MDP描述的完备的环境模型下可以计算出最优策略的优化算法。
DP的两种性质：1.最优子结构：问题的最优解法可以被分为若干个子问题；2.重叠子问题：子问题之间存在递归关系，解法是可以被重复利用的。在强化学习中，MDP满足两个性质，DP的关键思想就是利用价值函数组织并结构化对好的策略的搜索。
1. 策略评估(Policy Evalution)
策略评估也被称为“预测问题”，就是计算任意一个随机策略\(\pi\)的状态价值函数\(v_\pi\)的问题。
在MDP中，由公式\((2.11)\)最终得到了状态价值函数的贝尔曼方程：\(v_ \pi(s)=\displaystyle \sum_a\pi(a|s) \sum_{s^\prime.r} p(s^\prime,r|s,a) [r+\gamma v_\pi(s^\prime)]\)，该方程可以通过迭代法求解，方法如下：
1.将状态价值函数序列记为\(\left\{ v_0,v_1,...,v_k\right\}\)
2.\(v_0\)作为初始状态价值函数，任意取值（在终止状态时，取值必须为0）
3.通过下面的公式进行迭代$$v_{k+1}=\displaystyle \sum_a\pi(a|s) \sum_{s^\prime.r} p(s^\prime,r|s,a) [r+\gamma v_k(s^\prime)] \tag{3.1}$$
序列\(\left\{v_k\right\}\)在\(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}=s\right] \\ & \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}=s\right] \\ &=\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}=s\right] \\ &=\mathbb{E}_{\pi^{\prime}}\left[R_{t+1}+\gamma R_{t+2}+\gamma^{2} v_{\pi}\left(S_{t+2}\right) | S_{t}=s\right] \\ & \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}=s\right] \\ & \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}=s\right] \\ &=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}=a\right] \\ &=\underset{a}{\operatorname{argmax}} \sum_{s^{\prime}, r} p\left(s^{\prime}, r | s, a\right)\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}=a\right] \\ &=\max _{a} \sum_{s^{\prime}, r} p\left(s^{\prime}, r | s, a\right)\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.
