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

Jul 31, 2026

Parameter-Free Heavy-Tailed Bandits

Heavy-tailed distributions arise naturally in sequential decision-making problems such as financial investment, online advertising, and network management, where rare but extreme outcomes can dominate performance. Heavy-tailed bandits model online decision-making in these settings by assuming only that rewards XX satisfy E[∣X∣1+ε]≤u\mathbb{E}[|X|^{1+ε}]\leq u, for some tail exponent ε∈(0,1]ε\in(0,1] and moment bound u<+∞u<+\infty. However, most existing regret minimization algorithms require these parameters to be known. This assumption is particularly restrictive in practice: εε and uu govern the frequency and magnitude of rare events and are therefore precisely the quantities that are hardest to infer reliably from limited observations. Motivated by an open problem posed by Genalti and Metelli at COLT 2025, we resolve the assumption-free adaptation problem for heavy-tailed bandits and characterize the price in the regret of not knowing the tail parameters. We first study adaptation to the moment bound uu for a fixed tail exponent εε. We prove that every algorithm unaware of uu, or of any upper bound on it, must obey a sharp trade-off between its distribution-dependent and distribution-free regret guarantees. We then introduce a scheduled-exploration algorithm that requires no knowledge of uu and matches the resulting adaptation frontier up to logarithmic factors. Finally, we show that the same algorithm can be instanced without knowing εε by calibrating its exploration schedule to the endpoint ε=1ε=1. It achieves sublinear regret for every fixed ε>0ε>0, while no algorithm can guarantee sublinear regret uniformly over all ε∈(0,1]ε\in(0,1]. Altogether, our results resolve the COLT open problem without additional distributional assumptions and provide a sharp characterization of the statistical cost of adapting to unknown heavy tails.
Apr 16, 2026

Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards

We study the tail behavior of regret in stochastic multi-armed bandits for algorithms that are asymptotically optimal in expectation. While minimizing expected regret is the classical objective, recent work shows that even such algorithms can exhibit heavy regret tails, incurring large regret with non-negligible probability. Existing sharp characterizations of regret tails are largely restricted to parametric settings, such as single-parameter exponential families. In this work, we extend the \KLinf\KLinf-UCB algorithm of to a broad nonparametric class of reward distributions satisfying mild assumptions, and establish its asymptotic optimality in expectation. We then analyze the tail behavior of its regret and derive a novel upper bound on the regret tail probability. As special cases, our results recover regret-tail guarantees for both bounded-support and heavy-tailed (moment-bounded) bandit models. Moreover, for the special case of finitely-supported reward distributions, our upper bound matches the known lower bound exactly. Our results thus provide a unified and tight characterization of regret tails for asymptotically optimal KL-based UCB algorithms, going beyond parametric models.
Aug 2, 2026

Sharp Characterization of Bias in Post-Bandit Inference

Bandit algorithms generate data for downstream inference, but adaptive sampling biases post-bandit sample means. We analyze this bias for stable index algorithms, including UCB1 and its generalizations, and derive sharp leading-order expressions for the sample-mean bias and expected ZZ-statistic, in bandit experiments of fixed horizon TT. Our characterization reveals the algorithmic origin of bias through a key index-function-dependent quantity, which we term effective exploration rate. For example, under UCB1, the effective exploration rate is of order log⁡T\sqrt{\log T}, and the standardized bias of any arm (that is not uniquely optimal) decays at the extremely slow rate 1/log⁡T1/\sqrt{\log T}. We also show how the choice of the index function affects both regret and bias, which reveals a regret-bias trade-off: more exploratory algorithm reduces bias but increases regret. We further show how bias most severely distorts confidence intervals and hypothesis tests when the tested arm is one of the tied-optimal arms. Our sharp characterization for bias uses a novel empirical fluid approximation of the algorithm's sampling dynamics, which may be of independent interest.