Batched bandits with heavy-tailed rewards
Information and Inference: A Journal of the IMA · 2026
DOI: 10.1093/imaiai/iaag031 ↗Kurz gefasst
Fachartikel in der Zeitschrift Information and Inference: A Journal of the IMA, 2026. Verfasst von Yunlu Shu und 3 weiteren Autor:innen. Die Arbeit nennt 57 Literaturangaben. Gefördert von: National Natural Science Foundation of China, Science and Technology Commission of Shanghai Municipality, ByteDance Inc..
Abstract (Originalsprache)
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.
Förderung
- National Natural Science Foundation of China
- Science and Technology Commission of Shanghai Municipality
- ByteDance Inc.
Zitieren
APA
Shu, Y., Guo, Y., Zhuo, G., & Wang, T. (2026). Batched bandits with heavy-tailed rewards. Information and Inference: A Journal of the IMA. https://doi.org/10.1093/imaiai/iaag031
Vancouver
Shu Y, Guo Y, Zhuo G, Wang T. Batched bandits with heavy-tailed rewards. Information and Inference: A Journal of the IMA. 2026. doi:10.1093/imaiai/iaag031
BibTeX
@article{Shu2026,
author = {Shu, Yunlu and Guo, Yunwen and Zhuo, Gongyi and Wang, Tianyu},
title = {Batched bandits with heavy-tailed rewards},
journal = {Information and Inference: A Journal of the IMA},
year = {2026},
doi = {10.1093/imaiai/iaag031}
}
EUVIMED