# Learning Shortest Paths When Data is Scarce

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 56 references that are in the map.
- First posted on arXiv 7 Jan 2026.

## Builds on (most cited first, 17 of 17)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [Smart "Predict, then Optimize"](https://mlsanity.com/paper/1710.08005/) (2017)
- [Data-driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations](https://mlsanity.com/paper/1505.05116/) (2015)
- [Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization](https://mlsanity.com/paper/1809.05504/) (2018)
- [From Predictive to Prescriptive Analytics](https://mlsanity.com/paper/1402.5481/) (2014)
- [Data-Driven Robust Optimization](https://mlsanity.com/paper/1401.0212/) (2013)
- [Online Learning with Feedback Graphs: Beyond Bandits](https://mlsanity.com/paper/1502.07617/) (2015)
- [Distributionally Robust Optimization: A Review](https://mlsanity.com/paper/1908.05659/) (2019)
- [Generalization Bounds in the Predict-then-Optimize Framework](https://mlsanity.com/paper/1905.11488/) (2019)
- [A Gang of Bandits](https://mlsanity.com/paper/1306.0811/) (2013)
- [Data-Pooling in Stochastic Optimization](https://mlsanity.com/paper/1906.00255/) (2019)
- [A simulation-based optimization approach for the calibration of a discrete event simulation model of an emergency department](https://mlsanity.com/paper/2102.00945/) (2021)

## Abstract (arXiv)

Digital twins and other simulators are increasingly used to support routing decisions in large-scale networks. However, simulator outputs often exhibit systematic bias, while ground-truth measurements are costly and scarce. We study a stochastic shortest-path problem in which a planner has access to abundant synthetic samples, limited real-world observations, and an edge-similarity structure capturing expected behavioral similarity across links. We model the simulator-to-reality discrepancy as an unknown, edge-specific bias that varies smoothly over the similarity graph, and estimate it using Laplacian-regularized least squares. This approach yields calibrated edge cost estimates even in data-scarce regimes. We establish finite-sample error bounds, translate estimation error into path-level suboptimality guarantees, and propose a computable, data-driven certificate that verifies near-optimality of a candidate route. For cold-start settings without initial real data, we develop a bias-aware active learning algorithm that leverages the simulator and adaptively selects edges to measure until a prescribed accuracy is met. Numerical experiments on multiple road networks and traffic graphs further demonstrate the effectiveness of our methods.