# Learning to Search via Retrospective Imitation

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Placed in Imitation learning methods, one of 13 directions in Offline RL and imitation learning from data.
- First posted on arXiv 3 Apr 2018.

## Placed in

- Offline RL and imitation learning from data / [Imitation learning methods](https://mlsanity.com/offlinerl/imitation-learning-methods/)

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

- [Learning to Compare Nodes in Branch and Bound with Graph Neural Networks](https://mlsanity.com/paper/2210.16934/) (2022)
- [Towards Foundation Models for Mixed Integer Linear Programming](https://mlsanity.com/paper/2410.08288/) (2024)
- [Hindsight Learning for MDPs with Exogenous Inputs](https://mlsanity.com/paper/2207.06272/) (2022)
- [Self-Improved Retrosynthetic Planning](https://mlsanity.com/paper/2106.04880/) (2021)
- [Learning to Configure Separators in Branch-and-Cut](https://mlsanity.com/paper/2311.05650/) (2023)
- [Artificial Intelligence for Operations Research: Revolutionizing the Operations Research Process](https://mlsanity.com/paper/2401.03244/) (2024)
- [SORREL: Suboptimal-Demonstration-Guided Reinforcement Learning for Learning to Branch](https://mlsanity.com/paper/2412.15534/) (2024)
- [Multi-task Representation Learning for Mixed Integer Linear Programming](https://mlsanity.com/paper/2412.14409/) (2024)
- [Learning Backdoors for Mixed Integer Linear Programs with Contrastive Learning](https://mlsanity.com/paper/2401.10467/) (2024)
- [Accelerating Multi-Agent Planning Using Graph Transformers with Bounded Suboptimality](https://mlsanity.com/paper/2301.08451/) (2023)
- [Exact Combinatorial Optimization with Temporo-Attentional Graph Neural Networks](https://mlsanity.com/paper/2311.13843/) (2023)
- [Search Strategy Generation for Branch and Bound Using Genetic Programming](https://mlsanity.com/paper/2412.09444/) (2024)
- [Designing faster mixed integer linear programming algorithm via learning the optimal path](https://mlsanity.com/paper/2601.16056/) (2026)
- [Sequence-Structured Decision Learning for Branch-and-Bound in Mixed-Integer Linear Programming](https://mlsanity.com/paper/2610.14835/) (2026)

## Abstract (arXiv)

We study the problem of learning a good search policy for combinatorial search spaces. We propose retrospective imitation learning, which, after initial training by an expert, improves itself by learning from textitretrospective inspections of its own roll-outs. That is, when the policy eventually reaches a feasible solution in a combinatorial search tree after making mistakes and backtracks, it retrospectively constructs an improved search trace to the solution by removing backtracks, which is then used to further train the policy. A key feature of our approach is that it can iteratively scale up, or transfer, to larger problem sizes than those solved by the initial expert demonstrations, thus dramatically expanding its applicability beyond that of conventional imitation learning. We showcase the effectiveness of our approach on a range of tasks, including synthetic maze solving and combinatorial problems expressed as integer programs.