Atari 游戏得分提升两个数量级：Uber AI 的新强化学习算法 Go-Explore

雷锋网 AI 科技评论按：近期，Uber AI 研究院提出了一种新的强化学习算法 Go-Explore ，它的目标是克服当前热门的好奇心（内在奖励）大类方法尚未克服的遗忘和重复探索问题。他们也在极具挑战的 Atari 游戏「蒙特祖玛的复仇」和「Pitfall」中实验了算法，取得了好几个数量级的表现提升。雷锋网(公众号：雷锋网) AI 科技评论介绍如下。

在强化学习（RL）中，解决 Atari 经典游戏「蒙特祖玛的复仇」和「Pitfall」是一项巨大的挑战。这些游戏代表了一类具有普遍挑战性的现实问题——「硬探索问题」，即智能体必须通过非常稀疏或有欺骗性的反馈来学习复杂任务。

之前最先进的算法玩蒙特祖玛的平均分为 11,347，最高分为 17,500，并且在十次闯关后通过了第一关。令人惊讶的是，尽管进行了大量的研究工作，但到目前为止对于 Pitfall，还没有算法能获得大于 0 的分数。

Atari 游戏得分的新突破

今天介绍的 Go-Explore，是一个新的算法类型，它能够在蒙特祖玛上得分超过 2 百万分，平均得分超过 400万分！Go-Explore 可以很稳定的通关整个游戏，其实这个游戏只有前三关不一样，后续关卡都是前三关的衍生（每个关卡仅在时间的长短和屏幕显示的分数上有所不同而已）。Go-Explore 甚至可以达到159级！

在 Pitfall 中，Go-Explore的平均得分超过 21,000，远超人类的平均表现，并且首次在已有算法上实现零得分的突破。为此，它要穿过 40 个房间，完成水上绳索跳跃、跳过鳄鱼、陷阱门、移动桶、爬梯子和躲避其他危险物。 

总而言之，Go-Explore 算法分别将蒙特祖玛的复仇和 Pitfall 的得分现状提升了两个数量级和 21,000 分。再者它无需「人工演示」，并且在性能上完胜目前所有涉及「人工演示」的最先进的算法。 

Go-Explore 可以从人工领域知识中受益，无需人工通关游戏作为演示。领域知识很小，很容易从像素中获得，这突出了 Go-Explore 利用最小先验知识的深刻能力。然而，即使没有任何领域知识，Go-Explore 在蒙特祖玛中的得分也超过了 3.5 万分，远超现有技术三倍之多。 

Go-Explore 与其他深度强化学习算法完全不同。Uber 研究院认为它可以在各种重要的，具有挑战性的问题中取得快速进展，特别是机器人技术方面。因此他们也希望它能够帮助 Uber 和其他团队更多地利用人工智能的优势。 

探索的挑战

奖励稀疏的问题很难解决，因为随机行为无法产生奖励，因此无法学习。蒙特祖玛就是这样一个奖励稀疏的问题。奖励具有欺骗性时就更棘手，这意味着在短期内最大化奖励可能会使智能体在总分上表现不佳。Pitfall 中的奖励则具有欺骗性，许多行为会导致小的负面奖励（比如击中敌人），因此大多数算法都选择智能体不移动，因此永远无法收集到其他奖励。许多具有挑战性的现实问题的奖励都是稀疏和有欺骗性的。 

普通的 RL 算法通常无法离开蒙特祖玛的第一个房间（得分为400或更低）并且在 Pitfall 上得分为 0 或更低。为了尝试解决这些挑战，研究人员为智能体增加了探索奖励，通常称为内在动机（intrinsic motivation，IM），鼓励他们到达新状态（情境或地点）。尽管 IM 算法专门用于解决稀疏奖励问题，但他们在蒙特祖玛和Pitfall的任务中仍表现不佳，在蒙特祖玛中表现最好的也鲜有能过第一关的，在Pitfall中更是以0分完败。

Uber AI 的研究人员们猜测当前 IM 算法的一个主要弱点是分离，即算法忘记了他们访问过的「有奖励」的区域，这意味着他们返回这些区域的时候不会再有新的奖励。举个例子，想象智能体处在两个迷宫入口之间。它先从左边的迷宫开始随机搜索，由于 IM 算法有要求智能体随机的尝试新行为以找到更多的内在奖励的机制，在搜索完左边迷宫的 50 %时，智能体会在任意时刻开始对右边迷宫的搜索，但由于深度学习自身的灾难性遗忘问题，在完成右边的搜索后智能体并不记得在左边迷宫中探索的事情；更糟糕的是，左边迷宫的一部分已经被探索过，所以几乎没有可获得的内在奖励，这就严重影响了智能体的学习过程。Uber AI 的研究人员们将这种状况称为：算法从提供内在动机的状态范围分离开了。因此，当已经探索了当前智能体访问过的区域时，探索可能会停滞。如果智能体能够返回到先前发现的有奖励的探索区域，就可以解决这个探索停滞问题。

内在动机（IM）算法中的分离示例。 绿色区域表示内在奖励，白色表示没有内在奖励的区域，紫色区域表示算法当前正在探索的位置。

GO-explore

Go-Explore算法的高度概括

而 Uber AI 提出的新算法 Go-Explore 将学习分为两个步骤：探索和强化。

阶段1：探索到解决为止。 Go-Explore 构建了一个有趣的不同游戏状态（称之为「单元格」）和导致状态轨迹的存档，如下所示：

重复到解决为止：

• 根据概率选择存档中的单元格（可选择有可能有奖励的单元格，例如更新的单元格）

• 回到那个单元格

• 从该单元格开始探索（例如，随机进行 n 个步骤）

• 对于所有访问的单元格（包括新单元格），如果新的轨迹更好（例如更高的分数），则更新单元格轨迹。

通过在存档中明确记录状态的轨迹，Go-Explore 能够记住并返回到「有奖励」的区域进行探索（这不同于内在动机的训练策略）。此外，通过探索单元格前先返回单元格的操作，特别是对于那些距离远的、难以到达的单元格，Go-Explore 避免过度探索容易达到的状态（例如在起点附近），而是专注于扩展其知识领域。最后，因为 Go-Explore 尝试访问所有可达状态，所以它不太容易受到欺骗性奖励的影响。熟悉质量多样性算法的人可以理解这些想法。下文将继续讨论 Go-Explore 如何表示一种新型的质量多样性算法。

阶段2：强化（如有必要）。如果找到的解决方案对噪声的鲁棒性较差，可以使用模拟学习算法将它们置于深度神经网络中。

单元格表示

为了能够驾驭 Atari 游戏这样的高维状态空间，Go-Explore 需要一个较低维度的单元格表示来进行存档。因此，单元格表示应该将十分相似且无需单独探索的状态进行合并（但不混合意义上有差别的状态）。重要的是，创建这样的表示不需要游戏特定的领域知识。经研究发现，最朴素的单元格表示可能非常有效：只需对当前游戏框架进行下采样。

返回单元格

根据环境的限制，可以通过以下三种方式实现探索之前先返回单元格的操作。为了提高效率：

• 可重置环境中，可以简单地将环境状态重置为单元格的状态

• 在确定性环境中，可以重现到细胞的轨迹

• 在随机环境中，人们可以训练一个学习可靠返回到单元格的目标条件策略

虽然大多数有趣的问题都是随机的，但 Go-Explore 背后的一个核心思想是我们可以先解决问题，之后再想办法使解决方案更加具有鲁棒性（如有必要）。特别是，我们通常认为确定性会阻碍产生更具鲁棒性、更高性能的智能体，但 Go-Explore 观点与之相反，当我们了解到模拟器是确定的和可重置的（通过保存和还原模拟器状态）事实后，确定性可能还有助于产生更高性能的智能体，然后可以随机创建一个更强大的策略（包括添加领域随机化）。此观察结果与机器人任务尤为相关，在策略迁移到实际任务之前，需要在模拟器中完成相关训练。

Atari 游戏是可重置的，因此出于效率原因，Uber AI 的研究人员们通过加载游戏状态返回到先前访问过的单元格。在蒙特祖玛的复仇中，这种优化使他们能够比「回顾轨迹方法」快 45 倍地通关第一级。然而，Go-Explore 不需要访问模拟器，访问模拟器只是为了让它变得更快。

在这项工作中，当智能体返回一个经随机行为探索的单元格后（很可能重复以前的行为）。尽管在强化中常常会用到神经网络，但这种探索不需要神经网络或其他控制器，并且后续实验中所有的探索都不使用。完全随机的探索工作非常好的突出了仅返回目标单元格的惊人能力。

探索阶段的结果

通过下采样图像单元格表示，在蒙特祖玛游戏中， Go-Explore 仅用了先前技术的 65% 的时间就通关了第一关（其中包含24个不必要探索的房间），平均到达房间 37 个，而先前的技术水平平均只探索了22个房间。

Go-Explore在没有领域知识(通过缩小像素表示)的探索阶段发现的房间数量

鲁棒化

Uber AI 当前版本的 Go-Explore 利用确定性来更快地找到解决方案（高性能轨迹）。这样的轨迹是脆弱的：不能泛化到其他差异场景中，包括那些通过使 Atari 游戏有点随机的经典方式所创造的状态，即迫使智能体在开始游戏之前随机 30 多次什么都不做。

Go-Explore 通过模仿学习解决了这个脆弱性问题，模仿学习是一种可以从演示中学习鲁棒无模型策略的算法。通常这样的算法需要人工演示，但是 Go-Explore 的第1阶段可以自动生成这样的演示（其中一部分比人工演示效果更好）。

任何可靠的模仿学习算法都可行。起初 Uber AI 的研究人员们选择了 Salimans 和 Chen 的「后向算法」，因为它是开源的，并且在提供人工演示时可以解决蒙特祖玛的问题。

他们还发现从单一演示中学习有点不可靠。然而，因为 Go-Explore 可以产生大量的演示，他们为了同时学习多个演示而改进了后向算法（在这种情况下学习 4 个演示，以及后面的领域知识实验中 10 个）。他们还在初始条件中添加了一个随机数的无操作（不执行任何命令），以使策略对此类随机性具有鲁棒性。

结果具有强大的深度神经网络策略

所有试图从蒙特祖玛第一关通关轨迹中学习的鲁棒策略都有效。平均得分为 35,410 分，是之前技术水平均分 11,347 分的 3 倍以上，并略高于人类专家的均分 34,900 分！

无领域知识的Go-Explore与其他RL算法在Montezuma复仇中的比较。情节中的每一点都代表了一个不同的算法，测试蒙特祖玛的复仇。

添加领域知识

算法能将易得的领域知识集成的能力是很重要的。Go-Explore 支持利用单元格表示中的领域知识。Uber AI 的研究人员们在蒙特祖玛上测试了具有领域知识的 Go-Explore 版本，其中单元格被定义为智能体的 x-y 位置、当前房间、当前关卡和当前持有的密钥数量的唯一组合。他们编写了简单的代码来直接从像素中提取这些信息。

通过这种改进的状态表示，在 Go-Explore 的第 1 阶段，智能体就惊人地发现了 238 个房间，平均通过 9 个关卡，并且在模拟器中，相比与缩略图的单元格表示，Go-Explore 智能体仅用了一半步骤就完成了该任务。

仅使用由像素导出的领域知识的单元格表示，Go-Explore第1阶段发现的房间数量，

强化的结果

利用有领域知识的 Go-Explore 版本找到的轨迹的而产生的深度神经网络策略，可以稳定的通过蒙特祖玛的前三个关卡（并且对随机数量的初始无操作具有鲁棒性）。因为在这个游戏中，3 级以上的所有关卡几乎相同（如上所述），Go-Explore 已经通关了整个游戏！

事实上，Uber AI 的智能体大致已经超过了他们的初始轨迹，平均通过 19 关并获得了 469,209 的分数！这就已经突破了蒙特祖玛的最好成绩，无论是相对于传统的 RL 算法还是以人工演示形式提供解决方案的模仿学习算法。令人难以置信的是，一些 Go-Explore 的神经网络得到了 200 多万分、159级！为了充分了解这些智能体可以做到什么程度，Uber AI 增加了 OpenAI 的 Gym 允许智能体玩游戏的时间。 Go-Explore 的最高分数远高于人类世界纪录 1,219,200，可以说达到了严格意义上的「超越人类表现」。

结合领域知识的GO-EXPLORE与其他RL算法的比较。红点表示以人工演示的形式给出的解决方案的算法

这个破纪录的完整视频在加速 4 倍后仍然有 53 分钟长。智能体不会死亡，只是达到了最大时间限制（尽管时间已经大大增加）。

Pitfall 游戏

Pitfall 也需要大量的探索，并且比蒙特祖玛更难，因为它的奖励更稀疏（只有 32 个积极奖励分散在 255 个房间中），许多行动产生小的负面奖励，阻止 RL 算法探索环境。目前为止，所有已知的 RL 算法在这个游戏中甚至没有收到任何一个积极奖励（没有给人工演示的情况下）。

相比之下，Go-Explore 在具有最小领域知识的情况下，即我们从像素中获得的屏幕上的位置和房间号，其能够访问所有 255 个房间并在算法的探索阶段收集超过 60,000 个点。没有领域知识（即在缩小的像素表示）的情况下，Go-Explore 找到了 22 个房间，但没有找到任何奖励。Uber AI 的研究人员们认为缩小的像素表示在Pitfall上的表现不佳，因为游戏包含许多具有相同像素表示的不同状态（即游戏中位置不同但外观相同的房间）。在没有领域知识的情况下区分这些状态可能需要考虑先前状态的状态表示，或者开发其他技术。

在Go-Explore 在Pitfall游戏中探索阶段发现的房间(左)和获得的奖励(右)。

从探索阶段收集的轨迹中，Uber AI 能够可靠地收集超过 21,000 点的轨迹进行强化，这大大超过现有技术水平和人类平均表现。 更长、更高得分的轨迹强化起来很困难，可能是因为视觉上无法区分的状态可能需要采取不同的行为。 他们相信可以通过进一步研究智能体消除状态歧义的技术来解决这个问题。

三大关键原则

Uber AI 认为 Go-Explore 之所以在「硬探索问题」上表现非常出色是源于三个关键原则：

• 记住探索过程中好的「基础步骤」（目前为止访问到的不同的有趣场景）

• 先返回到一个场景，然后再探索

• 先解决问题，然后进行鲁棒化（如有必要）

大多数 RL 算法中都没有应用这些思想，但如果把这些思想嵌入到以往 RL 算法中，那将会是一件有意思的事情。如上所述，目前的 RL 算法不会考虑第一点。第二点很重要，因为当前的 RL 算法采用随机扰动参数或随机动作的探索策略是希望能够探索到环境内的新区域，这些区域可能会因为一些策略上的改变而使得智能体表现的非常差，如在进行进一步区域探索之前不能先返回到难以到达的场景中。这个问题会随着到达状态的必要动作序列更长、更复杂、要求更为精确变得越来越严重。Go-Explore 通过首先返回状态然后从那里开始探索来解决这个问题。这样做可以保证找到问题解决方案后的深入探索，然后在此基础上鲁棒化以产生更可靠的策略（原则3）。

从存档的轨迹中保存和探索的想法来自质量多样性（QD）算法类型（如 MAP-elites 和本地比赛的新颖搜索），Go-Explore 是基于 MAP-Elites 的增强 QD 算法。然而，之前的 QD 算法侧重于通过随机扰当前存档策略来探索行为空间，而不是通过重新探索来明确探索状态空间。从状态空间的确切位置开始，之前的探索就停止了。实际上，Go-Explore 提供了比其他 QD 方法更有控制的状态空间探索，确保探测范围通过状态空间累积，因为每个新的探索轨迹都离开了前一个探测轨迹的终点。

值得注意的是，当前版本的 Go-Explore 通过在探索时采取完全随机的行为（没有任何神经网络！）来工作，并且即使应用在状态空间的简单离散化上也很有效。尽管搜索如此简单，但它的成功有力地表明了记住和探索良好的轨迹是有效探索的关键，并且进行简单探索比深层RL方法更有助于寻找新状态并完成状态表示。如果将其与有效的，经过学习的表示相结合，并用更智能的探索策略取代当前的随机探索，Go-Explore 可以更加强大。这也是我们正在追求的两种途径。

Go-Explore 还演示了解决探索和处理环境随机性的问题是可以通过以下两个阶段分别完成的，即先在确定性环境中进行探索然后强化相关解决方案。依赖于访问确定性环境最初可能看起来像是 Go-Explore 的缺点。但是，Uber AI 认为确定性环境可用于许多流行的 RL 领域，包括计算机游戏，机器人模拟器，甚至学术世界模型。一旦找到一种或多种鲁棒性较弱的解决方案后，就可以在模拟中生成稳健的解决方案。如果最终目标是应用于现实中的策略（例如，机器人技术），则可以使用许多可用技术中的任何一种将强健策略从模拟器中转移到现实世界。此外，Uber AI 计划证明用目标条件策略替代加载确定性状态的可能性，该策略从一开始就学习处理随机环境。这样的算法仍然可以从 Go-Explore 的三个关键原则中受益。

有些人可能持反对意见，虽然这种方法已经在采集原始像素进行 Atari 的高维域中证明有效，但它无法扩展到真实的高维域，如现实世界的模拟器中。Uber AI 则相信这种方法在真实高维域也可以工作，但它必须将不同的有趣状态（例如，世界的学习，压缩表示）的更智能的单元格表示与智能探索策略（不是随机策略）相结合。有趣的是，状态合并的越多（将更多的状态映射到同一个单元格表示），就越需要进行智能探索以到达这些本质上不同的单元格。另外，从任意给定单元格中学习智能探索需要有效地重用探索必备技能（如游走）。

相关工作

Go-Explore 让人想起早期分离探索和开发的工作。然而，Go-Explore 进一步分解了探索的三个要素：积累基础步骤、返回有奖励的基础步骤，并从中寻找额外的基础步骤（即上面的原理＃1和＃2）。通过为每个元素插入非常简单的算法，Go-Explore 实现了令人印象深刻的结果，这显示了分解的价值。如上所述，与 QD 算法相比，所有当前 RL 算法的另一个不同之处在于 Go-Explore 不会通过扰乱新状态的策略来尝试探索新的高性能的状态，而是首先返回到一个确定的状态，然后从中探索。

Go-Explore 首先找到一个解决方案然后围绕它进行优化的思路在「引导策略搜索」（https://arxiv.org/pdf/1504.00702.pdf）中已有先例。然而，这种方法需要一种无欺骗性、非稀疏、可微分的损失函数来寻找解决方案，这意味着它不能直接应用于如 某些 Atari 游戏许多现实世界的问题一样，奖励是离散的、稀疏的、具有欺骗性的问题。此外，引导式策略搜索需要有可微分的全局模型或学习一组局部模型，这些局部模型易于处理，需要在训练期间观察系统的完整状态。

结论

总体而言，Go-Explore 是一个用于解决硬探索的强化学习问题（即具有稀疏和/或欺骗性奖励的问题）的令人兴奋的新算法类型。 它开辟了大量新的研究方向，包括测试不同的存档，选择返回单元格的不同方法，不同的单元格表示，不同的探索方法，以及不同的模拟方法，如不同的模仿学习算法。 Uber AI 也很高兴看到 Go-Explore 的优势与不足， 这像是一个探索可能性的新乐园，也希望更多研究人员能和他们一起进行该领域的研究。

Uber AI 正在撰写这篇论文，预计很快就会正式发表。介绍博客原地址为 https://eng.uber.com/go-explore/，文末也对博客发布后来自其它研究人员们的疑问给出了回应。感兴趣的读者可以继续关注。

雷锋网 AI 科技评论编译。

。