Regret Minimization in Heavy-Tailed Bandits

Abstract

We revisit the classic regret-minimization problem in the stochastic multi-armed bandit setting when the arm-distributions are allowed to be heavy-tailed. Regret minimization has been well studied in simpler settings of either bounded support reward distributions or distributions that belong to a single parameter exponential family. We work under the much weaker assumption that the moments of order $(1+\epsilon )$ are uniformly bounded by a known constant B, for some given $\epsilon >0$. We propose an optimal algorithm that matches the lower bound exactly in the first-order term. We also give a finite-time bound on its regret. We show that our index concentrates faster than the well known truncated or trimmed empirical mean estimators for the mean of heavy-tailed distributions. Computing our index can be computationally demanding. To address this, we develop a batch-based algorithm that is optimal up to a multiplicative constant depending on the batch size. We hence provide a controlled trade-off between statistical optimality and computational cost.

arXiv comment35 pages, 2 figures

References in corpus (6)

• Analysis of Thompson Sampling for the multi-armed bandit problem
• A Finite-Time Analysis of Multi-armed Bandits Problems with Kullback-Leibler Divergences
• An Asymptotically Optimal Policy for Uniform Bandits of Unknown Support
• A Scale Free Algorithm for Stochastic Bandits with Bounded Kurtosis
• Optimal Best-Arm Identification Methods for Tail-Risk Measures
• Optimal $\delta$-Correct Best-Arm Selection for Heavy-Tailed Distributions

Cited by in corpus (3)

• Optimal Best-Arm Identification Methods for Tail-Risk Measures
• Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits
• Regret Minimization in Isotonic, Heavy-Tailed Contextual Bandits via Adaptive Confidence Bands