# Imitation Learning for Combinatorial Optimisation under Uncertainty

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Imitation learning methods, one of 13 directions in Offline RL and imitation learning from data.
- Builds on 61 of its 122 references that are in the map.
- First posted on arXiv 8 Jan 2026.

## Placed in

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

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

- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Smart "Predict, then Optimize"](https://mlsanity.com/paper/1710.08005/) (2017)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Learning a SAT Solver from Single-Bit Supervision](https://mlsanity.com/paper/1802.03685/) (2018)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [End-to-End Constrained Optimization Learning: A Survey](https://mlsanity.com/paper/2103.16378/) (2021)
- [A Survey of Imitation Learning: Algorithms, Recent Developments, and Challenges](https://mlsanity.com/paper/2309.02473/) (2023)
- [Decision-Focused Learning: Foundations, State of the Art, Benchmark and Future Opportunities](https://mlsanity.com/paper/2307.13565/) (2023)
- [Imitation Learning from Imperfect Demonstration](https://mlsanity.com/paper/1901.09387/) (2019)
- [EnsembleDAgger: A Bayesian Approach to Safe Imitation Learning](https://mlsanity.com/paper/1807.08364/) (2018)
- [Discriminator-Weighted Offline Imitation Learning from Suboptimal Demonstrations](https://mlsanity.com/paper/2207.10050/) (2022)
- [Query-Efficient Imitation Learning for End-to-End Autonomous Driving](https://mlsanity.com/paper/1605.06450/) (2016)
- [A Survey of Contextual Optimization Methods for Decision Making under Uncertainty](https://mlsanity.com/paper/2306.10374/) (2023)
- [Learning to Branch](https://mlsanity.com/paper/1803.10150/) (2018)
- [Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies](https://mlsanity.com/paper/2002.05120/) (2020)
- [Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learning](https://mlsanity.com/paper/2206.13414/) (2022)
- [Imitation Learning: Progress, Taxonomies and Challenges](https://mlsanity.com/paper/2106.12177/) (2021)
- [LazyDAgger: Reducing Context Switching in Interactive Imitation Learning](https://mlsanity.com/paper/2104.00053/) (2021)
- [MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers](https://mlsanity.com/paper/2205.14210/) (2022)
- [Learning to Select Cuts for Efficient Mixed-Integer Programming](https://mlsanity.com/paper/2105.13645/) (2021)
- [Neural Network Branching for Neural Network Verification](https://mlsanity.com/paper/1912.01329/) (2019)
- [A GNN-Guided Predict-and-Search Framework for Mixed-Integer Linear Programming](https://mlsanity.com/paper/2302.05636/) (2023)
- [Learning to Solve Large-Scale Security-Constrained Unit Commitment Problems](https://mlsanity.com/paper/1902.01697/) (2019)
- [Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning](https://mlsanity.com/paper/2302.01578/) (2023)
- [Learning to Compare Nodes in Branch and Bound with Graph Neural Networks](https://mlsanity.com/paper/2210.16934/) (2022)
- [Lookback for Learning to Branch](https://mlsanity.com/paper/2206.14987/) (2022)
- [Hindsight Learning for MDPs with Exogenous Inputs](https://mlsanity.com/paper/2207.06272/) (2022)
- [Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programming](https://mlsanity.com/paper/2402.05501/) (2024)

## Abstract (arXiv)

Imitation learning (IL) provides a data-driven framework for approximating policies for large-scale combinatorial optimisation problems formulated as sequential decision problems (SDPs), where exact solution methods are computationally intractable. A central but underexplored aspect of IL in this context is the role of the expert that generates training demonstrations. Existing studies employ a wide range of expert constructions, yet lack a unifying framework to characterise their modelling assumptions, computational properties, and impact on learning performance. This paper introduces a systematic taxonomy of experts for imitation learning in combinatorial optimisation under uncertainty. The literature is classified along three principal dimensions: (i) treatment of uncertainty; (ii) level of optimality, distinguishing task-optimal and approximate experts; and (iii) interaction mode with the learner, ranging from one-shot supervision to iterative, interactive schemes. We further identify additional categories capturing other relevant expert characteristics. Building on this taxonomy, we propose a generalised Dataset Aggregation (DAgger) framework that accommodates multiple expert queries, expert aggregation, and flexible interaction strategies. The proposed framework is evaluated on a dynamic physician-to-patient assignment problem with stochastic arrivals and capacity constraints. Computational experiments compare learning outcomes across expert types and interaction regimes. The results show that policies learned from stochastic experts consistently outperform those learned from deterministic or full-information experts, while interactive learning improves solution quality using fewer expert demonstrations. Aggregated deterministic experts provide an effective alternative when stochastic optimisation becomes computationally challenging.