Pure Exploration of Multi-Armed Bandits with Heavy-Tailed Payoffs
Abstract
Inspired by heavy-tailed data distributions in real scenarios, we investigate the problem on pure exploration of Multi-Armed Bandits (MAB) with heavy-tailed payoffs by breaking the classic sub-Gaussian assumption in MAB, and assuming that stochastic payoffs from bandits are bounded by the p-th moment, where p ∈ (1, +∞). The main contributions in this paper are three-fold. First, we technically analyze tail probabilities of empirical average and truncated empirical average (TEA) for estimating expected payoffs in sequential decisions with heavy-tailed noises. Second, we propose two effective bandit algorithms based on different prior information (i.e., fixed confidence or fixed budget) for pure exploration of MAB, which generates payoffs with finite p-th moment. Third, we derive theoretical guarantees for the proposed two bandit algorithms, and demonstrate the effectiveness of two algorithms in pure exploration of MAB with heavy- tailed payoffs.
Authors: Xiaotian Yu, Han Shao, Michael Rung-Tsong Lyu, Irwin King
Published in: Uncertainty in Artificial Intelligence (2018)