[Reinforcement Learning] 动态规划(Planning)

动态规划

动态规划（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满足上述两个性质：

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

策略评估

策略评估（Policy Evaluation）指的是计算给定策略的价值，解决的问题是 “How to evaluate a policy”。

策略评估的思路：迭代使用贝尔曼期望方程（关于 MDP 的贝尔曼期望方程形式见《马尔可夫决策过程》）。

策略评估过程如下图所示：

广义策略迭代

通过上述提到的策略评估我们不难发现，策略评估是一个不断迭代的过程

​ v_π(s)=E[R_t+1+γR_t+2+…|S_t=s]

那么问题来了，Does policy evaluation need to converge to v**πvπ?
我们是不是可以引入一个停止规则或者规定在迭代 kk 次后停止策略评估？
再进一步想，我们为什么不在每次策略评估的迭代过程中进行策略提升（等同于策略评估迭代1次后停止）？
注：这和后续要介绍的值迭代等价

因此我们可以把上述策略迭代的过程一般化，即广义策略迭代（Generalised Policy Iteration，简称GPI）框架

值迭代

介绍值迭代之前，我们先介绍下最优化原理。

最优化原理

最优化原理（Principle of Optimality）定义：

一个过程的最优决策具有这样的性质：即无论其初始状态和初始决策如何，其今后诸策略对以第一个决策所形成的状态作为初始状态的过程而言，必须构成最优策略。

最优化原理如果用数学化一点的语言来描述的话就是：

以状态 s 为起始点，策略π(a|s) 可以得到最优值 v_π(s)=v∗(s) 当且仅当：

• 任意状态s′ 对于状态 *ss 均可达；
• 以状态s′ 为起始点，策略 π 可以得到最优值 v_π(s′)=v∗(s′)。

MDP值迭代

值迭代（Value Iteration，简称VI）解决的问题也是 “Find optimal policy *ππ”。
但是不同于策略迭代使用贝尔曼期望方程的是，值迭代使用贝尔曼最优方程进行迭代提升。

值迭代与策略迭代不同的地方在于：

• Use Bellman optimal function, rather than Bellman expectation function
• Unlike policy iteration, there is no explicit policy
• Intermediate value functions may not correspond to any policy

e is no explicit policy**

• Intermediate value functions may not correspond to any policy