# Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewards

arXiv: https://arxiv.org/abs/2310.18701 · HTML: https://mlsanity.com/paper/2310.18701/

## 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 (most cited first, 19 of 19)

- [Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges](https://mlsanity.com/paper/1507.08025/) (2015)
- [Scalable Generalized Linear Bandits: Online Computation and Hashing](https://mlsanity.com/paper/1706.00136/) (2017)
- [Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2205.06811/) (2022)
- [Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data](https://mlsanity.com/paper/2106.01336/) (2021)
- [Near-optimal Representation Learning for Linear Bandits and Linear RL](https://mlsanity.com/paper/2102.04132/) (2021)
- [Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Models](https://mlsanity.com/paper/2202.04593/) (2022)
- [Almost Optimal Algorithms for Linear Stochastic Bandits with Heavy-Tailed Payoffs](https://mlsanity.com/paper/1810.10895/) (2018)
- [An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling](https://mlsanity.com/paper/2006.04012/) (2020)
- [Generalized Linear Bandits with Local Differential Privacy](https://mlsanity.com/paper/2106.03365/) (2021)
- [Online Stochastic Linear Optimization under One-bit Feedback](https://mlsanity.com/paper/1509.07728/) (2015)
- [Nearly Optimal Regret for Stochastic Linear Bandits with Heavy-Tailed Payoffs](https://mlsanity.com/paper/2004.13465/) (2020)
- [Bayesian Optimization under Heavy-tailed Payoffs](https://mlsanity.com/paper/1909.07040/) (2019)
- [Multi-Objective Generalized Linear Bandits](https://mlsanity.com/paper/1905.12879/) (2019)
- [Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed Bandits](https://mlsanity.com/paper/2201.11921/) (2022)
- [Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise](https://mlsanity.com/paper/2206.01095/) (2022)
- [Communication Efficient Federated Learning for Generalized Linear Bandits](https://mlsanity.com/paper/2202.01087/) (2022)
- [Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions](https://mlsanity.com/paper/2211.16333/) (2022)
- [Linear Bandit Algorithms with Sublinear Time Complexity](https://mlsanity.com/paper/2103.02729/) (2021)
- [Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits with Super Heavy-Tailed Payoffs](https://mlsanity.com/paper/2110.13876/) (2021)

## Built on by (most cited first, 11 of 11)

- [uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABs](https://mlsanity.com/paper/2410.03284/) (2024)
- [Low-rank Matrix Bandits with Heavy-tailed Rewards](https://mlsanity.com/paper/2404.17709/) (2024)
- [Single Index Bandits: Generalized Linear Contextual Bandits with Unknown Reward Functions](https://mlsanity.com/paper/2506.12751/) (2025)
- [Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update](https://mlsanity.com/paper/2503.00419/) (2025)
- [Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards](https://mlsanity.com/paper/2506.04775/) (2025)
- [Robust Length Prediction: A Perspective from Heavy-Tailed Prompt-Conditioned Distributions](https://mlsanity.com/paper/2604.07931/) (2026)
- [Tight Complexity of Muon under Heavy-Tailed Noise](https://mlsanity.com/paper/2605.18528/) (2026)
- [Learning Personalized Ad Impact via Contextual Reinforcement Learning under Delayed Rewards](https://mlsanity.com/paper/2510.20055/) (2025)
- [Online Learning to Rank under Corruption: A Robust Cascading Bandits Approach](https://mlsanity.com/paper/2511.03074/) (2025)
- [Robust and Computationally Efficient Linear Contextual Bandits under Adversarial Corruption and Heavy-Tailed Noise](https://mlsanity.com/paper/2603.15596/) (2026)
- [Nonlinear Bandit](https://mlsanity.com/paper/2607.07304/) (2026)

## 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.