Pure Exploration of Multi-Armed Bandits with Heavy-Tailed Payoffs

Inspired by heavy-tailed distributions in prac- tical scenarios, we investigate the problem on pure exploration of Multi-Armed Bandits (MAB) with heavy-tailed payoffs by breaking the assumption of payoffs with sub-Gaussian noises in MAB, and assuming that stochastic payoffs from bandits are with finite p-th mo- ments, where p $\in$(1, +$\infty$). The main contri- butions in this paper are three-fold. First, we technically analyze tail probabilities of empir- ical average and truncated empirical average (TEA) for estimating expected payoffs in se- quential decisions with heavy-tailed noises via martingales. Second, we propose two effective bandit algorithms based on different prior in- formation (i.e., fixed confidence or fixed bud- get) for pure exploration of MAB generating payoffs with finite p-th moments. Third, we derive theoretical guarantees for the proposed two bandit algorithms, and demonstrate the ef- fectiveness of two algorithms in pure explo- ration of MAB with heavy-tailed payoffs in synthetic data and real-world financial data.