Sample mean based index policies byO(logn) regret for the multi-armed bandit problem

Publisher Website
Google Scholar
Abstract
We consider a non-Bayesian infinite horizon version of the multi-armed bandit problem with the objective of designing simple policies whoseregretincreases slowly with time. In their seminal work on this problem, Lai and Robbins had obtained aO(logn) lower bound on the regret with a constant that depends on the Kullback–Leibler number. They also constructed policies for some specific families of probability distributions (including exponential families) that achieved the lower bound. In this paper we construct index policies that depend on the rewards from each arm only through their sample mean. These policies are computationally much simpler and are also applicable much more generally. They achieve aO(logn) regret with a constant that is also based on the Kullback–Leibler number. This constant turns out to be optimal for one-parameter exponential families; however, in general it is derived from the optimal one via a ‘contraction' principle. Our results rely entirely on a few key lemmas from the theory of large deviations.