# Learning to Route Efficiently with End-to-End Feedback: The Value of Networked Structure

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Oct 2018.

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

- [A sequential transit network design algorithm with optimal learning under correlated beliefs](https://mlsanity.com/paper/2305.09452/) (2023)
- [Tangential Randomization in Linear Bandits (TRAiL): Guaranteed Inference and Regret Bounds](https://mlsanity.com/paper/2411.12154/) (2024)
- [Stochastic Reset Pathfinding: Path-Level Regret for Cascading Bandits over Graph Paths](https://mlsanity.com/paper/2607.15440/) (2026)

## Abstract (arXiv)

We introduce efficient algorithms which achieve nearly optimal regrets for the problem of stochastic online shortest path routing with end-to-end feedback. The setting is a natural application of the combinatorial stochastic bandits problem, a special case of the linear stochastic bandits problem. We show how the difficulties posed by the large scale action set can be overcome by the networked structure of the action set. Our approach presents a novel connection between bandit learning and shortest path algorithms. Our main contribution is an adaptive exploration algorithm with nearly optimal instance-dependent regret for any directed acyclic network. We then modify it so that nearly optimal worst case regret is achieved simultaneously. Driven by the carefully designed Top-Two Comparison (TTC) technique, the algorithms are efficiently implementable. We further conduct extensive numerical experiments to show that our proposed algorithms not only achieve superior regret performances, but also reduce the runtime drastically.