Batched Bandits with Heavy-Tailed Rewards

Yunwen Guo; Yunlun Shu; Gongyi Zhuo; Tianyu Wang

cs.LGOct 4, 2025

Batched Bandits with Heavy-Tailed Rewards

Authors: Yunwen Guo, Yunlun Shu, Gongyi Zhuo, Tianyu Wang

Organizations: School of Mathematical Sciences, Fudan University, 220 Handan Rd., 200433, Shanghai, China · Shanghai Center for Mathematical Sciences, Fudan University, 220 Handan Rd., 200433, Shanghai, China

Abstract

The batched multi-armed bandit (MAB) problem, where rewards are collected in batches, is pivotal in applications like clinical trials. While prior work assumes light-tailed reward distributions, real-world scenarios often exhibit heavy-tailed outcomes. This paper addresses this gap by introducing robust batched bandit algorithms for heavy-tailed rewards in both multi-arm and Lipschitz settings. We uncover somewhat surprising phenomena for such problems -- heavier tails require fewer batches to achieve near-optimal regret in the instance-independent setting, as well as the Lipschitz setting. In sharp contrast, in the instance-dependent setting, the number of batches required to achieve near-optimal regret does not depend on the tail heaviness.

Explore similar work

Parameter-Free Heavy-Tailed Bandits
Jul 31, 2026Gianmarco Genalti, Alberto Maria MetelliLong-Tailed Distribution Bandits
Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards
Apr 16, 2026Subhodip Panda, Shubhada AgrawalOptimal Bandit Algorithms Regret
Robust Multi-Agent Bandits with Heavy-Tailed Rewards and Information Asymmetry
Aug 11, 2026Daphne Feng, Ricardo Parada, Lily Jiang +2Multi-Agent Reinforcement Learning Bandits

Jul 31, 2026 · cs.LGJ/K move · Enter open · S save

Parameter-Free Heavy-Tailed Bandits

Gianmarco Genalti, Alberto Maria Metelli

Politecnico di Milano

Heavy-tailed distributions arise naturally in sequential decision-making problems such as financial investment, online advertising, and network management, where rare but extreme outcomes can dominate performance. Heavy-tailed bandits model online decision-making in these settings by assuming only that rewards

X

satisfy

\mathbb{E}[|X|^{1+ε}]\leq u

, for some tail exponent

ε\in(0,1]

and moment bound

u<+\infty

. However, most existing regret minimization algorithms require these parameters to be known. This assumption is particularly restrictive in practice:

ε

and

u

govern the frequency and magnitude of rare events and are therefore precisely the quantities that are hardest to infer reliably from limited observations. Motivated by an open problem posed by Genalti and Metelli at COLT 2025, we resolve the assumption-free adaptation problem for heavy-tailed bandits and characterize the price in the regret of not knowing the tail parameters. We first study adaptation to the moment bound

u

for a fixed tail exponent

ε

. We prove that every algorithm unaware of

u

, or of any upper bound on it, must obey a sharp trade-off between its distribution-dependent and distribution-free regret guarantees. We then introduce a scheduled-exploration algorithm that requires no knowledge of

u

and matches the resulting adaptation frontier up to logarithmic factors. Finally, we show that the same algorithm can be instanced without knowing

ε

by calibrating its exploration schedule to the endpoint

ε=1

. It achieves sublinear regret for every fixed

ε>0

, while no algorithm can guarantee sublinear regret uniformly over all

ε\in(0,1]

. Altogether, our results resolve the COLT open problem without additional distributional assumptions and provide a sharp characterization of the statistical cost of adapting to unknown heavy tails.

Long-Tailed Distribution Bandits

Open paper Ask about it PDF

Abstract

Explore similar work

Parameter-Free Heavy-Tailed Bandits

Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards

Robust Multi-Agent Bandits with Heavy-Tailed Rewards and Information Asymmetry