The True Sample Complexity of Identifying Good Arms

Julian Katz-Samuels, Kevin Jamieson

We consider two multi-armed bandit problems with $n$ arms: (i) given an $\epsilon >0$, identify an arm with mean that is within $\epsilon$ of the largest mean and (ii) given a threshold ${\mu }_0$ an…