First return, then explore

By Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O. Stanley, Jeff Clune. 2020

459 citations recorded by the source corpus.

Reinforcement learning promises 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 sparse1 and deceptive2 feedback. Avoiding these pitfalls requires a thorough exploration of the environment, but creating algorithms that can do so remains one of the central challenges of the field. Here we hypothesize that the main impediment to effective exploration originates from algorithms forgetting how to reach previously visited states (detachment) and 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 returning to such states before intentionally exploring. Go-Explore solves all previously unsolved Atari games and surpasses the state of the art on all hard-exploration games1, with orders-of-magnitude improvements on the grand challenges of Montezuma’s Revenge and Pitfall. We also demonstrate the practical potential of Go-Explore on a 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 substantial performance gains from Go-Explore suggest that the simple principles of remembering states, returning to them, and exploring from them are a powerful and general approach to exploration—an insight that may prove critical to the creation of truly intelligent learning agents. A reinforcement learning algorithm that explicitly remembers promising states and returns to them as a basis for further exploration solves all as-yet-unsolved Atari games and out-performs previous algorithms on Montezuma’s Revenge and Pitfall.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Hyperparameter Selection for Imitation Learning (2021, background): “Indeed, just as the reward-engineering problem leads to policies maximizing a reward in an unexpected way (Sims, 1994; Feldt, 1998; Ecoffet et al., 2021), selecting policies on the basis of an incautiously designed metric or of a biased human judgement can lead to biased policies (Henderson et al.,…”
A Brief Overview of ChatGPT: The History, Status Quo and Potential Future Development (2023, background): “, gaming [68]–[70], robotics control [71]–[73], molecular optimization [74], [75] and other fields [76], [77].”
Multi-Stage Episodic Control for Strategic Exploration in Text Games (2022, unknown): “Policy-based Go-Explore (Ecoffet et al., 2021) uses self-imitation learning to ‘exploit’ high-reward trajectories, but requires choosing intermediate sub-goals for the agent to condition its policy on.”
Semantic Exploration from Language Abstractions and Pretrained Representations (2022, background): “Others use novelty measures to identify interesting states from which they can perform additional learning [16, 54].”
BeBold: Exploration Beyond the Boundary of Explored Regions (2020, methodology): “Go-Explore tries to resolve this dilemma between “dedication” and “exploration” by using a two-stage approach with many hand-tuned parameters.”
Video PreTraining (VPT): Learning to Act by Watching Unlabeled Online Videos (2022, background): “10,11 13–19 Many virtual tasks, e.g. navigating websites, using Photoshop, booking ﬂights, etc., can be very hard to learn with RL and do not have large, commonly available sources of labeled data.”
Intrinsically Motivated Goal Exploration Processes with Automatic Curriculum Learning (2017, methodology): “The idea of this stepping-stone preserving operator is similar to the Go-Explore approach (Ecoﬀet et al., 2021).”
Prioritized Level Replay (2020, methodology): “Unlike singleton environments, like those in the Arcade Learning Environment benchmark (Bellemare et al., 2013), which are exploitable by memorization and deterministic reset strategies (Ecoffet et al., 2019; 2020), PCG environments create novel environment instances or levels algorithmically.”
The NetHack Learning Environment (2020, methodology): “It also disqualiﬁes current state-of-the-art exploration methods such as Go-Explore [22, 23] that are based on a goal-conditioned policy to navigate to previously visited states.”