mlsanityData to 7 Oct 2026

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

arXiv 1810.10895 ↗First posted 25 Oct 2018cs.LG stat.MLcited by 31

Not on the map. Why?

Abstract (arXiv)

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 underlinelinear stochastic underline bandits with hunderline eavy-underline tailed payoffs (LinBET), where the distributions have finite moments of order 1+ε, for some ε∈ (0,1]. We rigorously analyze the regret lower bound of LinBET as Omega(T^frac11+ε), implying that finite moments of order 2 (i.e., finite variances) yield the bound of Omega(√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.

Key facts. Cited by 31 papers in the map (data through 7 Oct 2026). First posted on arXiv 25 Oct 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 5; 2023: 8; 2024: 5; 2025: 5; 2026: 6.

31 papers.

Sort:

By area:

  1. 2023Towards Robust Offline Reinforcement Learning under Diverse Data Corruptioncited by 24
  2. 2022Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed Banditscited by 17
  3. 2021No-Regret Reinforcement Learning with Heavy-Tailed Rewardscited by 13
  4. 2022Safe Linear Bandits over Unknown Polytopescited by 13
  5. 2023Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Boundscited by 13
  6. 2024Trustworthy Distributed AI Systems: Robustness, Privacy, and Governancecited by 12
  7. 2023Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewardscited by 11
  8. 2023Provably Robust Temporal Difference Learning for Heavy-Tailed Rewardscited by 9
  9. 2021Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits with Super Heavy-Tailed Payoffscited by 8
  10. 2023Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewardscited by 8
  11. 2023Quantum Heavy-tailed Banditscited by 7
  12. 2023Robust Offline Reinforcement learning with Heavy-Tailed Rewardscited by 7
19 more
  1. 2022Bandits Corrupted by Nature: Lower Bounds on Regret and Robust Optimistic Algorithmcited by 6
  2. 2024Low-rank Matrix Bandits with Heavy-tailed Rewardscited by 6
  3. 2024Learning pure quantum states (almost) without regretcited by 5
  4. 2025Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Updatecited by 5
  5. 2025Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewardscited by 4
  6. 2024Fast UCB-type algorithms for stochastic bandits with heavy and super heavy symmetric noisecited by 3
  7. 2024Revisiting Matrix Sketching in Linear Bandits: Achieving Sublinear Regret via Dyadic Block Sketchingcited by 3
  8. 2025Catoni Contextual Bandits are Robust to Heavy-tailed Rewardscited by 3
  9. 2022On solutions of the distributional Bellman equationcited by 2
  10. 2023Implicitly normalized forecaster with clipping for linear and non-linear heavy-tailed multi-armed banditscited by 1
  11. 2025Safe Bayesian optimization across noise models via scenario programmingcited by 1
  12. 2026Best-of-Both-Worlds for Heavy-Tailed Markov Decision Processescited by 1
  13. 2022Cost-Efficient Distributed Learning via Combinatorial Multi-Armed Banditscited by 0
  14. 2025Batched Bandits with Heavy-Tailed Rewardscited by 0
  15. 2026Robust and Computationally Efficient Linear Contextual Bandits under Adversarial Corruption and Heavy-Tailed Noisecited by 0
  16. 2026Learning Pure Quantum States in Any Dimension (Almost) Without Regretcited by 0
  17. 2026Nonlinear Banditcited by 0
  18. 2026Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Setcited by 0
  19. 2026Robust Multi-Agent Bandits with Heavy-Tailed Rewards and Information Asymmetrycited by 0