动态规划方法（DP）指的是一类用来计算最优策略的方法。
特点是需要精确知道环境模型，然后把问题描述成为 MDP问题。
经典的动态规划由于精确的环境模型难以获得和过大的计算开销，使得他们在强化学习中应用不多，但是在理论上仍然十分重要。
强化学习所有的方法都可以看成是为了实现和DP相似的效果，只是弱化已知精确环境模型的假设或者计算量更小。
DP方法一般用于有限的MDP问题，即状态、动作和回报集合都是有限的。对于连续状态动作空间的问题，仅在特别的情况下具有精确解。一种获得近似解的通用方法是把连续状态动作空间离散化，然后利用有限MDP下的DP算法。（有限相当于离散，与连续对应）
强化学习的核心思想是使用值函数来组织和结构化搜索策略，DP方法同样如此。在介绍MDP中，我们通过贝尔曼最优方程求解值函数，然后通过值函数求解最优策略，贝尔曼最优方程为：
\[\begin{align} v_*(s) &= \max_{a \in \mathcal{A}(s)} q_{\pi_*} (s,a) \\ &= \max_a \mathbb{E} [R_{t+1} + \gamma v_*(S_{t+1})| S_t =s, A_t =a] \\ & = \max_a \sum_{s',r}p(s',r|s,a)[r+ \gamma v_*(s')] \tag{0-1} \end{align}\] \[\begin{align} q_*(s,a)& = \mathbb{E} \left[ R_{t+1} + \gamma \max_{a'} q_*(S_{t+1}, a') | S_t =s, A_t =a) \right] \\ & = \sum_{s', r} p(s',r|s,a) \left[r + \gamma \max_{a'} q_*(s', a') \right] \tag{0-2} \end{align}\]DP方法把贝尔曼等式变成了分配操作，即通过更新规则来逐步的改善对于期望值函数的近似效果。
与直接求解贝尔曼方程的区别是DP使用了迭代近似求解的方式。
1. 策略评估
什么是策略评估？
给定任意一个策略$\pi$，求解当前策略对应的状态值函数$v_\pi$的过程叫策略评估
其实很好理解，之前提到过值函数是求解策略的手段，贝尔曼方程也是直接操控的值函数，因此，我们需要先将策略装换成对应的值函数，然后对值函数进行提升，即使用贝尔曼最优方程，然后将提升后的值函数再转换成策略，上述过程就是求解最优策略的过程。
我们来思考怎样将策略转换为对应的值函数，即进行策略评估。
值函数的本质特性是满足一个迭代的关系，即贝尔曼方程，我们来回顾一下公式：
\[\begin{align} v_\pi(s) & \doteq \mathbb{E}_\pi[G_t | S_t =s] = \mathbb{E}_\pi[R_{t+1} + \gamma G_{t+1} | S_t =s] \\ &= \sum_a \pi(a|s) \sum_{s',r} p(s',r | s,a) \left[ r + \gamma \mathbb{E}_\pi [G_{t+1} | |S_{t+1} = s'] \right] \\ &= \sum_a \pi(a|s) \sum_{s',r} p(s',r | s,a) \left[ r + \gamma v_\pi (s') \right] \tag{1-1} \end{align}\]我们来观察一下公式1-1，首先这个公式满足迭代是肯定的，但是在迭代的过程中，涉及到策略$\pi$，所以我们可以精确求解这个公式，获取对应的1-1，但是又回到那个问题，计算量很大。我们将公式1-1改成迭代更新的方式：
\[\begin{align} v_{k+1}(s) & \doteq \mathbb{E}_\pi[R_{t+1} + \gamma v_k (S_{t+1}) | S_t =s] \\ &= \sum_a \pi(a|s) \sum_{s',r} p(s',r | s,a) \left[ r + \gamma v_k (s') \right] \tag{1-2} \end{align}\]通过对比公式1-1和1-2，不同的是前后的值函数不一样了，在公式1-1中，迭代的值函数是同一个值函数；在公式1-2中，迭代前后的值函数有一个更新的过程。
实际上公式1-2中的迭代更新过程，会将值函数收敛到一个不动点，即$v_\pi=v_k$，公式1-2代表的算法就是迭代策略估计
ps：在公式1-2的迭代策略估计过程中，每次更新都是计算所有可能的状态和回报，我们称其为期望更新；相对应的就是通过采样得到一个可能的后续状态$s’$，然后进行更新，这就是后面要将的蒙特卡洛法和时间差分法。
我们来思考一下迭代更新的方式和更新顺序：
第一种情况是使用两个数组，一个表示$v_{k+1}(s)$另一个表示$v_k(s)$，在更新时，我们更新的值并不会立刻影响到后续状态的更新，因为在一轮更新中$v_k(s)$不变。
第二种就是使用同一个数组，更新的$v_k(s)$会立刻影响到后续状态的更新。这种方式相对第一种收敛更快，最大幅度利用更新的信息。一般来说，将DP方法时，默认是第二种。
下面来看一下利用上述信息形成的伪代码：
看一下伪代码流程：
- 输入被评估的策略$\pi$
- 确定一个阈值，表示估算的精度
- 初始化每个状态的值函数，初始化为任意值（中止状态初始化为0）
- 不断循环迭代过程，直至更新的差值小于阈值
以上就是基于贝尔曼方程，进行迭代策略评估的方法。
2. 策略提升
策略提升的目的是找到一个更好的策略，但是新的策略满足什么条件，会是一个更好的策略呢？
我们首先看一下策略提升定理：
设$\pi$和$\pi’$都是确定性策略，满足所有的$s\in S$：
\[q_\pi(s,\pi'(s)) \geq v_\pi(s)\tag{2-1}\]那么新的策略就不会比原来的差，即对于所有的$s \in S$满足：
\[v_{\pi'}(s) \geq v_\pi(s) \tag{2-2}\]定理想要说明的是，只要按照新的策略选择动作，那么在旧策略下的动作值函数大于等于其状态值函数，这样的新策略就是一个更好的策略。
我们来看一下策略提升定理的证明：
\[\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}(s)\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) | S_{t+1}, A_{t+1}=\pi^{\prime}\left(S_{t+1}\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]\\ \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{2-3}\]证明的原理就是通过公式2-1推导出公式2-2，过程为先按照动作值函数的定义展开$q_\pi$，然后重复利用公式2-1的结论，最终得到了策略$\pi’$状态值函数的定义。
有了策略提升定理，说明我们只要构造一个新的策略，满足策略提升定理，那么就证明新策略比旧策略好。
我们再回顾一下状态值函数和动作值函数的关系：$v_\pi(s)=\Bbb E_{a \sim \pi}(q_\pi(s,a))$，即状态值函数是不同动作下动作值函数的期望，对于确定性策略两者是相等的，因为选择动作的概率为1，只有一个动作。
因此$\max_aq(s,a) \geq \Bbb E_\pi [q(s,a)]=v_\pi(s)$，所以新策略的公式为：
\[\begin{align} \pi'(s) & \doteq \arg \max_a q_\pi(s,a) \\ &= \arg \max_a \mathbb{E} [R_{t+1} + \gamma v_\pi(S_{t+1})| S_t =s, A_t =a] \\ &= \arg \max_a \sum_{s', r} p(s',r |s,a) [r + \gamma v_\pi(s')] \end{align}\tag{2-4}\]按照公式2-4更新策略真的可以收敛到最优策略吗？
我们来证明一下，我们假设目前已收敛，即$v_\pi=v_{\pi’}$，那么最终$v_{\pi’}$为：
\[\begin{align} v_{\pi'}(s) &= \max_a \mathbb{E} [R_{t+1} + \gamma v_{\pi'}(S_{t+1})| S_t =s, A_t =a] \\ &= \max_a \sum_{s', r} p(s',r |s,a) [r + \gamma v_{\pi'}(s')] \end{align} \tag{2-5}\]公式2-5是收敛以后的公式，即值函数“不能再好”，我们观察一下公式2-5，恰好是贝尔曼最优方程，因此，当策略收敛时，就是收敛到最优策略。
策略提升的整个流程同样适用于随机策略（但是会消除概率，只会存在为1的概率和为0.5的概率两种）
3. 策略迭代
在第一小节中，我们将了如何将策略转换成对应的值函数，在第二小节我们讲了如果根据值函数提升策略。不断重复上述两个过程，就可以不断的改善策略，直到最优策略。这就是策略迭代的思想。
\[\large \pi_0 \xrightarrow{\small E} v_{\pi_0} \xrightarrow{\small I} {\pi_1} \xrightarrow{\small E} v_{\pi_1} \xrightarrow{\small I} {\pi_2} \xrightarrow{\small E} v_{\pi_2} \xrightarrow{\small I} {\pi_3} \dots \xrightarrow{\small E} v_{\pi_*} \xrightarrow{\small I} {\pi_*} \tag{3-1}\]公式3-1中，就是不断使用策略评估与策略提升两个步骤，直至策略收敛到最优策略。
上图就是策略迭代的伪代码。
- 首先初始化值函数和策略
- 进行策略评估
- 进行策略提升（判断提升前后所有的策略选择的动作是否相同，若相同表示策略以提升到最优策略）
ps：不是很复杂的逻辑，就是循环调用策略评估与策略提升
4. 值迭代
在第三小节策略迭代中，我们可以发现。首先我们将策略评估成对应的值函数，然后使用值函数进行策略提升，转换成提升后的策略，判断新策略和旧策略是否一样，若不一样，说明没有收敛到最优（或者已收敛到最优，但是判断不出来），因此重复策略评估与策略提升两个步骤。
在这里我们可以发现，策略迭代很符合强化学习的思想：值函数只是求解策略的手段，我们最终求解的是策略。但是我们每次使用值函数来提升策略，却要使用策略来判断是否收敛到最优，所以导致不断地进行策略评估，这很繁琐。既然本质上使用值函数提升策略，为什么不直接用值函数判断对应的策略是否收敛到最优呢？这样就免去了策略评估的过程，且策略提升也可以优化为仅提升值函数。当值函数收敛时，我们再转化为策略。
上面的分析结果就是值迭代的过程（个人理解每次使用值函数迭代、判断是否收敛，所以叫值迭代）：
\[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 \sum_{s',r} p(s',r|s,a)[r + \gamma v_k(s')] \tag{4-4}\]公式4-4其实就是贝尔曼最优方程，这样我们在公式2-5已经证明过，它可以收敛，并且收敛到最优。
下面看值迭代的伪代码：
策略迭代的代码理解了，值迭代的就很简单了，不再赘述。
5. 广义策略迭代（Generalized）
在第三小节策略迭代的过程中，可以发现策略评估和策略提升是有次序的，即完全执行策略评估后，再进行策略提升，这样周而复始。
这种让策略评估和策略提升过程中交互进行的想法就是广义策略迭代（GPI），不依赖两个过程中的具体细节。
几乎所有的RL算法都可以使用GPI描述，他们都有策略和值函数，策略基于值函数进行改进。
上图就是策略评估和策略提升迭代的过程，当一个策略经过策略评估与策略提升后，并没有改变，说明收敛到最优策略了。
在GPI中，策略提升和策略评估是相互竞争又相互合作的。竞争体现在他们都在互相拉扯，如果值函数相对于策略是贪婪地，那么策略是不正确的；如果策略相对于值函数是贪婪的，那么值函数是不正确的。长期来看，两个过程互相作用，找到最终的解决方案，即最优策略和最优值函数。
上图是广义策略迭代的过程，体现了两个过程的交互。
6. DP的效率
DP算法对于状态空间很大的问题可能有些不切实际，但是与其他方法相比，DP实际上是十分有效的。
DP与直接策略搜索相比较。在状态数为n，动作数为k的MDP问题中，策略的空间大小是$k^n$（确定性策略，每个状态下可能有k个动作，即k个策略）。使用DP的时间复杂度是多项式级别的，使用直接搜索的时间复杂度指数级别的。
DP与线性规划相比较。线性规划方法的收敛性是要好于DP方法的，但是它能够求解的规模远远小于DP方法，差别在100倍左右。
但是仍旧倍维度灾难所控制，即状态空间或者动作空间的大小会随着状态或者动作的维度指数级增长。这也是表格式方法的诟病。不过使用异步DP会一定程度解决维度灾难的问题（每轮不需要扫描全部的状态）。
7. 结论
DP方法的一个特点是：所有的更新都依赖其后继状态的估计值，这称为自举（bootstrapping）
DP方法的另一个特点就是需要精确知道环境模型（计算期望值）
在接下来的笔记中，会介绍不需要模型也不需要自举的方法——蒙特卡洛法；不需要模型但是需要自举的方法——时间差分法。
