# Online Learning of Network Bottlenecks via Minimax Paths

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 49 references that are in the map.
- First posted on arXiv 17 Sep 2021.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Sampling](https://mlsanity.com/paper/1802.09127/) (2018)
- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [Combinatorial Multi-Armed Bandit with General Reward Functions](https://mlsanity.com/paper/1610.06603/) (2016)
- [Optimal Non-Asymptotic Lower Bound on the Minimax Regret of Learning with Expert Advice](https://mlsanity.com/paper/1511.02176/) (2015)
- [An Online Learning Framework for Energy-Efficient Navigation of Electric Vehicles](https://mlsanity.com/paper/2003.01416/) (2020)
- [Stochastic Online Shortest Path Routing: The Value of Feedback](https://mlsanity.com/paper/1309.7367/) (2013)
- [Combinatorial Pure Exploration with Bottleneck Reward Function](https://mlsanity.com/paper/2102.12094/) (2021)
- [Unsupervised Representation Learning with Minimax Distance Measures](https://mlsanity.com/paper/1904.13223/) (2019)

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

- [Online Learning of Energy Consumption for Navigation of Electric Vehicles](https://mlsanity.com/paper/2111.02314/) (2021)
- [A Contextual Combinatorial Semi-Bandit Approach to Network Bottleneck Identification](https://mlsanity.com/paper/2206.08144/) (2022)
- [Autonomous Drug Design with Multi-Armed Bandits](https://mlsanity.com/paper/2207.01393/) (2022)
- [Cost-Efficient Online Decision Making: A Combinatorial Multi-Armed Bandit Approach](https://mlsanity.com/paper/2308.10699/) (2023)
- [Adaptive Prior Selection in Gaussian Process Bandits with Thompson Sampling](https://mlsanity.com/paper/2502.01226/) (2025)
- [A Pure Hypothesis Test for Inhomogeneous Random Graph Models Based on a Kernelised Stein Discrepancy](https://mlsanity.com/paper/2505.21580/) (2025)
- [A Combinatorial Semi-Bandit Approach to Charging Station Selection for Electric Vehicles](https://mlsanity.com/paper/2301.07156/) (2023)
- [Prediction of Time and Distance of Trips Using Explainable Attention-based LSTMs](https://mlsanity.com/paper/2303.15087/) (2023)
- [Empirical Auditing of Edge-Private Graph Generators](https://mlsanity.com/paper/2609.25155/) (2026)

## Abstract (arXiv)

In this paper, we study bottleneck identification in networks via extracting minimax paths. Many real-world networks have stochastic weights for which full knowledge is not available in advance. Therefore, we model this task as a combinatorial semi-bandit problem to which we apply a combinatorial version of Thompson Sampling and establish an upper bound on the corresponding Bayesian regret. Due to the computational intractability of the problem, we then devise an alternative problem formulation which approximates the original objective. Finally, we experimentally evaluate the performance of Thompson Sampling with the approximate formulation on real-world directed and undirected networks.