Bandits With Heavy Tail

By Sébastien Bubeck, Nicolò Cesa-Bianchi, Gábor Lugosi. 2012

338 citations recorded by the source corpus.

The stochastic multiarmed bandit problem is well understood when the reward distributions are sub-Gaussian. In this paper, we examine the bandit problem under the weaker assumption that the distributions have moments of order 1 + ε, for some ε ∈ (0,1]. Surprisingly, moments of order 2 (i.e., finite variance) are sufficient to obtain regret bounds of the same order as under sub-Gaussian reward distributions. In order to achieve such regret, we define sampling strategies based on refined estimators of the mean such as the truncated empirical mean, Catoni's M-estimator, and the median-of-means estimator. We also derive matching lower bounds that also show that the best achievable regret deteriorates when ε <; 1.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research

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 Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates (2018, methodology): “…Lerasle and Oliveira (2011), Minsker et al. (2015), Nemirovskii et al. (1983), and has been applied to bandit and least square regression problems (Bubeck et al., 2013, Kogler and Traxler, 2016, Lugosi and Mendelson, 2016) as well as problems involving heavy-tailed distributions (Hsu and Sabato,…”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “Refinements and bibliographic remarks 19 is allowed to be a certain function εt of the current time step t, namely εt = K/(d 2t), then the regret grows logarithmically like (K lnn)/d2, provided 0 d mini 6=i∗ ∆i.”
Geometric median and robust estimation in Banach spaces (2013, background): “Recently, the aforementioned “median of the means” construction appeared in [7] in the context of multi-armed bandit problem under weak assumptions on the reward distribution.”
Why ADAM Beats SGD for Attention Models (2019, neutral): “: Then Our lower bound construction is inspired by Theorem 2 of Bubeck et al. (2013).”
Convergence rates of least squares regression estimators with heavy-tailed errors (2017, background): “t on the errors, we refer the reader to [7]. It is worthwhile to note that the shortcomings of the LSE quantiﬁed here also rigorously justify the motivation of developing other robust procedures (cf. [4, 14, 15, 18, 19, 24, 35, 36, 45, 46, 47, 57]). Remark 9. Our Theorems 3 and 4 show that the momen”
Bandit Algorithms (2020, methodology): “While the framework was introduced relatively lately, the core ideas have been worked out earlier in the special case of linear prediction with nonlinear losses (the book of Cesa-Bianchi and Lugosi [2006] can be used as a reference to this literature). Mirror descent was first developed by Nemirovsk”
Sub-Gaussian mean estimators (2015, neutral): “It is shown in Bubeck, Cesa-Bianchi, and Lugosi [4] that for each M > 0, α ∈ (0 , 1], and δ , there exists an estimator (cid:98) E n ( X n 1 , δ ) such that sup The estimator (cid:98) E n ( X n 1 , δ ) satisfying this bound is the median-of-means estimator with appropriately chosen parameters.”