强化学习 3：基于模型——动态规划（Dynamic Programming）

基于动态规划的强化学习是一种【基于模型的强化学习方法】，也就是在已知模型的基础上判断一个策略的价值函数，并在此基础上寻找到最优的策略和最优价值函数，或者直接寻找最优策略和最优价值函数。

当问题具有下列特性时，通常可以考虑使用动态规划来求解：

① 最优子结构性质：一个复杂问题的最优解由数个小问题的最优解构成，可以通过寻找子问题的最优解来得到复杂问题的最优解；

②重叠子问题性质：子问题在复杂问题内重复出现，使得子问题的解可以被存储起来重复利用。所以动态规划经分解得到的子问题往往不是相互独立的。

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

DP方法和强化学习的核心思想是通过价值函数来搜索最优策略，一旦我们通过迭代更新价值函数找到了最佳价值函数，那么我们将很容易得到最优策略。

参考资料

[1] 叶强：《强化学习》第三讲 动态规划寻找最优策略

[2] 华师数据学院·王嘉宁：强化学习（四）：基于表格型动态规划算法的强化学习

[3] 时雨：强化学习4：动态规划

目录

  • 预测与控制
  • 策略评估（Policy Evaluation）——估计状态价值
  • 策略提升（Policy Improvement）——估计动作价值
  • 策略迭代（Policy Iteration）
  • 价值迭代（Value Iteration）
  • 策略迭代和价值迭代的区别
  • 广义策略迭代（Generalized Policy Iteration, GPI）

1 预测与控制

我们可以用规划来进行预测和控制。

1.1 预测问题

在给定策略下迭代计算价值函数。

给定一个MDP[公式]和策略[公式]，或者给定一个MRP[公式]，要求输出基于当前策略[公式]的状态价值[公式]。

1.2 控制问题

给定一个MDP[公式]，要求确定最优价值函数[公式]和最优策略[公式]。

2 策略评估（Policy Evaluation）——估计状态价值

策略评估是指根据后续的状态价值来更新当前时刻的状态价值，是对状态价值的一种估计，也就是解决“预测”问题。

动态规划是一种有模型的算法，已经保存当前时刻所有状态以及所有可能采取的动作，因此需要通过当前已知的这些信息来预估每个状态最终的价值，也就是说，这些状态价值是一个唯一的值，只是我们并不知道具体是多少，而动态规划的目的就是去找到这个值。

那么，如何评估智能体Agent不同的状态价值呢？采用的方法就是反向迭代应用贝尔曼方程。

状态价值函数的贝尔曼方程：（上一章笔记）

[公式]

其中状态[公式]是状态[公式]的下一个状态。

如果根据策略[公式]，则可以用贝尔曼方程不断地对每一个状态的价值函数进行迭代：

[公式]

其中，

[公式] —— [公式]时刻状态[公式]的价值函数的第[公式]次迭代值；

[公式] —— [公式]时刻状态[公式]的价值函数的第[公式]次迭代值。

在这个迭代式中我们假定了一个近似值函数序列[公式]，它们是处于收敛前的各个阶段的价值函数，这里是按照迭代顺序排列（迭代是由后往前反向迭代），和状态顺序是刚好相反的。

在这其中，我们对[公式]进行随机初始化，然后开始进行迭代更新，当[公式]时，[公式]将逐渐收敛于[公式]，我们就称这个过程为【迭代策略评估】。

3 策略提升（Policy Improvement）——估计动作价值

策略提升又叫做策略控制、策略更新、策略改进。

在上面，我们用策略评估来估计状态价值，当前的值函数已经是在当前策略[公式]下的最优值函数，能够准确指示在策略[公式]下的不同状态能够获得的期望收益。

但是，当前状态未必是最佳状态，所以这就要求我们进一步进行策略提升。

我们假设在状态[公式]时，我们执行一个新动作[公式]（并不是在策略[公式]指导下进行），并在此后一直运行原来的策略[公式]，计算其动作价值为：

[公式][公式]

我们把这个新动作 [公式] 构成的行为模式称为新策略 [公式]，对比 [公式] 和 [公式] 的好坏就是比较[公式]和[公式]，有可能后者就优于前者了。

实现策略提升的方法就是贪心算法（greedy algorithm）:

[公式][公式]

4 策略迭代（Policy Iteration）

策略迭代就是策略评估与策略控制相互交替的过程。在这个过程中，不断更新值函数与策略，最终收敛到最优策略与最优值函数，如下：

E表示策略评估，I表示策略提升。

首先进行的是策略评估，当前仅当策略评估收敛时，才进行策略控制。

有时候不需要持续迭代至最有价值函数，可以设置一些条件提前终止迭代，比如设定一个Ɛ，比较两次迭代的价值函数平方差；直接设置迭代次数；以及每迭代一次更新一次策略等。

5 价值迭代（Value Iteration）

价值迭代是将策略评估与策略控制相结合，即在每一次迭代中直接选择最优的动作来更新当前的状态价值，这样就能保证每个状态都能够保存最好的策略。

价值迭代是由贝尔曼最优方程得到的，贝尔曼最优方程为：

[公式]

价值迭代的迭代形式为：

[公式]

与策略迭代不同，价值迭代在每一次策略评估迭代之后就紧接着进行策略提升，将两者结合地更加紧密。

6 策略迭代和价值迭代的区别

策略迭代的策略评估过程中其收敛方向是当前策略下的价值函数，然后进行策略提升来优化策略。

而价值迭代的目的更加直接，是当前状态下的最优值函数，当最优值函数得到之后，只要在其基础上采用贪心算法就可以得到最优策略。

策略迭代的收敛速度更快一些，在状态空间较小时，最好选用策略迭代方法。当状态空间较大时，价值迭代的计算量更小一些，节约内存。

7 广义策略迭代（Generalized Policy Iteration, GPI）

无论是策略迭代还是价值迭代都是融合了【策略评估】与【策略提升】两个过程的产物，我们将这种搜索智能体Agent最优策略的方法统称为广义策略迭代。

几乎所有的强化学习问题都可以描述为GPI过程，因为它们都有着策略和价值函数这两个重要元素，两者相辅相成，策略的更新往往来源于价值函数，而价值函数的更新方向又是向着策略的，而当两者都处于稳定状态之后，那么值函数与策略一定已经收敛到了最优状态，它们之间的关系可以通过下图表示：

因为要遍历状态空间，DP方法往往在大规模的状态空间上不太适用，这被称之为“维度灾难”。

但是，相比于其他解决MDPs问题的方法，它又是最有效的，理论上可以搜索到最优策略。还有很多改进方法，例如异步动态规划（Asynchronous Dynamic Programming）、近似动态规划（Approximate Dynamic Programming）等等。

（待完善）