PaperlayerView exact revision on arXiv

Source-linked AI summary

First return, then explore

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

arXiv:2004.12919v6cs.AI

TL;DR

Go-Explore addresses exploration by returning to archived states before exploring from them, while grouping similar states to manage large state spaces. It achieves strong Atari results, although exploration does not itself produce a robust policy and Montezuma’s Revenge performance is time-limited.

  • Problem

    Non-trivial environments contain too many states to store explicitly, complicating exploration.

  • Method

    Go-Explore returns to a selected state, explores from it, and updates an archive while grouping similar states.

  • Results

    Go-Explore quadruples the state-of-the-art score on Montezuma’s Revenge, surpasses average human performance on Pitfall, and achieves a mean Pitfall score of 102,571.

  • Takeaways & Limitations

    Applying diversity ideas to reach new locations within environments provides a novel exploration approach.

  • Takeaways & Limitations

    The exploration phase does not produce a policy robust to inherent stochasticity, and Montezuma’s Revenge performance is limited by the default time setting.

Abstract

from arXiv · show

The promise of reinforcement learning is 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 sparse and deceptive feedback. Avoiding these pitfalls requires thoroughly exploring the environment, but creating algorithms that can do so remains one of the central challenges of the field. We hypothesise that the main impediment to effective exploration originates from algorithms forgetting how to reach previously visited states ("detachment") and from 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 first returning to such states before intentionally exploring. Go-Explore solves all heretofore unsolved Atari games and surpasses the state of the art on all hard-exploration games, with orders of magnitude improvements on the grand challenges 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.

The Go-Explore family of algorithms

Go-Explore addresses detachment and derailment by archiving promising states, returning to a selected state before exploration, and updating a cell-based archive. Its exploration phase can later support robust policy training through demonstrations.

  • Archive and cells: The archive prevents detachment by retaining visited states and grouping them into cells, while better trajectories replace existing entries.States mapping to new cells are added; better-performing or shorter trajectories can update known cells.
  • Core procedure: Go-Explore iteratively selects an archived state, returns to it, explores from it, and adds novel states to the archive.The return step can restore simulator state or use a goal-conditioned policy.
  • Core procedure: Go-Explore avoids derailment by separating returning from exploration, minimizing exploratory actions during the return step.After returning, the algorithm can switch to a purely exploratory policy.
  • Novelty: Cell-based exploration applies quality-diversity ideas to discovering new locations in state space rather than new behavioral styles.Unlike MAP-Elites, Go-Explore extends trajectories instead of modifying a policy.
  • Robustification: When returning without a policy, Go-Explore stores high-scoring trajectories and uses them for learning from demonstrations during robustification.This converts brittle exploration trajectories into robust, high-performing policies.

Learning to play Atari when returning without a policy

Go-Explore’s simulator-restoring exploration and cell representation produce strong Atari performance, including superhuman results across hard-exploration games. Domain knowledge and robustification further improve outcomes, although one key result is constrained by the benchmark’s frame limit.

  • Results: Go-Explore’s final mean performance is superhuman and surpasses the state of the art in all eleven focus games except Freeway, where both reach the maximum score.The evaluation uses the appropriately challenging stochastic Atari version with sticky actions.
  • Results: Go-Explore quadruples the state-of-the-art score on Montezuma’s Revenge and surpasses average human performance on Pitfall, where previous algorithms scored no points.These results are reported for the stochastic benchmark setting with sticky actions.
  • Exploration phase: 83.6% of the 55 Atari games yielded exploration trajectories scoring higher than state-of-the-art algorithms, while trajectories exceeded human scores in all 55 games.The exploration phase found superhuman trajectories across the full OpenAI Gym Atari set.
  • Domain knowledge: With domain knowledge, Go-Explore discovered all 255 Pitfall rooms and completely solved Montezuma’s Revenge by reaching the end of level 3.The representation used room number and coordinates for both games, plus level number and keys for Montezuma’s Revenge.
  • Robustification: Robustified policies achieved a mean score of 102,571 on Pitfall and 1,731,645 on Montezuma’s Revenge.The Montezuma’s Revenge score exceeded the previous state-of-the-art score by a factor of 150.
  • Scope boundary: The Montezuma’s Revenge performance is limited by OpenAI Gym’s default 400,000-frame time limit, which is not inherent to the game.Without the limit, one agent frequently exceeded 40 million after 12.5 million frames.

A hard-exploration robotics environment

Go-Explore tackles a sparse-reward simulated Fetch task by restoring simulator states and exploring with random actions. It discovers successful pick-and-place trajectories and produces robust policies despite unrestricted arm control.

  • Task difficulty: PPO receives no reward after one billion frames in this environment, demonstrating its hard-exploration character.All nine robot-arm joints are independently controlled across their permitted ranges.
  • Method: Go-Explore restores simulator state, explores with random actions, and assigns states to cells using easy-to-provide domain knowledge.This uses the simulator’s ability to return instantly to previously seen states.
  • Task: The simulated Fetch robot must grasp an object and place it on one of four shelves, with two shelves behind latched doors.A reward is given only when the object reaches the specified target shelf.
  • Exploration: Go-Explore quickly and reliably discovers successful trajectories for placing the object on each of the four shelves.A count-based intrinsic-motivation control using the same representation discovers no reward and only a fraction of the cells after one billion frames.
  • Robustification: Robustification produces reliable robot policies in 99% of cases while allowing a sparse reward focused only on the high-level task.The diverse trajectories include different successful strategies, such as throwing or gently depositing the object.

Policy-based Go-Explore

Policy-based Go-Explore combines simulator restoration or policy-based returns with goal-conditioned exploration, improving exploration efficiency on difficult Atari tasks. It outperforms state-of-the-art and human performance on Montezuma’s Revenge and Pitfall, while stochastic environments can make some previously discovered trajectories unreliable to repeat.

  • Method: Policy-based Go-Explore conditions a policy on the state or cell to which the agent should return, rather than requiring simulator-state restoration.The policy is trained to follow the best trajectory of cells previously leading to the selected state.
  • Trade-offs: Policy-based returns are less efficient than restoring simulator state because the actions required to return must be executed in the environment.Training a policy during exploration can nevertheless remove the need for a separate robustification phase and support exploration in stochastic environments.
  • Limitations: In stochastic environments, lucky transition sequences may not be reliably repeatable even under optimal actions, potentially preventing some trajectories from being revisited.This was not a major roadblock in the reported experiments, but could matter in other domains; direct stochastic-environment exploration with a policy can detect such cases early.
  • Method: The policy can also guide post-return exploration toward additional goals, including cells adjacent to the current position or goals not already in the archive.Exploration alternates between random actions and policy sampling with equal probability in the comparison described.
  • Results: Mean reward reached 97,728 points on Montezuma’s Revenge and 20,093 points on Pitfall, surpassing state-of-the-art and human performance.These results indicate that performance is not merely attributable to simulator restorability, but to the overall design.
  • Results: Policy sampling discovered over four times more cells than random actions on both Montezuma’s Revenge and Pitfall.Policy sampling became increasingly effective during training as the policy acquired generally useful skills.

Conclusion

Go-Explore's effectiveness suggests broad potential for sequential decision-making, while its modular design leaves many possible variants unexplored. The paper also argues that remembering states, returning to them, and exploring from them may extend beyond this algorithm family.

  • Conclusion: Go-Explore's effectiveness on the presented problems suggests it could enable progress across many domains framed as sequential decision-making problems.Examples include robotics, neural architecture search, language understanding, scheduling, marketing, and drug design.
  • Conclusion: The described Go-Explore instantiations represent only a fraction of the possible implementations of the modular paradigm.Potential variants include learning cell representations, return choices, exploration targets, and specialized exploration policies.
  • Conclusion: Future variants could support safer real-world exploration, continuous density-based archives, and robustification using transitions gathered during exploration.The passage presents these as unexplored possibilities rather than demonstrated capabilities.
  • Conclusion: The paper proposes that remembering previously found states, returning to them, and exploring from them may be a powerful and general approach to learning.The authors suggest these insights may be fundamental to learning in general and relevant beyond Go-Explore.

Methods

The methods establish evaluation practices for Atari and define Go-Explore’s state representations, exploration weighting, and adaptive downscaling procedure. They also describe domain-knowledge representations, robustness checks, and a policy-based variant for stochastic environments.

  • Evaluation: The Atari state-of-the-art comparison uses community-relevant evaluation standards and selects the highest score reported across 23 algorithms and variants for each game.Work evaluated only with no-ops is excluded from the formal state-of-the-art definition, although it is shown for context.
  • State representations: Go-Explore represents Atari cells using dynamically downscaled grayscale frames whose width, height, and pixel depth are tuned by randomized search.Candidate representations are evaluated by cell count and frame-distribution objectives that balance exploration against time and memory complexity.
  • State representations: The downscaling objective targets a fixed number of cells while encouraging uniformly distributed frames, avoiding excessive aggregation or an intractably large representation.L(n, T) measures deviation from the target cell count, while H_n(p) is normalized entropy over cell assignments.
  • State representations: Domain-knowledge representations encode task-relevant locations and object states, and Atari features can be extracted from pixels using hand-written classifiers rather than simulator RAM.Robotics representations use simulator state, including gripper position, contact or grasp status, target-shelf status, and door information.
  • Exploration phase: During exploration, cells are sampled in proportion to selection weights, then explored with random actions after return; additional domain-knowledge weighting did not substantially improve Pitfall.The Pitfall result is reported for domain-knowledge weighting relative to W alone.
  • Policy-based Go-Explore: Policy-based Go-Explore learns to return to states, enabling application without assuming a deterministic or restorable exploration environment.The policy-based variant is presented as learning how to return rather than restoring states directly.

Extended Data

The extended data specifies network architectures, Atari environment settings, hyperparameters, and supplementary exploration and robustification measurements. These materials also document robotics success, policy-based exploration, and archive behavior during representation recomputation.

  • Neural network architectures: The Atari network processes 12 channels from four RGB frames and combines convolutional, fully connected, and GRU layers with policy and value heads.The robotics setup uses separate policy and value networks, while policy-based Go-Explore adds goal representation g to the Atari architecture.
  • Atari results: Extended Data Figure 2 reports maximum end-of-episode exploration scores, averaging 50 or 5 runs in panel (a) and 100 runs in panel (b).Some curves begin only after the first episode end because only end-of-episode scores are reported.
  • Archive behavior: Archive size can decrease when cell representations are recomputed because previous archives are converted into the new format.If conversion produces more than 50K cells, one exploration iteration runs before another recomputation.
  • Policy-based exploration: Sampling from the goal-conditioned policy discovered roughly four times more cells than random actions in Montezuma’s Revenge and Pitfall.The advantage emerged only after the policy acquired basic skills; initially, policy sampling and random actions were effectively equivalent.

Supplementary Information

The supplementary material identifies detachment and derailment as major exploration obstacles and describes Go-Explore’s mechanisms and reported performance across Atari and robotics tasks.

  • Detachment and derailment: Detachment is losing track of interesting areas to explore from, while derailment occurs when exploration prevents returning to previously visited states.These issues can make agents forget how to reach frontiers or fail to return before exploring further.
  • Detachment and derailment: Intrinsic-motivation methods can detach because visited states lose intrinsic reward, eventually removing incentives to revisit or rediscover distant frontiers.The same failure can recur if intrinsic rewards are periodically regrown.
  • Detachment and derailment: Exploration schedules trade off derailment against exploration: low fixed probabilities limit exploration, whereas annealing initially explores heavily but can prevent reliable returns.State-agnostic mechanisms such as ϵ-greedy exploration become increasingly unlikely to reach distant states requiring many precise actions.
  • Go-Explore mechanisms: Go-Explore avoids derailment by separating exploration from returning and using separate exploration probabilities, while maintaining an archive of visited states.Its exploration phase can return reliably to high-scoring archive cells at test time.
  • Robotics evidence: Count-based intrinsic motivation failed to discover rewards in the robotics environment, with derailment evidence concentrated at transitions from touch to grasp and grasp to lift.In 90% of runs, grasp counts were at least 10x smaller than touch counts; in one of the remaining runs, lift counts were over 10x smaller than grasp counts.
Loading 2004.12919v6…