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

원문 초록

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 $\Delta$ and constant $A$, its logarithmic coefficient and the information lower bound are of order $\Delta^{-1}e^{A/\Delta}$, exponential in the inverse gap within one visibility class.