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

Understand

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.