First return, then explore — part 1/5

Cleaned-text code points [0, 15553). Bibliography omitted here; source.md includes it.

\defbibcheck onlynew

# First return, then explore

###### Abstract

The promise of reinforcement learning is to solve complex sequential decision problems autonomously by specifying a high-level reward function only. However, reinforcement learning algorithms struggle when, as is often the case, simple and intuitive rewards provide sparse [ 121 ] and deceptive [ 122 ] feedback. Avoiding these pitfalls requires thoroughly exploring the environment, but despite substantial investments by the community, creating algorithms that can do so remains one of the central challenges of the field. We hypothesise that the main impediment to effective exploration originates from algorithms forgetting how to reach previously visited states (“detachment”) and from failing to first return to a state before exploring from it (“derailment”). We introduce Go-Explore, a family of algorithms that addresses these two challenges directly through the simple principles of explicitly remembering promising states and first returning to such states before intentionally exploring. Go-Explore solves all heretofore unsolved Atari games (meaning those for which algorithms could not previously outperform humans when evaluated following current community standards for Atari [ 123 ] ) and surpasses the state of the art on all hard-exploration games [ 121 ] , with orders of magnitude improvements on the grand challenges Montezuma’s Revenge and Pitfall . We also demonstrate the practical potential of Go-Explore on a challenging and extremely sparse-reward pick-and-place robotics task. Additionally, we show that adding a goal-conditioned policy can further improve Go-Explore’s exploration efficiency and enable it to handle stochasticity throughout training. The striking contrast between the substantial performance gains from Go-Explore and the simplicity of its mechanisms suggests that remembering promising states, returning to them, and exploring from them is a powerful and general approach to exploration, an insight that may prove critical to the creation of truly intelligent learning agents.

{affiliations}

Uber AI, San Francisco, CA, USA

OpenAI, San Francisco, CA, USA (work done at Uber AI)

∗ These authors contributed equally to this work

Authors’ note : This is the pre-print version of this work. You most likely want the updated, published version, which can be found as an unformatted PDF at https://adrien.ecoffet.com/files/go-explore-nature.pdf or as a formatted web-only document at https://tinyurl.com/Go-Explore-Nature .

Please cite as: Ecoffet, A., Huizinga, J., Lehman, J., Stanley, K.O. and Clune, J. First return, then explore. Nature 590, 580–586 (2021). https://doi.org/10.1038/s41586-020-03157-9

Recent years have yielded impressive achievements in Reinforcement Learning (RL), including world-champion level performance in Go [ 124 ] , Starcraft II [ 125 ] , and Dota II [ 126 ] , as well as autonomous learning of robotic skills such as running, jumping, and grasping [ 127 , 128 ] . Many of these successes were enabled by reward functions that are carefully designed to be highly informative. However, for many practical problems, defining a good reward function is non-trivial; to guide a household robot to a coffee machine, one might provide a reward only when the machine is successfully reached, but doing so makes the reward sparse , as it may require many correct actions for the coffee machine to be reached in the first place. One might instead attempt to define a denser reward, such as the Euclidean distance towards the machine, but such a reward function can be deceptive ; naively following the reward function may lead the robot into a dead end that does not lead to the machine. Furthermore, attempts to define a dense reward function are a common cause of reward hacking , in which the agent finds a way to maximise the reward function by producing wholly unintended (and potentially unsafe) behaviour [ 129 , 130 ] , such as knocking over furniture or driving through a wall to reach the machine.

These challenges motivate designing RL algorithms that better handle sparsity and deception. A key observation is that sufficient exploration of the state space enables discovering sparse rewards as well as avoiding deceptive local optima [ 131 , 132 ] . We argue that two major issues have hindered the ability of previous algorithms to explore: detachment , in which the algorithm loses track of interesting areas to explore from, and derailment , in which the exploratory mechanisms of the algorithm prevent it from returning to previously visited states, preventing exploration directly and/or forcing practitioners to make exploratory mechanisms so minimal that effective exploration does not occur (Supplementary Information). We present Go-Explore, a family of algorithms designed to explicitly avoid detachment and derailment. We demonstrate how the Go-Explore paradigm allows the creation of algorithms that thoroughly explore environments. Go-Explore solves all previously unsolved Atari games * * * Concurrent work [ 133 ] has similarly reached this milestone on all Atari games, but was evaluated under easier, mostly deterministic conditions that do not meet community-defined standards [ 123 ] for evaluation on Atari (Methods “ 0.1 State of the art on Atari ”). Also, even if these differences in evaluation are ignored, Go-Explore accomplished the same feat at effectively the same time, but via a totally different method, which is useful for the scientific community. Go-Explore additionally obtains higher scores on most of the games that we tested (Supplementary Information). , where solved is defined as surpassing human performance, which has been posited as a major milestone in previous work [ 134 , 135 , 133 ] . It also surpasses the state of the art on all hard-exploration Atari games (except in one case where the maximum score is reached by Go-Explore and previous algorithms). Additionally, we demonstrate that it can solve a practical simulated robotics problem with an extremely sparse reward. Finally, we show that its performance can be greatly increased by incorporating minimal domain knowledge and examine how harnessing a policy during exploration can improve exploration efficiency, highlighting the versatility of the Go-Explore family.

## The Go-Explore family of algorithms

To avoid detachment, Go-Explore builds an archive of the different states it has visited in the environment, thus ensuring that states cannot be forgotten. Starting from an archive containing the initial state, it builds this archive iteratively: first, it probabilistically selects a state to return to from the archive (Fig. 1 a), goes back (i.e. returns) to that state (the “go” step; Fig. 1 b), then explores from that state (the “explore” step; Fig. 1 c) and updates the archive with all novel states encountered (Fig. 1 e). Previous RL algorithms do not separate returning from exploring, and instead mix in exploration throughout an episode, usually by adding random actions a fraction of the time [ 134 , 136 ] or by sampling from a stochastic policy [ 137 , 138 ] . By first returning before exploring, Go-Explore avoids derailment by minimizing exploration in the return policy (thus minimizing failure to return) after which it can switch to a purely exploratory policy.

In practice, non-trivial environments have too many states to store explicitly. To resolve this issue, similar states are grouped into cells , and states are only considered novel if they are in a cell that does not yet exist in the archive (Fig. 1 d). To maximise performance, if a state maps to an already known cell, but is associated with a better trajectory (e.g. higher performing or shorter, see Methods), that state and its associated trajectory will replace the state and trajectory currently associated with that cell. This behaviour is reminiscent of the MAP-Elites algorithm [ 139 ] , and quality diversity algorithms more broadly [ 140 , 141 ] , although it is novel because it applies such ideas to reach new locations within a state space, instead of to discover new styles of behaviour as MAP-Elites typically does. Additionally, Go-Explore differs from MAP-Elites in that exploration is done by extending trajectories, rather than by modifying a policy and rerunning it.

While a policy can return the agent to a state (as we demonstrate at the end of this work), Go-Explore provides a unique opportunity to leverage the availability of simulators in RL tasks; due to the large number of training trials current RL algorithms require, as well as the safety concerns that arise when running RL directly in the real world, simulators have played a key role in training the most compelling applications of RL [ 142 , 128 , 143 , 144 ] , and will likely continue to be harnessed for the foreseeable future. The inner state of any simulator can be saved and restored at a later time, making it possible to instantly return to a previously seen state. However, returning without a policy also means that this exploration process, which we call the exploration phase , does not produce a policy robust to the inherent stochasticity of the real world. Instead, when returning without a policy, Go-Explore stores and maintains the highest-scoring trajectory (i.e. sequence of actions) to each cell. After the exploration phase is complete, these trajectories make it possible to train a robust and high-performing policy by Learning from Demonstrations (LfD) [ 145 ] , where the Go-Explore trajectories replace the usual human expert demonstrations. Because it produces robust policies from brittle trajectories, we call this process the robustification phase (Fig. 1 “Robustification Phase”).

## Learning to play Atari when returning without a policy

The Atari benchmark suite [ 146 ] , a prominent benchmark for RL algorithms [ 134 , 147 , 148 ] , contains a diverse set of games with varying levels of reward sparsity and deceptiveness, making it an excellent platform for demonstrating the effectiveness of Go-Explore. The following experiment highlights the benefit of a “go” step that restores the simulator state directly. In this experiment, the “explore” step happens through random actions. The state-to-cell mapping consists of a parameter-based downscaling of the current game frame, which results in similar-looking frames being aggregated into the same cell (Fig. 1 d). This mapping does not require any game-specific domain knowledge. Good state-to-cell-mapping parameters result in a representation that strikes a balance between two extremes: lack of aggregation (e.g. one cell for every frame, which is computationally inefficient) and excessive aggregation (e.g. assigning all frames to a single cell, which prevents exploration). To identify good downscaling parameters we define a downscaling objective function that estimates the quality of the balance achieved. Because appropriate downscaling parameters can vary across Atari games and even as exploration progresses within a given game, such parameters are optimised dynamically at regular intervals by maximising this objective function over a sample of recently discovered frames (Methods).

Here, the robustification phase consists of a modified version of the “backward algorithm” [ 149 ] , currently the highest performing LfD algorithm on Montezuma’s Revenge . Due to the large computational expense of the robustification process, the focus of this work is on eleven games that have been considered hard-exploration by the community [ 121 ] or for which the state-of-the-art performance was still below human performance (Methods “ 0.1 State of the art on Atari ”). To ensure that the trained policy becomes robust to environmental perturbations, during robustification stochasticity is added to these environments following current community standards for what constitutes the appropriately difficult version of this benchmark [ 123 ] . The rewards in these games differ by orders of magnitude and standard reward clipping overemphasises small rewards over bigger payoffs. However, the exploration phase provides extensive information about the rewards available in each game, making it possible to automatically scale rewards to an appropriate range (Methods).

At test time, the final mean performance of Go-Explore is both superhuman and surpasses the state of the art in all eleven games (except in Freeway where both Go-Explore and the state of the art reach the maximum score; Fig. 2(b) ). These games include the grand challenges of Montezuma’s Revenge , where Go-Explore quadruples the state-of-the-art score, and Pitfall , where Go-Explore surpasses average human performance while previous algorithms were unable to score any points † † † Recall that only results evaluated according to community-defined standards as to the appropriately challenging stochastic version of Atari are considered here, namely those with sticky actions [ 123 ] . Some algorithms have scored points on Pitfall without sticky actions, including recent concurrent work [ 133 , 150 ] . . Also noteworthy is the performance on Private Eye , where Go-Explore is able to reliably achieve the highest possible score in 4 out of 5 runs, and the performance on Skiing , where Go-Explore outperforms human performance despite the fact that the reward structure of this game makes it notoriously hard to train on [ 151 , 133 ] .

Interestingly, there are many cases where the robustified policies obtain higher scores than the trajectories discovered during the exploration phase. There are two reasons for this: first, while the exploration phase does optimise for score by updating trajectories to higher scoring ones, the robustification phase is more effective at fine-grained reward optimisation; second, we provide the backward algorithm with demonstrations from multiple (10) runs of the exploration phase, thus allowing it to follow the best trajectory in the sample while still benefiting from the data contained in worse trajectories.

The ability of the Go-Explore exploration phase to find high-performing trajectories is not limited to hard-exploration environments; it finds trajectories with superhuman scores for all of the 55 Atari games provided by OpenAI gym [ 152 ] , a feat that has not been performed before (save concurrent work published just prior to this work [ 133 ] ) and in 83.6% of these games the trajectories reach scores higher than those achieved by state-of-the-art algorithms (Fig. 3 ), suggesting its potential for automatically generating solution demonstrations in many other challenging domains. Modern RL algorithms are already able to adequately solve the games not included in the 11 focus games in this work, as demonstrated by previous work (Extended Data Table 3 ). Thus, because robustifying these already solved games would have been prohibitively expensive, we did not perform robustification experiments for these 44 games.

Go-Explore can also harness easy-to-provide domain knowledge to substantially boost performance. It can do so because the way Go-Explore explores a state space depends on the cell representation, meaning exploration efficiency can be improved by constructing a cell representation that only contains features relevant for exploration. We demonstrate this principle in the games of Montezuma’s Revenge and Pitfall, where the features are the agent’s room number and coordinates for both games, as well as the level number and keys for Montezuma’s Revenge.