Boltzmann Exploration for Heavy-Tailed Bandits

Abstract

We study the stochastic multi-armed bandit problem with heavy-tailed rewards, assuming only that each arm’s reward distribution has a finite p-th moment for p∈(1,2]. Although prior work has proposed algorithms that are robust to heavy-tailed rewards, these methods do not admit closed-form action-selection probabilities. This hinders efficient offline evaluation and can introduce bias in inverse propensity weighting (IPW) estimators. We propose heavy Boltzmann exploration (H-BE), a Boltzmann-style randomized policy whose action-selection probabilities remain available in closed form under heavy-tailed noise. Theoretically, we show that H-BE achieves the minimax-optimal gap-independent regret bound O(ν^1/p K^1-1/p T^1/p). It also attains the gap-dependent regret bound O(∑_i:Δ_i>0log(T Δ_i^p/p-1/K)/Δ_i^1/p-1), where ν bounds the p-th moment, K is the number of arms, T is the horizon, and Δ_i is the suboptimality gap of arm i. Empirically, H-BE attains competitive cumulative regret relative to state-of-the-art baselines, while its explicit propensities enable more stable and efficient offline evaluation.