2020/10/24 by Kyungjae Lee, Hongjun Yang, Lee, Kyungjae +5 · 2 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Optimization and Search Problems #Reinforcement Learning in Robotics #Risk and Portfolio Optimization
paper · pdf · doi:10.48550/arxiv.2010.12866
openalex publication_date 2020/10/24 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
In this paper, we consider stochastic multi-armed bandits (MABs) with\nheavy-tailed rewards, whose p-th moment is bounded by a constant \νp\nfor 1<p\≤2. First, we propose a novel robust estimator which does not\nrequire \νp as prior information, while other existing robust estimators\ndemand prior knowledge about \νp. We show that an error probability of\nthe proposed estimator decays exponentially fast. Using this estimator, we\npropose a perturbation-based exploration strategy and develop a generalized\nregret analysis scheme that provides upper and lower regret bounds by revealing\nthe relationship between the regret and the cumulative density function of the\nperturbation. From the proposed analysis scheme, we obtain gap-dependent and\ngap-independent upper and lower regret bounds of various perturbations. We also\nfind the optimal hyperparameters for each perturbation, which can achieve the\nminimax optimal regret bound with respect to total rounds. In simulation, the\nproposed estimator shows favorable performance compared to existing robust\nestimators for various p values and, for MAB problems, the proposed\nperturbation strategy outperforms existing exploration methods.\n