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

Abstract

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

arXiv comment37 pages, 14 figures; added references to Goyal et al. and Oh et al., updated reference to Colas et al; updated author emails; point readers to updated paper

References in corpus (37)

• Continuous control with deep reinforcement learning
• Overcoming catastrophic forgetting in neural networks
• Prioritized Experience Replay
• Dueling Network Architectures for Deep Reinforcement Learning
• Evolution Strategies as a Scalable Alternative to Reinforcement Learning
• Robots that can adapt like animals
• Roulette-wheel selection via stochastic acceptance
• IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures
• Deep Neuroevolution: Genetic Algorithms Are a Competitive Alternative for Training Deep Neural Networks for Reinforcement Learning
• Distributed Prioritized Experience Replay
• Rainbow: Combining Improvements in Deep Reinforcement Learning
• Illuminating search spaces by mapping elites
• Massively Parallel Methods for Deep Reinforcement Learning
• Parameter Space Noise for Exploration
• Count-Based Exploration with Neural Density Models
• #Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning
• Deep Q-learning from Demonstrations
• Incentivizing Exploration In Reinforcement Learning With Deep Predictive Models
• Learning Dexterous In-Hand Manipulation
• Exploration by Random Network Distillation
• Uncertainty-Aware Reinforcement Learning for Collision Avoidance
• A Deeper Look at Experience Replay
• Intrinsically Motivated Goal Exploration Processes with Automatic Curriculum Learning
• The Predictron: End-To-End Learning and Planning
• Self-Imitation Learning
• Surprise-Based Intrinsic Motivation for Deep Reinforcement Learning
• Observe and Look Further: Achieving Consistent Performance on Atari
• Learning Montezuma's Revenge from a Single Demonstration
• Contingency-Aware Exploration in Reinforcement Learning
• Combating Reinforcement Learning's Sisyphean Curse with Intrinsic Fear
• Diffusion-based neuromodulation can eliminate catastrophic forgetting in simple neural networks
• Backplay: "Man muss immer umkehren"
• Recall Traces: Backtracking Models for Efficient Reinforcement Learning
• Deep Curiosity Search: Intra-Life Exploration Can Improve Performance on Challenging Deep Reinforcement Learning Problems
• The Effects of Memory Replay in Reinforcement Learning
• Fast Exploration with Simplified Models and Approximately Optimistic Planning in Model Based Reinforcement Learning
• Fractal AI: A fragile theory of intelligence

Cited by in corpus (90)

• A Survey and Critique of Multiagent Deep Reinforcement Learning
• Exploration in Deep Reinforcement Learning: A Survey
• Decision Transformer: Reinforcement Learning via Sequence Modeling
• Character Controllers Using Motion VAEs
• Agent57: Outperforming the Atari Human Benchmark
• Exploration in Deep Reinforcement Learning: From Single-Agent to Multiagent Domain
• Covariance Matrix Adaptation for the Rapid Illumination of Behavior Space
• A Survey of Algorithms for Black-Box Safety Validation of Cyber-Physical Systems
• Unsupervised Learning of Object Keypoints for Perception and Control
• A Review of Robot Learning for Manipulation: Challenges, Representations, and Algorithms
• Evolutionary Reinforcement Learning: A Survey
• A survey on intrinsic motivation in reinforcement learning
• Never Give Up: Learning Directed Exploration Strategies
• Language as a Cognitive Tool to Imagine Goals in Curiosity-Driven Exploration
• Learning Dynamic Belief Graphs to Generalize on Text-Based Games
• Making Efficient Use of Demonstrations to Solve Hard Exploration Problems
• AI-GAs: AI-generating algorithms, an alternate paradigm for producing general artificial intelligence
• The NetHack Learning Environment
• Enhanced POET: Open-Ended Reinforcement Learning through Unbounded Invention of Learning Challenges and their Solutions
• Deep Reinforcement Learning at the Edge of the Statistical Precipice
• Diversity Policy Gradient for Sample Efficient Quality-Diversity Optimization
• RIDE: Rewarding Impact-Driven Exploration for Procedurally-Generated Environments
• Coordinated Exploration via Intrinsic Rewards for Multi-Agent Reinforcement Learning
• Generating Adjacency-Constrained Subgoals in Hierarchical Reinforcement Learning
• How to Avoid Being Eaten by a Grue: Structured Exploration Strategies for Textual Worlds
• Interactive Fiction Games: A Colossal Adventure
• On Bonus-Based Exploration Methods in the Arcade Learning Environment
• Asymmetric self-play for automatic goal discovery in robotic manipulation
• Hit and Lead Discovery with Explorative RL and Fragment-based Molecule Generation
• Curiosity in exploring chemical space: Intrinsic rewards for deep molecular reinforcement learning
• Is Deep Reinforcement Learning Really Superhuman on Atari? Leveling the playing field
• See, Hear, Explore: Curiosity via Audio-Visual Association
• BeBold: Exploration Beyond the Boundary of Explored Regions
• Planning With Uncertain Specifications (PUnS)
• Explore, Discover and Learn: Unsupervised Discovery of State-Covering Skills
• Explaining Bayesian Neural Networks
• Task-agnostic Exploration in Reinforcement Learning
• How To Avoid Being Eaten By a Grue: Exploration Strategies for Text-Adventure Agents
• Optimistic Exploration even with a Pessimistic Initialisation
• Self-Attentional Credit Assignment for Transfer in Reinforcement Learning
• Adversarially Guided Actor-Critic
• Ecological Reinforcement Learning
• Leveraging exploration in off-policy algorithms via normalizing flows
• Curiosity-Driven Multi-Criteria Hindsight Experience Replay
• MADE: Exploration via Maximizing Deviation from Explored Regions
• Evaluating Agents without Rewards
• Multi-task curriculum learning in a complex, visual, hard-exploration domain: Minecraft
• Causal-aware Safe Policy Improvement for Task-oriented dialogue
• MULEX: Disentangling Exploitation from Exploration in Deep RL
• OffWorld Gym: open-access physical robotics environment for real-world reinforcement learning benchmark and research
• Self-Imitation Advantage Learning
• Enhanced Adversarial Strategically-Timed Attacks against Deep Reinforcement Learning
• BOP-Elites, a Bayesian Optimisation algorithm for Quality-Diversity search
• Uncertainty-sensitive Learning and Planning with Ensembles
• Multiplayer Support for the Arcade Learning Environment
• Fiber: A Platform for Efficient Development and Distributed Training for Reinforcement Learning and Population-Based Methods
• Reinforcement Learning with Probabilistically Complete Exploration
• Safer Deep RL with Shallow MCTS: A Case Study in Pommerman
• Play to Grade: Testing Coding Games as Classifying Markov Decision Process
• Solving Challenging Dexterous Manipulation Tasks With Trajectory Optimisation and Reinforcement Learning
• Prioritized Level Replay
• Disentangled Planning and Control in Vision Based Robotics via Reward Machines
• On Catastrophic Interference in Atari 2600 Games
• GDI: Rethinking What Makes Reinforcement Learning Different From Supervised Learning
• Adaptive Procedural Task Generation for Hard-Exploration Problems
• PBCS : Efficient Exploration and Exploitation Using a Synergy between Reinforcement Learning and Motion Planning
• Learning Abstract Models for Strategic Exploration and Fast Reward Transfer
• Improving the Diversity of Bootstrapped DQN by Replacing Priors With Noise
• Multimodal Reward Shaping for Efficient Exploration in Reinforcement Learning
• Hierarchical reinforcement learning for efficient exploration and transfer
• Exploration via Hindsight Goal Generation
• Exploring Restart Distributions
• Guided Exploration with Proximal Policy Optimization using a Single Demonstration
• Alternative Techniques for Mapping Paths to HLAI
• Hierarchical Representation Learning for Markov Decision Processes
• Temporally-Extended ε-Greedy Exploration
• Curiosity creates Diversity in Policy Search
• Don't Do What Doesn't Matter: Intrinsic Motivation with Action Usefulness
• TAMPC: A Controller for Escaping Traps in Novel Environments
• General Characterization of Agents by States they Visit
• Optimistic Proximal Policy Optimization
• Exploring Unknown States with Action Balance
• Measuring Progress in Deep Reinforcement Learning Sample Efficiency
• Diagnosing and exploiting the computational demands of videos games for deep reinforcement learning
• Lucid Dreaming for Experience Replay: Refreshing Past States with the Current Policy
• When should agents explore?
• Leveraging Sequentiality in Reinforcement Learning from a Single Demonstration
• Learning in Sparse Rewards settings through Quality-Diversity algorithms
• Rapid Task-Solving in Novel Environments
• Time-Aware Q-Networks: Resolving Temporal Irregularity for Deep Reinforcement Learning