Optimal Top-Two Method for Best Arm Identification and Fluid Analysis

Top-2 methods have become popular in solving the best arm identification (BAI) problem. The best arm, or the arm with the largest mean amongst finitely many, is identified through an algorithm that at any sequential step independently pulls the empirical best arm, with a fixed probability β, and pulls the best challenger arm otherwise. The probability of incorrect selection is guaranteed to lie below a specified δ > 0. Information theoretic lower bounds on sample complexity are well known for BAI problem and are matched asymptotically as δ 0 by computationally demanding plug-in methods. The above top 2 algorithm for any β (0, 1) has sample complexity within a constant of the lower bound. However, determining the optimal β that matches the lower bound has proven difficult. In this paper, we address this and propose an optimal top-2 type algorithm. We consider a function of allocations anchored at a threshold. If it exceeds the threshold then the algorithm samples the empirical best arm.