Optimal Algorithms for Stochastic Multi-Armed Bandits with Heavy Tailed Rewards
This work addresses the challenge of handling heavy-tailed rewards in bandit problems, which is incremental but improves robustness and optimality for applications in decision-making under uncertainty.
The paper tackles the problem of stochastic multi-armed bandits with heavy-tailed rewards by proposing a novel robust estimator that does not require prior knowledge of moment bounds, and a perturbation-based exploration strategy that achieves minimax optimal regret bounds, with simulations showing favorable performance compared to existing methods.
In this paper, we consider stochastic multi-armed bandits (MABs) with heavy-tailed rewards, whose $p$-th moment is bounded by a constant $ν_{p}$ for $1<p\leq2$. First, we propose a novel robust estimator which does not require $ν_{p}$ as prior information, while other existing robust estimators demand prior knowledge about $ν_{p}$. We show that an error probability of the proposed estimator decays exponentially fast. Using this estimator, we propose a perturbation-based exploration strategy and develop a generalized regret analysis scheme that provides upper and lower regret bounds by revealing the relationship between the regret and the cumulative density function of the perturbation. From the proposed analysis scheme, we obtain gap-dependent and gap-independent upper and lower regret bounds of various perturbations. We also find the optimal hyperparameters for each perturbation, which can achieve the minimax optimal regret bound with respect to total rounds. In simulation, the proposed estimator shows favorable performance compared to existing robust estimators for various $p$ values and, for MAB problems, the proposed perturbation strategy outperforms existing exploration methods.