Source-linked AI summary
Bandits with heavy tail
Sébastien Bubeck, Nicolò Cesa-Bianchi, Gábor Lugosi
TL;DR
The paper asks how stochastic multi-armed bandits can be analyzed when rewards have only moments of order 1 + ε rather than sub-Gaussian tails. It builds UCB strategies from robust mean estimators and compares their regret guarantees. Finite variance recovers sub-Gaussian-order regret, while ε < 1 worsens the best achievable gap dependence.
Problem
The paper addresses stochastic bandits when reward distributions may be heavy-tailed and lack finite moment-generating functions, weakening standard empirical-mean guarantees.
Method
The paper constructs UCB strategies using truncated means, median-of-means, and Catoni’s M-estimator as robust alternatives to the empirical mean.
Results
Finite variance suffices for regret of the same order as under sub-Gaussian rewards, while finite 1 + ε moments yield logarithmic regret with worsening gap dependence as ε decreases.
Takeaways & Limitations
Robust mean estimation extends near-standard UCB regret guarantees to heavy-tailed bandits under moment assumptions weaker than sub-Gaussianity.
Takeaways & Limitations
Catoni’s estimator is analyzed only for finite variance, and the proofs rely heavily on independent rewards for each arm.
Abstract
from arXiv · showhide
The stochastic multi-armed 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 $ε\in (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.
1 Introduction
The paper studies stochastic multi-armed bandits beyond sub-Gaussian rewards, where finite moment-generating functions may fail and standard guarantees can deteriorate. It develops robust-estimator-based strategies and shows that finite variance can recover sub-Gaussian-order regret, while heavier tails worsen gap dependence.
- The classical problem has K unknown reward distributions, and the agent seeks to minimize regret over n rounds.
- Most existing analyses assume sub-Gaussian rewards and obtain regret of order P_i(log n)/∆_i, optimal even for bounded rewards.
- Finite-moment-generating-function assumptions can be insufficient for heavy-tailed rewards, and existing gap dependence becomes sub-optimal as tails grow heavier.
- With finite variance, the paper achieves regret bounds of the same form as in the sub-Gaussian case.
- For finite moments of order 1 + ε, regret remains logarithmic in n, but dependence on the gaps worsens as ε decreases.
- The proposed strategies replace empirical means with refined mean estimators and use upper confidence bounds, with matching lower bounds establishing unavoidable 1/∆_i^(1/ε) dependence.
2 Robust upper confidence bound strategies
The paper extends UCB strategies to heavy-tailed rewards by replacing empirical means with robust estimators satisfying concentration guarantees. Finite variance recovers sub-Gaussian-order regret, while finite (1+ε)-moments yield logarithmic dependence on n with worse gap dependence and matching lower bounds.
- 2 Robust upper confidence bound strategies: Robust UCB requires a mean estimator with a suitable concentration guarantee, then uses that estimator within an upper-confidence index.The framework defines estimator conditions and derives regret bounds from them.
- 2 Robust upper confidence bound strategies: The robust UCB policy has regret bounds obtained by controlling the expected number of pulls of each suboptimal arm.The proof bounds suboptimal-arm pulls before converting them into regret guarantees.
- 2.1 Truncated empirical mean: The truncated mean supports heavy-tailed rewards but depends on raw moments and is not translation invariant.Median-of-means instead can yield bounds based on centered moments, while Catoni’s estimator is considered for finite-variance settings.
- 2.1 Truncated empirical mean: Finite variance yields regret of order ∑i(log n)/∆i, matching the order known for sub-Gaussian and bounded rewards.The paper states that stronger tail conditions cannot improve this order.
- 2.3 Catoni’s M estimator: Catoni’s estimator has similar guarantees to median-of-means with better numerical constants, but its guarantee requires finite variance and a known variance upper bound.Its concentration result also requires n ≥ 4 log(1/δ), motivating a modified policy.
3 Discussion and conclusions
The paper compares three robust mean estimators for heavy-tailed bandits, identifying trade-offs among moment assumptions, regret guarantees, and update costs. It also highlights open extensions to broader sequential settings and dependent rewards.
- Estimator trade-offs: The median-of-means estimator uses central (1 + ε)-moments without requiring known moment bounds, while truncated mean uses raw moments and requires a known bound.Catoni’s estimator similarly uses central moments but requires a known bound and applies only when ε = 1.
- Estimator trade-offs: The truncated mean requires constant time and space per update, whereas median-of-means and Catoni’s estimator have higher sequential update costs.Catoni’s M-estimator requires linear space per update.
- Open questions: Open questions include whether an estimator can match median-of-means concentration with constant update cost and whether similar results hold for dependent heavy-tailed rewards.The paper’s proof techniques rely heavily on independence of rewards for each arm.
- Broader applications: The concentration results may also apply to racing algorithms and nonparametric Monte Carlo estimation, where existing applications are limited to empirical means for bounded rewards.The paper presents these settings as examples of related sequential decision problems.
A Empirical mean
This appendix analyzes the finite-sample behavior of the empirical mean when only moments of order 1 + ε are available. It derives a bound, shows its order is tight, and contrasts its polynomial deviations with the stronger concentration of robust estimators.
- Finite-sample analysis: The appendix focuses on finite-sample guarantees because non-asymptotic control is needed for finite-time bandit results.The discussion concerns the standard empirical mean under moments of order 1 + ε.
- Assumptions: The analysis assumes i.i.d. rewards with finite mean and a bounded central moment E|X − µ|^(1+ε) ≤ v, while u bounds the corresponding raw moment.The setting uses ε ∈ (0, 1].
- Proof strategy: The proof decomposes the empirical-mean deviation into a truncated-sum event and a large-observation event, then bounds them using moment inequalities.The cited steps use a union bound, Chebyshev’s inequality, Hölder’s inequality, and a truncation threshold.
- Tightness: The empirical mean’s bound is tight up to a constant factor for a heavy-tailed distribution constructed from point masses at 0 and 1/γ.The construction satisfies E|X − µ|^(1+ε) ≤ 1.
- Comparison with robust estimators: The empirical mean has polynomial dependence on 1/δ, unlike the polylogarithmic dependence of the truncated mean and median-of-means estimators.The three estimators have similar dependence on n in the confidence term, but the empirical mean has polynomial rather than exponential deviations.