Quantum Heavy-tailed Bandits

In this paper, we study multi-armed bandits (MAB) and stochastic linear bandits (SLB) with heavy-tailed rewards and quantum reward oracle. Unlike the previous work on quantum bandits that assumes bounded/sub-Gaussian distributions for rewards, here we investigate the quantum bandits problem under a weaker assumption that the distributions of rewards only have bounded (1+v)-th moment for some v∈ (0,1]. In order to achieve regret improvements for heavy-tailed bandits, we first propose a new quantum mean estimator for heavy-tailed distributions, which is based on the Quantum Monte Carlo Mean Estimator and achieves a quadratic improvement of estimation error compared to the classical one. Based on our quantum mean estimator, we focus on quantum heavy-tailed MAB and SLB and propose quantum algorithms based on the Upper Confidence Bound (UCB) framework for both problems with TildeO(T^frac1-v1+v) regrets, polynomially improving the dependence in terms of T as compared to classical (near) optimal regrets of TildeO(T^frac11+v), where T is the number of rounds. Finally, experiments also support our theoretical results and show the effectiveness of our proposed methods.