OpenAI等人在《Evolution Strategies as a Scalable Alternative to Reinforcement Learning》中提出了Evolution Strategies的并行实现：
1.介绍
开发一个可以完成在复杂、不确定environments中的任务挑战的agents，是AI的一个核心目标。最近，分析该问题的大多数流行范式已经使用许多基于Markov Decision Process(MDP)公式、以及value functions的RL算法。这些方法的成功包括了：从像素中学习玩Atari的系统【Mnih. 2015】、执行直升机动作【2006】或者玩专级业的围棋【2016】。
求解RL问题的一个可选方法是：使用黑盒最优化（black-box optimization）。该方法有名的有：direct policy search [Schmidhuber, 1998]、或者neuro-evolution，当应用到neural network时。在本paper中，我们研究了Evolution Strategies (ES)【Rechenberg, 1973】，在该类别中一种特殊的最优化算法集合。我们展示了：ES可以可靠训练nueral network policies，并能很好地扩展到现代分布式计算机系统中，用来控制在MuJoCo物理模拟器中的机器人【Todorov 2012】，并能玩具有pixel输入的Atari游戏。我们的关键发现如下：
- 1.我们发现：使用virtual batch normalization和其它关于neural network policy的再参数化（reparameterizations），可以极大改进evolution strategies的可靠性。如果没有这些方法，在我们的实验中ES会被证明非常脆弱；但有这些reparameterizations方法，我们可以在大多数environments中达到很强的结果
- 2.我们发现：evolution strategies方法可以高度并行化：通过引入一个基于公共随机数的新通信机制，当使用上千台workers时，可以在runtime上达到线性加速。特别的，使用1440 workers，我们已经能在10分钟内求解MujoCo 3D拟人任务。
- 3.evolution strategies的数据效率惊人的好：在大多数Atari environments上，当使用在3x和10x倍间的数据时，我们能匹配A3C的最终效果。在数据效率上的轻微减少，…
2.Evolution Strategies
Evolution Strategies (ES)是一类黑盒最优化算法，它是一种受天然进化（natural evolution）启发的启发搜索过程（heuristic search procedures）：
在每次iteration (一代：“generation”)，一群参数向量（基因型：“genotypes”）会被扰动（突变：“mutated”），它们的目标函数值（适应度：“fitness”）会被评估。具有最高得分的参数向量会接着重组（recombine）来形成下一代的群组（polulation），该过程会一直迭代，直到objective被完全最优化。
这类算法在关于他们表示群组、以及如何执行变异和重组上是有区别的。ES中最广为人知的是：【CMA-ES：covariance matrix adaptation evolution strategy，它表示了通过一个full-covariance multivariate Gaussian的群组。CMA-ES已经被广泛用于求解在低维、中维的最优化问题。
在本工作中，我们使用的ES版本，属于natural evolution strategies (NES)【Wierstra 2008】，并与Sehnke et al. [2010]的工作相近。假设：
- F表示在参数\(\theta\)上的objective function。
NES算法：
- \(p_{\phi}(\theta)\)（通过\(\phi\)进行参数化）：使用该参数分布来表示群组（population）
通过SGA(随机梯度上升)搜索\(\phi\)的方式，来最大化在群组上的平均目标值：
- \(E_{\theta \sim p_{\phi}} F(\theta)\)：表示在群组上的平均目标值
特别的，对于和REINFORCE[Williams 1992]相似的方式使用score function estimator来计算\(\nabla_{\phi} F(\theta)\)。NES算法会以如下estimator来更新在\(\phi\)上的gradient steps：
\[\nabla_{\phi} E_{\theta \sim p_{\phi}} F(\theta) = E_{\theta \sim p_{\phi}} \lbrace F(\theta) \nabla_{\phi} log p_{\phi}(\theta) \rbrace\]对于特例，其中：\(p_{\phi}\)是factored Gaussian，生成的gradient estimator也被称作：simultaneous perturbation stochastic approximation [Spall, 1992], parameterexploring policy gradients [Sehnke et al., 2010], or zero-order gradient estimation [Nesterov and Spokoiny, 2011]。
在本工作中，我们关注于RL问题，因而：
- \(F(\cdot)\)：会是由一个environment提供的随机返回
- \(\theta\)：是一个deterministic 或 stochastic plicy \(\pi_\theta\)的参数，描述了在该environment（被离散或连续actions控制）中的一个agent
在RL算法中的许多创新，关注于应对environment或policy的不可导问题。这种非平滑性（non-smoothness）可以使用ES来解决。我们会：将种群分布\(p_{\phi}\)实例化成一个具有均值为\(\phi\)和固定方差\(\sigma^2 I\)的isotropic multivariate Gaussian，它允许我们以平均参数向量\(\theta\)直接写出\(E_{\theta \sim p_{\phi}} F(\theta)\)：我们设置：
\[E_{\theta \sim p_{\phi}} F(\theta) = E_{\epsilon \sim N(0, I)} F(\theta + \sigma \epsilon)\]在该setup下，我们的stochastic objective可以被看成是一个关于原始objective F的Gaussian-blurred版本，免于非平滑性可以由environment或由policy选中的潜在离散actions被引入。接着在第3节讨论，ES和policy gradient方法是如何应对non-smoothness的。
我们的objective以\(\theta\)来定义，我们会直接在\(\theta\)上对score function estimator使用SGA最优化：
\[\nabla_{\theta} E_{\epsilon \sim N(0, I)} F(\theta + \sigma \epsilon) = \frac{1}{\sigma} E_{\epsilon \sim N(0, I)} \lbrace F(\theta + \sigma \epsilon) \epsilon \rbrace\]它可以使用样本来近似。生成的算法（1）会重复执行两个阶段：
- 1）随机扰动关于policy的参数，并通过运行在environment中的一个episode来评估生成的参数
- 2）组合这些episodes的结果，计算一个随机梯度估计（stochastic gradient estimate），并更新参数
算法1
2.1 扩展（Scaling）和并行化（parallelizing）ES
ES可以很好地扩展到许多并行workers上：
- 1）它在完整的episodes上操作，因此仅需要很少的workers间通信
- 2）每个worker获得的信息只是一个由单个episode返回的scalar；如果在最优化前，我们在workers间同步随机种子（random seeds），每个worker会知道其它workers使用什么扰动（perturbations），因此每个worker只需要与其它worker通信一个scalar，在参数更新上达成一致。因此，对比起policy gradient方法（需要workers间通信整个gradients），ES需要极低的带宽。
- 3）它不需要值函数近似（value function approximations）。具有value function estimation的RL是天然有顺序的：为了在一个给定policy上提升，value function的多次更新通常是需要获得足够的信号。每次该policy显著发生变化，对于value function estimator的多次迭代是必须的，以便捕获信号。
一个ES的简单的并行版本如算法2所示。主要的创新点是：该算法会利用共享的random seeds，它可以弹性地减小在workers间通信所需的带宽。
算法2
实际上，我们通过在训练开始时，每个worker会实例化一大块Gaussian noise的方式来实现sampling；接着在每次iteration时通过添加对这些noise variables的一个随机索引subset，来对这些参数进行扰动。尽管该意味着：扰动在跨各次迭代间不是严格独立的，在实操中我们并不认为这是个问题。使用该策略，我们可以发现：算法2的第二部分（9行-12行）只会花费少部分的总时间，即使时当使用达到1440并行workers时。当使用更多workers时，或者当使用非常大的neural networks，我们可以减少算法该部分的计算开销，通过workers只用扰动参数\(\theta\)的一个子集，而非所有；在本case中，扰动分布\(p_{\phi}\)对应于一个混合高斯（a mixture of Gaussians），更新等式仍保持不变。在非常极端的情况下，每个worker只会扰动参数向量的单个坐标，这意味着我们会使用纯有限差分（pure finite differences.）
为了减小variance，我们使用对偶抽样（antithetic sampling） Geweke【1988】，也被称为 镜像抽样（mirrored sampling）【Brockhoff 2010】：也就是说，对于Gaussian noise vector \(\epsilon\)， 我们总是评估扰动pairs：\(\epsilon, -\epsilon\)。我们发现，它对于执行fitness shaping很有用：在计算每个参数更新时，通过使用一个rank变换到returns中。这么做可以移除在每个种群（population）中的异类个体（outlier）的影响，为ES减少趋势，在训练时间时更早达到局部最优。另外，我们还对我们的policy network的参数使用weight decay：这可以防止参数增长到非常大（对比perturbations）。
不同于【Wierstra2014】，我们不会看到在训练期间对\(\sigma\)自适应的好处，因此我们将它看成是一个固定的超参数。我们会在参数空间直接执行最优化。。
上述提到的Evolution Strategies是在full-length episodes上工作的。在一些罕见的场景中，这会导致低CPU利用率，因此一些episodes会比另一些运行更多的steps。对于该原因，我们可以为所有workers限定长度为一个常数：m个steps，我们可以动态调节训练过程。例如，通过将m设置成每个episode的steps的均值的两倍，我们可以保证CPU利用率在最差时也会在50%之上。
2.2 网络参数的影响
像Q-learning和policy gradients的RL算法，会通过对来自一个stochastic policy的actions进行sampling来进行探索，Evolution Strategies会从policy参数的实例中进行sampling来学习信号。在ES中的探索（Exploration）是通过参数扰动（ parameter perturbation）的方式驱动的。对于ES来说，在参数\(\theta\)之上进行提升，一些种群成员必须要比其它成员达到更好的return：例如，Gaussian perturbation vectors \(\epsilon\)偶尔会导致新的个体\(\theta + \sigma \epsilon\)具有更好的return。
对于Atari environments，我们发现：在DeepMind的convolutional架构上的 Gaussian parameter perturbations，不总是产生足够的探索（adequate exploration）：对于一些environments，随机扰动参数会趋向于编码这样的policies：那些总是采用指定action，忽略掉state已给定作为input。然而，我们发现：对大多数游戏来说，在policy specification中使用虚拟batch归一化（virtual batch normalization），可以匹配policy gradient方法的效果。。。。
3.在parameter空间上的smoothing vs. 在action空间上的smoothing
3.1 什么时候ES要比policy gradients要好？
给定对decision问题进行smoothing的两个方法，你应该怎么使用？答案非常依赖于decision问题的结构，以及使用哪种类型的 Monte Carlo estimator来估计gradients \(\nabla_{\theta} F_{PG}(\theta)\)和\(\nabla_{\theta} F_{ES}(\theta)\)。假设：在return和单个actions间的相关性（correlation）很低（对于任何很难的RL问题来说都是true的）。假设：我们使用单个Monte Carlo (REINFORCE) 来近似这些gradients，我们有：
\[Var[\nabla_{\theta} F_{PG}(\theta)] \approx Var[R(a)] Var[\nabla_{\theta}] log p(a; \theta)] \\ Var[\nabla_{\theta} F_{ES}(\theta)] \approx Var[R(a)] Var[\nabla_{\theta} log p(\bar{\theta}; \theta)]\]如果两种方法都执行相同数目的探索，\(Var[R(a)]\)对于两个表达式来说是相似的。因而在第二项上有会区别。这里我们有：\(\nubla_{\theta} log p(a; \theta) = \sum\limits_{t=1}^T \nabla_{\theta} log p(a_t; \theta)\)是一个关于T个不相关项的求和，因此policy gradient estimator的variance会随T接近线性增长。evolution stategies的对应项，\(\nabla_{\theta} log p(\bar{\theta}; \theta)\)，与T相互独立。对于具有非常多time steps的长episodes，Evolution strategies会比policy gradients有优势。实际上，steps T的数目上通常在policy gradient方法中会通过discounting rewards而减小。如果actions的影响是短暂的，这允许我们动态减小在我们的gradient estimate中的variance，这在Atari games等应用中非常关键。然而，如果actions具有很长的影响，该discounting会造成gradient estimate有偏。减小T的有效值的另一个策略是：使用value function approximation。这也是有效的，但运行的风险仍是：对gradient estimates有偏。因而，如果没有合适的value function estimates提供，Evolution strategies是对于time steps T的数目过长、actions具有长持续效应时的一种更好选择。
3.2 问题维度
ES的梯度估计可以被解释成：在高维空间中的一个随机有限差分。确实，使用事实 \(E_{\epsilon \sim N(0,I)} \lbrace F(\theta) \epsilon / \sigma \rbrace = 0\)，我们得到：
\[\nabla_{\theta} \eta(\theta) = E_{\epsilon \sim N(0,I)} \lbrace F(\theta + \sigma \epsilon) \epsilon / \sigma \rbrace = E_{\epsilon \sim N(0, I)} \lbrace F(\theta + \sigma \epsilon) - F(\theta)) \epsilon / \sigma \rbrace\]很明显的是，ES可以被看成是：计算在一个随机选中方向上的一个有限差分导数估计，特别是\(\sigma\)会变小。ES与有限差分的相似性（resemblance），会建议该方法会与参数\(\theta\)的维度进行较差扩展。理论分析确实展示了：对于通用的非平滑最优化问题，最优化的steps数据随维度线性扩展。然而，很重要的是：这并不意味着：当使用ES最优化时，更大的neural networks会要比更小的networks效果更差：重要的是最优化问题的难度，或固有维度。为了看到：我们模型的维度可以被完全独立于最优化问题的有效维度，考虑一个回归问题：其中我们使用一个线性模型\(\hat{y} = x \cdot w\)来近似一个单变量y：如果我们质疑在该模型中的features和参数数目，通过将x与自身进行拼接，该问题不会变得更复杂。ivv应用到更高维问题时，ES算法会做完全相近的事情，只要我们将noise的标准差除以2，同时learning rate也除以2.
实际上，我们观察到：当使用ES到更大networks上时，会有稍微更好的结果。例如，我们同时尝试：使用A3C的更大网络和更小网络来学习Atari 2600游戏，使用更大network来平均获得更好结果。我们假设：这是因为相同效应，会做出关于大的neural networks标准的gradient-based最优化，比小网络更容易：大网络具有更少的局部最小值。
3.3 不计算gradients的优点
除了很方便并行化外，在长action序列和delayed reward的情形下，黑盒最优化算法（像ES）具有比计算gradients的RL技术具有其它优点。分布式实现ES的通信开销，要低于完全RL的方法（比如：policy gradients和Q-learning），因为在进程间通信的信息只有scalar return和用于生成扰动\(\epsilon\)的random seed，而非一个完整的梯度（full gradient）。同时，ES可以最大化处理sparse和delayed rewards；只要一个episode的总return被使用，而其它方法会使用独立rewards、以及准确的timing。
由于不需要backpropagation，黑盒优化器（black box optimizers）会将每个episode的计算量减少两三倍，内存则更多。另外，不需要显式计算一个分析梯度，可以避免梯度爆炸的问题（这在RNN中很常见）。通过对在parameter空间中的cost function进行smoothing，我们可以减小造成这些问题的病理骨折：将cost functions限定为足够平滑，不会有梯度爆炸。极端上，ES允许我们将非微分元素包含到我们的框架中，比如：使用hard attention的模块。
黑盒最优化方法（Black box optimization）是唯一适合低精度硬件进行深度学习的。低精度计算（Low precision arithmetic），比如在binary neural networks，要比高精度成本便宜很多。当最优化这样的低精度结构时，当使用gradient-based方法时，有偏的低精度梯度估计可能是个问题。相似的，对于neural network inference的指定硬件（比如：TPUs），当使用ES最优化时可以被直接使用，而它们有限的内容通常会让backpropagation不可能。
通过在参数空间进行扰动（而非action空间），黑盒优化器天然对于agent在environment中的动作频率是不变的。对于MDP-based的RL算法，另一方面，frameskip是一个很重要的参数，对于最优化的成功来说很重要【Braylan 2005】。而这对于游戏（只需要短期的planning和action）来说通常是一个可解问题，对于学习更长期的策略行为来说是个问题。对于这些问题，RL需要成功，当使用黑盒最优化时它不是必要的。
#