Visible Tails: Characterizing Adaptation to Unknown Moments in Heavy-Tailed Bandits
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
| Work | Optimal-arm condition | Inputs | Competitor moment | Regret per arm |
| Bubeck et al. (2013) | moment of order | order | ||
| Genalti et al. (2024) | truncated non-positivity | none | raw, order | |
| Tamás et al. (2025) | symmetry about the mean, on every arm | none | some higher moment | gap-dependent |
| Ashutosh et al. (2021) | some higher moment | scaling function | some higher moment | superlogarithmic |
| Honda and Takemura (2015) | moment generating function near zero | upper endpoint | bounded above | |
| \Cref thm:integrability | central, order |
| Setting | Method | |||
|---|---|---|---|---|
| Theorem, | raw VT | 2793.3 | 2941.3 | 2999.1 |
| centered VT | 2865.7 | 2865.7 | 2865.7 | |
| Practical, | raw VT | 2472.3 | 2847.3 | 2997.9 |
| centered VT | 2252.1 | 2252.1 | 2252.1 |
Multi-Armed Bandits
Multi-Armed Bandits study how to choose among uncertain actions over time while balancing immediate rewards with learning.
See all 377 papers