【文献阅读】17年进化算法和DRL结合的文章_qd算法

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

Brief

目前该文已经有了上百的引用量，还是有点厉害。
文章地址 链接
代码链接 code
作者来自佛罗里达大学和openAI

Abstract

【开篇明义】Evolution strategies (ES) are a family of black-box optimization algorithms able to train deep neural networks roughly as well as Q-learning and policy gradient methods on challenging deep reinforcement learning (RL) problems, but are much faster (e.g. hours vs. days) because they parallelize better. 进化策略(ES)是一个黑盒优化算法系列，能够在具有挑战性的深度强化学习(RL)问题上训练深度神经网络，其效果与Q-learning和策略梯度方法大致相同，但速度要快得多(如几小时与几天)，因为它们的并行化程度更好。
【转折】However, many RL problems require directed exploration because they have reward functions that are sparse or deceptive (i.e. contain local optima), and it is not known how to encourage such exploration with ES. 然而，许多RL问题需要定向探索，因为它们的奖赏函数是稀疏的或具有欺骗性的（即包含局部optima），目前还不知道如何用ES鼓励这种探索。

这里给出了问题，就是对奖励稀疏和含有局部最优的RL问题，不知道如何用进化算法来指导这种定向探索。

【我们的方法】Here we show that algorithms that have been invented to promote directed exploration in small-scale evolved neural networks via populations of exploring agents, specifically novelty search (NS) and quality diversity (QD) algorithms, can be hybridized with ES to improve its performance on sparse or deceptive deep RL tasks, while retaining scalability. 在这里，我们表明，已经发明了通过探索代理的群体来促进小规模进化神经网络中的定向探索的算法，特别是新奇搜索（NS）和质量多样性（QD）算法，可以与ES杂交，以提高其在稀疏或欺骗性的深度RL任务上的性能，同时保留可扩展性。

这句话真够长的，信息量也非常大。NS 和 QD 是本文最重要的两个概念。

【实验及结果】Our experiments confirm that the resultant new algorithms, NS-ES and a version of QD we call NSR-ES, avoid local optima encountered by ES to achieve higher performance on tasks ranging from playing Atari to simulated robots learning to walk around a deceptive trap. 我们的实验证实，由此产生的新算法，NS-ES和我们称之为NSR-ES的QD版本，避免了ES遇到的局部optima，在从玩Atari到模拟机器人学习绕着欺骗性陷阱行走的任务上实现了更高的性能。
This paper thus introduces a family of fast, scalable algorithms for reinforcement learning that are capable of directed exploration. It also adds this new family of exploration algorithms to the RL toolbox and raises the interesting possibility that analogous algorithms with multiple simultaneous paths of exploration might also combine well with existing RL algorithms outside ES.
因此，本文介绍了一个用于强化学习的快速、可扩展的算法系列，这些算法能够进行定向探索。它还将这个新的探索算法家族添加到RL工具箱中，并提出了一种有趣的可能性，即具有多条同时探索路径的类似算法也可能与ES之外的现有RL算法很好地结合。

1. Introduction

第一段

在RL中，agent试图学习在一个环境中执行一系列动作，使累积奖励最大化。【转折】然而，奖励函数往往具有欺骗性deceptive，并且单纯的奖励优化而没有一些鼓励智能探索 intelligent exploration 的机制，可能会导致陷入局部最优状态，agent无法正确的学习。【局部最优】与具有深度神经网络（DNNs）的监督学习不同，在神经网络中，局部最优值不被认为是一个问题，RL中的训练数据是由 agent 采取的动作 actions 决定的。如果agent贪婪地采取回报最大化的行动，那么算法的训练数据将是有限的，它可能无法发现具有更大回报的替代策略alternate strategies（即它可能卡在局部最优中。）【稀疏奖励】对于只实现奖励最大化的算法来说，稀疏的奖励信号sparse reward signals 也可能是一个问题，因为优势可能没有奖励梯度可循。奖励信号中存在欺骗性和/或稀疏性的possibility可能性，促使人们需要进行有效的定向探索，在这种情况下，agent 被激励去访问未搜索的状态，以学习积累更高的奖励。【总结问题】虽然深度RL算法近年来表现出了惊人的feats 功绩，但它们大多是依靠简单的，非定向的（aka dithering 也就是摇摆不定）探索策略完成的，在这种策略中，agent希望通过采取随机行动来探索环境中的新区域（如贪婪的探索 epsilon-greedy exploration）。

第二段

【总领】已经提出了很多方法来促进RL中的定向探索，包括最近用DNNs处理高维状态空间的方法。【方法一】一个常见的想法是鼓励agent访问它很少或从未访问过的状态（或在这些状态采取新的novel actions ）。所提出的跟踪状态（或者状态-动作对）访问频率的方法包括（1）基于自动编码的状态潜码[11]或者来自状态空间密度模型的伪计数 pseudo-counts 来逼近状态访问次数，（2）学习一个可以预测未来状态的动态模型（假设对于很少访问的状态/状态-动作对的预测会更差），（3）基于压缩的方法（新的状态应该更难压缩）。

Methods proposed to track (or state-action pair) visitation frequency
include (1) approximating state visitation counts based on either
auto-encoded latent codes of states or pseudo-counts from state-space
density models, (2) learning a dynamics model that predicts future
states (assuming predictions will be worse for rarely visited
states/state-action pairs), and (3) methods based on compression
(novel states should be harder to compress).
这一块的内容居然完全懵逼，每个单词都认识，拼到一起就不知道啥意思了

第三段

【承上启下】这些方法都是分别计算每个状态。【方法二】另一种不同的方法是手工设计（或者学习）一个抽象的abstract，整体性holistic对agent一生行为的描述，然后鼓励agent表现出与之前的行为不同的行为。【起名字】那就是novelty search （NS）新颖性搜索 和quality diversity （QD）质量多样性 算法的方法，下面详细介绍。【算法特点】这样的算法也有interestingly different 有意思的不同，并且具有不同的能力，因为他们是用一群agents 而不是单个agent 来执行探索的（在SI Sec. 6.2 中讨论）。NS和QD已经在低维输入和输出空间的问题上，用较小的神经网络显示出了希望。【ES】进化策略evolution strategies （ES）最近被证明可以在很短的wall clock time 挂钟时间内，通过对许多分布式计算机的良好扩展，在高维深度RL任务上表现良好。【本文】在本文中，我们首次研究了如何将这两类算法与ES进行杂交hybridized，将其扩展到深度神经网络，从而在不牺牲ES的速度/可扩展性优势的前提下，处理困难的高维深度强化学习问题。【具体内容】我们首先研究NS，它只执行探索（忽略奖励函数），以找到一组信仰的解。然后，我们研究平衡探索和利用的算法，特别是QD算法的新颖实例，它寻求产生一组既新颖又高性能的解。NS和QD在第三节中详细解释。

第四段

【总领句】ES直接在神经网络的参数空间中进行搜索，寻找有效的策略。【举例子】OpenAI 的一个团队最近表明，ES可以在许多强化学习任务上获得具有竞争力的性能，同时与传统的基于梯度的RL方法相比具有一些独特的优势[24]。【例子的最大优点】Most notably 最值得注意的是，ES具有高度的可并行性 ES is highly parallelizable, 这使得运行时的速度在CPU/GPU workers 的作用下接近线性提升。例如，在使用数百个并行CPU的情况下，ES能够在1小时内对相同DNN架构的Atari游戏实现与A3C在24小时内大致相同的性能 [24]。【本文】在本文中，外面研究了仅在ES中添加NS和DQ；在未来的工作中，外面将研究它们如何与Q-learning和策略梯度方法混合。外面从ES开始，因为（1）它的快速wall-clock time 挂壁时间允许快速的实验迭代，（2）NS和QD最初是作为神经进化方法开发的，因此很自然地先用ES来尝试，ES也是一种进化算法。

第五段

【本文任务的凝练版本】在这里外面测试了通过NS和QD鼓励novelty 新颖性是否能提高ES在系数和/或欺骗性控制任务上的性能。【实验】外面的实验证实，NS-ES 和 QD-ES 的两个简单版本（NSR-ES 和 NSRA-ES）避免了ES遇到局部作用并在从模拟机器人学习绕过欺骗性陷阱到玩Atari 游戏的高维像素-到-动作 的任务上实现了更高的性能。【贡献】我们的结果将这些新的探索算法家族添加到工具箱中，为研究如何将它们与RL算法（无论是ES还是其它算法）进行最佳结合开辟了一条途径。

2 Background

2.1 Evolution strategies

第一段： ES的定义，原理，本文用到的是NES

进化策略（ES）是一类受自然进化启发的黑盒优化算法[23]：在每一次迭代 （generation），参数向量种群（genomes基因组）被扰动（mutated 突变），并，可选地，通过 crossover 重新组合 recombined （merged 合并）。“At every iteration (generation), a population of parameter vectors (genomes) is perturbed (mutated) and, optionally, recombined (merged) via crossover. ” 然后根据一些目标函数objective function （reward）对每个结果后代resultant offspring 的fitness 适应性进行评估，然后通过某种形式的选择确保具有较高奖励的个体倾向于为下一代产生后代。ES 类的许多算法在对种群的表示和重组方法上有所不同；本工作中随后提到的算法属于Natural Evolution Strategies 自然进化策略（NES）类[25,26]。 NES将种群表示为参数向量 $\theta$ 的分布，其特征是参数 $\varphi$ : $p_{\varphi }(\theta )$。在适应度函数 $f(\theta )$ 下，NES通过随机梯度上升优化 $\varphi$ ，寻求种群平均适应度 ${\mathbb{E}}_{\theta \sim p_{\varphi }}[f(\theta )]$ 的最大化。

第二段：参数梯度更新

OpenAI 最近的工作outlines 概述了一个应用于标准RL基准问题的NES版本[24]。我们今后将把这种变体简称为ES，在他们的工作中，一个适应度函数$f(\theta )$ 代表了在一个完整的agent交互episode中所经历的随机奖励，其中 $\theta$ 参数化了策略 ${\pi }_{\theta }$。从种群分布 $p_{{\varphi }_t}$ 中，对参数 ${\theta }_t^i\sim \mathcal{N}({\theta }_t,{\sigma }^{2}I)$ 进行采样和估计，得到 $f({\theta }_t^i$