# Planning from Pixels in Environments with Combinatorially Hard Search Spaces

arXiv: https://arxiv.org/abs/2110.06149 · HTML: https://mlsanity.com/paper/2110.06149/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 47 references that are in the map.
- First posted on arXiv 12 Oct 2021.

## Builds on (most cited first, 30 of 35)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Dream to Control: Learning Behaviors by Latent Imagination](https://mlsanity.com/paper/1912.01603/) (2019)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Learning Latent Dynamics for Planning from Pixels](https://mlsanity.com/paper/1811.04551/) (2018)
- [Hindsight Experience Replay](https://mlsanity.com/paper/1707.01495/) (2017)
- [Mastering Atari with Discrete World Models](https://mlsanity.com/paper/2010.02193/) (2020)
- [Recurrent World Models Facilitate Policy Evolution](https://mlsanity.com/paper/1809.01999/) (2018)
- [Deep Reinforcement Learning in a Handful of Trials using Probabilistic Dynamics Models](https://mlsanity.com/paper/1805.12114/) (2018)
- [SphereFace: Deep Hypersphere Embedding for Face Recognition](https://mlsanity.com/paper/1704.08063/) (2017)
- [Leveraging Procedural Generation to Benchmark Reinforcement Learning](https://mlsanity.com/paper/1912.01588/) (2019)
- [Learning Invariant Representations for Reinforcement Learning without Reconstruction](https://mlsanity.com/paper/2006.10742/) (2020)
- [Deep metric learning using Triplet network](https://mlsanity.com/paper/1412.6622/) (2014)
- [Visual Reinforcement Learning with Imagined Goals](https://mlsanity.com/paper/1807.04742/) (2018)
- [Differentiation of Blackbox Combinatorial Solvers](https://mlsanity.com/paper/1912.02175/) (2019)
- [Semi-parametric Topological Memory for Navigation](https://mlsanity.com/paper/1803.00653/) (2018)
- [Contrastive Learning of Structured World Models](https://mlsanity.com/paper/1911.12247/) (2019)
- [DeepMDP: Learning Continuous Latent Space Models for Representation Learning](https://mlsanity.com/paper/1906.02736/) (2019)
- [Action-Conditional Video Prediction using Deep Networks in Atari Games](https://mlsanity.com/paper/1507.08750/) (2015)
- [Provably efficient RL with Rich Observations via Latent State Decoding](https://mlsanity.com/paper/1901.09018/) (2019)
- [Planning with Goal-Conditioned Policies](https://mlsanity.com/paper/1911.08453/) (2019)
- [World Model as a Graph: Learning Latent Landmarks for Planning](https://mlsanity.com/paper/2011.12491/) (2020)
- [Recurrent Environment Simulators](https://mlsanity.com/paper/1704.02254/) (2017)
- [Dreaming: Model-based Reinforcement Learning by Latent Imagination without Reconstruction](https://mlsanity.com/paper/2007.14535/) (2020)
- [A Survey on Metric Learning for Feature Vectors and Structured Data](https://mlsanity.com/paper/1306.6709/) (2013)
- [Classical Planning in Deep Latent Space: Bridging the Subsymbolic-Symbolic Boundary](https://mlsanity.com/paper/1705.00154/) (2017)
- [Path Planning using Neural A* Search](https://mlsanity.com/paper/2009.07476/) (2020)
- [Robot Motion Planning in Learned Latent Spaces](https://mlsanity.com/paper/1807.10366/) (2018)

## Built on by (most cited first, 5 of 5)

- [Contrastive Representations for Temporal Reasoning](https://mlsanity.com/paper/2508.13113/) (2025)
- [Graph World Models: Concepts, Taxonomy, and Future Directions](https://mlsanity.com/paper/2604.27895/) (2026)
- [Challenges to Solving Combinatorially Hard Long-Horizon Deep RL Tasks](https://mlsanity.com/paper/2206.01812/) (2022)
- [Discrete World Models via Regularization](https://mlsanity.com/paper/2603.01748/) (2026)
- [Neurosymbolic Learning of Interpretable World Models](https://mlsanity.com/paper/2610.19955/) (2026)

## Abstract (arXiv)

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.