BLISS Seminar: Sparsity, variance, and curvature in multi-armed bandits
Seminar | October 23 | 3-4 p.m. | 540 Cory Hall
Sebastien Bubeck, Microsoft Research
In (online) learning theory the concepts of sparsity, variance and curvature are well-understood and are routinely used to obtain refined regret and generalization bounds. In this work we further our understanding of these concepts in the more challenging limited feedback scenario. We consider the adversarial multi-armed bandit and linear bandit problems and solve several open problems pertaining to the existence of algorithms with good regret bounds under the following assumptions: (i) sparsity of the individual losses (open problem by Kwon and Perchet), (ii) small variation of the loss sequence (open problem by Kale and Hazan), and (iii) curvature of the action set (open problem by Bubeck, Cesa-Bianchi and Kakade).
Joint work with Michael B. Cohen and Yuanzhi Li.