提出适用于重尾奖励的分批多臂老虎机算法，发现尾部越重所需批次反而越少。
Batched Bandits with Heavy-Tailed Rewards
- 设计鲁棒算法应对重尾奖励，适配多臂与Lipschitz场景
- 重尾情况下，实例无关设置下批次数更少即可逼近最优后悔值
- 实例相关设置中，批次数与尾部轻重无关，适合真实场景建模
分批多臂老虎机问题在临床试验等场景中至关重要。以往研究假设奖励分布为轻尾，但现实常呈现重尾特性。本文针对重尾奖励，提出多臂与Lipschitz设置下的鲁棒分批算法。研究发现令人意外：在实例无关设置及Lipschitz设置中，尾部越重，实现近似最优后悔值所需的批次数反而越少；而在实例相关设置中，达到近似最优后悔值所需的批次数不随尾部轻重变化。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。