Batched Bandits with Heavy-Tailed Rewards

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.