arXiv:2611.12140 · v1

Visible Tails: Characterizing Adaptation to Unknown Moments in Heavy-Tailed Bandits

首次提交 2026-11-09 17:53

版本更新 2026-11-09 17:53

雷达观测 2026-11-10 15:22

摘要

Heavy-tailed bandit learners without moment parameters face an obstruction: the rewards that carry an arm's mean can stay unseen. We address the remaining part of a COLT open problem by characterizing the optimal-arm laws that permit adaptation to unknown moments at constant-factor cost. The condition, variance-core visibility, is one-sided and translation-invariant: the mean hidden in any rare event is at most a constant multiple of the standard error of the rewards that remain. A quantile-trimmed UCB index that knows the visibility constants attains the central-moment benchmark on this class, and no single strategy adapts across all visibility levels. The same index achieves logarithmic expected regret on every instance with a visible optimal arm and finite-mean rewards. On an explicit family with no higher moment, gap $Δ$ and constant $A$, its logarithmic coefficient and the information lower bound are of order $Δ^{-1}e^{A/Δ}$, exponential in the inverse gap within one visibility class.