First return, then explore.

最近读完了Nature上强化学习的一篇经典作品 First return, then explore. 做一下阅读笔记，不知道是不是Nature要求的论文写作结构比较奇怪，还是作者本身的问题，虽然创新很突出，不过写法上有些乱，重新梳理一遍如下：

PART 1. 问题与突破

强化学习在围棋、星际争霸、刀塔等游戏中的卓越成就在很大程度上得益于精心设计、信息稠密的奖励函数。然而，对于许多实际问题而言，定义一个良好的奖励函数并不容易，例如达到冰箱，如果奖励只在达到的时刻给予，那么奖励会变得稀疏，由于探索实际上是概率进行的，且不可能进行无数次，算法可能无法找到该奖励；如果设计奖励更加稠密(变为欧式距离)则会误导机器人，比如陷入死胡同，或者说撞到障碍物。

那么解决关键在哪里呢？

作者认为对状态空间的充分探索有助于避免陷入局部最优解。而从前的算法之所以做不到这一点，主要有两点原因：

为了避免脱离和脱轨，作者提出了Go-Explore这一族算法，

算法优势：

成就与突破

PART 2. 算法思想与流程

在上一个Part中我们看到了作者针对先前算法所提出的两个问题：脱离和脱轨，而在这两个问题上作者都强调了一件事：返回之前探索过的状态，那么为什么之前探索过的状态如此重要？

我们先来思考一个看起来不相关的问题：如何通关一个游戏或者说如何更好地通关一个游戏？

在魂斗罗中，显然我们需要找到威力大的子弹；尽量保留更多条命；找到更优的站位等等

而在超级玛丽中，我们则需要找到蘑菇，增大体型并且能够发射弹药；吃金币，躲蘑菇怪等。

现在来想象一个场景：假设你现在是一个对该游戏一窍不通的小白，进入游戏后你随便按动游戏柄或鼠标，你总会有概率达到一些好的接近通关的状态，比如剩余血量较高，分数较高，手里的武器更好等等，但由于你对前方状态未知，你仍然通关失败了，于是你重新启动下一次游戏，你会怎么做呢？

一个很简单且直接的想法就是：既然上一次已经达到那个好的状态，那就先重复上次的操作，回到那个状态，再以一个良好的状态尝试继续通关游戏。

正好，这篇论文也是这么想的。

将上述玩游戏的思想应用到强化学习中，可以换一种描述方式：存储目前已知的最优的一个或多个状态以及到达该状态所需要的轨迹，每次探索时首先采用该轨迹回到存储的某个状态，在此状态的基础上继续进行探索。

再做进一步思考可以看到：第一：有些状态可能只是在已有局部认知情况下的最优，未必是达到全局最优解的轨迹，因此不仅需要保存看起来更有优势的状态，也需要保存并探索与已知状态相比更“新”的状态以保证真正收敛到全局最优；第二：人在玩游戏的时候通常无法完全记忆并复现某个状态及到达该状态的轨迹，其优势在于因为不能完全复现，因此具有一定的探索性质，保证更加充分的探索性与泛化性，更加适应随机环境；而劣势在于可能该状态已经是最优，但回归代价较大（花费更多时间），但计算机可以完全存储。

实际上这就是本篇论文所提出“Go-Explore”以及变种算法“Policy-based Go-Explore” 的主要思想所在。

现在，可以来看看这篇论文所提出的算法——Go-Explore，不过在此之前，首先聊一聊算法里的一些名词：

算法流程如下：

探索阶段的流程图如下：

在利用模拟器这种可恢复环境的特性时，Go-Explore在其“探索阶段”通过不断恢复其档案中的一个状态来彻底探索环境。最终，返回找到的得分最高的轨迹。然而此类轨迹对随机性或意外结果并不鲁棒。为解决这个问题，Go-Explore通过“从演示中学习”（Learning From Demonstrations, LFD） 以得到鲁棒的策略，其中探索阶段的轨迹取代了通常由人类专家提供的演示，所使用的环境变体具有足够的随机性以确保鲁棒性。只要接近示例轨迹仍能导致累积奖励较高，探索阶段的轨迹在随机环境中就是有指导意义的。因为它能从开环轨迹中产生鲁棒策略，此LFD过程称为鲁棒化阶段(robustification phase)。

如果你注意到了在上面流程图上b步骤有两种方法，那么你大概会知道作者对Go-Explore算法的一个变种，即Policy-Based Go-Explore（基于策略的Go-Explore），事实上返回一个状态有两种办法：使用模拟器直接返回，即前文所述的基础的Go-Explore；采用基于目标的策略，即Policy-Based Go-Explore

与人不能完全复现游戏所具有的优势一样，基于策略的Go-Explore也有以下优势：

但同时基于策略的Go-Explore算法也有如人一般的劣势，即很可能无法完全回归，因此作者在回归阶段使用增加了一些设置：

以上是本篇论文的核心思想，其实很简单，但朴素的思想往往来自于对生活细致的观察，更加详细发现学习中的每个阶段每种模式，并加以发展应用，智能才能真正被认知和拓展。

PART 3. 算法具体方法与细节

友情提醒，这一节可能会非常繁琐（原文就这样（悲））。

一、Atari上的最新表现

Atari上的强化学习经常发生进展，且不同方法间往往差异很大，需要使用统一标准比较不同方法，确定每个游戏的最先进得分：

在评估最先进得分的过程中，包括了23种算法和变体。对于每个游戏，最先进的得分是所有算法中取得的最高分数。

二、Atari中的下采样

在“使用状态恢复学习Atari”的Go-Explore变体中，细胞表示是原始游戏帧的缩小版本，可以应用于任何状态是视觉图像的领域。

下采样的方法：

一组固定的参数 w、h 和 d 的值不仅未必适合当前游戏并且无法跨游戏进行泛化，因此通过以下优化方式动态更新：提出不同的值进行计算，计算最近帧的样本将如何在这些提出的参数下分组到细胞中，然后选择产生最佳细胞分布的值。
候选缩放参数的目标函数是基于目标细胞数 T（ T 是样本中细胞数量的固定分数），当前考虑的参数产生的实际细胞数 n，以及样本帧在细胞上的分布 p 计算的。其一般形式为： 

L(n,T)衡量了当前参数下细胞数量n与目标细胞数量T之间的差异。它防止了所发现的表示将太多帧聚合在一起，这将导致探索不足，或者将太少的帧聚合在一起，这将导致时间和内存复杂度不可解。其定义如下:

Hn(p)是帧在细胞之间分布熵与大小为n的离散均匀分布熵的比率。高度不均匀的分布可能会导致与过度聚合相同的探索不足或与不足聚合相同的不可解性，这种标准化熵可以在不同数量的细胞之间进行比较，从而可以仅通过L(n, T)来控制细胞的数量。其形式为:

几何采样：在随机搜索的每一步中，通过从几何分布中采样来提出每个参数w、h和d的新值，其中几何分布的均值是给定参数的当前已知最佳值。
如果当前已知的最佳值低于最小均值，则将最小均值用作几何分布的均值(该算法对最小均值的特定设置不太敏感)。如果新参数值超出该参数的有效范围，则会重新对其进行采样。
搜索样本：最近观察到的帧构成了进行参数搜索的样本，这些帧是通过在Go-Explore运行时维护一组最近看到的样本帧而获得的,即每当在探索步骤中看到尚未包含在该集合中的帧时，就以1%的概率将其添加到运行集合中，以确保该集合包含多种帧而不仅仅是最近的帧。如果结果集包含超过10,000帧，则删除其中最老的帧。
这个集合类似于先进先出的重放缓冲区，但只存储单个帧，而不是完整的状态转换。

采样频率 ：首次采样在以单一细胞表示运行一定帧后进行。为了处理随着探索进展而发生的帧分布变化，并避免陷入糟糕的表示，每运行一定帧就会进行一次新表示的搜索。为了避免过多的内存使用，如果档案中的细胞数量超过一定数量，也会重新计算表示。
切换表示：当切换到新表示时，将创建一个新的档案，并通过将先前档案中的每个状态对应的帧转换为新表示来初始化它。
超参数：超参数是通过对蒙特祖马的复仇进行初始随机扫描找到的，然后对排名前10的组合进行了测试，以确保它们的普适性。超参数除了目标比例、最小均值和缓冲采样率外，还控制了计算和内存效率与获得下采样参数质量之间的权衡。

三、专业知识的表示方式

1.Pitfall

在Pitfall中，使用到的专业知识表示方法包括智能体当前所处的房间以及智能体的x、y位置的离散化。

2.Montezuma’s Revenge

在Montezuma’s Revenge中，表示还包括智能体当前持有的钥匙（包括它们在哪个房间找到的）以及当前层数。

这些特征（层数、房间和x、y位置）大多用于指定智能体的位置，考虑到探索需要发现空间内不同位置，智能体持有的钥匙是允许其到达新位置的重要能力。

3.信息获取

这些信息使用小型手写分类器从像素中提取，说明使用专业知识表示不一定需要访问模拟器的内部状态。对于实际应用，有助于探索的特征通常比执行任务所需的特征更容易识别和获取。

4.机器人领域

在机器人领域，专业知识表示是从 MuJoCo 模拟器的内部状态中提取的（先前的工作已经能够从实际机器人的原始摄像头图像中提取类似的信息）。

其专业知识表示包括机器人夹持器的当前三维位置，以0.5米的边长的体素进行离散化，机器人当前是否接触（用单个夹持器）或抓取（用两个夹持器接触）物体，以及物体当前是否位于目标架子上。

对于带门的两个目标架子，还包括门和门闩的位置。门闩和门的离散化遵循以下公式，其中d是闩/门距离其起始位置的距离（以米为单位）：⌊(d + 0.195)/0.2⌋。

四、探索阶段
在探索阶段，每一步中细胞的选择概率与其选择权重成比例，除非另有规定，其计算如下：

其中， C_seen 是访问该细胞的探索步骤的数量（即，当细胞在探索步骤中被访问时，即使该细胞在该步骤中被访问多次，其C_seen 计数也会增加一次）。这种倒数平方根权重类似于诸如UCT和基于计数的内在动机算法中使用的探索奖励。引入专业知识到细胞表示中的一个优势是，可以利用对领域特征的语义理解来改进细胞的选择。
以Montezuma’sRevenge为例，其中没有返回策略但有专业知识，根据以下内容定义细胞的选择权重：

位置权重：

位置权重表示了一个直觉的概念：档案中缺少邻居的细胞很可能位于当前的搜索前沿（垂直邻居不具有相同的效果，因为从一个垂直级别移动到另一个垂直级别通常更加困难，例如需要有梯子存在），并且如果智能体持有更多的钥匙，则智能体具有更多的探索能力。

具有专业知识的权重：

将W_location 与 W 结合，以及给定细胞的层数 l 和档案中的最大层数 L，以获得具有专业知识的Montezuma’sRevenge的最终权重：

这种级别加权方式更加强调到目前为止达到的最高层数的细胞，因此将探索重点放在搜索的前沿。这些专业知识特征相对于上述默认选择权重 W ，显着提高了在Montezuma’sRevenge的复杂性，但使用默认选择权重的Go-Explore仍能够到达第3级的末尾，仍然能够遍历整个Montezuma’sRevenge的轨迹。虽然可以为Pitfall使用专业知识产生类似的细胞选择权重，但是没有这样的权重能够显著改进 W。

动作采样：当返回到一个细胞，探索将继续执行随机动作一定数量的步骤（在Atari中为100步，在机器人领域为30步），或者直到从环境中接收到结束的信号。在Atari中，由于动作集是离散的，所以动作是均匀随机选择的。在机器人领域，每个动作的九个连续值分量独立地且均匀地从区间-1到1中进行抽样。为了帮助在一个一致的方向上进行探索，在Atari中重复执行上一个动作的概率为95%，在机器人领域为90%。

并行处理：为了提高效率，探索阶段通过在多个进程中选择一批返回细胞并从每个细胞中进行探索来并行处理。

模拟器返回:除了基于策略的Go-Explore外，都通过直接恢复模拟器状态来返回。只要有模拟器可用，这种返回方法就可用；模拟器在训练强化学习最引人注目的应用中发挥了关键作用，并且在可预见的未来可能继续被利用。

五、反向算法

反向算法将agent放置在接近末端的轨迹处，并运行近端策略优化（PPO），直到agent的性能与专家演示相匹配。一旦agent达到可比较的性能，其起始点将被移动到轨迹的接近开始处，然后重复该过程。这个迭代过程使agent逐渐学会从轨迹末端到开始的模仿专家行为。旨在通过调整agent的起始点、利用多次演示、跟踪部分进展并采用自我模仿学习和奖励归一化技术，有效地训练agent模仿专家演示。

六、评估

Atari实验中，探索阶段的得分是在每个周期结束时所达到的最高得分。对于11个重点游戏，探索阶段的得分是在50次探索阶段运行中进行平均的。对于其他游戏和专业知识，分别进行了5次和100次运行的平均。只有11个重点游戏在随机环境中进行了鲁棒性测试和评估。对于已经被解决的游戏，因为鲁棒化的成本过高，所以没有进行进一步的实验。

在Robustification过程中，每100次训练迭代（13,926,400帧）产生一个检查点。检查点被选取为训练期间得分滚动平均值最高的时刻。对所选检查点进行测试，评估其在100个测试周期中的得分，并对得分最高的检查点进行进一步的测试，以消除选择偏差。在Robustification过程中，使用粘性动作进行测试，并修复了一个ALE的bug，以确保准确比较与人类世界记录的分数。

机器人实验通过50次运行评估每个目标货架的探索阶段，总共进行了200次运行。机器人实验的指标是发现成功轨迹的比例。与Atari不同，机器人实验的结果是二元的（成功或失败），一旦agent可靠地成功，就没有继续进行鲁棒化的理由。机器人实验的鲁棒化过程在agent成功率超过98.5%的情况下终止，并在成功后进行了150个训练迭代（19,660,800帧）以上的运行。

与普通的PPO和带有基于计数的内在奖励的PPO进行了对比实验。前者在1亿帧下未找到任何奖励，从而证实了机器人环境的困难性；后者在20亿帧下仍然无法与探索阶段相媲美，表明即使运行时间更长，也无法有效解决问题。通过这些实验和对比，作者验证了机器人环境的困难性，并证明了探索阶段的有效性和优越性。

PART 4. 实验验证

这一部分主要找两个比较有代表性的实验（原文实验有快60组）。

一、基于策略的Go-Explore

蒙特祖玛的复仇和玛雅人的冒险的问题是所需要的奖励（rewards）信号很少。两个游戏都涉及典型场景：主角要探索充满致命生物和陷阱的方块世界，在游戏中许多所必需的行为都无助于提高分数，只在长时间完成特定的一系列动作之后才会收到奖励信号。普通的强化学习算法甚至过不去蒙特祖玛的复仇和玛雅人的冒险的第一关，他们得分完全为零。

基于策略的Go-Explore在Montezuma’s Revenge和Pit-fall上进行了测试，并使用专业知识细胞表示档案与策略的目标，游戏状态以像素形式输入。 它在Montezuma’s Revenge中获得了97728分，在 Pit-fall中获得了20093分，Go-Explore的得分远远高于最新的强化学习方法与人类基准。基于策略的 Go-Explore消除了额外复杂性、超参数开销，为强化学习提供了一种高效且灵活的解决方案。
二、机械臂抓取任务

如上图所示，机械臂应用场景的要求是操作机械臂将一个物体进行抓取并将它放到一个具有四个格子的架子中，其中两个格子是敞开的，另外两个格子是被关上门且带有插销的，奖励只在将物体放入指定目标货架时给出。该任务是一个典型的困难探索环境，需要机器人执行复杂的操作，如移动、抓取和放置物体。

机械臂抓取问题的网络架构包含两个相互独立的网络。每个网络都有两个全连接层（用于特征提取和转换）和一个GRU层（门控循环细胞，用于处理序列数据的循环神经网络结构，能够捕捉序列中的时间依赖关系）。左方的网络为策略评价网络，可以通过返回手臂执行器扭矩和每个抓取器手指所需位置的均值μ_t和方差σ_t来指定策略π_t (s_t|a_t)。右方的网络为值函数网络，用于实现值函数V_t (s_t)，用于评估在给定状态下采取某个策略的长期预期回报。抓取器手指在这里被实现为Mujoco位置执行器。其刚度系数K_p设置为104，决定了执行器对位置偏差的响应程度，控制范围[0,0.05]，意味着手指的位置可以在这个范围内调整。

Go-Explore彻底探索了周围的环境，解决了脱离（例如，一旦每个橱柜被打开，算法永远不会忘记那些状态）或脱轨（算法可以直接恢复到难以到达的状态，如抓取）问题的影响。PPO+IM在20亿帧训练后只发现了探索阶段发掘的一小部分细胞，在训练始终未遇到任何奖励。相比之下Go-explore可以更快的探索到更多状态，在四个不同目标位置的情况下，机器人都能够在99%的试验中抓起物体起来并将其放置于架子上。

PART 5. 创新与贡献

本文主要创新点：

主要贡献：

以上。特别感谢一起读的四位同学，在讨论中澄清了许多理解上的问题。