进化策略与有限差分近似

进化策略又称随机搜索（random search）或梯度的随机有限差分近似，是一类数值优化方法，它不仅适用于不连续、不可微目标函数最优化问题，而且是一种无导数优化方法。

该算法来自OpenAI，具有里程碑意义。作者们设计了一类特殊的遗传算法——进化策略。该算法在各种强化学习基准上表现出色。接下来我会详细解释，为什么进化策略会是最优化中的核心方法并且它更能揭示强化学习的特点。

进化策略是梯度上升

进化策略(ES)算法目标是最大化奖励函数其中是维的。算法在当前状态小的扰动下计算奖励函数，然后将返回的函数值计入到一个新的状态。准确地说，算法采样个随机的方向，采样分布服从均值为零，方差不变的正态分布。然后算法根据以下规则更新状态：

为什么这是一个合理的更新？先考虑的情况，更新简化为：

其中：

意思是你应该沿着的方向走且与奖励大小成正比。更大的奖励意味着你应该在这个方向上走得更远。如果是负的，大的负奖励导致你向的负方向移动较远距离。为了方便理解，我们取，并且令等于：

我们可以清楚的看到，表示的是采用了有限差分近似的方式计算奖励函数在点处的近似梯度并且我们让沿着近似梯度方向移动，在这里方向就是近似梯度方向（需要注意的是这只是一个近似梯度方向，权重为）。和具有相同的期望值是不明显的，尽管计算简单。

有限差分的解释也有助于揭示这个算法本质上是奖励上随机梯度上升的一个例子：

然后，对随机方向求期望：

因此，对于足够小的，更新就像是对梯度的随机近似。

由在实验中，使用而不是。称为对偶采样(antithetic sampling)，这种对偶采样可以显著提高ES算法的实验性能。

该算法(基于对偶采样的进化策略)与Nesterov和Spokoiny在2010年提出的无导数优化方法完全等价。这种等价性，就可以解释所观察到的ES的一些优点，并提出一些可改进的方案。

减少方差

为什么性能比好？答案很简单的，尽管它们的期望值相同，但大大降低了方差。为了理解其中的原因，研究一下基本的二次型函数最优化问题：

然后可以明确写出两个更新：

多了两个项，这些项对收敛非常不利。首先，这项取决于偏移量。如果值很大，实际上告诉算法使用所有方向都是相等的。任何值得考虑的优化算法都不应该对这个偏移量敏感。第二项的方差成正比于，这相当不可取。

当我们采用批处理时，会发生什么？在这种情况下，我们有几个方向的和。如果都是正交的，在一个随机子空间上这就类似于沿着梯度移动。但如果比小得多，这几乎就是在一个随机子空间（random subspace directions，）内沿着有限差分近似的梯度移动。因此，这个算法和随机坐标上升非常相似。如果选择随机坐标（ random coordinates）而不是随机子空间方向在这些问题上也能表现得不错，我们也不会太惊讶。

Pieter Abbeel 在这个教程中提出了如何采用有限差分法求解强化学习的问题。这是一个经过深入研究的观点，但由于某种原因，与交叉熵或策略梯度方法相比，它不那么受欢迎。但是根据OpenAI最近的工作，原因可能是在所有的坐标上计算有限差分近似的开销太大了。实验清楚地表明，使用坐标方向的一个小的子集在计算上是廉价的（采用进化策略ES），并且可以找到一个很好的方向来提高在OpenAI Gym中许多基准测试的奖励。

随机搜索算法需要的迭代次数不超过梯度法的倍。如果使用批大小进行批处理，迭代次数将减少大约倍。但是，收益随着批处理大小增大将逐渐减少，最终最好还是计算完整的梯度。而且，即使方差减小了，但函数调用次数仍保持不变：每一个小批处理都需要次函数评价，所以函数求值的总数仍然是梯度法所需步骤数的倍。

因此，在串行情况下，批处理可能会对你造成伤害。理论上，使用批处理无法在迭代中得到线性减少，而批处理过大会减慢收敛速度。在极端情况下，本质上只是计算梯度的有限差分近似。但是在并行的情况下，批处理是非常好的，因为可以利用并行性，即使函数评估的总数大于串行情况，也可以显著减少收敛时间。

加速进化

对这个无梯度算法的一个很好的补充是增加动量（momentum）来加速收敛，只需要简单地将更新过程改为：

以在标准的策略梯度方法上提供进一步的加速。

使用你的梯度

这种随机搜索技术能用于训练神经网络进行监督学习吗？答案是取决于你有多少时间：如果你的神经网络模型有几百万个参数，这种有限差分方法可能需要的迭代次数是梯度下降法的一百万倍。正如Nesterov所说“如果你有梯度，你应该使用它们！”

回到最开始的问题：为什么有限差分法在强化学习中效果很好？因为，无模型强化学习本质上就是无导数优化。如果对系统行为（动态）的唯一访问是通过查询给定策略下的奖励，你从来不会得到奖励的导数。像策略梯度这样的方法，它们让你觉得你在进行梯度下降，但事实上下降的梯度并不是试图优化的函数的梯度！