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

Authors

Tuan Ngoc Do,Hai Duc Nguyen

Abstract

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.

Resources

Ray graphicRay graphicRay graphicRay graphic

Stay in the loop

Every AI paper that matters, free in your inbox daily.

Details

  • takara.ai
  • Custom AI and machine learning from the Frontier Research Team.
  • © 2026 takara.ai Ltd
  • Content is sourced from third-party publications.
Ray graphicRay graphicRay graphic