Almost Optimal Algorithms for Linear Stochastic Bandits with Heavy-Tailed Payoffs

Abstract

In linear stochastic bandits, it is commonly assumed that payoffs are with sub-Gaussian noises. In this paper, under a weaker assumption on noises, we study the problem of \underline{lin}ear stochastic {\underline b}andits with h{\underline e}avy-{\underline t}ailed payoffs (LinBET), where the distributions have finite moments of order $1+\epsilon$, for some $\epsilon \in (0,1]$. We rigorously analyze the regret lower bound of LinBET as $\Omega (T^{\frac{1}{1+\epsilon }})$, implying that finite moments of order 2 (i.e., finite variances) yield the bound of $\Omega (\sqrt{T})$, with $T$ being the total number of rounds to play bandits. The provided lower bound also indicates that the state-of-the-art algorithms for LinBET are far from optimal. By adopting median of means with a well-designed allocation of decisions and truncation based on historical information, we develop two novel bandit algorithms, where the regret upper bounds match the lower bound up to polylogarithmic factors. To the best of our knowledge, we are the first to solve LinBET optimally in the sense of the polynomial order on $T$. Our proposed algorithms are evaluated based on synthetic datasets, and outperform the state-of-the-art results.

References in corpus (6)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Analysis of Thompson Sampling for the multi-armed bandit problem
• Loss minimization and parameter estimation with heavy tails
• Delay Bounds for Networks with Heavy-Tailed and Self-Similar Traffic
• Optimal Resource Allocation with Semi-Bandit Feedback
• A Scale Free Algorithm for Stochastic Bandits with Bounded Kurtosis

Cited by in corpus (5)

• Model Selection in Contextual Stochastic Bandit Problems
• Local Differential Privacy for Bayesian Optimization
• Nearly Optimal Regret for Stochastic Linear Bandits with Heavy-Tailed Payoffs
• Regret Minimization in Isotonic, Heavy-Tailed Contextual Bandits via Adaptive Confidence Bands
• Optimal Algorithms for Stochastic Multi-Armed Bandits with Heavy Tailed Rewards