漫谈强化学习中的引导搜索策略

©PaperWeekly 原创 · 作者｜李文浩

学校｜华东师范大学博士生

研究方向｜强化学习

本文将介绍 GPS 方法，GPS 方法是由强化学习大牛 Sergey Levine（在最近的 ICLR 2019 发表了 13 篇论文）于 2013 年提出的，目前被作为基础算法广泛应用于各种强化学习任务中。

其出发点在于纯粹的策略梯度方法在更新参数时不会用到环境模型因而属于一种无模型强化学习算法，所谓成也萧何败也萧何，虽然这使得策略梯度方法通用性很好，但是由于没有利用到任何环境的内在属性，使得其训练只能完全依靠试错，效率较低。

基于模型的路径优化算法（例如 iLQR）方法，能够充分利用环境模型，从而在利用较少训练样本的情况下即可使得算法收敛到局部最优解。

但是路径优化算法是一个开环方法，在随机环境下效果较差，虽然能够通过使用 MPC 方法（基本思想是每次只执行路径优化算法输出的第一个时间步的动作）来增加算法的稳定性，但是执行时耗时较长无法适用于实时任务。但是策略梯度方法是一个闭环方法，因而其对于随即环境的适应能力以及执行耗时上都能达到很好的效果。

因而一个直观的想法是，能不能将两者结合起来，用路径优化算法的输出结果来指导策略梯度方法的训练过程，从而提升策略梯度方法的效率呢？GPS 方法正是基于这种思想提出的。

本文主要对早期 GPS 的三篇论文进行了总结（还包括了一些其他论文的相关结论），具体请参阅文末的参考文献。

文章的结构如下：第一部分将会对最原始的 GPS 方法进行介绍，第二部分将会介绍一个改进版本。注意，这两种版本的 GPS 算法都必须事先已知环境模型。第三部分将介绍一个在未知环境模型（需要在算法训练的过程中对环境模型进行局部估计）的情况下也能够使用的 GPS 算法。

以上三种 GPS 算法均属于基于模型的强化学习算法（以后我将专门写一篇文章来介绍基于模型的强化学习算法）。为了方便起见，我将最原始的GPS算法记为 GPS-V1 (ICML 2013) [2]，改进版记为 GPS-V2 (ICML 2014) [3]，最后一个版本记为 GPS-V3 (NIPS 2014) [4]。

GPS-V1

原始版本的 GPS 算法基本思想是首先使用路径优化算法产生一些训练数据并加入训练集中用以指导后续策略梯度方法的训练。但是策略梯度方法是在线策略算法，只能使用当前策略采样得到的数据来估计梯度从而更新参数。

为了能够使用其他策略采样的数据，这里必须要使用一种技术：重要性采样。在这里我首先跑一下题来介绍一下重要性采样。

1.1 重要性采样

对于一个函数 以及一个概率分布 ，我们想要计算如下统计量：

我们知道，一般估计一个期望值的方法是从变量从属的概率分布中进行采样，然后计算均值。但是实际上概率分布 可能非常复杂，我们没有办法从其中进行采样。重要性采样方法通过从另外一个较为简单的分布 中采样出的样本对以上期望值进行估计：

1.2 基于重要性采样的策略梯度方法

让我们回到正题，利用这种方法就可以在估计当前正在学习的策略的梯度时采用其他策略采样出的样本：

其中 。从理论上来说 才是期望的无偏估计，这里为了减小训练时的方差采用了这个特殊值。

但是我们是在其他策略采样出的样本分布的基础上进行新策略的搜索，一旦新策略的样本分布与采样样本分布相距较远时，无法保证估计梯度的准确性。前面有工作是通过计算重要性权重的方差来判断新策略的准确性的 [6]，但是对于很长的路径，重要性权重在大部分地方都为0，方差也很小，但是并不能说明什么问题。

V1 版本的 GPS 算法通过在优化目标上额外加入重要性权重的对数值的方式，来“软最大化”重要性权重值，毕竟重要性权重越大，代表新策略分布与采样分布更为接近（但其实在采样分布概率较小的地方新策略分配一个较大的概率也会使得这个值比较大，所以感觉这种方法还是有很大缺陷的）：

1.3 指导样本的生成

GPS 系列算法希望使用路径优化算法生成的指导样本来引导策略梯度算法往高回报的区域搜索（而非暴力试错）。在之前的文章中我们讲过 iLQR 算法，但是只展开讲了确定性情况下的相关知识。

而策略梯度算法的应用场景大部分都是非确定性场景，即使是确定性场景，也会因为噪声的存在使其实际上同样是非确定性的。因而，下面我们主要关注非确定性场景下的指导样本生成。

在非确定性条件下，指导样本将服从某个概率分布，我们希望这个概率分布满足以下两个性质：

1. 各区域的概率密度不要过大（否则会使得重要性权重较小，使得指导样本对于梯度的贡献很小）
2. 该分布要尽可能覆盖高回报区域

GPS-V1 的作者发现，如果指导样本的分布 是分布 的 I-投影，即最小化如下 KL 散度：

得到的分布 即可满足以上两个性质。具体来说，上式右边第一部分保证了性质 2，右边第二部分保证了性质 1。那么剩余的问题是分布 的具体形式是什么呢？

GPS-V1 假设分布 是一个高斯分布，这是一个很自然的也是最容易想到的假设。而且如果我们希望能够用只能解决非随机环境的路径优化算法例如 iLQR 来解决随即环境下的规划问题的话，只能假设 为高斯分布。

为了能够直接使用类似 iLQR 算法的路径优化算法，我们这里再引入另外一个概念或者一个框架，叫做线性可解马尔科夫决策过程（LMDP）[5]。该框架的核心思想在于，摒弃动作（action）的概念。

智能体在不断优化其策略的过程中，会通过动作来改变其自身的状态转移概率（即在一个状态下转移到下一个状态的概率，策略在不断优化，那么每个状态下采取的动作也会变化，因而状态转移概率也会发生变化）。那么为何不放弃这一间接的做法，将策略直接定义为状态转移概率呢？即:

这就是 LMDP 的核心思想（这部分牵涉的知识较广，我同样会之后单独写一篇文章来详细介绍）。在 LMDP 的框架下，其回报函数变成如下形式：

其中 代表学习到的策略（即学习到的状态转移概率）， 代表智能体在没有任何算法控制的情况下的状态转移概率。当 表示一个均匀分布时，上式可转化为：

因而求解一个 LMDP 得到的指导样本的概率分布是满足前面提到的两个性质的。另外，可以证明，当状态转移是线性以及回报函数是二次函数的情况下，最优策略可以直接通过 iLQR 算法求解并且求解出的最优策略服从以下高斯分布：

代表确定环境下运用 iLQR 算法得出的最优策略， 代表确定环境下运行 iLQR 算法中的参数，具体参见 iLQR 算法。值得注意的是，由于 LMDP 并没有动作这一概念，之所以可以得出以上结论，是采用 LMDP 估计 MDP 得出的结论，具体细节我会单独写一篇文章细讲。

这里得出的结论是什么意思呢？其实就是说在运行 iLQR 算法时，将前向循环中计算最优动作的过程转化为从以上高斯分布中采样，然后将优化目标从仅仅最小化（或最大化）损失函数（或回报函数）转变为同时最大化最优策略的熵即可即可。这样导出的指导样本就满足我们的要求。

还有一个问题是 只有在状态转移是线性的情况下才是一个高斯分布，在状态转移是非线性的情况下， 是指导样本分布的一个局部的高斯估计。

由于 GPS 算法需要通过指导样本来将策略搜索的方向引导向高回报区域（这个高回报区域就是采样出指导样本的高斯分布的均值区域），但是这个分布只在指导样本附近是准确的，离得比较远就会出现较大误差，但是策略搜索的区域是任意的，就会出现梯度估计不准确的现象。

以上问题其实已经缓解了，前面提到的改进版的梯度公式中的正则项保证了策略搜索的区域会靠近指导样本的区域：

1.4 适应性指导样本分布

我们的策略是用某个特定的函数来进行估计的，而函数的表示能力是有限的（即使是神经网络，不同网络层数以及神经元个数都会对网络的表示能力产生影响。而所谓的通用函数估计器是在神经元个数无限的情况下才成立），那么强行让学习策略的分布与知道样本的分布尽可能一致可能会导致一些问题。

考虑下面这种情况：指导样本是在了解模型的情况下进行决策的，而策略梯度算法是在不知道模型的情况下进行决策的。因而前者除了观察到的状态外还利用了环境模型的信息，在相似的观察下可能会进行差异较大的决策。换句话讲，策略函数要尝试去拟合一些相似输入产生不同输出的数据点，这就会使得算法训练起来十分困难。

目前的算法流程是在算法初始化时就使用 iLQR 算法产生大量的指导样本，之后就不再产生新的指导样本了。为了解决以上问题，在策略不断更新的过程中，重新根据以下这个新的回报函数来运行 iLQR 算法产生新的指导样本：

通过以上回报函数产生的指导样本会尝试产生策略函数能够产生的样本分布。

1.5 算法框架

GPS-V1 的整体流程如下图所示：

这里有几点细节需要说明。

1. 算法第 6 行选取训练样本，其实主要包括以下两种样本。第一种，全部的指导样本；第二种，重要性权重较大的新样本，权重较大代表与指导样本更为相似。

2. 第 7 行进行参数更新时，是从上一步最优的参数作为初始点进行更新的。但是有时算法会陷入到局部最优解中，使得在该局部最优解下指导样本的重要性权重较小，那么指导样本就对梯度的估计无法产生影响，这样就会使得算法进一步往更差的方向更新。

为了防止以上问题，这一步的参数更新从两个不同的初始点开始：第一个初始点就是上一步更新的结果；而第二个则是求得一个使得当前采集到的回报较高的样本重要性权重最大的参数当作初始化参数。

3. 关于第 11-17 行，具体解释以下为什么要采取这些操作。当新搜索到的策略比原先的策略要好时，适当减小约束项的权重，这样可以增大下一步的策略搜索范围，换句话说就是可以步子迈得大一些。

反之，如果新搜索到的策略比上一步的要差，那么可能目前处于一个局部最优解较多的区域内，或者搜索区域过大使得梯度估计得不准确，这时候应该适当缩小搜索范围，在更接近指导样本的区域内搜索。再者，如果这样还是不能搜索到更好的策略，那么可能就是采样出的训练样本不好，这时候可以尝试重新采样。

以上就是 GPS-V1 算法的全部内容。其实在理解 GPS-V1 算法之后，后面两个版本就很简单了，因此我下面的内容相对也会少很多。

GPS-V2

作者在 GPS-V1 算法里发现了一个问题，其实 V1 算法也尝试去解决这个问题但是效果不好，这个问题就是 1.4 节中所描述的问题。

基于模型的路径优化算法产生的指导样本，不基于模型的策略梯度方法有时候并不能拟合出来，就像在上一节中讲到的那样，策略梯度算法观察不到一些通过模型才能反应出来的因素。这样会使得对于复杂问题学习出来的样本分布并不能与指导样本分布符合的很好。

GPS-V2 从另外一个角度解决了上述问题，即完全抛弃了策略梯度步骤，直接让策略通过对指导样本进行监督学习得出，并且在路径优化算法更新时考虑到与当前策略的距离并且尝试使得这个距离尽可能小。通过这样一种迭代更新的流程来使得两者最终匹配。

上述思想其实 GPS-V1 部分的 1.4 节已经考虑到了，但是是通过改变回报函数的方式达到的。GPS-V2 通过一种更直接的方式来建模，并抛弃了策略梯度部分，通过更加鲁棒的监督学习来学习策略，使得算法更新更为稳定。

具体来说，GPS-V2 求解以下优化问题：

其中第一个和第二个约束在路径优化算法运行的过程中已经默认保证了，实际我们只需要考虑第三个约束。注意优化目标就是 GPS-V1 中提到的 I-projection，只不过这里没有展开。我们采用拉格朗日乘子法（或者扩展拉格朗日乘子法）将上述问题转化为一个无约束优化问题：

而对于上述优化问题，我们可以采用对偶梯度下降法（DGD，或者交替方向乘子法，ADMM）分别更新三部分的参数。而对偶变量通过以下公式更新：

可以看出更新 其实就是在采用路径优化算法，更新 时就是在做监督学习。最后给出算法流程：

GPS-V3

其实我觉得最实用的还是 V3 版本的 GPS 算法，因为对于大部分现实问题，环境模型对与算法设计者来说都是未知的。但是前两个版本的 GPS 算法都假设环境模型是已知的（这样才能运行路径优化算法）。

GPS-V3 算法尝试解决事先未知环境模型场景下的相关问题，其实其基本思想也很直接，未知模型那我就估计模型，只不过全局模型肯定是很难估计准确的，而且要采用类似 iLQR 这种路径优化算法要对模型进行线性近似，因而更加不可能采用全局模型了。

GPS-V3 通过估计局部模型来缓解上述问题，但是采用局部模型又会引入类似 GPS-V1 这样的问题，在搜索区域距离当前样本过远时，算法误差就会较大，因而 GPS-V3 在 GPS-V2 的基础上再加了一个约束来解决这个问题。

具体来说，GPS-V1 是解决如下优化问题来产生指导样本的：

然后我们先转回到最原始 iLQR 算法的优化目标，不过因为这个时候我们是用估计的局部模型来运行该算法的，我们加上如下KL散度的约束来使得搜索范围不会离当前样本太远：

接下来同样采用拉格朗日乘子法（或者扩展拉格朗日乘子法）将其转变为无约束问题：

将上式中的 KL 散度展开：

和 GPS-V1 的优化问题对比，我们可以发现一个优秀的巧合，我们只需要对上式两边除以 ，并将回报函数转变一下：

就可以直接采用 GPS-V1 一样的方法产生指导样本。再将 GPS-V2 算法引入进来：

对于上式同样采用 GPS-V2 一样的 DGD 方法（或者 ADMM 算法）求解即可。具体流程如下：

这里需要再提一点，关于估计局部模型采用的方法。由于局部模型是一个高斯分布，我们其实只要去估计其均值即可（方差设定为 ）。而均值又是个线性函数，其实只要估计两个梯度即可：

因而可以用简单的线性回归方法。当然，对于较复杂的问题，一般会采用贝叶斯线性回归，选用高斯过程、深度网络或者高斯混合模型作为贝叶斯先验（这部分有机会我也会展开讲一讲）。

总结

最后，我引用 [1] 中的一段文字来总结 GPS 算法的核心思想：

Since each trajectory-centric teacher only needs to solve the task from a single initial state, it is faced with a much easier problem. The final policy is trained with supervised learning, which allows us to use a nonlinear, high-dimensional representation for this final policy, such as a multilayer neural network, in order to learn complex behaviors with good generalization.

A key component in guided policy search is adaptation between the trajectories produced by the teacher and the final policy. This adaptation ensures that, at convergence, the teacher does not take actions that the final policy cannot reproduce.

This is realized by an alternating optimization procedure, which iteratively optimizes the policy to match each teacher, while the teachers adapt to gradually match the behavior of the final policy.

参考文献

[1] Zhang, Marvin, et al. "Learning deep neural network policies with continuous memory states." 2016 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2016.

[2] Levine, Sergey, and Vladlen Koltun. "Guided policy search." International Conference on Machine Learning. 2013.

[3] Levine, Sergey, and Vladlen Koltun. "Learning complex neural network policies with trajectory optimization." International Conference on Machine Learning. 2014.

[4] Levine, Sergey, and Pieter Abbeel. "Learning neural network policies with guided policy search under unknown dynamics." Advances in Neural Information Processing Systems. 2014.

[5] Dvijotham, Krishnamurthy, and Emanuel Todorov. "Inverse optimal control with linearly-solvable MDPs." Proceedings of the 27th International Conference on Machine Learning (ICML-10). 2010.

[6] Jie, Tang, and Pieter Abbeel. "On a connection between importance sampling and the likelihood ratio policy gradient." Advances in Neural Information Processing Systems. 2010.

🔍

现在，在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧

关于PaperWeekly

PaperWeekly 是一个推荐、解读、讨论、报道人工智能前沿论文成果的学术平台。如果你研究或从事 AI 领域，欢迎在公众号后台点击「交流群」，小助手将把你带入 PaperWeekly 的交流群里。