mlsanityData to 7 Oct 2026

Nearly Optimal Regret for Stochastic Linear Bandits with Heavy-Tailed Payoffs

arXiv 2004.13465 ↗First posted 28 Apr 2020cs.LG stat.MLcited by 25

Not on the map. Why?

Abstract (arXiv)

In this paper, we study the problem of stochastic linear bandits with finite action sets. Most of existing work assume the payoffs are bounded or sub-Gaussian, which may be violated in some scenarios such as financial markets. To settle this issue, we analyze the linear bandits with heavy-tailed payoffs, where the payoffs admit finite 1+ε moments for some ε∈(0,1]. Through median of means and dynamic truncation, we propose two novel algorithms which enjoy a sublinear regret bound of widetildeO(d^frac12T^frac11+ε), where d is the dimension of contextual information and T is the time horizon. Meanwhile, we provide an Omega(d^fracε1+εT^frac11+ε) lower bound, which implies our upper bound matches the lower bound up to polylogarithmic factors in the order of d and T when ε=1. Finally, we conduct numerical experiments to demonstrate the effectiveness of our algorithms and the empirical results strongly support our theoretical guarantees.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 6; 2023: 5; 2024: 1; 2025: 3; 2026: 4.

25 papers.

Sort:

By area:

  1. 2021Topology-Imbalance Learning for Semi-Supervised Node Classificationcited by 56
  2. 2022Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Modelscited by 35
  3. 2021Imbalanced Graph Classification via Graph-of-Graph Neural Networkscited by 27
  4. 2023Towards Robust Offline Reinforcement Learning under Diverse Data Corruptioncited by 24
  5. 2022Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed Banditscited by 17
  6. 2021Graph Classification by Mixture of Diverse Expertscited by 16
  7. 2023Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Boundscited by 13
  8. 2022Knowledge Learning with Crowdsourcing: A Brief Review and Systematic Perspectivecited by 11
  9. 2023Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewardscited by 11
  10. 2021Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits with Super Heavy-Tailed Payoffscited by 8
  11. 2023Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewardscited by 8
  12. 2023Quantum Heavy-tailed Banditscited by 7
13 more
  1. 2024Low-rank Matrix Bandits with Heavy-tailed Rewardscited by 6
  2. 2021Tackling the Imbalance for GNNscited by 5
  3. 2022NodeTrans: A Graph Transfer Learning Approach for Traffic Predictioncited 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. 2025Catoni Contextual Bandits are Robust to Heavy-tailed Rewardscited by 3
  7. 2022Graph Convolutional Network for Multi-Target Multi-Camera Vehicle Trackingcited by 2
  8. 2026Scale-Invariant Neural Network Optimization: Norm Geometry and Heavy-Tailed Noisecited by 2
  9. 2021Fast and Accurate Graph Learning for Huge Data via Minipatch Ensemblescited by 1
  10. 2026Best-of-Both-Worlds for Heavy-Tailed Markov Decision Processescited by 1
  11. 2022Graph Decipher: A transparent dual-attention graph neural network to understand the message-passing mechanism for the node classificationcited by 0
  12. 2026Robust and Computationally Efficient Linear Contextual Bandits under Adversarial Corruption and Heavy-Tailed Noisecited by 0
  13. 2026Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Setcited by 0