On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models

摘要

The stochastic multi-armed bandit model is a simple abstractionthat has proven useful in many different contexts in statisticsand machine learning. Whereas the achievable limit in terms ofregret minimization is now well known, our aim is to contributeto a better understanding of the performance in terms ofidentifying the $m$ best arms. We introduce generic notions ofcomplexity for the two dominant frameworks considered in theliterature: fixed-budget and fixed-confidence settings. In thefixed-confidence setting, we provide the first knowndistribution-dependent lower bound on the complexity thatinvolves information-theoretic quantities and holds when $mgeq1$ under general assumptions. In the specific case of two armed-bandits, we derive refined lower bounds in both the fixed-confidence and fixed-budget settings, along with matchingalgorithms for Gaussian and Bernoulli bandit models. Theseresults show in particular that the complexity of the fixed-budget setting may be smaller than the complexity of the fixed-confidence setting, contradicting the familiar behavior observedwhen testing fully specified alternatives. In addition, we alsoprovide improved sequential stopping rules that have guaranteederror probabilities and shorter average running times. Theproofs rely on two technical results that are of independentinterest : a deviation lemma for self-normalized sums (Lemma 7)and a novel change of measure inequality for bandit models(Lemma 1). color="gray">