First return, then explore
  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.
