第3章　动态规划

3.1　动态规划简介

动态规划（Dynamic Programming）是运筹学的一个分支，是求解决策过程最优化的数学方法。20世纪50年代初，美国数学家R.E.Bellman（贝尔曼）等在研究多阶段决策过程的优化问题时提出了著名的最优化原理，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系逐个求解，创立了解决这类过程优化问题的新方法——动态规划。

其基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。适合于用动态规划求解的问题，经分解得到的子问题往往不是互相独立的，因此在解决子问题的时候，其结果通常需要存储起来用以解决后续复杂问题。这样就可以避免大量的重复计算，节省时间。

当问题具有下列特性时，通常可以考虑使用动态规划来求解：第一个特性是一个复杂问题的最优解由数个小问题的最优解构成，可以通过寻找子问题的最优解来得到复杂问题的最优解；第二个特性是子问题在复杂问题内重复出现，使得子问题的解可以被存储起来重复利用。

马尔可夫决策过程（MDP）具有上述两个特性。贝尔曼方程把问题递归为求解子问题，价值函数相当于存储了一些子问题的解，可以复用。因此可以使用动态规划来求解马尔可夫决策过程（MDP）。

使用动态规划算法求解马尔可夫决策过程（MDP）模型，也就是在清楚模型结构（包括状态转移概率、回报等）的基础上，用规划方法来进行策略评估和策略改进，最终获得最优策略。

策略评估（预测）：给定一个马尔可夫决策过程模型MDP：<S，A，P，R，γ>和一个策略π，要求输出基于当前策略π的所有状态的值函数V_π。

策略改进（控制）：给定一个马尔可夫决策过程模型MDP：<S，A，P，R，γ>和一个策略π，要求确定最优值函数V*和最优策略π*。