动态规划

动态规划（Dynamic Programming，简称DP）是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划常常适用于具有如下性质的问题：

• 具有最优子结构（Optimal substructure）
  • Principle of optimality applies
  • Optimal solution can be decomposed into subproblems
• 重叠子问题（Overlapping subproblems）
  • Subproblems recur many times
  • Solutions can be cached and reused

动态规划方法所耗时间往往远少于朴素解法。

马尔可夫决策过程MDP满足上述两个性质：

• 贝尔曼方程提供了递归分解的结构；
• 价值函数可以保存和重复使用递归时的结果。

使用动态规划解决MDP/MRP

动态规划需要满足MDP过程是已知的（model-based）。

• For Predict：
  • Input：MDP <S,A,P,R,γ> 和策略 π 或者是 MRP <S,P,R,γ>
  • Output：价值函数 vπ
• For Control：
  • Input：MDP <S,A,P,R,γ>
  • Output：最优价值函数 
    关键字：