2011/10/19 by Nicolò Cesa-Bianchi, Nicolò Cesa‐Bianchi, Sham Kakade +3
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Optimization and Search Problems #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.1110.4322
This paper is superseded by S. Bubeck, N. Cesa-Bianchi, and S.M. Kakade, "Towards minimax policies for online linear optimization with bandit feedback"
openalex publication_date 2011/10/19 · arxiv created 2012/02/14 · arxiv updated 2012/02/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We provide the first algorithm for online bandit linear optimization whose regret after T rounds is of order sqrtTd ln N on any finite class X of N actions in d dimensions, and of order d*sqrtT (up to log factors) when X is infinite. These bounds are not improvable in general. The basic idea utilizes tools from convex geometry to construct what is essentially an optimal exploration basis. We also present an application to a model of linear bandits with expert advice. Interestingly, these results show that bandit linear optimization with expert advice in d dimensions is no more difficult (in terms of the achievable regret) than the online d-armed bandit problem with expert advice (where EXP4 is optimal).