第三课&＃xff1a;动态规划

        课程标题本来是“Planning by Dynamic Programming”&＃xff0c;应该翻译为”利用动态规划方法进行规划“&＃xff0c;但是感觉有点长&＃xff0c;所以就使用”动态规划“作为标题&＃xff0c;大家理解就好......

        先说下这节课讲的主要内容&＃xff0c;主要有&＃xff1a;策略估计、策略迭代、值迭代、动态规划扩展、收缩映射定理。其中策略估计主要介绍如何利用迭代方法对策略的值函数进行估计&＃xff0c;也即我们在第一课中讨论的问题&＃xff1b;策略迭代与值迭代则是在策略估计的基础上&＃xff0c;引入策略改进&＃xff0c;从而达到控制的目的&＃xff0c;二者的主要区别是策略迭代基于贝尔曼期望方程和贪婪法&＃xff0c;而值迭代则是基于贝尔曼最优方程&＃xff1b;动态规划扩展介绍了几种改进方法&＃xff1b;最后的收缩映射证明了策略迭代与值迭代都将收敛到最优策略。

       1.动态规划简介

        什么是动态规划&＃xff08;DP&＃xff09;&＃xff1f;课程中给出了这样的释义&＃xff1a;Dynamic means the sequential or temporal component to the problem; Programming means optimising a "program", i.e. a policy。就是说”动态“指的是该问题的时间序贯部分&＃xff0c;”规划“指的是去优化一个计划&＃xff0c;换句话说&＃xff0c;优化一个策略。

        动态规划通常分为三步&＃xff1a;a&＃xff09;将问题分解为子问题&＃xff1b;b&＃xff09;求解子问题&＃xff1b;c&＃xff09;合并子问题的解。

        是不是所有问题都能用动态规划求解呢&＃xff1f;不是的&＃xff0c;动态规划方法需要我们的问题包含以下两个性质&＃xff1a;

        a&＃xff09;最优子结构&＃xff1a;保证问题能够使用最优性准则&＃xff0c;从而问题的最优解可以分解为子问题最优解&＃xff1b;

        b&＃xff09;重叠子问题&＃xff1a;子问题重复出现多次&＃xff0c;因而我们可以缓存并重用子问题的解。

        恰巧&＃xff0c;MDP满足上面两个性质&＃xff0c;贝尔曼方程给出了问题的迭代分解&＃xff0c;值函数保存和重用问题的解。因此&＃xff0c;我们可以利用动态规划方法来求解MDP规划问题&＃xff0c;此时假定MDP的模型是已知的&＃xff0c;DP方法既可用于预测&＃xff0c;也可用于控制&＃xff1a;