- 进化策略 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样本利用率高
网友评论