Posterior-Tracking for Best-Arm Identification in Bernoulli Bandits

We study fixed-confidence best-arm identification in Bernoulli bandits. A learner sequentially samples from $K$ arms and aims to identify the unique best arm while keeping the error probability at most $\delta$. We ask whether the classical lower bound on expected sample complexity can be matched asymptotically without ongoing forced exploration. We propose a posterior-tracking algorithm that first samples each arm once, then repeatedly draws a bandit instance from the posterior, computes the oracle allocation for that instance, and randomly selects the next arm according to that allocation. Stopping is based on a Bernoulli generalized likelihood ratio test. Since the algorithm has no explicit forced-exploration mechanism after initialization, the main technical challenge is to show that posterior randomness alone sustains sufficient exploration. We prove that, with summable tail probabilities, every arm is sampled at least logarithmically often. This yields an integrable stabilization time after which the true best arm remains the empirical leader and the corresponding generalized likelihood ratio statistic grows linearly at the information-theoretic lower-bound rate. Consequently, the proposed procedure is $\delta$-correct and achieves asymptotically optimal expected sample complexity as $\delta \to 0$.