2017/02/24 by Alon Cohen, Cohen, Alon, Tamir Hazan +3 · 2 citations
Decision Sciences · #Advanced Bandit Algorithms Research #Auction Theory and Applications #Decision-Making and Behavioral Economics #FOS: Computer and information sciences #Machine Learning (cs.LG)
paper · pdf · doi:10.48550/arxiv.1702.07539
openalex publication_date 2017/02/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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Θ(k3/2√(dT)) 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√(dT)). Our bounds apply to several important instances of the framework, and in particular, imply a tight bound for the well-studied bandit shortest path problem. By that, we also resolve an open problem posed by Cesa-Bianchi and Lugosi (2012).