Boltzmann Exploration for Heavy-Tailed Bandits

Hyeon-jun Park, Yoon-Sik Cho, Kyungjae Lee
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:1180-1188, 2026.

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\in(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(\nu^{\frac{1}{p}} K^{1-\frac{1}{p}} T^{\frac{1}{p}})$. It also attains the gap-dependent regret bound $O(\sum_{i:\Delta_i>0}{\log(T \Delta_i^{\frac{p}{p-1}}/K)}/{\Delta_i^{\frac{1}{p-1}}})$, where $\nu$ bounds the $p$-th moment, $K$ is the number of arms, $T$ is the horizon, and $\Delta_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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-park26a, title = { Boltzmann Exploration for Heavy-Tailed Bandits }, author = {Park, Hyeon-jun and Cho, Yoon-Sik and Lee, Kyungjae}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {1180--1188}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/park26a/park26a.pdf}, url = {https://proceedings.mlr.press/v300/park26a.html}, 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\in(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(\nu^{\frac{1}{p}} K^{1-\frac{1}{p}} T^{\frac{1}{p}})$. It also attains the gap-dependent regret bound $O(\sum_{i:\Delta_i>0}{\log(T \Delta_i^{\frac{p}{p-1}}/K)}/{\Delta_i^{\frac{1}{p-1}}})$, where $\nu$ bounds the $p$-th moment, $K$ is the number of arms, $T$ is the horizon, and $\Delta_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. } }
Endnote
%0 Conference Paper %T Boltzmann Exploration for Heavy-Tailed Bandits %A Hyeon-jun Park %A Yoon-Sik Cho %A Kyungjae Lee %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-park26a %I PMLR %P 1180--1188 %U https://proceedings.mlr.press/v300/park26a.html %V 300 %X 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\in(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(\nu^{\frac{1}{p}} K^{1-\frac{1}{p}} T^{\frac{1}{p}})$. It also attains the gap-dependent regret bound $O(\sum_{i:\Delta_i>0}{\log(T \Delta_i^{\frac{p}{p-1}}/K)}/{\Delta_i^{\frac{1}{p-1}}})$, where $\nu$ bounds the $p$-th moment, $K$ is the number of arms, $T$ is the horizon, and $\Delta_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.
APA
Park, H., Cho, Y. & Lee, K.. (2026). Boltzmann Exploration for Heavy-Tailed Bandits . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:1180-1188 Available from https://proceedings.mlr.press/v300/park26a.html.

Related Material