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.
From: Yunwen Guo [view email]
[v1]
Sat, 4 Oct 2025 12:26:32 UTC (73 KB)
[v2]
Sun, 22 Mar 2026 14:01:31 UTC (72 KB)
[v3]
Sat, 4 Jul 2026 10:14:47 UTC (1,991 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。