Sparse Graphical Memory for Robust Planning
  To operate effectively in the real world, agents should be able to act from
high-dimensional raw sensory input such as images and achieve diverse goals
across long time-horizons. Current deep reinforcement and imitation learning
methods can learn directly from high-dimensional inputs but do not scale well
to long-horizon tasks. In contrast, classical graphical methods like A* search
are able to solve long-horizon tasks, but assume that the state space is
abstracted away from raw sensory input. Recent works have attempted to combine
the strengths of deep learning and classical planning; however, dominant
methods in this domain are still quite brittle and scale poorly with the size
of the environment. We introduce Sparse Graphical Memory (SGM), a new data
structure that stores states and feasible transitions in a sparse memory. SGM
aggregates states according to a novel two-way consistency objective, adapting
classic state aggregation criteria to goal-conditioned RL: two states are
redundant when they are interchangeable both as goals and as starting states.
Theoretically, we prove that merging nodes according to two-way consistency
leads to an increase in shortest path lengths that scales only linearly with
the merging threshold. Experimentally, we show that SGM significantly
outperforms current state of the art methods on long horizon, sparse-reward
visual navigation tasks. Project video and code are available at
https://mishalaskin.github.io/sgm/
