  The ability to form complex plans based on raw visual input is a litmus test
for current capabilities of artificial intelligence, as it requires a seamless
combination of visual processing and abstract algorithmic execution, two
traditionally separate areas of computer science. A recent surge of interest in
this field brought advances that yield good performance in tasks ranging from
arcade games to continuous control; these methods however do not come without
significant issues, such as limited generalization capabilities and
difficulties when dealing with combinatorially hard planning instances. Our
contribution is two-fold: (i) we present a method that learns to represent its
environment as a latent graph and leverages state reidentification to reduce
the complexity of finding a good policy from exponential to linear (ii) we
introduce a set of lightweight environments with an underlying discrete
combinatorial structure in which planning is challenging even for humans.
Moreover, we show that our methods achieves strong empirical generalization to
variations in the environment, even across highly disadvantaged regimes, such
as "one-shot" planning, or in an offline RL paradigm which only provides
low-quality trajectories.
