OpenAI的ES算法以及变体

作者: 臻甄 | 来源:发表于2022-07-26 21:26 被阅读0次

1 Evolution Strategies（ES）

paper Evolution Strategies as a
Scalable Alternative to Reinforcement Learning

摘要：我们探索使用进化策略（ES），一类黑盒优化算法，作为流行的基于 MDP 的 RL 技术（如 Q 学习和策略梯度）的替代方案。在 MuJoCo 和 Atari 上的实验表明，ES 是一种可行的解决方案策略，可以很好地随可用 CPU 数量扩展：通过使用基于常见随机数的新颖通信策略，我们的 ES 实现只需要通信标量，从而可以扩展超过一千个并行worker。这使我们能够在 10 分钟内解决 3D 人形步行问题，并在经过一小时的训练后在大多数 Atari 游戏中获得有竞争力的结果。此外，我们强调了 ES 作为黑盒优化技术的几个优点：它不受动作频率和延迟奖励的影响，容忍极长的视野，并且不需要时间贴现或价值函数逼近。

ES 是一类黑盒优化算法，可以作为RL的替代方案。
利用CPU的数量可以进行非常好的扩展
基于随机数通信，只需要传达标量就可以扩展到超过1000个并行进程。
使用虚拟批量标准化极大地提高了进化策略的可靠性，不然ES表现很差。
不需要执行反向传播和没有值函数，所需的计算量大大减少，这在一定程度上抵消了数据效率的轻微下降。
优点：
（1）不受行动频率和延迟奖励的影响
（2）能够容忍极长的视野
（3）不需要temporal discounting 或者值函数的逼近

1.1 常规ES

初始种群 >>> 交叉编译 >>> 评价 >>> 筛选下一代... 直到问题收敛
目标：
$maximize \ \Bbb{E}_{\theta \sim p_\psi}F(\theta)$ $\nabla \Bbb{E}_{\theta \sim p_\psi}F(\theta) = \Bbb{E}_{\theta \sim p_\psi} \{ F(\theta) \nabla_\psi \log p_\psi(\theta) \}$ $\nabla \Bbb{E}_{\theta \sim N(0,I)}F(\theta + \sigma \epsilon) = {\frac 1 \sigma} \Bbb{E}_{\theta \sim N(0,I)} \{ F(\theta + \sigma \epsilon)\epsilon \}$
$F$ 是评价函数， $\theta$ 是policy的参数， $p_\psi$ 是带噪音的分布，也就是当前的策略种群。使用natural evolution strategies (NES)的梯度。基于多元高斯分布来生成噪音。

1.2 并行化的ES

ES非常适合扩展到许多并行工作者：
（1）它在完整的episode上运行，因此进程之间不需要频繁通信。
（2）每个进程获得的唯一信息是episode的标量返回（一个随机种子，用于标识具体的随机扰动）。
（3）它不需要值函数近似，不需要假设目标函数是连续的（RL则需要多次更新值函数）。因此该算法可以有效的扩展到上千个工作进程。
（4）ES的探索由参数扰动驱动，所以能优化原参数 $\theta$ 的关键是，即高斯扰动向量偶尔导致新的个体 $\theta + \sigma \epsilon$ 具有更好的回报。

2.3 参数空间的扰动 vs 动作空间的扰动

RL 最大困难是缺乏policy的信息梯度（可能是不平滑的或者不存在），只能通过对环境的采样和预估获得。因为状态转移函数未知所以无法直接用反向传播算法来计算，只能通过添加噪声来估计。
令 ${\bf a}= \{ a_1, a_2, ...a_T \}, a_t=\pi(s;\theta)$ ，优化目标为 $F(\theta) = \Bbb{E}R( {\bf a} (\theta) )$
策略梯度方法在动作空间添加噪声 $\epsilon$ ，目标函数和梯度分别是： $F_{PG}(\theta) = \Bbb{E}_{\epsilon}R( {\bf a} (\epsilon) )$ $\nabla_\theta F_{PG}(\theta) = \Bbb{E}_{\epsilon} \{ R( {\bf a} (\epsilon, \theta) ) \nabla_\theta \log p({\bf a}(\epsilon, \theta)) ; \theta \}$
进化策略方法在参数空间添加噪声 $\epsilon$ ，对参数的改动和梯度分别是： $\overline{\theta} = \theta + \xi, a_t = {\bf a}(\xi, \theta) = \pi(s; \overline{\theta})$ $\nabla_\theta F_{ES}(\theta) = \Bbb{E}_{\xi} \{ R( {\bf a} (\xi, \theta) ) \nabla_\theta \log p(\overline{\theta} (\xi, \theta)) ; \theta \}$

2. NS-ES

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

摘要：进化策略 (ES) 是一系列黑盒优化算法，能够在具有挑战性的深度强化学习 (RL) 问题上大致训练深度神经网络以及 Q 学习和策略梯度方法，但速度要快得多（例如，几小时与天），因为它们可以更好地并行化。然而，许多 RL 问题需要定向探索，因为它们具有稀疏或欺骗性的奖励函数（即包含局部最优值），并且不知道如何用 ES 鼓励这种探索。在这里，我们展示了通过探索agent群体，特别是新颖性搜索（NS）和质量多样性（QD）算法，可以与 ES 混合以提高其在小规模进化神经网络中的性能，提高稀疏或欺骗性的深度强化学习任务的性能，同时保持可扩展性。我们的实验证实，由此产生的新算法 NS-ES 和两个 QD 算法 NSR-ES 和 NSRA-ES 避免了 ES 遇到的局部最优，从而在 Atari 和模拟机器人学习绕过欺骗性陷阱时获得更高的性能。因此，本文介绍了一系列能够进行定向探索的快速、可扩展的强化学习算法。它还将这个新的探索算法系列添加到 RL 工具箱中，并提出了一个有趣的可能性，即具有多个同时探索路径的类似算法也可能与 ES 之外的现有 RL 算法很好地结合。

Motivation：很多RL问题需要定向探索，因为有些奖励稀疏，有些奖励有欺骗性（包括局部最优值），普通ES不知道如何鼓励定向探索。
Contribution：提出新颖性搜索（NS）和质量多样性（QD）算法结合ES，帮助ES提高小规模进化神经网络的性能。

2.1 Evolution Strategies (ES)

NES（Natural ES）将群体表示为由参数 $\phi:p_\phi(\theta)$ 表征的参数向量 $\theta$ 的分布，用适应函数 $f(\theta)$ 表示效果，希望最大化群体平均适应度 $\Bbb{E}_{\theta \sim p_\phi} [f(\theta)]$ ，通过梯度下降优化参数。
OpenAI的工作是把NES用于RL（见第一节），假设群体分布是 $\theta_t^i \sim {\cal N} (\theta_t, \sigma^2 I)$ ，类似于REINFORCE，梯度为： $\nabla_\phi \Bbb{E}_{\theta \sim \phi}[f(\theta)] \approx {\frac 1 n} f(\theta_t^i) \nabla_\phi \log p_\phi(\theta_t^i)$
假设 $\theta_t^i = \theta_t+\sigma \epsilon, where \ \epsilon_i \sim {\cal N}(0, I)$ ，通过对样本参数扰动的总和进行加权来估计梯度： $\nabla_{\theta_t} \Bbb{E}_{\epsilon \sim {\cal N}(0, I) }[f(\theta_t + \sigma \epsilon)] \approx {\frac 1 {n\sigma}} \sum_{i=1}^{n} f(\theta_t^i) \epsilon_i$

2.2 Novelty Search Evolution Strategies (NS-ES)

NS(Novelty Search) 鼓励policy尽量不同于前面的试过的行为。
（1）该算法通过计算当前策略与先前生成的策略的相关性来鼓励不同的行为
（2）鼓励人口分布向参数空间区域移动，具有高新颖性。
NS中，策略 $\pi$ 被赋予描述其行为的域相关行为特征 $b(\pi)$ .
（1）比如在人形运动问题中， $b(\pi)$ 可以简单到包含人形的最终位置 $x,y$ 的二维向量。整个训练过程中，每个被评估的 $\pi_\theta$ 都会以一定的概率将 $b(\pi_\theta)$ 加入到档案集 $A$ 里面。然后桶过从一个特定策略中选择 $b(\pi_\theta)$ 的k个最近邻居并计算他们之间的平均距离，来计算该策略的新奇值 $N(b(\pi_\theta), A)$ 。 $N(\theta, A) = N(b(\pi_\theta), A) = {\frac 1 {|S|}} \sum_{j \in \epsilon} || b(\pi_\theta) - b(\pi_j) ||_2$ $S = kNN(b(\pi_\theta),A) = \{ b(\pi_1), b(\pi_2), ..., b(\pi_k) \}$
NS-ES使用ES框架来计算期望新颖性的梯度，用于告诉我们该如何改变当前策略的参数 $\theta$ 来增加我们参数分布的平均新颖性： $\nabla_{\theta_t} \Bbb{E}_{\epsilon \sim {\cal N}(0, I) }[N(\theta_t + \sigma \epsilon, A)|A] \approx {\frac 1 {n\sigma}} \sum_{i=1}^{n} N(\theta_t^i,A) \epsilon_i$
（1）首先初始化M个随机参数向量作为元群体，并在每次迭代时选择一个进行更新。实验中，我们根据 $\theta^m$ 的新颖性计算概率，从离散概率分布中选择更新的向量。 $P(\theta^m) = {\frac {N(\theta^m,A)} {\sum_{j=1}^{M} N(\theta^j,A)}}$
（2）从元群体中选择一个个体后，可以计算当前参数向量 $\theta_t^m$ 的期望新颖性梯度，并相应的执行更新步骤： $\theta_{t+1}^m \gets \theta_t^m + \alpha \frac{1}{n\sigma} \sum_{i=1}^n N(\theta_t^{i,m},A)\epsilon_i$
（3）更新当前参数向量后，将计算 $b(\pi_{\theta_{t+1}^m})$ ，并添加到共享归档A中。整个过程重复预定的迭代次数，因为NS没有真正的收敛点。在训练期间，算法会保留具有最高平均奖励的策略，并在训练完成后返回此策略。

2.3 QD-ES (NSR-ES and NSRA-ES)

单独的NS-ES可以使代理人避免在奖励功能中欺骗性的局部最优。然而，回报信号仍然提供非常丰富的信息，完全丢弃它们可能会导致性能下降。
因此，我们训练NS-ES的变体，我们称之为NSR-ES，它结合了（“适应性”）和针对给定的一组策略参数 $\theta$ 计算的新颖性： $\theta_{t+1}^m \gets \theta_t^m + \alpha \frac{n}{n\sigma} \sum_{i=1}^n \frac{ f(\theta_t^{i,m}) +N(\theta_t^{i,m},A)}{2} \epsilon_i$
因为奖励汇报和新颖度这两个信号的尺度不同，为了有效组合，可以在组合之前对他们进行rank-normalize

探索NSR-ES的进一步扩展，称为NSRAdapt-ES（NSRA-ES），NSR-ES具有相同的回报和新颖度梯度权重，在训练中是静态的，但NSRA-ES对均衡两者的权重是动态的，可以只能的调整权重 $w$ 来动态调解奖励和新颖度的优先级。
$\theta_{t+1}^m \gets \theta_t^m + \alpha \frac{n}{n\sigma} \sum_{i=1}^n wf(\theta_t^{i,m})\epsilon_i +(1-w)N(\theta_t^{i,m},A)\epsilon_i$
最初我们设置 $w=1.0$ ，如果性能在固定数量的区间停滞不前，我们会降低它知道性能提高，提高后再慢慢增加 $w$