一、动态规划的介绍
1、动态规划
动态规划 (Dynamic programming, DP)是一类优化算法
动态规划将待求解问题分解成若干子问题，先求解子问题，然后从这些 子问题的解得到目标问题的解。
2、动态规划与强化学习的关系
在完备的马尔可夫决策过程中，DP可用于计算最优策略。完备的马尔可夫决策过程就是Pss'和Rs都已知。
对于强化学习问题，传统的DP算法作用有限：
完备的环境模型只是一个假设
计算复杂度极高
但是，DP提供了必要的基础，所有其他方法都是对DP的近似。
3、基于动态规划的强化学习
1、策略迭代
策略迭代 (Policy iteration): 使用贝尔曼期望方程，求解最优策略。包含两个核心步骤：
（1）策略评估(Policy evaluation)：输入MDP (S,A,P,R,γ)和策略 π，输出价值函数 v_π
（2）策略提升(Policy Improvement)：输入MDP (S,A,P,R,γ)和价值函数 v_π，输出最优价值函数v_∗ 和 最优策略π_∗
2、价值迭代
价值迭代(Value iteration)：使用贝尔曼最优方程，求解最优策略
二、策略评估
1、迭代策略评估
作用：评估一个给定的策略 π，也称为“预测”问题
方法：迭代应用贝尔曼期望方程进行回溯
最终算法会收敛到 v_π
例：小型网格世界中的随机策略评估
每个动作的概率是0.25，折扣率γ为1，左上角和右下角为出口，价值函数一直为0，每个动作的奖励为-1
三、策略迭代
1、策略迭代
作用：找到最优策略
方法：策略迭代方法，交替迭代下述步骤：
贪婪方法改进策略如下：对每个状态，选那个能让“即时奖励 + 折扣后下一状态价值”最大的动作。
策略迭代方法的流程图：最终得到最优的策略
例子：小型网格世界中的策略改进（同步改进）
2、策略迭代算法
3、最优策略
经过上述的策略迭代算法一直迭代，如果迭代停止，满足贝尔曼最优方程，则得到最优策略π。
策略评估不需要收敛到v_π，再进行策略改进，若进行一次策略评估，就进行策略改进等效于价值迭代。
四、价值迭代（重要）
1、价值迭代与策略迭代关系
价值迭代等效于进行一次策略评估，就进行策略改进，直到得到最优策略。
然后将策略评估和策略改进合并得到：这是贝尔曼最优方程
2、价值迭代算法
作用：找到一个最优的策略 π
方法：迭代应用贝尔曼最优方程进行回溯
3、价值迭代算法
例子
