Online Learning of Network Bottlenecks via Minimax Paths
This work addresses bottleneck identification in networks for applications like routing or resource allocation, but it is incremental as it builds on existing bandit and path-finding methods.
The paper tackles the problem of identifying network bottlenecks using minimax paths in stochastic networks, modeling it as a combinatorial semi-bandit problem and applying Thompson Sampling with an approximate formulation to achieve computational feasibility, with experimental evaluation on real-world networks.
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.