BLISS Seminar: Sparsity, variance, and curvature in multi-armed bandits

Seminar | October 23 | 3-4 p.m. | 540 Cory Hall

 Sebastien Bubeck, Microsoft Research

 Electrical Engineering and Computer Sciences (EECS)

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.