• 进化策略 ES
• 遗传算法 GA
• 交叉熵方法 CME
• 协方差自适应进化策略 CMA-ES

进化策略 Evolutionary Strategy （ES）

• 优胜劣汰，适者生存
• 包括两个过程，重复迭代直至适应环境
  （1）选择：衡量适应度 f(x)，环境适应度高的个体生存下来
  （2）进化：产生新个体 x，让新个体去接受环境的考验
• 4个步骤：①初始化种群，②定义适应度，③选择，④进化新个体。然后重复③④

遗传算法 Genetic Algirithm （GA）

• 和ES不一样的的步骤在于进化新的个体，GA包括两个子阶段
  （1）交叉
  （2）变异

自然进化策略 Natural Evolution Strategy （NES）

• NES希望找到最优的参数来最大化期望的适应度(Fitness)
• 其中是参数值， 是服从的分布，是适应度函数，是分布的参数
  
• 用梯度对参数进行优化（是一个平滑变化的过程），然后用采样参数值来更新，这样就能得到参数服从的分布

交叉熵方法 Cross Entropy Method（CEM）

• 给定参数的先验分布(高斯分布)：
• 然后根据分布进行样本采样：
• 评估样本的适应度然后选取精英样本后验更新分布：
• 最后得到高斯分布的参数，返回均值作为最优参数值

参考多元高斯分布中协方差矩阵的工作原理

协方差自适应进化策略 Covariance Matrix Adaptation Evolution Strategy（CMA-ES）

• 上一代CEM方法中噪声的参数是固定，而CMA-ES希望能够自适应地改变搜索空间。

• 标准差 σ 决定了探索的程度（通常称之为「探索步长」）：当 σ 越大时，我们就可以在更大的搜索空间中对后代种群进行采样。在简单高斯演化策略中，σ(t+1) 与 σ(t) 密切相关，因此算法不能在需要时（即置信度改变时）迅速调整探索空间。「协方差矩阵自适应演化策略」（CMA-ES）通过使用协方差矩阵 C 跟踪分布上得到的样本两两之间的依赖关系，解决了这一问题。新的分布参数变为了：
• 需要多计算一个协方差矩阵，然后根据分布进行样本采样
• 自适应的改变噪声强度
• 更新分布的方式

详细介绍CMA-ES

ES+RL

直接用ES优化策略网络

Evolution Strategies as a Scalable Alternative to Reinforcement Learning(OpenAI, arXiv2017)

Motivation：

• 可以高度并行，多节点CPU使用
• 种群内多个子代探索不同的解空间
• 黑盒优化，不受噪声梯度、稀疏奖励的影响，对超参不敏感

Method：

• 使用随机种子来还原模型参数，降低节点之间的通信

Result：

• 实验表明：Atari Games中不同的frame-skip取值对ES影响不大，同时在一些运动控制的环境中sample efficiency较好

直接用GA优化

Deep Neuroevolution: Genetic Algorithms are a Competitive Alternative for Training Deep Neural Networks for Reinforcement Learning (UberAI, arXiv2017)

Motivation：

• OpenAI的ES也是基于梯度的方法，无梯度的方法GA或许更有效
• 某些环境下奖励信号具有欺骗性，容易陷入局部最优

Method

• 直接采用GA来优化策略参数
• 因为要优化的网络参数比较大，不考虑crossover，只考虑变异
• 每个个体维护自己的随机种子，最后由种子来还原网络参数。

Result

• 实验表明GA能够跳出某些local optimal （caused by deceptive reward signal）
• 加入了Novelty Search 的技巧在某些实验上会更有效
• 相比较ES需要计算后代参数的均值，大型网络的更新会更慢，GA可以快一些。
• 相比较ES需要经过virtual batch normalization 来 generate diverse policies，需要额外的前向传播，但GA不用，population 直接探索多样策略。

NS-ES

Improving Exploration in Evolution Strategies for Deep Reinforcement Learning via a Population of Novelty-Seeking Agents(NIPS2018)

Motivation

• 许多RL算法都有 探索-利用 机制，可以跳出稀疏奖励或者欺骗性奖励导致的局部最优，但ES缺乏类似的机制
• 可以借助现有的Novelty-Search（NS）和Quality Diversity（QS）来设计ES的变体

Method：包括3种变体

• NS-ES：设计一个行为特征函数来描述策略（可以简单到比如迷宫环境的横纵坐标），随后使用K近邻算法寻找种群内最近k个策略并计算距离来得出当前策略的novelty。然后使用ES来寻找使得Novelty最大化的参数，鼓励agent往没有探索过的空间去探索
• NSR-ES：最大化Novelty并不能保证reward的最大化，在更新过程中使用Novelty和Return的平均值
• NSRA-ES：自适应的改变Novelty和Return的权重，reward变差的时候需要提升Return的权重。

Result

• NSRA-ES可以有效跳出局部最优点，而ES会陷入局部最优

ERL

Evolution-Guided Policy Gradient in Reinforcement Learning(NeuIPS2018)

Motivation

• 常用强化学习算法存在三个难点
  （1）Temporal credit assignment with sparse rewards：Temporal difference可以用来解决第一个问题，使用bootstrapping技术来估计往后的值，但是当time horizon 过长并且奖励稀疏仍具有较大问题。与episode return 一样，可以使用multi step 来解决这个奖励稀疏或者time horion过长的问题，此方法对on-policy的方法比较有效。off-policy需要使用重要性采样的方法，如R-trace或者是V-trace来解决问题。
  （2）Lack of effective exploration :现有的探索方法：基于计数的，基于内在驱动的，基于好奇心以及变分信息最大化，然而这些方法都会引入敏感的超参和复杂的结构
  （3）Brittle convergence properties that are extremely sensitive to hyper-parameters :收敛问题，特别是off-policy，replay buffer 的使用，其收敛性质不太好。同时,DRL对参数较为敏感，ES更为鲁棒
• 常用EA算法也存在一些问题
  （1）high sample complexity and high dimensional problem
  （2）作者认为，EA的high sample complexity因为没有梯度指引方向，所以需要大量的个体进行探索，可以使用RL算法的梯度来指引EA进行探索，同时使用EA来解决强化学习算法中的三个问题

Method

• 提出EA+RL结合的框架 ERL，以及EA和RL之间的信息流动方式
  （1）EA -> RL：RL使用ES种群采样的经验进行学习
  （2）RL -> EA：间隔的将RL agent 插入到EA种群当中
• RL使用DDPG算法，ES使用遗传算法
• 遗传算法不考虑crossover
• 由于EA是往更高Return的方向走的，因此种群个体的经验是bias的，能够简介指导RL算法
• RL agent的参数直接插入到种群中影响ES，由于受到EA的机制影响，比如选择操作，如果RL agent 收到noisy gradient的影响，很容易在GA中被disgard

Result

• 实验看出，ERL可以结合两者的有点，提高了sample effciency
• 在稀疏奖励环境中也能很好的完成任务
• 在两个特殊的环境中，可能也会收到RL的影响过于深刻，陷入 local optimal后，后期再也没法跳出。

GEP-PG

GEP-PG: Decoupling Exploration and Exploitation in Deep Reinforcement Learning Algorithms(ICML2018)

Motivation：

• 标准的RL算法对环境的探索能力不够。
• ES中的Novelty Search（NS），Quality Diversity（QD），Goal Explore Process（GEP） 能够帮助RL。

Method：

• GEP : 使用一个behavior function来描述一个policy，在behavior space上进行探索。
  （1）在参数空间随机sample参数θ，然后使用behavior function评估得到结果o，存储数据对<θ,o>。
  （2）Behavior space中每个可能结果看成是一个goal，在behavioral feature space空间中采用多个o，
  （3）在存储的数据中寻找最近的数据对，将对应的参数进行扰动(高斯噪声)得到新的参数(策略)
  （4）新的策略可能能够或者尽量完成目标o，也或者产生另外一个新的目标的实现方式(类似Hindsight Experience Replay)，使用这种方式实现exploration
• GEP-PG :
  （1）将GEP过程对参数进行评估得到的交互经验存放到buffer当中供DDPG训练，实现exploitation
  （2）解耦 探索-利用，其他算法也类似
  （3）multi-goal exploration
  （4）avoid sparse or deceptive rewards
  （5）DDPG的信息没有传给GEP，GEP就只是在随机探索

CEM-RL

Combining evolutionary and gradient-based methods for policy search(ICLR2019)

Motivation:

• EA存在的low sample efficiency 可以借助 off-policy 算法的 gradient 来解决

Method：

• CEM-RL 直接使用Critic来更新种群中的个体，另外EA方面使用了CEM变体，使用当前样本的均值来更新分布，在更新方差的时候添加了噪声 来防止提前收敛。
• CEM使用梯度信息更新种群一半个体，使用种群的top个体来更新分布
• 种群的一半个体使用了RL的gradient 更新，受 detrimental gradient的影响可能较大

Result

• 实验结果表明CEM-RL在mujoco上效果明显
• 由于计算量太大，受计算资源限制，1M steps后停止更新CEM-RL
• 通过消融实验验证用于产生子代的importance mixing 技巧和添加 action noise 作用不大，原因可能是 CEM具有较强的探索能力

CERL

Collaborative Evolutionary Reinforcement Learning(ICML2019)

Motivation

• 现有强化学习算法缺乏有效的探索并且对超参敏感
• 使用EA中的个体来进行探索-利用

Method

• 在policy gradient learner中初始化多个agent，其中每个agent的折扣率不一样(衡量未来的影响)
• 每个agent具有自己actor，critic，每个agent可以使用不同的off-policy算法
• 所有agent共享一个replay buffer 提高 sample efficiency
• 假定计算资源是有限的，resource manager会将资源分配给表现最好的learner(exploration-exploition well)
• Learner pool会使用UCB原则对learner进行有放回地重新采样来更新
• EA跟RL的信息流动机制与ERL一致

Result

• mujoco上效果不错
• 超参数相对不敏感
• 计算资源比较大

PDERL

Proximal Distilled Evolutionary Reinforcement Learning(ICML2019)

Motivation:

• GAs 的应用没有被解决
• 传统GA中使用的机制会导致网络的灾难性遗忘问题，如变异操作，参数的丝毫改变可能无法继承到父辈优秀的行为
• ERL中使用node为单位进行crossover，然而node的顺序仍然未定义，子代可能无法继承父代优秀的基因
• 添加高斯噪声会带来不利的影响[1]，ERL只对一部分weights进行变异，降低了GA的优化速度

Method

• （1）每个个体具有自己的buffer，子代使用父代各一半的经验，然后使用模仿学习的方式来得到子代样本的参数(基因型-表现型)，只模仿父代Q值高的动作
• （2）Selection 设计两种机制选择父代进行交叉：Greedy和Distance based
• （3）Mutation 借助已有的safe mutation operator
• 综合上述三种新型算子，替换ERL中的EA算法得到如图的PDERL
• 其中RL Critic 用于 crossover中，选取Q值高的进行模仿
• EA和RL的信息流动机制与ERL一致
• 计算量又加剧了，子代都需要训练才能得到
• 子代的表现跟父代更为接近（KL距离和Return）是一种新的集成方式
• 在selection阶段也可能使用学习的算法

Result

• 在mujoco上的实验效果跟TD3差不多，作者还验证了引入的新算子能够使得子代和父代表现相近（从基因型到表现型）

SuperRL

Genetic Soft Updates for Policy Evolution in Deep Reinforcement Learning （ICLR 2021）

Motivation:

• DRL和EA的并行训练对计算资源是significant overhead，通过间隔使用EA作为policy evaluation
• 目前的框架无法与value based 算法结合，actor-critic在某些确定性环境效果不是很好。value based算法在某些continuous setting下具有 sample efficiency，better performance
• 如何防止DRL的detrimental behavior(这是由于EA后期的agent，weights tend to be 0)

Method

• 间歇性使用ES评估，减少资源消耗（伪代码第10-11行）
• 寻找种群中最好的agent，如果比RL agent好则进行soft update，否则RL agent不更新（伪代码第15行）

Result

• 在离散和连续动作的环境中都表现很好

小总结

ES的优点：
1）鲁棒性强
2）对稀疏，延迟奖励不敏感
3）高度并行化并且可以具有较低的通信开销
4）可以融合现有的不可微模块

ES的缺点：
1）参数高维优化困难
2）样本利用效率低下

RL的缺点：
1）对参数敏感
2）对稀疏，延迟奖励敏感
3）探索能力不足

RL的优点：
1）off-policy样本利用率高