动态规划是一类优化算法，将待求解的目标将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到目标问题的解，动态规划的核心特点：

最优子结构 -- 子问题的最优解是可以得到的重复子问题 -- 子问题的解决方案可以存储和重用

在强化学习中引入动态规划主要有以下两个目的：

在完备的马尔可夫决策过程中（完备表示系统的奖励Rs和状态转移矩阵完全知道），DP可用于计算得到最优策略；尽管完备的环境模型只是一个假设且传统的DP计算复杂度高，但是DP为其他方法提供了基础，所以有必要学习DP在强化学习中的运用；

在强化学习中使用DP求解最优策略，主要有两种方式：

策略迭代：使用贝尔曼期望方程，求解最优策略，包含两个核心步骤：策略评估 -- 输入MDP（S，A，P，R，γ）和策略π，输出价值函数vπ策略提升 -- 输入MDP（S，A，P，R，γ）和价值函数vπ，输出最优价值函数v*，和最优策略π*价值迭代：使用贝尔曼最优方程，求解最优策略

注：价值迭代是策略迭代的特殊情况，效率稍高

1.策略迭代1.1 策略评估

策略评估顾名思义就是评估谁的策略Π更好，经过前面的学习知道可以将该问题转化，即预测一个给定的策略Π在所有状态s下的价值函数vΠ；

如何求出给定策略Π在所有状态s下的价值函数呢？ -- 迭代使用贝尔曼期望方程进行回溯，用初始价值函数迭代更新后继价值函数，直到算法收敛到vΠ，因此该方法也称为迭代策略评估

下面给出迭代策略评估的算法

系统任意初始化得到的V(s)并不是该策略Π真正的价值函数，因为并不满足贝尔曼期望方程，只有整个系统收敛时得到的价值函数才会满足贝尔曼期望方程；系统收敛得到的vΠ一定满足贝尔曼期望方程，但是不一定满足最优方程，因为只有最优策略的vΠ才满足贝尔曼最优方程；1.2 策略提升

前面介绍了如何预测一个给定策略Π在所有状态s下的价值函数vΠ，是否可以根据该价值函数来改进该策略得到策略Π'，使得策略Π'的价值函数高于策略Π的价值函数？

这里我们应用贪婪方法来改进策略Π，具体使用的是当时最大化动作价值函数寻找最优策略的方式（实际上就是调整策略Π在状态s下对应的动作a的概率）

注：此处的*应该改为Π，表示普通策略的最大化动作价值函数

1.3 策略迭代

在大部分问题中，需要进行多次的策略评估和策略改进的迭代才能得到该问题的最优策略

下面给出完整的策略迭代算法

由以上算法得到的最优策略Π，是满足贝尔曼最优方程的，也是满足系统收敛条件的，此时，对于所有的状态s对应的状态价值函数都是最优状态价值函数；

2.价值迭代

在策略迭代的策略评估过程中，我们并不需要迭代到k=∞即系统收敛时才进行策略提升，当策略评估迭代的次数k越小表示运算量越小，当k=1时，此时的策略迭代就成了价值迭代

在价值迭代中，因为只需要进行一次策略评估

而在策略提升中会使用最大化动作价值函数

将这两个函数合并可以得到这样一个公式（也就是将策略迭代中的策略评估和策略提升两个步骤合二为一）

这个公式实际上就是贝尔曼最优方程

满足贝尔曼最优方程的策略一定是最优策略，这也不难解释为什么可以通过价值迭代找到最优策略；

注：迭代使用贝尔曼最优方程进行回溯得到的最优策略Π，可能完全是一个全新的策略，因为在迭代过程中得到的价值函数可能不符合任何一个已知策略 -- 价值迭代并不是在已知策略上进行改进，而是直接基于价值寻找一个最优策略；

下面给出价值迭代算法