PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:1901.10995v4cs.LGcs.AIstat.ML

TL;DR

Hard-exploration problems remain difficult for RL when rewards are sparse or deceptive, including on Montezuma’s Revenge and Pitfall. Go-Explore remembers and revisits promising states, separates exploration from robustification, and achieves large benchmark improvements, including 666,474 mean points on Montezuma’s Revenge with domain knowledge.

  • Problem

    Sparse or deceptive rewards make intelligent exploration difficult, while intrinsic-motivation methods still struggle on hard-exploration benchmarks.

  • Method

    Go-Explore archives promising states, returns to them without exploration before exploring further, then robustifies brittle solutions through imitation learning when necessary.

  • Results

    Go-Explore substantially improves performance across Montezuma’s Revenge and Pitfall, reaching a mean of 666,474 on Montezuma’s Revenge with domain knowledge.

  • Takeaways & Limitations

    Remembering and reliably returning to promising states is presented as central to effective exploration, with potential relevance to simulated training in robotics.

  • Takeaways & Limitations

    Some applications lack a simulator, determinism, or resettability, requiring substantially more expensive goal-conditioned policies as a future direction.

Abstract

from arXiv · show

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

1 Introduction

Hard-exploration tasks require long action sequences despite sparse or misleading rewards, and existing RL methods—including intrinsic motivation—struggle on Montezuma’s Revenge and Pitfall. Go-Explore addresses these failures by remembering promising states, returning to them before exploring, and separating brittle solution-finding from later robustification.

  • Sparse rewards require long action sequences, while deceptive rewards can steer agents toward local optima instead of the global objective.
  • Intrinsic motivation can detach from promising frontiers after consuming local novelty and forgetting how to return, causing exploration to stall.
  • Go-Explore first solves a problem through potentially brittle means, such as deterministic training, then robustifies high-performing trajectories through imitation learning.
  • Go-Explore archives interesting states and ways to reach them, then returns to an archived state without exploration before exploring from it.
  • Intrinsic-motivation algorithms improve over classic RL but still struggle, averaging around 11,500 on Montezuma’s Revenge and scoring no more than 0 on Pitfall.
  • With domain knowledge, Go-Explore reaches a mean of 666,474 on Montezuma’s Revenge and 59,494 on Pitfall; without it, Montezuma’s Revenge averages 43,763.

2 The Go-Explore Algorithm

Go-Explore explores hard-exploration problems by archiving distinct cells and trajectories, reliably returning to promising cells before further exploration, and using a second phase to robustify high-performing trajectories. Its experiments use compact state representations, optional domain knowledge, and deterministic simulators during exploration when available.

  • Cell representations: Cell representations reduce high-dimensional observations to a tractable low-dimensional search space while the final policy still acts in the original state space.The experiments test representations without game-specific knowledge and representations that exploit easy-to-provide domain knowledge.
  • Cell representations: A simple representation converts each frame to grayscale, downsamples it to 11 × 8 pixels, and uses 8 possible intensity levels without game-specific knowledge.The representation is fast to compute; the dimensions and intensity range were selected by grid search.
  • Cell representations: Domain knowledge represents Montezuma’s Revenge cells using discretized position, room and level information, plus key locations; Pitfall uses position and room number.The information is extracted directly from pixels.
  • Phase 1: Exploration: Phase 1 archives interestingly different states and returns to selected promising cells without added exploration before exploring from them.This design addresses detachment and derailment by remembering states and ways to reach them, then separating reliable return from subsequent exploration.
  • Returning to cells: When simulators are deterministic and resettable, Go-Explore can exploit resets during exploration, then robustify the resulting solution for stochastic evaluation.The paper’s reported results concern settings where stochasticity is required during evaluation but not during training; stochastic training remains future work.
  • Archive updates: A limitation is that replacing a cell’s route with a better route may not preserve later trajectory transitions because cells conflate many states.The paper suggests robust or goal-conditioned policies as a possible way to investigate such substitutions.

3 Results

Go-Explore combines exploration and robustification to achieve strong performance on Montezuma’s Revenge and Pitfall, with domain knowledge improving exploration and final scores. Its results also expose robustness limitations and a game-specific bug that required filtering.

  • Montezuma’s Revenge: 43,763 mean score was achieved on Montezuma’s Revenge after robustification, exceeding the human expert mean of 34,900.All policies solved level 1, and one of five solved level 2 in every evaluation.
  • Montezuma’s Revenge: 238 rooms, 9.1 levels, and a 148,220 mean score were found during Phase 1 with domain knowledge.These results were averaged over 50 runs, with roughly half the game frames required by the downscaled representation.
  • Montezuma’s Revenge: 666,474 mean score was obtained after robustification with domain knowledge using demonstrations from ten Phase 1 runs.The five robustification runs all succeeded, but required a mean of 4.59B game frames, or 2.6 days of training.
  • Montezuma’s Revenge: 18,003,200 points and 1,441 solved levels were achieved by the best robustified Montezuma’s Revenge run.The run lasted 6,198,985 game frames and exceeded the human world record by over an order of magnitude.
  • Pitfall: Pitfall robustification failed for full-length trajectories, possibly because visually indistinguishable states required different behaviors.The domain-knowledge cell representation did not help Phase 2 because the robustification network was not given that representation.
  • Pitfall: 59,494 mean points were achieved on Pitfall after truncated trajectories were robustified, with a best rollout of 107,363.The robustification phase required a mean of 8.20B game frames, or 4.5 days of training, and outperformed prior state of the art and human experts.

4 Discussion and Future Work

Go-Explore combines archived stepping stones, reliable return before exploration, and later robustification to address hard exploration. Discussion highlights extensions to representations, exploration, stochasticity, robotics, and safety, alongside scaling and determinism limitations.

  • Core principles: Go-Explore remembers good exploration stepping stones, returns to states before exploring, and robustifies solutions when necessary.These three principles structure the algorithm’s approach to hard-exploration problems.
  • Core principles: Unlike many quality diversity methods, Go-Explore explores cumulatively from precise state-space endpoints rather than randomly perturbing policies.The archive is based on MAP-Elites but provides more controlled state-space exploration.
  • Future improvements: Random actions and simple state discretization still produce effective exploration, suggesting stepping-stone preservation is central to performance.The authors propose learned representations and more intelligent exploration as future improvements.
  • Stochasticity: Deterministic exploration and stochastic robustification separate finding solutions from producing policies reliable under environmental randomness.The approach is positioned as useful where deterministic simulators are available, including games and robotic simulators.
  • Limitations: Scaling to real-world simulations may require more intelligent cell representations and exploration, especially when many states map to one cell.The paper identifies this as a possible scope boundary beyond Atari-from-pixels.
  • Limitations: Determinism can create a busy-highway problem by favoring risky shortcuts that are hard to reproduce over safer guaranteed detours.Robustification may then train on trajectories that fail under stochastic dynamics; using more demonstrations or stochasticity-aware training is proposed.
  • Future applications: Robotics is a promising application: solve tasks in deterministic simulation, robustify under stochasticity, then transfer policies to the real world.The proposed pipeline targets long-horizon tasks such as finding survivors, cleaning, or retrieving a drink.
  • Future applications: Go-Explore’s broad state-space exploration may also reveal states near catastrophic outcomes, connecting it to safe-exploration research.The discussion extends beyond sparse or deceptive rewards to analyzing domain states and safety-relevant regions.

5 Related Work

Related work connects Go-Explore to exploration, planning, archives, hierarchical RL, and imitation, while distinguishing its explicit separation of reliable return, exploration, and robustification.

  • Exploration and exploitation: Go-Explore differs from exploration-then-exploitation methods by decomposing exploration into returning to states, exploring from them, and robustifying solutions.Earlier work collected reward-agnostic experience before extracting a high-reward policy.
  • Imitation and robustification: Guided Policy Search also separates solution finding from robustification, but requires a differentiable, non-sparse, non-deceptive loss and differentiable world models.Those requirements prevent direct application to discrete sparse or deceptive Atari-style problems.
  • Imitation and robustification: Self-Imitation Learning trains with an imitation loss throughout learning, whereas Go-Explore uses imitation learning as a separate robustification phase.Self-Imitation Learning reported 2,500 points on Montezuma’s Revenge.
  • Returning to states: Bootstrapped DQN and Recall Traces support revisiting valuable states, but Go-Explore explicitly separates returning to states from exploring from them.Recall Traces create virtual trajectories toward heuristically valuable states and include them during training.
  • Returning to states: Hierarchical RL by Liu et al. stores abstract states and navigates reliably before exploring, closely matching Go-Explore’s first two principles.The abstract states are formed by conflating multiple states, similar to Go-Explore cells.
  • Returning to states: Dong et al.’s memory and goal-conditioned return approach reached around 1,000 on Montezuma’s Revenge, substantially below Go-Explore.The comparison concerns an algorithm that also explores after returning to novel states.
  • Planning: Planning methods differ in sparse-reward settings: UCT can fail when rewards lie beyond its planning horizon, while FMC reached 5,600 on Montezuma’s Revenge.FMC emphasizes depth and novel states within deterministic random-walk planning.
  • Planning: Go-Explore’s archive and cell-based graph-search interpretation connect it to Dijkstra, A*, and RRTs while emphasizing meaningful state-space differences.The authors identify adapting graph-search principles to high-dimensional state spaces as future work.

6 Conclusion

The conclusion presents Go-Explore as a new family of algorithms for sparse- and deceptive-reward problems, with broad opportunities for refinement and application.

  • Future research: Go-Explore opens research directions involving archives, cell selection, cell representations, exploration methods, and robustification methods.The conclusion frames these as extensions beyond the simple version described in the paper.
  • Future research: The authors expect Go-Explore to accelerate progress in challenging domains such as robotics while also identifying domains where it fails.The conclusion presents this as a broad future research agenda.

A.1 The meaning of “frames”

The appendix distinguishes emulator-produced game frames from frames seen and acted on by the training agent, clarifying a potentially significant reporting difference.

  • Implementation: Both Go-Explore phases use Atari frame skipping with k = 4, so the agent selects actions every four frames and each action persists across them.Frame skipping is implemented during both exploration and robustification.
  • Definitions: “Game frames” count frames produced by the underlying emulator, whereas “training frames” count frames seen and acted on by the agent.Reported frame totals can differ significantly depending on which convention is used.
  • Implementation: During exploration, actions are repeated with 95% probability each training frame.This example specifically refers to training frames rather than game frames.

A.2 Episode end

Episode termination differs between the two games: Montezuma’s Revenge ends on loss of life, whereas Pitfall ends on the game-over signal.

  • Montezuma’s Revenge defines episode termination as a loss of life, while Pitfall uses the game-over signal.

A.3 Extraction of domain knowledge features from pixels

Go-Explore extracts gameplay features from pixels to represent agent location and game progress. Game-specific transition and life-loss handling supports reliable room tracking, while inventory patterns enable key tracking in Montezuma’s Revenge.

  • Pixel-based features include agent x, y position, current room, current level, and rooms where held keys were found.The level and key-room features apply only to Montezuma’s Revenge.
  • Character location is identified directly from sprite pixels, making specialized classifiers unnecessary in both games.Searching for pixels with a red channel value of 228 is sufficient to locate the character in both games.
  • Room changes are inferred from sudden x-position shifts, with Pitfall requiring rules for three-room underground transitions and wraparound maps.
  • Montezuma’s Revenge ends episodes on life loss because revival can mimic room changes, whereas Pitfall’s fixed revival location avoids that ambiguity.
  • Montezuma’s Revenge key tracking pattern-matches the inventory display and associates increases in key count with the room number.

A.4 Filtering out bug trajectories

Bug-triggering trajectories are filtered when robustifying Montezuma’s Revenge without domain knowledge, using level progression to identify trajectories that avoided the treasure-room bug.

  • Bug-trajectory filtering is used without domain knowledge but is unnecessary with domain knowledge because top-scoring trajectories avoid the bug.
  • Trajectories are excluded when their level is below the archive’s maximum level, because the bug prevents leaving the treasure room and advancing.

A.5 Cell selection details

Go-Explore selects archive cells probabilistically from normalized scores combining count, neighbor, and level-based subscores. These components favor underexplored frontiers and progress while preserving nonzero selection probabilities.

  • Cell scoring and selection: Each iteration assigns every archive cell a score, normalizes scores across cells, and uses the resulting values as selection probabilities.All cell scores are positive, so every cell retains a nonzero chance of selection.
  • Count subscores: Count subscores favor cells with fewer prior selections, visits, or post-discovery selections because lower counts indicate greater promise.
  • Count subscores: The count-score formula uses attribute values, weights, powers, and ε terms to control scaling, zero-count treatment, and nonzero selection probability.The implementation uses ε1 = 0.001 and ε2 = 0.00001.
  • Neighbor subscores: Neighbor subscores favor domain-knowledge cells lacking archived vertical, horizontal, or higher-key neighbors because they lie near the exploration frontier.In experiments without domain knowledge, NeighScore is defined as 0 because cell neighbors are unclear.
  • Level weighting: Montezuma’s Revenge cells with domain knowledge are exponentially downweighted by distance from the maximum level, while LevelWeight remains 1 in the other settings.

A.6 Phase 1 hyperparameters

Phase 1 uses separate hyperparameter configurations for runs with and without domain knowledge, while cell selection includes count-based attributes. The power hyperparameter pa was fixed at 0.5 across experiments.

  • pa was 0.5 for every attribute in every experiment after grid search.
  • Count-based attributes track how often cells were chosen, how often they were chosen since improvement, and how often they were seen.
  • Table 1 covers Montezuma’s Revenge and Pitfall runs without domain knowledge, while Table 2 covers runs with domain knowledge.

A.7.1 Multiple demonstrations

The appendix describes multiple-demonstration robustification, Pitfall-specific reward and termination changes, computational costs, and a domain-knowledge-free Pitfall failure linked to state representation.

  • Multiple demonstrations: Montezuma’s Revenge used 10 demonstrations for robustification, while Pitfall with domain knowledge and truncated trajectories used 4.Long Pitfall trajectories were not robustified with multiple demonstrations.
  • Multiple demonstrations: Multiple demonstrations were handled by selecting one uniformly at random whenever the Backward Algorithm chose a demonstration state for rollout.
  • Pitfall-specific changes: Pitfall replaced reward clipping with 0.001 reward scaling because clipping disproportionately emphasized avoiding frequent negative rewards over obtaining rare positive rewards.Positive rewards ranged from 2,000 to 5,000, while negative rewards could be as small as -1.
  • Pitfall-specific changes: Pitfall rollouts received a 250-point allowed score deficit to prevent early termination when negative rewards made their cumulative score temporarily lag the demonstration.The threshold was selected empirically for Pitfall.
  • Computational cost: Phase 1 runs used single virtual machines with 22 CPU cores and 50GB of RAM.
  • Computational cost: Montezuma’s Revenge with domain knowledge ran for 600M game frames, requiring a mean of 74.9 hours.The reported confidence interval was 72.6–77.2 hours.
  • Computational cost: Cell selection scales superlinearly in practice because naive roulette-wheel selection costs O(n) as the archive grows.The authors note that O(log n) and O(1) implementations could substantially speed selection.
  • Pitfall without domain knowledge: Without domain knowledge, Pitfall quickly stopped finding new rooms and rewards, potentially because downscaled cells conflated too many states.Pitfall’s repeated rooms can look nearly identical while requiring different actions, indicating partial observability.
Loading 1901.10995v4…