Parameter-Free Heavy-Tailed Bandits

arXiv:2607.29460v1 Announce Type: new Abstract: 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 X satisfy E[|X|^{1+epsilon}]leq u, for some tail exponent epsilonin(0,1] and moment bound u0, while no algorithm can guarantee sublinear regret uniformly over all epsilonin(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.

Source: arXiv cs.LG | 2026-08-03