\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.

The exploration phase with added domain knowledge explores both games extensively, discovering all 255 rooms of Pitfall and completely solving Montezuma’s Revenge by reaching the end of level 3. After robustification, the resulting policies achieve a mean score of 102,571 on Pitfall, close to the maximum achievable score of 112,000. On Montezuma’s Revenge, the mean score of the robustified policies is 1,731,645, exceeding the previous state of the art score by a factor of 150. This post-robustification score on Montezuma’s Revenge is not only much greater than average human performance, but in fact is greater than the human world record of 1.2 million [ 153 ] (Fig. 2(a) ). Notably, the performance on Montezuma’s Revenge is limited not by the quality of the learned agents, but by the default time limit of 400,000 frames that is imposed by OpenAI Gym, but is not inherent to the game. With this limit removed, robustified agents appear to be able to achieve arbitrarily high scores, with one agent frequently reaching a score of over 40 million after 12.5 million frames (the equivalent of about 58 hours of continuous game play).

Besides effectively representing all information relevant for exploration, the spatial cell representation enables improving cell selection during exploration, such as by considering whether neighbouring cells have been visited. Doing so greatly improves performance in Montezuma’s Revenge, though it has little effect on Pitfall.

## A hard-exploration robotics environment

While robotics is a promising application for reinforcement learning and it is often easy to define the goal of a robotics task at a high level (e.g. to put a cup in the cupboard), it is much more difficult to define an appropriate and sufficiently dense reward function (which would need to consider all of the low-level motor commands involved in opening the cupboard, moving toward the cup, grasping the cup, etc.). Go-Explore allows us to forgo such a dense reward function in favor of a sparse reward function that only considers the high-level task. In addition, robot policies are usually trained in simulation before being transferred to the real world [ 142 , 128 , 143 , 144 ] , making robotics a natural domain to demonstrate the usefulness of harnessing the ability of simulators to restore states in reinforcement learning.

Accordingly, the following experiment, performed in a simulated environment, demonstrates that Go-Explore can solve a practical hard-exploration task in which a robot arm needs to pick up an object and put it inside of one of four shelves (Fig. 4(a) ). Two of the shelves are behind latched doors, providing an additional challenge. A reward is given only when the object is put into a specified target shelf. Grasping an object and picking it up is itself a challenging problem in robotics, in part due to the challenge of exploration [ 154 , 155 ] . Roboticists are often forced to employ the imperfect workaround of simplifying exploration by restricting the robot’s range of motion substantially to favour arm positions that make grasping more likely [ 156 ] . In our setup, by contrast, all nine joints of the robot arm are independently controlled to the full extent permitted by the robot’s specifications. A state-of-the-art RL algorithm for continuous control (PPO [ 138 ] ) does not encounter a single reward after training in this environment for a billion frames, showcasing the hard-exploration nature of this problem. For this problem, Go-Explore returns by restoring simulator state, explores by taking random actions, and assigns states to cells with an easy-to-provide domain-knowledge-based mapping (Methods).

In the exploration phase, Go-Explore quickly and reliably discovers successful trajectories for putting the object in each of the four shelves (Fig. 4(b) ). In contrast, a count-based intrinsic motivation algorithm with the same domain knowledge representation as the exploration phase is incapable of discovering any reward (Fig. 4(c) ), and indeed discovers only a fraction of the cells discovered by the exploration phase after 1 billion frames of training, 50 times more than the exploration phase of Go-Explore (Fig. 4(b) ). In spite of receiving intrinsic rewards for touching the object, this control was incapable of learning to reliably grasp, thus making a large fraction of cells unreachable (including those necessary to obtain rewards). Evidence suggests that this failure to grasp is due to the problem of derailment , which Go-Explore is specifically designed to solve (Supplementary Information).

While only a single trajectory was extracted for robustification from each exploration-phase run of Go-Explore in the Atari experiments, the trajectories discovered in the robotics task are exceptionally diverse (e.g. some throw the object into the shelf while others gently deposit it), making it possible to provide additional information to the robustification phase by extracting multiple trajectories from each exploration-phase run. Robustifying these trajectories produces robust and reliable policies in 99 % 99\% of cases (Fig. 4(c) ).

## Policy-based Go-Explore

Leveraging the ability of simulators to restore states provides many benefits that increase the efficiency of Go-Explore, but it is not a requirement. When returning, instead of restoring simulator state, it is possible to execute a policy conditioned on (i.e. told to go to) the state or cell to return to, which we call policy-based Go-Explore . While returning to a state in this manner is less efficient than restoring simulator state (the actions required to return to a state need to be executed in the environment), there are nevertheless advantages to doing so. First, having access to a policy in the exploration phase makes it possible to sample from this policy during the explore step, which has the potential to substantially increase its efficiency vs. taking random actions thanks to the generalisation properties of the policy (e.g. the algorithm need only learn how to cross a specific obstacle once instead of solving that problem again via random actions each time). Second, training a policy in the exploration phase obviates the need for robustification and thus removes its associated additional complexity, hyperparameters, and overhead (see ‘Implementation Details’ in Methods). Finally, in a stochastic environment, it may not always be possible to reliably repeat certain lucky sequences of transitions that enabled visiting a state, even when taking optimal actions. While this issue did not prove to be a major roadblock in our experiments, in other domains it could prevent certain trajectories from being robustified. Exploring directly in the stochastic environment with the help of a policy makes it possible to detect these cases early and take appropriate measures to avoid them (Supplementary Information).

In policy-based Go-Explore, a goal-conditioned policy is trained during the exploration phase with a common reinforcement learning algorithm (PPO [ 138 ] ). Because goal-conditioned policies often struggle to reach far away states [ 157 ] , instead of training the policy to directly reach cells in the archive, the policy is trained to follow the best trajectory of cells that previously led to the selected state (Methods). In addition, because trajectories that successfully overcome difficult obstacles are initially rare (the network has to rely on sequences of random actions to initially pass those obstacles) policy-based Go-Explore also performs self-imitation learning to extract as much information from these successful trajectories as possible [ 158 ] . After our publication of an early pre-print presenting Go-Explore without a return policy, and while our work on policy-based Go-Explore was well underway, another team independently introduced a Go-Explore variant that is similarly policy-based [ 159 ] ; policy-based Go-Explore substantially outperforms this variant in terms of performance and sample efficiency (see Supplementary Information for a full comparison).

The goal-conditioned policy has the potential to greatly improve exploration effectiveness over random actions; in addition to returning to previously visited cells, the policy can also be queried during the explore step by presenting it with additional goals, including goals not already in the archive. Such goal cells are chosen according to a simple strategy that either chooses a cell adjacent to the current position of the agent, possibly leading to a new cell, or randomly selects a cell from the archive, potentially repositioning the agent within the archive or finding new cells while trying to do so (Methods). To examine whether this exploration strategy is indeed more effective than taking random actions, every time post-return exploration is started, the algorithm randomly commits with equal probability to either taking random actions or sampling from the policy for the duration of the post-return exploration step, thus ensuring that each strategy will be employed in similar scenarios equally often.

Policy-based Go-Explore was tested on Montezuma’s Revenge and Pitfall with the domain-knowledge cell representation. On these games, it beats the state of the art and human performance with a mean reward of 97,728 points on Montezuma’s Revenge and 20,093 points on Pitfall (Fig. 5 ), demonstrating that the performance of Go-Explore is not merely a result of its ability to leverage simulator restorability, but a function of its overall design. Furthermore, we found that sampling from the policy is more effective at discovering new cells than taking random actions, and becomes increasingly more effective across training as the policy gains new, generally useful skills, ultimately resulting in the discovery of over four times more cells than random actions on both Montezuma’s Revenge and Pitfall (Extended Data Fig. 7 ). Given that random actions form the basis of exploration for many RL algorithms, this result highlights the potential for improvement by moving towards goal-conditioned policy-based exploration.

## Conclusion

The effectiveness of Go-Explore on the problems presented in this work suggest that it will enable progress in many domains that can be framed as sequential decision making problems, including robotics [ 142 , 128 , 143 , 144 ] , neural architecture search [ 160 ] , language understanding [ 161 ] , scheduling [ 162 ] , marketing [ 163 ] , and drug design [ 164 ] . In addition, as a result of the modular nature of the Go-Explore family, the instantiations described in this work are only a fraction of the possible ways in which the Go-Explore paradigm can be implemented. Other instantiations may learn the cell representation, learn to choose which cells to return to, learn which cells to try to reach during the exploration step, learn a separate, specialised policy whose job is only to explore after returning, learn to explore safely in the real world by mining diverse catastrophes in simulation, maintain a continuous density-based archive rather than a discrete cell-based one, leverage all transitions gathered during exploration for robustification, and so on. These unexplored variants could further improve the generality, performance, robustness, and efficiency of Go-Explore. Finally, the insights presented in this work extend beyond Go-Explore; the simple decomposition of remembering previously found states, returning to them and then exploring from them appears to be especially powerful, suggesting it may be fundamental feature of learning in general. Harnessing these insights, either within or outside of the context of Go-Explore, may be a key to improving our ability to create generally intelligent agents.

## Supplementary Information

### 0.10 Detachment and derailment in reinforcement learning

Environment exploration has long been a central topic in the field of reinforcement learning [ 121 , 159 , 167 , 168 , 174 ] . Despite the extensive research on exploration in reinforcement learning, we hypothesise that many previous algorithms have been affected by two major issues which we call detachment and derailment .

We define detachment as losing track of interesting areas to explore from. Here, “interesting areas to explore from” refers to states for which we have evidence (e.g. a low number of visits) that they could lead to the discovery of new areas of the environment. “Losing track” means that the algorithm stops trying to visit those areas prematurely, despite the fact that they are not thoroughly explored yet. For reinforcement learning algorithms that only optimise the expected return, detachment is almost guaranteed, as these algorithms do not attempt to promote exploration explicitly. Unless external rewards are aligned with interesting areas to explore from, such algorithms will stop visiting under-explored areas in favour of areas with a high return. However, algorithms that reward the agent for exploring new states can still suffer from detachment. In intrinsic-motivation (IM) algorithms, for example, detachment can happen because the intrinsic reward is lowered each time a state is visited, so that, eventually, they in effect provide no incentive for an agent to return to them. This issue can be especially prominent when there are multiple frontiers, as the agent may now, due to stochastic exploration, stop visiting one of those frontiers long enough to forget how to return to it (Fig. 9 ). When this happens, the agent has to effectively relearn how to reach the frontier from scratch, but this time there is no intrinsic reward anymore to guide the agent. If intrinsic rewards were required to find the frontier in the first place, meaning that an algorithm without intrinsic rewards would fail to find this frontier, the IM algorithm will similarly fail to rediscover the frontier as well, meaning it has detached from the frontier. One might think that allowing intrinsic motivation to regrow after a time would solve the issue, but in that case the same dynamic can just play out over and over again endlessly.

We define derailment as when the exploratory mechanisms of the algorithm prevent it from returning to previously visited states. Returning to previously visited states is important because many RL environments, and especially hard-exploration environments, contain a large number of states that are far way from a starting state and can not be easily reached from such a starting state through random actions, even when exploring for hundreds of billions of frames. To discover these states, many algorithms rely on the policy learning to take actions that lead to states that are increasingly further away, either because the policy discovered external rewards leading towards these far away states, or because the algorithm provides intrinsic rewards that lead the policy towards infrequently visited states. However, as the policy needs to take an increasingly large number of correct actions to reach unexplored areas of the environment, it becomes increasingly likely that a state-agnostic exploration mechanism (i.e. any exploration mechanism that explores the same amount in all states, regardless of whether the agent is in a novel or a well-explored area), such as ϵ \epsilon -greedy exploration, will cause the policy to take one or more exploratory actions that prevent it from reaching the distant state it sought to return to, thus stifling exploration. Two common strategies to prevent derailment are to (1) set the exploration probability (e.g. ϵ \epsilon in ϵ \epsilon -greedy exploration) to be small or (2) to start with a high exploration probability, but reduce it over training iterations [ 136 ] . Working with a fixed, low exploration probability throughout training reduces the effect derailment throughout training, but it also means that very little exploration will happen once a new state is reached. Annealing exploration over training iterations will initially lead to a lot of exploration at the cost of heavy derailment. Unfortunately, if there exists a far away state that requires precise actions to reach, that state will not be reached until the exploration probability has been reduced sufficiently to avoid derailment. This low exploration probability means that, once the agent is finally able reliably reach this far away state, very little exploration will be performed after reaching it.

The solution we propose to avoid derailment is to have an algorithm exhibit separate exploration probabilities depending on whether it is in a well-known area of the environment, meaning the probability of exploratory actions should be low, or in an unknown area of the environment, meaning the probabilities of exploratory actions should be high. While doing so is not a feature of state-agnostic exploratory mechanisms like ϵ \epsilon -greedy exploration, one could hope that it is a property of algorithms that explore by sampling from a stochastic policy, because stochastic policies could learn to be low entropy in familiar states (i.e. they are certain about the correct action) while remaining high entropy in new states (i.e. where they should be uncertain about the correct action). However, deep learning struggles to remain well-calibrated when provided out-of-distribution input data. In image classification, for example, when networks classify images far out of distribution, it would be helpful if these networks returned a uniform distribution of probability across classes to properly indicate uncertainty, but networks instead are often surprisingly overconfident [ 176 , 177 ] . In the context of RL, this result means that we can expect trained policies to be highly confident in their actions (i.e. low entropy), even in areas that they have never observed before, thus resulting in a lack of exploration. To remedy this issue, stochastic-policy RL algorithms generally add an entropy bonus to the loss function, encouraging the policy to assign more equal probability to all actions. However, because this entropy bonus applies equally throughout the trajectory of a policy, it is difficult to tune the entropy bonus in a way that guarantees effective exploration without sacrificing the network’s ability to return; if the entropy bonus is too high, the policy will frequently take exploratory actions that prevent it from returning, thus causing derailment, but if the entropy bonus is too small, the policy will not explore sufficiently when a new area is reached.

### 0.11 Derailment in robotics

As shown in the main text of this paper, a count-based intrinsic motivation control completely fails to discover any rewards in the robotics environment even though it is given the same domain knowledge state representation as Go-Explore’s exploration phase and when given a comparable budget of frames to Go-Explore’s exploration and robustification phases combined. Evidence from the experiments suggests that this failure is primarily due to the problem of derailment , specifically to the difficulty that the IM control has of learning to reliably grasp the object.

Grasping is widely considered an extremely difficult task to learn in robotics [ 154 , 155 ] . The overwhelming majority of undiscovered cells are those require grasping the object and lifting it to reach. The claim that the failure to explore the environment is due to derailment when grasping the object necessitates that grasping is discovered , but cannot be reliably reproduced by the policy due to its excessive exploratory mechanisms. We separate the discovery of grasping into three steps: touching the object with one of the two grippers (the “touch” step), touching that surrounds the object with both grippers (the “grasp” step), and finally lifting the object (the “lift” step). An analysis of the cells and counts discovered by 20 control runs (5 per target shelf) shows that all runs discover the “touch” and “grasp” step, but in 18 (90%) of these runs, the count associated with the “grasp” step is at least 10x smaller than that associated with the “touch” step, indicating difficulty (and thus possible derailment) in learning to go from the “touch” step to the “grasp” step. In the 2 (10%) remaining runs, the “grasp” step count is closer to the “touch” step count, but, in one case, lifting is never discovered, and in the other, lifting is discovered, but the count for the “lift” step is again over 10x smaller than that of the “grasp” step, indicating possible derailment in between those two steps. It is thus apparent that the IM control has difficulty returning to the grasping stepping stones that it discovers, in spite of these cells often having amongst the lowest counts of any cell discovered, and thus the highest intrinsic rewards, thereby providing evidence of derailment.

### 0.12 Policy-based Go-Explore and Stochastic Environments

Restoring simulator state is a highly efficient method for returning to previously visited states, as it both removes the need to replay the trajectory towards a previously visited state as well as the need to train a policy capable of doing so reliably. That said, doing so also has the potential drawback that some of the trajectories found by restoring simulator state can be hard to robustify if that trajectory is not representative of realistic policies that can succeed in the stochastic testing environment. For example, imagine a robot with the goal of crossing a busy highway. The cars on the highway are stochastic, meaning that their position, speed, and reactions will differ in every episode, but the highway is always busy. As such, we assume that there is no safe way to reliably cross the busy highway directly. The highway has an overpass that allows the robot to easily and reliably cross the highway safely, but it is located some distance away from the robot, meaning that it is not the shortest method to cross the highway. However, when restoring simulator state, it is likely that Go-Explore will find a way directly across the highway in this particular scenario, because there probably exists some static sequence of lucky actions that brings the agent from one cell on the highway to the next cell, and once the next cell is reached, that progress is saved in the form of the simulator state. Once the opposite side of the highway is reached, this shorter trajectory will overwrite any longer trajectories that go over the overpass, and the final trajectory returned will go directly over the highway. Training a policy that can reliably follow this trajectory may be impossible because the inherent stochasticity of the cars on the highway (i.e. the inherent stochasticity of the environment) can make it such that a sufficiently reliable policy simply does not exist. That is, each new random busy highway situation requires its own lucky set of actions that may not derive in any systematic way from the agent’s observations.

Policy-based Go-Explore can alleviate this situations in two ways. First, because its progress along the highway is not saved and because each trial is in a stochastic environment, policy-based Go-Explore must attempt to return manually to each cell across the highway in different conditions. If there does not exist a reliable policy that can do so, it is unlikely that policy-based Go-Explore will ever cross the highway this way. As a result, policy-based Go-Explore is much more likely to learn a policy that reliably navigates the overpass instead.

Second, because policy-based Go-Explore needs to return to cells in the presence of stochasticity, it can keep track of the success rate towards each cell in the archive. As such, even if policy-based Go-Explore is sometimes able to cross the highway, it is possible to not overwrite cells on the other side of the highway until the policy has learned to return to those cells reliably. Doing so prevents the shorter, but unreliable trajectories from overwriting the longer but more reliable trajectories that take the safe overpass. A similar mechanic could be implemented to deal with stochasticity in rewards, as policy-based Go-Explore makes it possible to track the average reward when attempting to reach a particular state. Because it was not necessary to implement such mechanics for the games of Montezuma’s Revenge and Pitfall, studying the effectiveness and exact implementation details of such a mechanic is a topic for future research.

Last, it may be possible to resolve these issues even when Go-Explore is allowed to restore simulator state. For example, it is possible to run the Go-Explore exploration phase many times with different random seeds, thus making it possible to estimate which trajectories are and which trajectories are not reliable. Recognising that trajectories with only slight differences in the states visited still represent effectively the same solution could be handled by the aggregation that occurs in the cell representation, meaning that solutions that visit the same cells in order (instead of the same states in order) could be considered the same. It thus seems possible to produce a version of Go-Explore that is able to estimate the reliability of different trajectories while still gaining the advantages of restoring simulator state. Identifying the exact form of that algorithm and experimentally validating it is a fruitful area of future research.

### 0.13 Policy-based Go-Explore vs. DTSIL

After a pre-print paper describing Go-Explore [ 178 ] (but not policy-based Go-Explore) was published, and after our work on policy-based Go-Explore was long underway, another research team independently developed and published the Diverse Trajectory-conditioned Self-Imitation Learning algorithm (DTSIL) [ 159 ] , which is similar to policy-based Go-Explore in many ways, as detailed below. Policy-based Go-Explore outperforms DTSIL on both Montezuma’s Revenge and Pitfall after 3.2 billion frames, despite the fact that policy-based Go-Explore was tested on a harder problem, i.e. with sticky actions (Fig. 1 ). In addition, the score of policy-based Go-Explore keeps increasing, eventually achieving a score of 97,728 on Montezuma’s Revenge and 20,093 on Pitfall after 12 billion and 10 billion frames, respectively. It is possible that the performance of DTSIL would also improve with additional frames, but those results were not reported.

DTSIL is similar to policy-based Go-Explore in that it follows the methodology described in the Go-Explore pre-print in the following ways: (1) Like the original Go-Explore, DTSIL explicitly keeps track of an archive of many different states and trajectories to those states, (2) DTSIL first moves the agent to one of these states before performing random exploration, (3) DTSIL determines whether to add a state to the archive with the help of a domain-knowledge based state embedding, where similar embeddings are grouped into a single cluster (i.e. a cell representation), and (4) DTSIL selects trajectories to follow (i.e. states to return to) by selecting them probabilistically based on the number of times particular clusters have been visited, though DTSIL did not consider any domain knowledge specific information for the purpose of this selection procedure.

Similar to policy-based Go-Explore, and as was recommended as a profitable future direction in our pre-print [ 178 ] , DTSIL is a method that returns to previously visited cells with the help of a goal-conditioned policy (referred to as a trajectory-conditioned policy in the DTSIL paper because the policy is provided with a sequence of the next few goals, as explained below). Also similar to policy-based Go-Explore, DTSIL follows a trajectory of intermediate sub-goals towards a particular goal cell, rather than conditioning the policy directly on the state to return to, and DTSIL includes self-imitation learning to make training the policy more sample efficient. While working on policy-based Go-Explore, we independently invented the technique of following a trajectory of sub-goals and harnessing self-imitation learning.

One major difference between policy-based Go-Explore and DTSIL is that, when following a trajectory, DTSIL aims to provide the entire trajectory as input to the policy, rather than just the next cell in the trajectory. As a result, the DTSIL network architecture requires some method to deal with variable length trajectories (resolved with an attention layer), while the policy-based Go-Explore architecture only requires the next (sub) goal cell as an input. Note that, in the DTSIL paper, most trajectories that are followed were found to be too long to provide to the network in their entirety, meaning the trajectory is instead provided to the network in small chunks, resulting in a dynamic that is similar to providing only the next goal.

Another major difference is that policy-based Go-Explore also samples from the policy while exploring, rather than just relying on random actions. As mentioned before (Extended Data Fig. 7 ), sampling from the policy results in the discovery of many more cells, potentially explaining the large performance advantage Go-Explore exhibits vs. DTSIL.

A third major difference is the way in which DTSIL and policy-based Go-Explore transition from exploration to exploitation. DTSIL transitions from exploration to exploitation by either slowly annealing across training iterations from selecting promising cells for exploration to selecting the highest scoring cells, or by making such a transition abruptly once a particular score threshold is reached. Policy-based Go-Explore, on the other hand, only focuses on exploration during training. Interestingly, despite being asked to return to all cells, rather than spending a good number of training iterations on just the highest performing ones (which is what DTSIL does), we found that policy-based Go-Explore tends to be able to reliably return to the highest scoring cell in the archive at test time.

A fourth major difference is our introduction of increasing entropy when the agent takes too long to reach the next cell (see Methods). This entropy increases the exploration performed by policy-based Go-Explore only when necessary, thus largely avoiding the problem of derailment. Because derailment can severely lower performance, we expect that this innovation contributes substantially to the performance advantage of our implementation of policy-based Go-Explore relative to DTSIL.

A last major difference is with respect to the experiments that were performed. DTSIL was tested on Montezuma’s Revenge and Pitfall without sticky actions. In preliminary experiments with policy-based Go-Explore, we found that removing sticky actions greatly simplified the problem, and testing policy-based Go-Explore without sticky actions would have increased its performance. As a result, and as explained in methods, we did not include DTSIL in our comparison with the state of the art, but we did provide a comparison at the beginning of this section.

Besides these major differences, there are many smaller differences between the two algorithms, including differences in cell selection probabilities, SIL equations, reward clipping, maximum episode length, and hyperparameters. For a full overview of these differences, we recommend comparing the methods explained in this paper directly with the methods described in the DTSIL paper [ 159 ] .

Because the algorithm described in the DTSIL paper is similar to policy-based Go-Explore, in preliminary experiments, we tested whether some of the hyperparameters described in the DTSIL paper would improve the performance of policy-based Go-Explore. In these preliminary experiments, we found that the grid size of their cell representation (determining the granularity for the x and y coordinates of the agent) of 9x9 ∥ ∥ ∥ Note that, while an Atari frame is 160x210 pixels, the top 50 rows of pixels are unreachable in our test games and were ignored, meaning that a discretization of 18x18 pixels does result in a 9x9 grid. and their learning rate of 2.5 ⋅ 10 − 4 2.5\cdot 10^{-4} did indeed perform better than the hyperparameters we were testing at that time, and we adopted these hyperparameters from the DTSIL paper instead.

The training performance of DTSIL on Montezuma’s Revenge and Pitfall was reported by [ 159 ] ( [ 159 ] ) [ 159 ] for experiments that ran for 3.2 billion frames. However, the performance-over-time graph presented in the DTSIL paper is not directly comparable with the performance-over-time graph shown in this paper because they represent results for different selection strategies. For policy-based Go-Explore, we always report the average score achieved when returning to the highest scoring cell in the archive (obtained after training is completed by loading stored checkpoints and testing the policy 100 times). In contrast, the DTSIL graph shows a rolling average score during training, which means that its average includes returning to low-scoring cells as the algorithm attempts to explore the environment. That said, the final performance of DTSIL after 3.2 billion frames is measured over only the highest scoring trajectories, and can thus be reasonably compared with the testing performance of policy-based Go-Explore after that many frames. For Montezuma’s Revenge, we compare policy-based Go-Explore against the results that were reported in the supplementary information of the DTSIL paper for a version of DTSIL that implemented the same cell representation as the one used in the policy-based Go-Explore experiments (note, the Montezuma’s Revenge results reported in the main DTSIL paper were lower). For Pitfall, we compare against the only reported results, which were obtained with a slightly different cell representation than the one used by policy-based Go-Explore. Specifically, the DTSIL cell representation includes the cumulative positive reward achieved; the representations are otherwise the same.

### 0.14 No-ops and sticky actions

The Atari benchmark has been accepted as a common RL benchmark because of the large variety of independent environments it provides [ 146 ] . One downside of the games available in this benchmark is that they are inherently deterministic, making it possible to achieve high scores by simply memorizing state-action mappings or a fixed sequence of actions, rather than learning a policy able to generalize to the much larger number of states that are available in each game. As the community is interested in learning general policies rather than brittle solutions, many have suggested approaches to improve the benchmark, usually by adding some form of stochasticity to the game [ 123 ] .

One of the first of these approaches was to start each game with a random number (up to 30) of no-op (i.e. do nothing) actions [ 134 ] . Executing a random number of no-ops causes the game to start in a slightly different state each episode, as many game entities like enemies and items move in response to time. While no-ops add some stochasticity at the start of an episode, the game dynamics themselves are still deterministic, allowing for frame-perfect strategies that would be impossible for a human player to reproduce reliably. In addition, with only 30 different possible starting states, memorization is more difficult, but still possible.

Because of the downsides of no-ops, an alternative approach called sticky actions was recommended by the community [ 123 ] . Sticky actions mean that, at any time-step greater than 0, there exists a 25 % 25\% chance that the current action of the agent is ignored, and the previous action is executed instead. In a way, sticky actions simulate the fact that it is difficult for a human player to provide the desired input at the exact right frame; often a button is pressed a little bit too early, a little bit too late, or held down for a little too long. Given that Atari games have been designed for human play, this means that human competitive scores should be achievable despite the stochasticity introduced by sticky actions.

While sticky actions have been recommended by the community, no-ops are still widely employed in many recent papers [ 150 , 133 ] . As it is possible that no-ops add some challenges not encountered with just sticky actions, we ensure that Go-Explore is evaluated under conditions that are at least as difficult as those presented in recent papers by evaluating Go-Explore with both sticky actions and no-ops. All Go-Explore scores in this paper come from evaluations with both of these forms of stochasticity combined.

### 0.15 PPO and SIL

Both the robustification “backward” algorithm and the implementation of policy-based Go-Explore are based on the actor-critic-style PPO algorithm from [ 138 ] ( [ 138 ] ) [ 138 ] , wherein N N parallel actors collect data in mini-batches of T T timesteps, and policy updates are performed after each batch. In all PPO-based algorithms presented here, the loss of the policy and value function (both parameterized by θ \theta ) is defined as ℒ ⁡ ( θ ) = ℒ P ​ G ​ ( θ ) + w V ​ F ​ ℒ V ​ F ​ ( θ ) + w E ​ N ​ T ​ ℒ E ​ N ​ T ​ ( θ ) + w L ​ 2 ​ ℒ L ​ 2 + w S ​ I ​ L ​ ℒ S ​ I ​ L ​ ( θ ) \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) (7) ℒ P ​ G ​ ( θ ) \mathcal{L}^{PG}(\theta) is the policy gradient loss with PPO clipping, defined as ℒ P ​ G ​ ( θ ) = 𝔼 s , a ∼ π θ ​ [ max ⁡ ( − A t ​ r t π ​ ( θ ) , − A t ​ clip ​ ( r t π ​ ( θ ) , 1 − ϵ , 1 + ϵ ) ) ] \mathcal{L}^{PG}(\theta)=\mathbb{E}_{s,a\sim\pi_{\theta}}[\mathrm{max}(-A_{t}r^{\pi}_{t}(\theta),-A_{t}\mathrm{clip}(r^{\pi}_{t}(\theta),1-\epsilon,1+\epsilon))] (8) r t π ​ ( θ ) = π θ ​ ( a t | s t ) π θ o ​ l ​ d ​ ( a t | s t ) r^{\pi}_{t}(\theta)=\frac{\pi_{\theta}(a_{t}|s_{t})}{\pi_{\theta_{old}}(a_{t}|s_{t})} (9) where s s izs a state, a a is an action sampled from the policy π θ \pi_{\theta} , r t r_{t} is the reward obtained at time-step t t , and ϵ \epsilon is a hyperparameter limiting how much the policy can be changed at each epoch. A t A_{t} is a truncated version of the generalised advantage estimation: A ^ t = δ t + ( γ ​ λ ) ​ δ t + 1 + … + ( γ ​ λ ) T − t + 1 ​ δ T − 1 \hat{A}_{t}=\delta_{t}+(\gamma\lambda)\delta_{t+1}+...+(\gamma\lambda)^{T-t+1}\delta_{T-1} (10) δ t = r t + γ ​ V θ ​ ( s t + 1 ) − V θ ​ ( s t ) \delta_{t}=r_{t}+\gamma V_{\theta}(s_{t+1})-V_{\theta}(s_{t}) (11) where γ \gamma is the discount factor, λ \lambda interpolates between a 1-step return and a T T -step return, V θ V_{\theta} is the value function parameterised by θ \theta , and s t s_{t} and r t r_{t} are the state and reward at time step t t , respectively. Similar to the policy gradient loss, the value function loss ℒ V ​ F ​ ( θ ) \mathcal{L}^{VF}(\theta) implemented here also includes PPO-based clipping, and is defined as ℒ V ​ F ​ ( θ ) = 𝔼 s , a ∼ π θ ​ [ max ⁡ ( ( V θ ​ ( s t ) − R ^ t ) 2 , ( clip ⁡ ( V θ ​ ( s t ) − V θ o ​ l ​ d ​ ( s t ) , − ϵ , ϵ ) − A ^ t ) 2 ) ] \mathcal{L}^{VF}(\theta)=\mathbb{E}_{s,a\sim\pi_{\theta}}[\mathrm{max}((V_{\theta}(s_{t})-\hat{R}_{t})^{2},(\mathrm{clip}(V_{\theta}(s_{t})-V_{\theta_{old}}(s_{t}),-\epsilon,\epsilon)-\hat{A}_{t})^{2})] (12) R ^ t = V θ o ​ l ​ d ​ ( s t , g t ) + A ^ t \hat{R}_{t}=V_{\theta_{old}}(s_{t},g_{t})+\hat{A}_{t} (13) The algorithms further include entropy regularization [ 179 ] ℒ E ​ N ​ T ​ ( θ ) \mathcal{L}^{ENT}(\theta) and an L2 regularization penalty ℒ L ​ 2 ​ ( θ ) \mathcal{L}^{L2}(\theta) .

Finally, both the robustification algorithm and policy-based Go-Explore include a self-imitation learning (SIL) loss [ 158 ] , ℒ S ​ I ​ L ​ ( θ ) \mathcal{L}^{SIL}(\theta) , which is calculated over previously collected data 𝒟 \mathcal{D} . While the source of 𝒟 \mathcal{D} differs between the robustification algorithm and policy-based Go-Explore (see their sub-sections for details), in both cases 𝒟 \mathcal{D} comes from previously collected trajectories τ \tau and consists of tuples ( s , a , R ) (s,a,R) , where s s is a state encountered in one of these rollouts, a a is the action that was taken in that state, and R R is the discounted reward that was collected from that state. With SIL, a small number ( N S ​ I ​ L N_{SIL} ) of PPO’s actors are assigned to be SIL actors. Each of these SIL actors, instead of taking actions in the environment, replays one of these trajectories τ \tau , and at each iteration the data collected by these SIL actors, forms the data set 𝒟 \mathcal{D} . The ℒ S ​ I ​ L ​ ( θ ) \mathcal{L}^{SIL}(\theta) loss is then calculated as ℒ S ​ I ​ L ​ ( θ ) = ℒ S ​ I ​ L ​ _ ​ P ​ G ​ ( θ ) + w S ​ I ​ L ​ _ ​ V ​ F ​ ℒ S ​ I ​ L ​ _ ​ V ​ F ​ ( θ ) + w S ​ I ​ L ​ _ ​ E ​ N ​ T ​ ℒ S ​ I ​ L ​ _ ​ E ​ N ​ T ​ ( θ ) \mathcal{L}^{SIL}(\theta)=\mathcal{L}^{SIL\_PG}(\theta)+w_{SIL\_VF}\mathcal{L}^{SIL\_VF}(\theta)+w_{SIL\_ENT}\mathcal{L}^{SIL\_ENT}(\theta) (14) ℒ S ​ I ​ L ​ _ ​ P ​ G ( θ ) = 𝔼 s , a , R ∈ 𝒟 [ − log π θ ( a | s ) ⋅ max ( 0 , R − V θ o ​ l ​ d ( s ) ) ] \mathcal{L}^{SIL\_PG}(\theta)=\mathbb{E}_{s,a,R\in\mathcal{D}}[-\mathrm{log}\pi_{\theta}(a|s)\cdot\mathrm{max}(0,R-V_{\theta_{old}}(s))] (15) ℒ S ​ I ​ L ​ _ ​ V ​ F ​ ( θ ) = 𝔼 s , a , r ∈ 𝒟 ​ [ 1 2 ​ max ​ ( 0 , R − V θ ​ ( s ) ) 2 ] \mathcal{L}^{SIL\_VF}(\theta)=\mathbb{E}_{s,a,r\in\mathcal{D}}\left[\frac{1}{2}\mathrm{max}(0,R-V_{\theta}(s))^{2}\right] (16)

Here, ℒ S ​ I ​ L ​ _ ​ E ​ N ​ T ​ ( θ ) \mathcal{L}^{SIL\_ENT}(\theta) is the entropy regularization term [ 179 ] calculated by evaluating the current policy over 𝒟 \mathcal{D} .

All architectures that feature recurrent units are updated with a variant of the truncated back-propagation-through-time algorithm called BPTT ( h ; h ′ ) (h;h^{\prime}) [ 180 ] , which is suitable when data is gathered in mini-batches. In BPTT ( h ; h ′ ) (h;h^{\prime}) , the network is updated every h ′ h^{\prime} timesteps (here h ′ = T h^{\prime}=T , the number of timesteps in the mini-batch), but it is unfolded for h ≥ h ′ h\geq h^{\prime} timesteps (here h = 1.5 ​ T h=1.5T ), meaning that gradients can flow beyond the boundaries of the mini-batch. To facilitate BPTT ( h ; h ′ ) (h;h^{\prime}) , the first mini-batch of each run consists of 1.5 ​ T 1.5T timesteps.

### 0.16 The backward algorithm

The “backward algorithm” [ 149 ] operates by placing the agent close to the end of the trajectory and running PPO until the performance of the agent matches or exceeds that of the demonstration. Once that is achieved, the agent’s starting point is moved closer to the trajectory’s beginning and the process is repeated. The algorithm thus learns the demonstration in a backward order.

The original version of the backward algorithm relied on a single demonstration due to the assumption that obtaining human demonstrations was expensive. In our case, however, obtaining multiple demonstrations is easy and cheap by simply re-running the exploration phase, which is why we modified the algorithm to utilise multiple demonstrations: at the start of each episode, a demonstration is chosen at random to provide the starting point for the agent. For Atari, 10 demonstrations from different runs of the exploration phase were used for each robustification. In Atari, the demonstration was extracted by finding all trajectories that reached an end-of-episode state (to prevent selection of length 0 trajectories in games with exclusively negative rewards, see Methods “ 0.5 Evaluation ”), and extracting the shortest one among those with the highest score. For robotics, because it was possible to extract diverse demonstrations from a single run of the exploration phase (this was not possible in Atari because high-scoring trajectories within a given Atari run tended to share most of their actions), 10 demonstrations from the same runs were used for robustification. In robotics, the first demonstration corresponds to the shortest successful trajectory (i.e. the shortest trajectory that puts the object in the shelf), while each subsequent demonstration corresponds to the successful trajectory with the highest mean difference from all previously selected trajectories, where the difference between two trajectories is given by ∑ i = 1 L I ⁡ ( τ i a ≠ τ i b ) L \frac{\sum_{i=1}^{L}I(\tau^{a}_{i}\neq\tau^{b}_{i})}{L} ( τ a \tau^{a} and τ b \tau^{b} are the list of actions being compared, L = min ⁡ ( | τ a | , | τ b | ) L=\min(|\tau^{a}|,|\tau^{b}|) , I I is the indicator function). Because actions are continuous, meaning that it is exceedingly unlikely for two independently sampled actions to be the same, τ i a = τ i b \tau^{a}_{i}=\tau^{b}_{i} only for parts where the trajectories are identical because they were branched from the same intermediate trajectory. As such, this metric effectively measures to what degree the two trajectories have a shared history, and prefers trajectories that share as little history as possible. In both cases, SIL was also performed on the set of demonstrations provided to the backward algorithm (see “PPO and SIL” section). Each robustification run used demonstrations from different, non-overlapping exploration phase runs (10 exploration runs for Atari, 1 for robotics).

On Atari, the score that can be obtained by starting the algorithm from the start of the environment is tracked throughout the run by adding a virtual demonstration of length 0, i.e. traditional training that executes the current policy from the domain’s traditional starting state. This addition makes it possible to occasionally obtain superhuman policies even when the backward algorithm has not yet reached the starting point of any of the non-virtual demonstrations it was provided. During training, the time limit of an episode is the remaining length of the demonstration (which is generally much shorter than the environment time limit, especially at the beginning of training since we start at the end of demonstrations and move backwards) plus a few extra frames (Extended Data Table 8(a) ). When the virtual demonstration is selected, however, the time limit is that of the underlying environment (Extended Data Table 8(b) ). As a result, training episodes in which the virtual demonstration was selected often require many more frames to complete than those corresponding to an exploration phase demonstration. To balance the number of frames allocated to the virtual demonstration, the average number of steps in an episode corresponding to the virtual demonstration ( l v l_{v} ) is tracked as well as the average number of steps corresponding to starting from any other demonstration ( l d l_{d} ), and the selection probability of the virtual demonstration is then 1 11 ​ l d l v \frac{1}{11}\frac{l_{d}}{l_{v}} , where 11 is the total number of demonstrations (10 from the exploration phase runs and 1 virtual demonstration). In cases where the virtual demonstration was not stochastically chosen, one of the exploration phase demonstrations was chosen uniformly at random.

A key difficulty in implementing an RL algorithm that can perform well across all Atari games with identical hyperparameters is the significant variations in reward scales within the Atari benchmarks, with some games having an average reward of 1 and others with average rewards of over 1,000. Traditionally, this challenge has been addressed with reward clipping , in which all rewards are clipped to either -1 or +1, but such an approach is problematic in games (e.g. Pitfall and Skiing) in which the scale of rewards within the game is relevant because it tells the agent the relative importance of different rewarded (or punished) actions. In this work, we take advantage of the fact that the deterministic exploration phase is unaffected by reward scale and can provide us with a sense of the scale of scores achievable in each game. We are thus able to use reward scaling in the robustification phase: at the start of the robustification phase, the rewards of the demonstrations are used to produce a reward multiplier that will result every game having approximately the same value function scale. This reward multiplier is given by m = C μ V m=\frac{C}{\mu_{V}} (17) where C C is a constant representing the target average absolute value of the value function when following the demonstration (in all our experiments, C = 10 C=10 ), and μ V \mu_{V} is defined as μ V = 1 ∑ d = 1 D T d ​ ∑ d = 1 D ∑ t = 1 T d | V d ​ ( t ) | \mu_{V}=\frac{1}{\sum_{d=1}^{D}T_{d}}\sum_{d=1}^{D}\sum_{t=1}^{T_{d}}|V_{d}(t)| (18) where D D is the number of demonstrations, T d T_{d} is the number of steps in each demonstration, and V d ​ ( t ) V_{d}(t) is the sum of discounted rewards in demonstration d d starting from step t t .

### 0.17 Go-Explore vs. Agent57

The creation of the Atari benchmark started the search for reinforcement learning algorithms capable of achieving super-human performance on all games in this benchmark [ 146 ] . For a majority of these games, super-human performance was reached quickly through early deep reinforcement learning techniques now considered standard [ 134 ] , but for a small set of games super-human performance remained out of reach. The work presented in this paper achieved this historic feat concurrently with an algorithm called Agent57 [ 133 ] . Go-Explore and Agent57 accomplish this milestone via very different methods, offering the scientific community a diversity of promising tools to use and build upon going forward.

Agent57 is built upon the Never Give Up (NGU) algorithm [ 150 ] . NGU was able to achieve superhuman performance on the majority of the Atari games by combining within-episode and across-episode intrinsic motivation, tracking many Q-functions that each maintain a different trade-off between intrinsic and extrinsic motivation, and implementing efficient parallelization of data collection. Agent57 elevated the performance of NGU to superhuman on all games by dynamically learning which of its many Q-functions provides the highest cumulative reward, stabilizing the learning of those Q-functions, and by running the algorithm for an impressive 100 billion frames. So, while Agent57 achieved the milestone of superhuman performance on the last few remaining games at the same time as Go-Explore, its method is vastly different from Go-Explore.

With respect to results, it is first of all important to reiterate that Go-Explore was evaluated in an environment with sticky actions (i.e. following community standards, see SI “No-ops and sticky actions”) while Agent57 was evaluated in an environment without sticky actions. Sticky actions make the games substantially harder to play well, which is why Agent57 was not considered for direct comparison with Go-Explore in the main paper (see Methods “State of the art on Atari”).

Despite the fact that Go-Explore solutions were evaluated under more difficult conditions, Go-Explore still outperforms Agent57 on 7 out of the 11 games that we tested (Table 1 ). It is also worth noting that the Go-Explore results reported here were obtained after a total of 30 billion (or 40 billion for Solaris) frames of training data, while Agent57 was trained for 100 billion frames. While Go-Explore does “skip” frames by reloading simulator state, we argue that these frames would also be skipped in almost any scenario where Go-Explore is practically applied, as it should be possible to save and restore the state of a modern simulator. That said, the relative sample efficiency of policy-based Go-Explore (e.g. 97,728 points on Montezuma’s Revenge after 12 billion frames) suggests that policy-based Go-Explore could be more sample efficient than Agent57 even if states can not be restored, though the fact that policy-based Go-Explore was only tested with domain knowledge makes it impossible to provide a fair comparison at this time.

### 0.18 ALE issues

While the Arcade Learning Environment (ALE) [ 146 ] , which is the underlying backend of OpenAI Gym, is the the standard way to interface with Atari games in RL, the library comes with a couple issues that needed to be addressed in our work.

First, the score on Montezuma’s Revenge rolls over (i.e. is subject to numerical overflow) when it exceeds 1 million, which is incorrectly interpreted by the ALE as a negative reward of -1 million. We patched the environment to remove this bug and thereby make it possible for algorithms to learn to produce scores higher than 1 million. This enabled us to learn that Go-Explore can substantially outperform the human world record of 1.2 million [ 153 ] . No previous work had achieved scores anywhere near high enough to trigger this particular bug on Montezuma’s Revenge.

Second, the implementation of Montezuma’s Revenge in the ALE library includes a bug that prevents the agent from progressing to the next level when the agent is on its last life, which is clearly unintended behaviour that does not occur in the original game. Because there are no penalties for losing a life, policy-based Go-Explore learns to sacrifice lives in order to bypass hazards or to return to the entrance of a room more quickly. As a result, policy-based Go-Explore frequently reaches the treasure room without any lives remaining, preventing further progress. As such, for policy-based Go-Explore only, we terminate the episode on first death, which avoids this bug without simplifying the game.

### 0.19 Infrastructure

In terms of infrastructure, each exploration phase run was performed on a single worker machine equipped with 44 CPUs and 96GB of RAM, though memory usage is substantially lower for most games. Each robustification run was parallelized across 8 worker machines each equipped with 11 CPUs, 24GB of RAM, and 1 GPU. Policy-based Go-Explore was parallelized across 16 worker machines each equipped with 11 CPUs, 10GB of RAM, and 1 GPU.