Tight Bounds for Bandit Combinatorial Optimization
[edit]
Proceedings of the 2017 Conference on Learning Theory, PMLR 65:629642, 2017.
Abstract
We revisit the study of optimal regret rates in bandit combinatorial optimization—a fundamental framework for sequential decision making under uncertainty that abstracts numerous combinatorial prediction problems. We prove that the attainable regret in this setting grows as $\widetildeΘ(k^3/2\sqrt{d}T)$ where $d$ is the dimension of the problem and $k$ is a bound over the maximal instantaneous loss, disproving a conjecture of Audibert, Bubeck, and Lugosi (2013) who argued that the optimal rate should be of the form $\widetildeΘ(k\sqrt{d}T)$. Our bounds apply to several important instances of the framework, and in particular, imply a tight bound for the wellstudied bandit shortest path problem. By that, we also resolve an open problem posed by CesaBianchi and Lugosi (2012).
Related Material


