First return, then explore — part 2/5

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

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.