Sparsity, variance and curvature in multi-armed bandits

By Sébastien Bubeck, Michael B. Cohen, Yuanzhi Li. 2017

68 citations recorded by the source corpus.

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 paper we further our understanding of these concepts in the more challenging limited feedback scenario. We consider the adversarial multi-armed bandit and linear bandit settings and solve several open problems pertaining to the existence of algorithms with favorable regret bounds under the following assumptions: (i) sparsity of the individual losses, (ii) small variation of the loss sequence, and (iii) curvature of the action set. Specifically we show that (i) for $s$-sparse losses one can obtain $\tilde{O}(\sqrt{s T})$-regret (solving an open problem by Kwon and Perchet), (ii) for loss sequences with variation bounded by $Q$ one can obtain $\tilde{O}(\sqrt{Q})$-regret (solving an open problem by Kale and Hazan), and (iii) for linear bandit on an $\ell_p^n$ ball one can obtain $\tilde{O}(\sqrt{n T})$-regret for $p \in [1,2]$ and one has $\tilde{\Omega}(n \sqrt{T})$-regret for $p>2$ (solving an open problem by Bubeck, Cesa-Bianchi and Kakade). A key new insight to obtain these results is to use regularizers satisfying more refined conditions than general self-concordance

Subfields: Artificial Intelligence, Management Science and Operations Research, Modeling and Simulation, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Modeling and Simulation

In Reinforcement Learning

Citations in the corpus

Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets (2020, background): “We can cite, for instance, `p norms (common regularization in machine learning problems or action set in online learning) (Bubeck et al., 2018; Kerdreux et al., 2021c; Wang et al., 2021), matrix Schatten norms (Braverman et al.”
Bandit Algorithms (2020, methodology): “The factor of k2 is suboptimal and can be removed using a careful instantiation of the mirror descent algorithm [Bubeck et al., 2018].”
Introduction to Multi-Armed Bandits (2019, background): “t(a) cost(a) T 2 is the total variation of the costs. However, a seemingly simple special case of i.i.d. 0-1 costs is essentially the worst case for this regret bound. Recently, Wei and Luo (2018); Bubeck et al. (2018, 2019a) obtain further data-dependent regret bounds that take advantage of, respe”
Stochastic matrix games with bandit feedback (2020, background): “The main threads are (a) using the online convex optimisation view and modifying the regularizer [2, 10, 42], for example, and (b) modifying the loss estimates to obtain high probability regret or adaptive bounds [5, 20, 26, 1].”