mlsanityData to 14 Oct 2026

Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewards

arXiv 2310.18701 ↗First posted 28 Oct 2023cs.LGcited by 11

Not on the map. Why?

Abstract (arXiv)

This paper investigates the problem of generalized linear bandits with heavy-tailed rewards, whose (1+ε)-th moment is bounded for some ε∈ (0,1]. Although there exist methods for generalized linear bandits, most of them focus on bounded or sub-Gaussian rewards and are not well-suited for many real-world scenarios, such as financial markets and web-advertising. To address this issue, we propose two novel algorithms based on truncation and mean of medians. These algorithms achieve an almost optimal regret bound of widetildeO(dT^frac11+ε), where d is the dimension of contextual information and T is the time horizon. Our truncation-based algorithm supports online learning, distinguishing it from existing truncation-based approaches. Additionally, our mean-of-medians-based algorithm requires only O(log T) rewards and one estimator per epoch, making it more practical. Moreover, our algorithms improve the regret bounds by a logarithmic factor compared to existing algorithms when ε=1. Numerical experimental results confirm the merits of our algorithms.

Key facts. Cited by 11 papers in the map (data through 14 Oct 2026). Builds on 19 of its 44 references that are in the map. First posted on arXiv 28 Oct 2023.

Builds on

19 of 44 references.

References · 19

  1. 2015Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challengescited by 114
  2. 2017Scalable Generalized Linear Bandits: Online Computation and Hashingcited by 64
  3. 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
  4. 2021Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Datacited by 47
  5. 2021Near-optimal Representation Learning for Linear Bandits and Linear RLcited by 45
  6. 2022Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Modelscited by 37
  7. 2018Almost Optimal Algorithms for Linear Stochastic Bandits with Heavy-Tailed Payoffscited by 31
  8. 2020An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Samplingcited by 30
  9. 2021Generalized Linear Bandits with Local Differential Privacycited by 29
  10. 2015Online Stochastic Linear Optimization under One-bit Feedbackcited by 26
  11. 2020Nearly Optimal Regret for Stochastic Linear Bandits with Heavy-Tailed Payoffscited by 25
  12. 2019Bayesian Optimization under Heavy-tailed Payoffscited by 21
7 more
  1. 2019Multi-Objective Generalized Linear Banditscited by 19
  2. 2022Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed Banditscited by 18
  3. 2022Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noisecited by 14
  4. 2022Communication Efficient Federated Learning for Generalized Linear Banditscited by 13
  5. 2022Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributionscited by 13
  6. 2021Linear Bandit Algorithms with Sublinear Time Complexitycited by 9
  7. 2021Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits with Super Heavy-Tailed Payoffscited by 8

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 2; 2025: 5; 2026: 4.

11 papers.

  1. 2024uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABscited by 8
  2. 2024Low-rank Matrix Bandits with Heavy-tailed Rewardscited by 7
  3. 2025Single Index Bandits: Generalized Linear Contextual Bandits with Unknown Reward Functionscited by 6
  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. 2026Robust Length Prediction: A Perspective from Heavy-Tailed Prompt-Conditioned Distributionscited by 3
  7. 2026Tight Complexity of Muon under Heavy-Tailed Noisecited by 2
  8. 2025Learning Personalized Ad Impact via Contextual Reinforcement Learning under Delayed Rewardscited by 0
  9. 2025Online Learning to Rank under Corruption: A Robust Cascading Bandits Approachcited by 0
  10. 2026Robust and Computationally Efficient Linear Contextual Bandits under Adversarial Corruption and Heavy-Tailed Noisecited by 0
  11. 2026Nonlinear Banditcited by 0