Learning Shortest Paths When Data is Scarce
This addresses the problem of biased simulator outputs for routing decisions in large-scale networks like digital twins, offering a solution for planners with limited real-world data, though it is incremental as it builds on existing stochastic shortest-path and regularization methods.
The paper tackles the problem of routing in networks when ground-truth data is scarce but simulator data is abundant but biased, by modeling and estimating edge-specific biases that vary smoothly over a similarity graph. It provides finite-sample error bounds, path-level suboptimality guarantees, and an active learning algorithm for cold-start settings, with numerical experiments on road and traffic networks demonstrating effectiveness.
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.