Our paper on stochastic multi-armed bandits with heavy tailed rewards is accepted to NeurIPS 2020


The following paper is accepted to Neural Information Processing Systems (NeurIPS 2020),

  • Optimal Algorithms for Stochastic Multi-Armed Bandits with Heavy Tailed Rewards by Kyungjae Lee, Hongjun Yang, Sungbin Lim, and Songhwai Oh
    • Abstract:In this paper, we consider stochastic multi-armed bandits (MABs) with heavy-tailed rewards, whose p-th moment is bounded by a constant nu_p for 1<p<=2. First, we propose a novel robust estimator where information about nu_p is not required in prior, while other existing robust estimators demand the constant nu_p as prior information. 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 regret analysis scheme that provides upper and lower regret bounds for a general perturbation 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 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 simulations, 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.