cs.LGNov 9, 2026

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

Authors: Tuan Ngoc Do, Hai Duc Nguyen

Organizations: Phenikaa School of Information Technology, Phenikaa University, Hanoi 12116, Vietnam · College of Computing and Data Science, Nanyang Technological University, Singapore

Abstract

Heavy-tailed bandit learners must tell a poor arm from an arm whose favorable rewards have not yet appeared. We characterize this obstruction through a scale of one-sided visibility conditions on the optimal reward law: the mean hidden in a rare event is at most a constant multiple of a retained central moment. A quantile-trimmed UCB index that is given the visibility constants attains arm-specific moment rates at every exponent, with no lower bound on the exponent. Conversely, every strategy with a fixed exploration budget has polynomial regret on each law that violates the corresponding condition. For the variance benchmark we determine the order of both budget constants in the visibility level. The frontier depends on the largest exponent the benchmark promises, and the resulting classes are strictly nested. The same index has logarithmic expected regret when rewards are integrable, with a coefficient that can be exponential in the inverse gap.

Figures & tables

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Parameter-Free Heavy-Tailed Bandits

    Jul 31, 2026Gianmarco Genalti, Alberto Maria MetelliMulti-Armed BanditsHeavy-Tailed Noise

  2. Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards

    Apr 16, 2026Subhodip Panda, Shubhada AgrawalMulti-Armed BanditsUCB Algorithms

  3. Sharp Characterization of Bias in Post-Bandit Inference

    Aug 2, 2026Lisu Wang, Yilun Chen, Jiaqi LuMulti-Armed BanditsAlgorithmic Bias