深度强化学习中的进化算法总结

IT圈老男孩1 · 发表于 2021-11-19 19:57

翻译并改编自https://lilianweng.github.io/lil-log/2019/09/05/evolution-strategies.html#applications-es-in-deep-reinforcement-learning、https://www.jiqizhixin.com/articles/2017-03-26-3、https://medium.com/beyond-intelligence/reinforcement-learning-or-evolutionary-strategies-nature-has-a-solution-both-8bc80db539b3 、https://arxiv.org/pdf/2002.07236.pdf……

什么是进化算法

进化策略（ES：evolution strategy）是一种已存在了数十年的优化技术，其在现代强化学习基准（如 Atari/MuJoCo）上的表现可以比肩标准的强化学习技术，同时还能克服强化学习的许多不便。

特别的几点包括：进化策略的实现更加简单（不需要反向传播），更容易在分布式环境中扩展，不会受到奖励稀疏的影响，有更少的超参数。这个结果令人吃惊，因为进化策略就好像是在一个高维空间中简单地爬山，每一步都沿着一些随机的方向实现一些有限的差异。

在一定的抽象程度上，进化方法可被视为这样一个过程：从个体构成的群体中采样并让其中成功的个体引导未来后代的分布。但是，其数学细节在生物进化方法的基础上实现了很大的抽象，我们最好将进化策略看作是一类黑箱的随机优化技术。

以交叉熵CEM（一种进化算法）为例，算法先随机初始化参数和确定根据参数生成解的规则，根据参数生成N组解并评价每组解的好坏，选出评估结果在前百分之ρ的解并根据这些精英解采取重要性采样方法更新参数，新参数被用作下一轮生成N组解，如此循环直到收敛~
进化算法的目标与强化学习优化的目标都是预期奖励。但是，强化学习是将噪声注入动作空间并使用反向传播来计算参数更新，而进化策略则是直接向参数空间注入噪声。换个说话，强化学习是在「猜测然后检验」动作，而进化策略则是在「猜测然后检验」参数。因为我们是在向参数注入噪声，所以就有可能使用确定性的策略（而且我们在实验中也确实是这么做的）。也有可能同时将噪声注入到动作和参数中，这样就有可能实现两种方法的结合。

进化算法的分类

进化算法通过维护以自适应方式生成的大量解样本来优化函数。从随机的初始种群开始，这些算法集在先前的精英样本附近产生新的个体。这些算法中的一些是基于启发式的临时优化方法，例如遗传算法，而另一些则基于估计精英样本的分布（例如估计分布算法（EDA））。交叉熵方法（CEM）和协方差矩阵自适应进化策略（CMA-ES）是此类中最知名的算法。比如在最简单的CEM形式中，我们假定基本分布是多元高斯分布，并对其概率密度函数（PDF）的均值和协方差矩阵进行调整，以增加在下一次迭代中采样更多类似于精英个体的可能性。
OpenAI ES for RL

在强化学习中使用进化算法的概念可以追溯到很久以前，但是由于计算上的限制，只限于表格形式的RL。
受NES的启发，OpenAI的研究人员（Salimans等人，2017年）建议使用NES作为无梯度黑盒优化器来找到最佳策略参数θ 最大化返回函数 F（θ ）。关键是在模型参数 $\theta$ 上添加高斯噪声 $\epsilon$ ，然后使用对数似然技巧将其写为高斯pdf的梯度。最终，只有噪声项作为测量性能的加权标量。
假设当前参数值为 θ^（添加的帽子是为了将值与随机变量θ区分开）。 θ的搜索分布设计为各向同性多元高斯，均值θ^且固定协方差矩阵 $\sigma^{2} I$ ，

$\theta \sim \mathcal{N}\left(\hat{\theta}, \sigma^{2} I\right) \text { equivalent to } \theta=\hat{\theta}+\sigma \epsilon, \epsilon \sim \mathcal{N}(0, I)$
θ的梯度更新是：

这里推导感觉有问题

在一代中，我们可以采样许多epsilon_i，i = 1，…，n并并行评估适用性。一种漂亮的设计是不需要共享大型模型参数，通过仅在worker之间传递随机种子，对于主节点进行参数更新就足够了。后来将此方法扩展为自适应地学习损失函数。请参阅我之前关于“进化的策略梯度”的文章。

图5.使用进化策略训练RL策略的算法。（图片来源：ES-for-RL论文）
为了使性能更加强大，OpenAI ES采用了虚拟批处理规范化（带有小批量的BN用于计算固定的统计信息），镜像采样（sampling a pair（-，）用于评估）和适应度塑形。
ES探索

探索（与利用）是RL中的重要主题。上面的ES算法中的优化方向仅从累积收益中提取F（θ ）而没有明确的探索，主体可能会陷入局部最优状态。
Novelty-Search ES（NS-ES ; Conti等人，2018）鼓励通过在最大化新颖性得分的方向上更新参数来进行探索。新奇分数取决于特定领域（domain-specific）的行为表征函数b （π_θ）。b （π_θ）的选择是特定于任务的，例如，在本文的类人机器人运动任务中，b （π_θ）是最后agent的（x ，y）位置。

ES优化步骤依赖于新颖性评分而不是适应度：

NS-ES拥有一组M个经过独立训练的媒介（“meta-population”）。 $\mathcal{M}=\left\{\theta_{1}, \ldots, \theta_{M}\right\}$ and picks one to advance proportional to the novelty score。最终，我们选择了最佳策略。这个过程相当于ensembling。SVPG中也有类似想法。

其中N是高斯摄动噪声向量的数量，α是学习率。
  NS-ES完全放弃了奖励函数，且仅针对新颖性进行了优化以避免欺骗性局部最优。为了将适应度重新纳入公式中，论文提出了另外两个变体。
NSR-ES：

NSRAdapt-ES（NSRA-ES）：最初自适应加权参数w = 1.0 。如果性能在多个世代保持稳定，我们将开始降低w。之后，当性能开始提高时，我们就不再降低w反而改为增加它。这样，当性能停止增长时，适应度为首选考虑因素，否则首选新颖性。

图6.（左）该环境为具有（起到欺骗陷阱的作用以创建局部最优值的）三面壁的类人动物运动。  （右）实验比较了ES基线和其他鼓励探索的变化。（图片来源：NS-ES论文）
CEM-RL（cross-entropy method-RL）

图7.（a）CEM-RL和（b）ERL算法的体系结构（图片来源：CEM-RL论文）
CEM-RL方法（Pourchot＆Sigaud，2019）将交叉熵方法（CEM）与DDPG或TD3相结合。这里的CEM与上述简单的高斯ES几乎一样，因此可以使用CMA-ES替换相同的函数。  CEM-RL建立在进化强化学习(ERL;Khadka & Tumer, 2018)的框架上（标准EA算法选择并进化了一批actors，然后将过程中产生的rollout经验添加到答复缓冲区中对RL-actor and RL-critic网络进行训练）。
工作流程：

Post: Device Placement with Cross-Entropy Minimization and Proximal Policy Optimization nips 2018 将CEM与PPO结合，主体框架是CEM，参数更新公式结合了PPO的思想~算法如下：

扩展：深度学习中的EA

进化算法已应用于许多深度学习问题。 POET（Wang et al，2019）是一个基于EA的框架，它试图在解决问题本身的同时产生各种不同的任务。 POET已在我上一则有关meta-RL的文章中介绍。进化强化学习（ERL）是另一个例子。参见图7（b）。
下面，我想更详细地介绍两个应用——Population-Based Training (PBT)andWeight-Agnostic Neural Networks (WANN).
超参数调整：PBT

图8.比较不同的超参数调整方式的范例。（图片来源：PBT）
Population-Based Training（Jaderberg等人，2017）在超参数调整问题上应用EA。它联合训练一组模型和相应的超参数以获得最佳性能。
PBT从一组随机候选项开始，每个候选项均包含一对模型权重初始化和超参数 $\left\{\left(\theta_{i}, h_{i}\right) \mid i=1, \ldots, N\right\}$ 。每个样本都经过并行训练，并定期异步评估性能。每当一个member认为准备就绪时（即在执行了足够的渐变更新步骤之后，或者当性能足够好时），就有机会通过与整个总体比较来进行更新：

exploit()

explore()

在此过程中，只有有希望的模型和超参数对可以生存并继续发展，从而更好地利用计算资源。

图9.基于人口的训练算法（图片来源：PBT ）
网络拓扑优化：WANN

权重不可知神经网络（Weight Agnostic NeuralNetworks WANN; Gaier ＆Ha 2019）进行实验以寻找无需训练网络权重即可实现最佳性能的最小网络拓扑。通过不考虑网络权重的最佳配置，WANN更加注重架构本身，从而使重点与NAS有所不同。WANN受经典遗传算法的启发以发展网络拓扑，被称为NEAT（“增强拓扑的神经进化”；Stanley＆Miikkulainen 2002）。
WANN的工作流程与标准GA大致相同：

共享的

图10.在WANN中寻找新网络拓扑的变异操作（图片来源：WANN论文）
在“评估”阶段，所有网络权重均设置为相同。这样，WANN实际上正在搜索可以用最小描述长度描述的网络。在“选择”阶段，将同时考虑网络连接和模型性能。

图11.将WANN发现的在不同RL任务上的网络拓扑性能与文献中常用的基准FF网络进行比较。“调整共享重量”仅需调整一个weight value。（图片来源：WANN论文）
图11显示了使用随机权重和共享权重（单个权重）评估WANN结果。有趣的是，即使在所有权重上执行权重共享并调整此单个参数时，WANN仍可以发现实现出色性能的拓扑。
进化策略和强化学习间的权衡

进化策略和强化学习的差异：

1.在参数空间进行探索和优化
强化学习一般在动作空间（Action Space）进行探索（Exploration）。而相应的Credit或者奖励，必须在动作空间起作用，因此，存在梯度回传（back propagation）。进化算法直接在参数空间探索，不关心动作空间多大，以及对动作空间造成多大影响。

2. 强化学习存在Credit Assignment问题，而进化算法不存在
强化学习需要将一个Episode的总体表现又通过Credit Assignment返回给每一步动作，而Evolution不需要。Evolution中探索的每一组参数，都用于执行一个或者多个Episode, 然后根据这组参数的整体表现，来确定该组参数是否更优秀，以最终决定是否要往这个参数方向移动。
https://zhuanlan.zhihu.com/p/104374240

进化策略和SGD的差异：

进化策略为由概率分布描述的预期奖励而优化，而SGD为一个单独的策略而优化奖励，前者是搜索空间中的一个晕，而后者是搜索空间中的一个点。
这种不同，让ES会访问搜索空间中的不同区域，无论好坏。对一群参数扰动进行整体优化的另一个结果是，ES获得了SGD所不具备的奖状性特征。
强调ES对一群参数进行优化同样也凸显了ES和贝叶斯方法之间的联系。

相比于强化学习算法，进化策略有多个优势（一些优势有些技术性）：

不需要反向传播。快+不需要担心 RNN 中的梯度爆炸问题+能够探索更大类别的策略函数，包括不可微分的网络（比如二值网络）/包括复杂模块的网络~
高度可并行。进化策略只需要工作器彼此之间进行少量纯数量的通信，然而在强化学习中需要同步整个参数向量（可能会是百万数值的）。直观来看，这是因为我们在每个（worker）上控制随机 seeds，所以每个worker能够本地重建其他worker的微扰（perturbations）。在实验中我们观察到，随着我们以千为单位增加 CPU 进行优化时，加速是线性的。
高度稳健。在强化学习实现中难以设置的数个超参数在进化策略中被回避掉了。例如，强化学习不是「（scale-free）的」，所以在 Atari 游戏中设置不同的跳帧（frame-skip）超参数会得到非常不同的学习输出，而进化策略在任何跳帧上有同样的结果。
https://www.jiqizhixin.com/articles/2017-03-26-3
对环境要求不高。如对激励稀疏与否没有明显高要求。
高度的可伸缩性和灵活性。数据生成、精英选择、探索利用上都可以改，即插即用~
目标函数的开放性。在RL中，在某些情况下放弃常规目标可能会更好。新颖的搜索和促进行为多样性的相关方法可以帮助克服奖励稀少或局部最优的欺骗性问题。进化算法的主要优点之一就是其目标函数的开放性。

ES相比于DRL的不足

1.进化算法探索和利用的机制没RL这么多样（不过可将这些手段借鉴过来）；
2.有些任务上用梯度可能快很多（OpenAI描述了使用ES训练简单的MNIST分类网络，它的速度“慢了1000倍”），如果要用ES达到类似效果，可能要耗费更多样本；
3.没用神经网络的丰富的学习能力：
如，DRL可引入对环境未来状态的预测来丰富稀疏的奖励信号，从而扩展其网络的典型策略输出，更快地学习更复杂的行为。这些增强功能仅适用于利用梯度信号的方法，而不是像ES之类的黑盒方法。

https://medium.com/beyond-intelligence/reinforcement-learning-or-evolutionary-strategies-nature-has-a-solution-both-8bc80db539b3的观众评论：
在我看来，Interleaved reinforcement learning and evolutionary simulation for RL 是最有前途的方法之一，希望一旦我研究了并行化组件，就会发表一篇不错的文章:)

附录

关于采样效率

https://www.zhihu.com/question/290530992/answer/1149119187

ChuanXin · 发表于 2021-11-19 19:58

南大演化算法/演化学习方面的集大成著作，或可为题主带来更多理论启发：《演化学习：理论与算法进展》(周志华，俞扬，钱超)【摘要书评试读】- 京东图书。P.S. 该书里的“演化”指的就是题主这里的“进化”，译法不同而已。

RedZero9 · 发表于 2021-11-19 20:08

博主您好，进化学习+增强学习，Github上，有比较靠谱的repo推荐吗？

		自动登录	找回密码
密码			立即注册

深度强化学习中的进化算法总结

本帖子中包含更多资源