On Best-Arm Identification with a Fixed Budget in Non-Parametric Multi-Armed Bandits

Understand

We lay the foundations of a non-parametric theory of best-arm identification in multi-armed bandits with a fixed budget T.

• We consider general, possibly non-parametric, models D for distributions over the arms; an overarching example is the model D = P(0,1) of all probability distributions over [0,1].
• We propose upper bounds on the average log-probability of misidentifying the optimal arm based on information-theoretic quantities that correspond to infima over Kullback-Leibler divergences between some distributions in D and a given distribution.
• This is made possible by a refined analysis of the successive-rejects strategy of Audibert, Bubeck, and Munos (2010).