Go-Explore: a New Approach for Hard-Exploration Problems

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

449 citations recorded by the source corpus.

A grand challenge in reinforcement learning is intelligent exploration, especially when rewards are sparse or deceptive. Two Atari games serve as benchmarks for such hard-exploration domains: Montezuma's Revenge and Pitfall. On both games, current RL algorithms perform poorly, even those with intrinsic motivation, which is the dominant method to improve performance on hard-exploration domains. To address this shortfall, we introduce a new algorithm called Go-Explore. It exploits the following principles: (1) remember previously visited states, (2) first return to a promising state (without exploration), then explore from it, and (3) solve simulated environments through any available means (including by introducing determinism), then robustify via imitation learning. The combined effect of these principles is a dramatic performance improvement on hard-exploration problems. On Montezuma's Revenge, Go-Explore scores a mean of over 43k points, almost 4 times the previous state of the art. Go-Explore can also harness human-provided domain knowledge and, when augmented with it, scores a mean of over 650k points on Montezuma's Revenge. Its max performance of nearly 18 million surpasses the human world record, meeting even the strictest definition of "superhuman" performance. On Pitfall, Go-Explore with domain knowledge is the first algorithm to score above zero. Its mean score of almost 60k points exceeds expert human performance. Because Go-Explore produces high-performing demonstrations automatically and cheaply, it also outperforms imitation learning work where humans provide solution demonstrations. Go-Explore opens up many new research directions into improving it and weaving its insights into current RL algorithms. It may also enable progress on previously unsolvable hard-exploration problems in many domains, especially those that harness a simulator during training (e.g. robotics).

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Reinforcement Learning

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 Computer Vision and Pattern Recognition

In Reinforcement Learning

Citations in the corpus

WebShop: Towards Scalable Real-World Web Interaction with Grounded Language Agents (2022, background): “Ideas from query (re)formulation [22, 59, 37, 51] may help agents expand the range of search exploration, and improved action exploration [40, 12, 49] and memory [53, 13, 23] mechanisms could help agents make better decisions over the long horizon and large action space.”
Decision Transformer: Reinforcement Learning via Sequence Modeling (2021, methodology): “For instance, Decision Transformer can serve as a powerful “memorization engine” and in conjunction with powerful exploration algorithms like Go-Explore [28], has the potential to simultaneously model and generative a diverse set of behaviors.”
Unsupervised Learning of Object Keypoints for Perception and Control (2019, background): “Our learned action space is agnostic to the control algorithm and hence other exploration algorithms [24, 4, 26] can also benefit from using it.”
Interactive Fiction Games: A Colossal Adventure (2019, methodology): “lanning algorithms Monte-Carlo Tree Search [Coulom, 2007] as well as reinforcement learning approaches that rely on the ability to restore state such as Backplay [Resnick et al., 2018] and GoExplore [Ecoffet et al., 2019]. Jericho additionally provides the option to seed the game’s random number gen”
A survey and critique of multiagent deep reinforcement learning (2018, background): “This sparseness is already a challenge for RL [20, 330] where approaches such as count-based exploration/intrinsic motivation [193, 331, 332, 333, 334] and hierarchical learning [335, 336, 109] have been proposed”
Making Efficient Use of Demonstrations to Solve Hard Exploration Problems (2019, background): “First, the agent has a single learner process which samples from both demonstration and agent buffers in order to update its policy parameters, the pseudocode of the R2D3 learner can be found in Algorithm 1.”
MineDojo: Building Open-Ended Embodied Agents with Internet-Scale Knowledge (2022, methodology): “Prior methods in open-ended agent learning [30, 57, 130, 63, 26] do not make use of external knowledge, but our approach leverages internet-scale database to learn open-vocabulary reward models, thanks to Minecraft’s abundance of gameplay data online.”
First return, then explore (2020, methodology): “Policy-based Go-Explore vs. DTSIL After a pre-print paper describing Go-Explore 58 (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-Attentional Credit Assignment for Transfer in Reinforcement Learning (2019, unknown): “We think purely exploratory methods [Ecoffet et al. , 2019] could have advantages over using an RL agent and leave the study of their use for future work.”
On Bonus Based Exploration Methods In The Arcade Learning Environment (2020, background): “…or not) has aspired to improve performance on this particular game, ranging from a much deeper exploration (6600 points; Bellemare et al., 2016), to completing the ﬁrst level (14000 points; Pohlen et al., 2018; Burda et al., 2019), to super-human performance (400,000 points; Ecoffet et al., 2019).”
Dead-ends and Secure Exploration in Reinforcement Learning (2019, background): “This is a serious issue and it is often for this very reason that designers avoid using negative rewards in their implementations (see for example Ecoffet et al. (2019) for a discussion on the adverse effect of negative rewards).”
BeBold: Exploration Beyond the Boundary of Explored Regions (2020, methodology): “Count-based approaches favor novel states in the environment but suffer from detachment and derailment (Ecoffet et al., 2019), in which the agent gets trapped into one (long) corridor and fails to try other choices.”
Fiber: A Platform for Efficient Development and Distributed Training for Reinforcement Learning and Population-Based Methods (2020, methodology): “For example, Go-Explore (Ecoffet et al. 2019) requires only CPUs during its exploration phase, but relies on GPUs later in the robustiﬁcation phase.”
Voyager: An Open-Ended Embodied Agent with Large Language Models (2023, background): “[11] Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O.”
Hierarchical reinforcement learning for efficient exploration and transfer (2020, methodology): “The main difference is that our al-gorithm can learn near-optimal policies for transitioning between regions, while Go-Explore does not improve on the ﬁrst action sequence generated randomly.”