Evolution Strategies
神经网络模型具有高度的表达能力和灵活性，如果我们能够找到合适的模型参数集，则可以使用神经网络来解决许多具有挑战性的问题。
深度学习的成功很大程度上取决于使用反向传播算法来有效地计算每个模型参数上目标函数的梯度的能力。利用这些梯度，我们可以有效地在参数空间上进行搜索，以找到通常足以使我们的神经网络完成困难任务的解决方案。但是，存在许多问题，无法使用反向传播算法。
例如，在强化学习（RL）问题中，我们可以训练神经网络做出决策，以执行一系列动作来完成环境中的某些任务。但是，估计将来提供给智能体的奖励信号与智能体现在执行的操作之间的梯度并非无关紧要，特别是如果奖励在将来的许多时间步后才获取时。
即使我们能够计算出准确的梯度，也存在卡在局部最优值中的问题，很多的RL任务都存在该问题。
Credit assignment问题在RL中是一个热点问题，与其说计算未来的奖励对现在的策略网络的梯度，不如直接抛弃梯度信息，尝试使用黑盒优化的方式去训练智能体，比如Genetic Algorithms(GA) 或者 Evolution Strategies(ES)。
我们可以将进化策略定义为一种算法，该算法可为用户提供一组候选解决方案以评估问题。
solver = EvolutionStrategy()
while True:
# ask the ES to give us a set of candidate solutions
solutions = solver.ask()
# create an array to hold the fitness results.
fitness_list = np.zeros(solver.popsize)
# evaluate the fitness for each given solution.
for i in range(solver.popsize):
fitness_list[i] = evaluate(solutions[i])
# give list of fitness results back to ES
solver.tell(fitness_list)
# get best parameter, fitness from ES
best_solution, best_fitness = solver.result()
if best_fitness > MY_REQUIRED_FITNESS:
break
Simple Evolution Strategy
最简单的进化策略之一就是从正态分布中采样一组解决方案，均值$\mu$，固定标准偏差$\sigma$。比如在一个二维问题中，$\mu =(\mu_x, \mu_y)$，$\sigma=(\sigma_x, \sigma_y)$。 最初，将$\mu$设置为原点，在对适应度结果进行评估之后，我们将$\mu$设置为总体中的最佳解，并围绕该新均值采样下一代解。
该简单的算法通常仅适用于简单问题，考虑到它的贪婪性，它会选择最佳解决方案而抛弃其他所有方案，并且倾向于陷入局部最优。更好的选择策略是从代表更多样化想法集的概率分布中抽样下一代，而不是仅从当前一代的最佳解决方案中抽样。
Simple Genetic Algorithm
简单版本GA：仅保留当前一代中性能最佳的解决方案的10％，然后让抛弃其他候选者。在下一代中，要采样一个新的解决方案，就是从上一代的幸存者中随机选择两个解决方案，并重新组合它们的参数以形成一个新的解决方案。 此交叉重组过程使用掷硬币来确定从哪个父级获取每个参数。在重组过程之后，具有固定标准偏差的高斯噪声也将注入到每个新解决方案中。
遗传算法通过跟踪各种各样的候选解决方案来繁殖下一代来帮助实现多样性。然而，实际上，随着时间的流逝，精英生存者中的大多数解决方案趋于收敛到局部最优。有多种更复杂的改进遗传算法，例如CoSyNe，ESP和NEAT，其思想是将种群中的相似体聚集在一起成为不同的物种，以随着时间的推移保持更好的多样性。
Covariance-Matrix Adaptation Evolution Strategy (CMA-ES)
Simple ES和Simple GA的一个缺点是我们的标准偏差噪声参数是固定的。有时候，我们想探索更多并增加搜索空间的标准偏差，但是有时候，我们有信心策略已经接近一个最佳优化，仅仅想微调策略而已。
CMA-ES是可以获取每一代的结果，并自适应地增加或减少下一代的搜索空间。它不仅将适应均值$\mu$和$\sigma$参数，还将计算参数空间的整个协方差矩阵。 在每一代中，CMA-ES都会提供多元正态分布的参数以从中提取候选者。该算法是最流行的无梯度优化算法之一，并且已成为许多研究人员和从业人员的首选算法。唯一真正的缺点是，如果我们需要求解的模型参数数量很大，则性能会很高，因为协方差计算为$O(N^2)$，尽管最近有一些近似方法$O(N)$。通常当搜索空间少于一千个参数时，CMA-ES是首选算法。
Natural Evolution Strategies
到目前为止，提到的算法的一个弱点是它们放弃了大多数解决方案，而只保留最佳解决方案。 弱的解决方案包含有关不执行操作的信息，这对于为下一代计算更好的估算值而言是有价值的信息。
NES的核心思想是： 使采样解决方案的适用性得分的期望值最大化。如果预期结果足够好，则抽样总体中表现最好的成员将更好，因此针对预期进行优化可能是明智的方法。最大化抽样解决方案的预期适应性评分与最大化整个人群的总体适应性评分几乎相同。
关于Fitness的近似梯度核心公式为：
$$ \triangledown_\theta J(\theta) \approx \frac{1}{N} \sum_{i=1}^{N}F(z^i) \triangledown_\theta \log \pi(z^i, \theta) $$
OpenAI Evolution Strategy
在OpenAI的论文中，他们实施了进化策略，这是上一个概述的REINFORCE-ES算法的特例。 特别是，$\sigma$固定为常数，并且每一代仅更新$\mu$参数。
Fitness Shaping
Fitness Shaping使我们能够避免总体中的离群值控制先前提到的近似梯度计算。如果一个特定的$F(z^m)$大于总体中其他$F(z^i)$的大小，则该异常值将成为梯度的主导因素，并且增加了算法陷入局部最优的可能性。为了减轻这种情况，可以对适应度进行等级转换。我们不使用实际的适应度函数，而是对结果进行排名，并使用与解决方案在总体中的排名成正比的增强适应度函数。说白了就是每轮迭代计算适应度之后对其先排序，然后将其rescale到一个相对小的区间， 比如最好的0.5， 次好0.49，依次类推，次差-0.49，最差-0.5，将这些值作为计算fitness梯度的值方向传播。变相地可以理解为是将fitness的结果直接进行Batch Normalization操作。
如果目标函数对于给定的策略网络而言不确定，则Fitness Shaping对于RL任务非常有用，因为在RL中，环境通常是随机生成的地图且各种对手具有随机策略的情况。 它对于优化确定性良好的策略不太有用，并且使用Fitness Shaping有时会减慢找到一个好的解决方案所需的时间。
ES for Reinforcement Learning
尽管RL算法要求在每个时间步长都将奖励信号反馈给智能体，但ES算法仅关心在环境中智能体在其执行动作结束时获得的最终累积奖励。 在许多问题中，我们仅知道任务结束时的结果，例如，智能体是赢还是输，机器人手臂是否捡起物体，智能体是否还活着，在这些问题中，使用ES与传统RL方法相比更具有优势。
下面是ES仅仅考虑整个最终积累reward的伪代码：
def rollout(agent, env):
obs = env.reset()
done = False
total_reward = 0
while not done:
a = agent.get_action(obs)
obs, reward, done = env.step(a)
total_reward += reward
return total_reward
我们可以将上面的rollout方法定义为智能体的策略网络参数映射到其适应度评分中的目标函数，并使用ES方法找到合适的模型参数集。
Deterministic and Stochastic Policies
在RL中，可以使用hard-coded rules, decision trees, linear functions, RNN等作为智能体策略，当这些策略的参数$W$固定的时候，针对同样的状态输入，输出是确定的，这种策略叫做Deterministic Policies，通常有一个简单的形式：
$$ y = F(x, W) $$
要想得到一个最有的带有随机性的策略，一种方法是让$W$随机，即我们从一个正太分布$N(\mu_i, \sigma_i)$中采样策略模型的每一个参数$w_i \in W$，这种随机网络的方式叫做Bayesian Neural Network，是一种参数具有先验分布的神经网络。
学术界已经有很多针对贝叶斯网络训练的方法，See NIPS2019 Bayesian Deep Learning.
通过将随机策略的参数设置为$\mu$和$\sigma$，而不是直接的全部神经网络参数$W$，ES也可以被用来训练得到随机策略的最佳参数。
在RL中， PPO算法的最后一层输出就是一套$\mu$和$\sigma$参数，然后动作是从正太分布$N(\mu, \sigma I)$中采样得到。
Adding noise to parameters are also known to encourage the agent to explore the environment and escape from local optima. 通常可以仅仅对神经元的bias随机采样，即可获得较好的随机效果。
Evolving Robust Policies for Bipedal Walker
在BipedalWalkerHardcore-v2环境中，地图是随机生成的，每一次rollout都不一样，难易程度不同，为了一个策略因为运气得到一个简单的地图从而一次rollout得到高分而进入到下一个ES迭代，使用16次随机的rolouts的reward的平均值作为fitness score，当然这样会造成16倍的数据效率损失。
Reference
Note: Cover Picture