Minimax Policy for Heavy-tailed Bandits
This addresses the problem of robust decision-making in bandit algorithms for scenarios with heavy-tailed rewards, which is incremental as it builds on existing MOSS methods.
The paper tackles the stochastic Multi-Armed Bandit problem with heavy-tailed reward distributions by developing Robust MOSS, a modified minimax policy that achieves worst-case regret matching the lower bound and maintains distribution-dependent logarithmic regret when the reward distribution has a moment of order 1+ε.
We study the stochastic Multi-Armed Bandit (MAB) problem under worst-case regret and heavy-tailed reward distribution. We modify the minimax policy MOSS for the sub-Gaussian reward distribution by using saturated empirical mean to design a new algorithm called Robust MOSS. We show that if the moment of order $1+ε$ for the reward distribution exists, then the refined strategy has a worst-case regret matching the lower bound while maintaining a distribution-dependent logarithm regret.