论文速览【RL - Exploration】—— 【Go-Explore】First return, then explore

• 标题：First return, then explore

• 文章链接：First return, then explore

• 发表：Nature 2021

• 领域：强化学习 —— Exploration

  • 本文最初版本 2019 年挂在 arXiv 上，文章链接：Go-Explore: a New Approach for Hard-Exploration Problems
  • 2021 发在 Nature 的完整版主要的改动是在 return 阶段（阶段1）增加了基于 goal-condition 的方法，解除了训练阶段环境必须是确定性环境（deterministic env）的限制；另外补充了很多实验
  • 本文主要围绕 21 年的 First return, then explore 文章进行说明，同时兼顾 19 年的原版论文。为了区别两篇文章的方法，19 年论文的方法称为 “原始 Go-Explore”；21 年论文的方法称为 “policy-based Go-Explore”

---

1. 动机

• 本文主要考虑 难探索hard-exploration 问题，即状态动作空间非常大，而奖励相对非常稀疏的 RL 任务，这种情况下 agent 面对以下两个困境

  1. 稀疏奖励：agent 必须精确执行很长的动作序列才能得到 reward 信号
  2. 奖励信号具有欺骗性：这个可以从 reward shaping 的角度来理解，当奖励稀疏时我们常常加入一些辅助奖励函数，这样虽然可以让 agent 收到的指导信号更加密集，但也很容易误导 agent 导致 reward hacking（比如增加一个 “减小到目标位置的距离” 作为辅助奖励，agent 可能为了收集这个奖励进入死胡同，或者做出撞墙等不安全行为）。这里可以参考 强化学习拾遗 —— 再看奖励函数

  过去的研究已经表明，如果能对状态空间进行充分探索，就能发现稀疏的奖励，并避免欺骗性的局部最优，这引发了对于探索方法的诸多研究。基于内部激励的好奇心探索方法（intrinsic motivation, IM）是一类比较流行的鼓励探索方案，这类方法会对访问过的状态进行计数，根据状态的新奇程度给予内部奖励（intrinsic reward, IR），从而无差别地鼓励 agent 探索新状态

• 作者认为 IM 类方法有以下两个问题

  1. 分离Detachment：agent 在 IR 的驱使下部分探索了一个区域，然后由于轨迹结束或随机性切换到第二个区域（IM 方法常要求智能体随机尝试新行为以找到更多的 IR）。由于深度学习的 灾难性遗忘，agent 会忘记如何返区域一，又因为此时区域一边缘部分的 IR 已经被大量消耗，agent 不会被鼓励回到之前的探索边界，这样探索范围就十分有限
     

  2. 脱轨Derailment：即使 agent 记住了去往当前探索边界的完整动作序列，由于一般策略的探索机制（如 $ϵ$-greedy），agent 会边走边试探，无法准确地返回目标边界位置；如果为了有效返回减小探索动作，又无法进行有效的探索了。另外环境的随机性也会导致这个问题

• 作者希望能解决 IM 类方法的上述两个问题，达成两个目标

  1. 微观层面上：探索过程中可以记住探索边界，每次先到达边界再向外探索，从而高效地探索整个状态空间
  2. 宏观层面上：通过高效探索直接得到可以完成任务的较好的轨迹，然后利用这些轨迹学出一个有鲁棒性的策略（learn form demonstration，如模仿学习）

  作者自己把这两个总结为 first return ,then explore；first solve, then robustify

2. 本文方法

2.1 思路

• 如第 1 节最后说明，本文方法分两个阶段
  

  1. 第一阶段（Exploration phase）维护一个访问状态存档（archive），其中记录了前往此状态的动作序列。每轮迭代按一定规则选出一个状态，利用存档中的信息走到这个状态上，再从此出发做探索，如果探索到了新的状态，或者到达某个状态更好的路径，就记录下来加入/更新存档（类似最短路的 Dijsktra 算法）。只要这个探索阶段做得足够好，我们几乎可以找到去向任何状态的较好的轨迹，其中也包括可以完成既定任务的轨迹，即 explore until solved

  2. 第二阶段（Robustification phase）使用阶段一得到的轨迹做模仿学习，得到足够鲁棒的策略。这里作者借鉴了《Learning Montezuma’s Revenge from a single demonstration.》这篇文章提出的 “backward algorithm” 方法

     这个方法大致上来说，就是拿到一条高奖励的轨迹之后，先把智能体放在离轨迹末端较近的位置，让智能体能够学习到如何从这个离目标很近状态走到目标，然后再逐步把智能体放在轨迹上离目标更远一些的地方。通过这种方式智能体就能逐步学习到如何从初始位置走到目标位置。其学习的算法还是使用的 PPO 等通用 RL 算法 。这个过程也可以看做是一个课程学习（curriculum learning），使用第一部分生成的反向轨迹来作为由易到难设定的课程。

     注意第一阶段可能是在确定性环境中得到的示范轨迹（用 2019 年文章的纯随机探索方法探索方法），而我们最终的目标是在随机性环境中完成任务，因此阶段二必须在随机环境中完成。这个 “backward algorithm” 算法本质是在用课程学习的方式做一系列 RL，所以它可以处理环境的随机性，并实现比示范轨迹更好的性能。由于阶段一生成轨迹的能力非常强，作者将 “backward algorithm” 算法修改为可以从多个示范轨迹中学习版本，进一步提升了性能

• 上面主要是 2019 年初版论文的思路
  • 2019 版论文中，阶段1纯粹通过随机 action 进行探索的，这种情况下为了保证可以回到对应状态，要求训练阶段的环境必须是确定性的。由于阶段1不训练任何形式的策略，只是得到了一些脆弱的轨迹，所以必须加上阶段2，在随机性环境中利用这些轨迹做模仿学习得到鲁棒的策略
  • 2021 年 Nature 版论文中增加了基于 goal-condition 的探索策略，如果在阶段1这样进行探索，则训练时就可以使用随机性环境，直接得到鲁棒的策略，这时阶段2可以直接去掉（详见 2.2.3 节），这个方法被作者称为 Policy-based Go-Explore

2.2 算法细节

• 先放一张带说明的算法流程图
  

• 注意上面的阶段1（Exploration phase）

  • a. 依概率性地选择从存档中要返回的状态，偏好与有前途的 cell（见 2.2.2 节）相关联的状态.
  • b. “go” step返回选择的状态，例如恢复模拟器状态或运行目标条件策略
  • c. “explore” step通过采取随机动作或从已训练的策略中采样, 并从该状态探索
  • d. 将每一个在返回和探索过程中遭遇的状态映射到低维单元表示.
  • e. 将映射到新单元格的状态添加到存档并更新其他存档条目

2.2.1 环境

• 本文主要考虑以 Montezuma’s Revenge 为代表的 Atari 套件中的难探索环境，这些环境绝大多数本身是确定性的，并且通常使用视觉画面作为状态
• 考虑到大部分现实任务（如机器人任务）都是工作在随机性环境中，作者希望其方法可以工作在随机性环境种，因此在训练和测试时使用 ‘sticky actions’ trick 向其中加入随机性，这个 trick 就是每次 action 后随机重复几帧动作，模拟人类玩家在操作时的动作粘连

  Note：在 2019 年文章中作者还用了 ‘no-ops’ trick 技巧加入随机性，即在环境启动初期不操作随机长度的时间，这样环境会自己运行到某个随机状态，从而对起始状态加入随机性。这种方法现在不被社区提倡了

2.2.2 状态表示 & 建立存档

• 难探索问题的状态空间通常很大，直接使用原始观察/状态作为单位建立存档不可行。这里作者使用了两种方法进行降维
  1. 对于 state 是 visual observation 的环境，使用 “转灰度图+下采样” 的方法降维得到 cell
     
     这里最后得到 cell 的尺寸和像素深度要根据游戏情况变化，过度聚类会导致探索效率下降；聚类不足会导致内存问题。这里作者设计了一个自动调节下采样参数的方法，随着存档建立会动态变化（每次变化都要把存档中的所有 state 重新下采样得到 cell ），这里具体请参考原文
  2. 大多数任务中我们都可以低成本地获取一些 domain-knowledge，比如 Atria 游戏中 agent 的位置坐标、当前得分、当前所在的 level 等级、当前收集到的钥匙数量等，这些信息都可以用 CV 分类器从游戏画面中提取。基于这种考虑，一个 cell 也可表示为 domain-knowledge + 很粗粒度的固定尺寸下采样图像

     注意：探索阶段需要探索尽量多的状态空间，而 agent 持有的 domain-knowledge 往往是指引它到达新位置的重要启示，使用这种 cell 表示方法可以大幅提升 Go-Explore 的性能

• 存档是一个类似 replay buffer 的先进先出队列，不过其中存储的内容不是 transition，而是 state 及去向它的轨迹。探索阶段遇到的每一个未见状态有 1% 的概率加入存档，以保证存档帧的多样性

2.2.3 探索阶段 a —— 选择去向的 cell

• 这一步的中心思想是尽量扩展 agent 探索的范围，多去探索边界或边界附近的 cell，这里作者借鉴了 IM 类算法的思路

  1. 不考虑 domain-knowledge 时，使用类似基于计数的好奇心机制来从 archive 中选择去向的 cell。各个 cell 权重如下
     $$W=\frac{1}{\sqrt{C_{\text{seen}}+1}}$$ 其中 $C_{\text{seen}}$ 是该探索过程中该 cell 被访问的次数

  2. 如果使用 goal-condition 方式实现 “go” step，改用以下权重
     $$W=\frac{1}{0.5C_{\text{seen}+1}}$$ 这时分母增大速度变快很多，即更加强调最近发现的 cell，这是为了

     1. 帮助 goal-condition 方法更好地学习如何到达目标 cell
     2. 在到达目标 cell（在探索区域边缘）的路上会经过很多中间 cell，虽然 agent 没有显式地指定要到达他们，但是 agent 也在从这些中间单元开始进行探索，这样发现新 cell 的效率，即探索状态空间的效率（绿线）会比确定性环境中直接设置模拟器到达对应位置（蓝线）来得高
        

     作者注意到，如果目标位置很远，直接训练 goal-condition 会策略不稳定，所以这里使用了 Efficient exploration with self-imitation learning via trajectory-conditioned policy 这篇文章中的方法，以一个 soft order 跟踪存档轨迹

     简单说就是把很长的轨迹分成小段，逐段设置子目标

     • agent 每到达一个子目标 cell（或轨迹中该 cell 后方指定窗口范围内的后续 cell），就给予轨迹奖励 $r_t^{\tau }=1$
     • 当到达最后一个子目标（即真正的目标时），给予轨迹奖励 $r_t^{\tau }=3$ (要高于中间子目标的奖励值，实践上看这样效果好)

     另外，合理地利用 domain-knowledge 可以大幅提升探索效率（比如 agent 可以利用位置信息更快地找出已探索区域的边界），作者也尝试了基于游戏的 domain-knowledge 设计更好的启发式的权重，并取得良好效果

• 另外，在目标选择时 19 年和 21 年论文方法还有一个不同
  1. 原始 19 年论文中这里就是直接按上面权重采样目标 cell
  2. 新的 21 年论文中使用了以下标准，当 agent 已经在一个 cell 完成了探索后
     1. 10% 概率随机移动到一个不在存档的相邻 cell（若所有相邻 cell 都在存档，此项概率按比例分配给下面的两项）
     2. 22.5% 概率移动到一个相邻 cell，无论它在不在存档
     3. 67.5% 概率使用以上权重从存档中选择一个 cell

2.2.4 探索阶段 b —— Go step

• Go step 做的是 “返回指定的 cell” 这件事，这里要直面第1节中说明的 Derailment 问题

  1. 19 年的论文本中进行了放松，无论任务环境是确定性还是随机性的，都用模拟器把训练阶段强行搞成确定性环境，这样重放动作序列就能回到指定 state，为了提升效率，直接将模拟器设定那个状态即可，文中称之为 “leverage the availability and wide-spread use of simulators”。显然，这种确定性环境下探索出的成功轨迹是很脆弱的，因此不得不加上在随机性环境中做模仿学习的第二阶段，以获取有鲁棒性的策略

  2. 21 年的论文中，作者用 goal-condition 方法实现了指定 cell 的返回，这样有三个好处

     1. 大幅提升探索效率（探索过程中可以学会并泛化绕过障碍等技巧，纯随机探索可能每次遇到障碍都要被挡一会）
     2. 直接学到一个鲁棒的策略，可以去除阶段2（Robustification phase）
     3. 可以直接在随机性环境中训练

     所谓 “goal-condition RL” 其实和普通 RL 区别很小，某种程度上可以理解成把要去向的目标 $g$ 增加到状态空间中，具体而言，本文中

     1. 使用 PPO 方法训练目标条件策略 $\pi (a|s,g)$
     2. 奖励信号是环境奖励 $r_t^e$ 和上面 2.2.3 节轨迹奖励 $r_t^{\tau }$ 之和

        Note：相比遵循轨迹，我们认为在环境中获取更高性能更重要，所以这里对 $r_t^e$ 进行处理，使得 $r_t^e>r_t^{\tau }$ 绝大多数时刻成立

     3. 使用了自模仿学习（self-imitation learning）方法，提升 agent 在初期的学习效率

     下面给出这个 PPO 训练使用的损失函数
     $$\mathcal{L}(\theta )={\mathcal{L}}^{PG}(\theta )+w_{VF}{\mathcal{L}}^{VF}(\theta )+w_{ENT}{\mathcal{L}}^{ENT}(\theta )+w_{L2}{\mathcal{L}}^{L2}+w_{SIL}{\mathcal{L}}^{SIL}(\theta )$$ 其中前三项都是 PPO 原文中的损失，最后一项是 self-imitation learning 的损失，中间是 $L_2$ 正则化项。对于这些损失的详细说明可以参考对应论文和本论文 supplementary information 材料 14 节

     此外，作者注意到 agent 可能由于动作存在一定收敛，导致很难到达指定的 goal。为了防止 goal condition 实现不了，探索不足，论文额外增加熵的概念来提升探索率，这部分详见论文21页

• 再次强调，19 年的原始 Go-Explore 方法中，探索阶段只能得到轨迹，不涉及策略训练，因此必须要结合 2.2.7 鲁棒化阶段才能得到策略；21 年的 Policy-based Go-Explore 方法中，探索阶段就直接训练了策略，因此不需要鲁棒化阶段了

2.2.5 探索阶段 c —— explore step

• 这一步就是执行随机 action，直到完成任务或者轨迹长度达到设定的 rollout length $L$，期间经过的 state 都会用来更新存档，为了维持一定的探索方向（不要原地打转），以高概率重复上一步的动作（95% for Atria）

2.2.6 探索阶段 d/e —— 更新存档

• 2.2.4 节的探索过程中，存档会在两种情况下进行更新

  1. 经历的所有未见 state 都会有 1% 概率加入存档
  2. 新遇到的轨迹比已经在存档中的 cell 的轨迹 “更好”（return 更高或return一样但是长度更短）时，去向该 cell 的轨迹及相关信息（如果有的话，比如分数这样的 domain-knowledge）会更新

• 因为 cell 合并了许多 state，不能假设从 cell A $\to$ cell B $\to$ cell C 的轨迹在 cell A $\to$ cell B 的轨迹替换后还能到达 C；因此更好的轨迹不会整合到建立到其他包含原始轨迹的细胞的记录轨迹中

  注意上面这个过程其实很像 Dijsktra，只是 Dijsktra 中的轨迹更新会作用到所有节点的轨迹记录上

• 考虑存档更新的影响

  1. 对于 19 年的原版 Go-Explore 算法，存档更新直接优化探索阶段找出的可以完成任务的轨迹
  2. 对于 21 年的 Policy-based Go-Explore 算法，存档更新也在优化去向任意目标 cell 的轨迹，然后通过轨迹奖励 $r_t^{\tau }$ 间接地优化目标条件策略 $\pi (a|s,g)$

2.2.7 鲁棒化阶段

• 对于 19 年论文中的原始 Go-Explore 算法，探索阶段只能得到确定性环境上的一些轨迹，必须加上这个阶段训练出可以在随机性环境中运行的，具有鲁棒性的策略
• 2.1 节已经对本文使用的模仿学习方法进行了比较详细的说明，这里不重复了。就是注意一下复杂任务需要多条示范轨迹作为参考，否则可能模仿不了，无法推广到随机性环境中
  

2.2.8 并发实现

• 下面给出 21 年论文中补充的 Policy-based Go-Explore 方法的训练结构图
  
  注意这种 Policy-based Go-Explore 方法使用了 goal-condition 策略，因此只需这一个训练阶段即可

2.3 伪代码

2.3.1 Go-Explore【2019】

• 阶段1：Exploration Phase with Simulator Restoration
  
• 阶段2：Robustification Phase Rollout Worker
  

2.3.2 Policy-based Go-Explore【2021】

• 只有一个阶段
  

3. 实验结果

• 本文方法效果非常卓越，大幅提升了 Montezuma’s Revenge 这个很难的 hard-exploration 问题的得分，增加 domain-knowledge 后打破了人类世界记录
• 在所有雅达利游戏上都超过了人类平均表现，并在大多数游戏上取得 SOTA
  
• 对于一个 hard-exploration 的机器人任务，成功率到达 100%
  

4. 总结

• 本文方法取得的性能令人印象深刻，它告诉我们高效的探索可以有效处理 Hard-Exploration 问题，并给出两条途径：
  1. 确定性环境中，只要对状态空间进行充分的探索，就一定能找出实现任务的近似最优轨迹，再基于它们做模仿学习就能得到适用于随机性环境的鲁棒策略
  2. 随机性环境中，如果探索足够高效，也可以找出大量实现任务的高质量轨迹（由于环境随机性会稍有差异），通过奖励函数让 goal-condition RL 间接地模仿它们，进而学到很好的鲁棒策略
• 过去 RL 算法无法解决太复杂的任务，主要就是因为这时任务目标过于抽象，难以给出稠密的奖励，sparse reward 导致 Hard-Exploration 问题，这种情况在机器人领域尤其常见。使用 Go-Explore 方法就能有效解决此问题，只用简单的高层次定性奖励，就能训练 agent 完成复杂任务了
• 本文提升探索效率的思路很有价值：
  1. 直接走到最前沿的某个状态，然后再探索，尽量扩大探索空间的边界。这个思路也很符合人类平时探索的思维模式，确实能有效解决目前强化学习探索上的痛点

     还有一点，即使只使用最易于获取的 domain-knowledge，也可大幅提升探索效率

  2. 更新存档的方式非常类似经典的图算法 Dijkstra，或许可以尝试将其他经典的规划算法如 MCTS 和 A* 等的思想融入 RL 探索，使其更有 planning-like nature
• 文章最后作者也提出了几个改进方向
  1. learn to choose which cells to return to
  2. learn which cells to try to reach during the exploration step
  3. learn a specialized policy for exploration in the ‘explore’ step
  4. learn to explore safely in the real world by mining diverse catastrophes in simulation
  5. maintain a continuous density-based archive rather than a discrete cell-based one
  6. improve sample efficiency by leveraging multiple trajectories (or even all transitions) from a single exploration-phase run
  7. improve the robustification phase to work from a single demonstration, and so on.