# Neuro-algorithmic Policies enable Fast Combinatorial Generalization

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 61 references that are in the map.
- First posted on arXiv 15 Feb 2021.

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

- [Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1606.03476/) (2016)
- [Domain Randomization for Transferring Deep Neural Networks from Simulation to the Real World](https://mlsanity.com/paper/1703.06907/) (2017)
- [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)
- [When to Trust Your Model: Model-Based Policy Optimization](https://mlsanity.com/paper/1906.08253/) (2019)
- [CURL: Contrastive Unsupervised Representations for Reinforcement Learning](https://mlsanity.com/paper/2004.04136/) (2020)
- [Image Augmentation Is All You Need: Regularizing Deep Reinforcement Learning from Pixels](https://mlsanity.com/paper/2004.13649/) (2020)
- [Model-Based Reinforcement Learning for Atari](https://mlsanity.com/paper/1903.00374/) (2019)
- [Leveraging Procedural Generation to Benchmark Reinforcement Learning](https://mlsanity.com/paper/1912.01588/) (2019)
- [Reinforcement Learning with Augmented Data](https://mlsanity.com/paper/2004.14990/) (2020)
- [Data-Efficient Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1805.08296/) (2018)
- [Input Convex Neural Networks](https://mlsanity.com/paper/1609.07152/) (2016)
- [Smart "Predict, then Optimize"](https://mlsanity.com/paper/1710.08005/) (2017)
- [Deep Visual Foresight for Planning Robot Motion](https://mlsanity.com/paper/1610.00696/) (2016)
- [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)
- [Search on the Replay Buffer: Bridging Planning and Reinforcement Learning](https://mlsanity.com/paper/1906.05253/) (2019)
- [SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver](https://mlsanity.com/paper/1905.12149/) (2019)
- [Value Iteration Networks](https://mlsanity.com/paper/1602.02867/) (2016)
- [Imagination-Augmented Agents for Deep Reinforcement Learning](https://mlsanity.com/paper/1707.06203/) (2017)
- [Value Prediction Network](https://mlsanity.com/paper/1707.03497/) (2017)
- [Model-Free Episodic Control](https://mlsanity.com/paper/1606.04460/) (2016)
- [MIPaaL: Mixed Integer Program as a Layer](https://mlsanity.com/paper/1907.05912/) (2019)
- [The Predictron: End-To-End Learning and Planning](https://mlsanity.com/paper/1612.08810/) (2016)
- [Smart Predict-and-Optimize for Hard Combinatorial Optimization Problems](https://mlsanity.com/paper/1911.10092/) (2019)
- [Optimal Control Via Neural Networks: A Convex Approach](https://mlsanity.com/paper/1805.11835/) (2018)
- [Learning with Differentiable Perturbed Optimizers](https://mlsanity.com/paper/2002.08676/) (2020)
- [Automatic Data Augmentation for Generalization in Deep Reinforcement Learning](https://mlsanity.com/paper/2006.12862/) (2020)
- [Learning Compositional Koopman Operators for Model-Based Control](https://mlsanity.com/paper/1910.08264/) (2019)
- [SparseMAP: Differentiable Sparse Structured Inference](https://mlsanity.com/paper/1802.04223/) (2018)

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

- [A Survey of Zero-shot Generalisation in Deep Reinforcement Learning](https://mlsanity.com/paper/2111.09794/) (2021)
- [Backpropagation through Combinatorial Algorithms: Identity with Projection Works](https://mlsanity.com/paper/2205.15213/) (2022)
- [Explore to Generalize in Zero-Shot RL](https://mlsanity.com/paper/2306.03072/) (2023)
- [Causal Action Influence Aware Counterfactual Data Augmentation](https://mlsanity.com/paper/2405.18917/) (2024)
- [Optimize Planning Heuristics to Rank, not to Estimate Cost-to-Goal](https://mlsanity.com/paper/2310.19463/) (2023)
- [Planning from Pixels in Environments with Combinatorially Hard Search Spaces](https://mlsanity.com/paper/2110.06149/) (2021)
- [Towards Combinatorial Generalization for Catalysts: A Kohn-Sham Charge-Density Approach](https://mlsanity.com/paper/2310.18702/) (2023)
- [A Differentiable Loss Function for Learning Heuristics in A*](https://mlsanity.com/paper/2209.05206/) (2022)
- [Evolving Pareto-Optimal Actor-Critic Algorithms for Generalizability and Stability](https://mlsanity.com/paper/2204.04292/) (2022)
- [SLOPE: Search with Learned Optimal Pruning-based Expansion](https://mlsanity.com/paper/2406.04935/) (2024)
- [A Novel Switch-Type Policy Network for Resource Allocation Problems: Technical Report](https://mlsanity.com/paper/2501.11136/) (2025)

## Abstract (arXiv)

Although model-based and model-free approaches to learning the control of systems have achieved impressive results on standard benchmarks, generalization to task variations is still lacking. Recent results suggest that generalization for standard architectures improves only after obtaining exhaustive amounts of data. We give evidence that generalization capabilities are in many cases bottlenecked by the inability to generalize on the combinatorial aspects of the problem. Furthermore, we show that for a certain subclass of the MDP framework, this can be alleviated by neuro-algorithmic architectures. Many control problems require long-term planning that is hard to solve generically with neural networks alone. We introduce a neuro-algorithmic policy architecture consisting of a neural network and an embedded time-dependent shortest path solver. These policies can be trained end-to-end by blackbox differentiation. We show that this type of architecture generalizes well to unseen variations in the environment already after seeing a few examples.