Optimal Best Arm Identification with Fixed Confidence II: Characterization of the Optimal Proportions of Arm DrawsResearch Paper
In best arm identification with fixed confidence, a learner samples unknown distributions ("arms") sequentially and must name the arm with the largest mean, with error probability at most a prescribed , using as few samples as possible. Garivier and Kaufmann (arXiv:1602.04589, COLT 2016) showed that every -PAC strategy needs, in expectation,…