COLT 2025 Papers

The heavy-tailed bandit problem Bubeck et al.,2013 , is a variant of the stochastic multi-armed bandit problem where the reward distributions have finite absolute raw moments of maximum order 1+ϵ, uniformly bounded by a constant u < +∞, for some ϵ∈ (0,1]. In this setting, most of the proposed approaches crucially rely on the knowledge of both ϵ and u. Recent works have highlighted that adapting to such parameters when they are unknown is harder than adapting to the subgaussian constant or the rewards range in non-heavy-tailed bandits. It is known that it is not possible to adapt to either ϵ or u without either (i) incurring extra regret or (ii) enforcing additional assumptions. However, it remains an open question what the best attainable performance is when no additional assumptions are provided. Moreover, the assumptions proposed in the literature are not comparable, as none of them is strictly weaker than the others. Thus, another open question is about the nature of the assumptions needed to compensate for this cost.