Prediction with Expert Advice under Heavy-Tailed Losses

We study prediction with expert advice over T rounds with K experts under heavy-tailed losses whose (1+ε)-moment is bounded by θ>0 for some ε∈(0,1]. In this setting, existing algorithms designed for the case ε=1 can be suboptimal when ε<1, suffering an additional polynomial dependence on K. We characterize the minimax pseudo-regret rate as Theta((θ T)^frac11+ε(log K)^fracε1+ε) and establish gap-dependent lower bounds in a self-bounded environment. To attain this minimax rate without prior knowledge of either ε or θ, we propose Adaptive Heavy-Tailed FTRL, which uses robust data-dependent scale adaptation together with truncation. We further develop Adaptive Heavy-Tailed OMD, which likewise requires neither ε nor θ and achieves near-optimal regret guarantees in both adversarial and self-bounded environments. Finally, when ε and θ are known, an FTRL algorithm with Shannon-entropy regularization achieves optimal regret guarantees in both environments.