  This paper investigates a hitherto unaddressed aspect of best arm
identification (BAI) in stochastic multi-armed bandits in the fixed-confidence
setting. Two key metrics for assessing bandit algorithms are computational
efficiency and performance optimality (e.g., in sample complexity). In
stochastic BAI literature, there have been advances in designing algorithms to
achieve optimal performance, but they are generally computationally expensive
to implement (e.g., optimization-based methods). There also exist approaches
with high computational efficiency, but they have provable gaps to the optimal
performance (e.g., the $\beta$-optimal approaches in top-two methods). This
paper introduces a framework and an algorithm for BAI that achieves optimal
performance with a computationally efficient set of decision rules. The central
process that facilitates this is a routine for sequentially estimating the
optimal allocations up to sufficient fidelity. Specifically, these estimates
are accurate enough for identifying the best arm (hence, achieving optimality)
but not overly accurate to an unnecessary extent that creates excessive
computational complexity (hence, maintaining efficiency). Furthermore, the
existing relevant literature focuses on the family of exponential
distributions. This paper considers a more general setting of any arbitrary
family of distributions parameterized by their mean values (under mild
regularity conditions). The optimality is established analytically, and
numerical evaluations are provided to assess the analytical guarantees and
compare the performance with those of the existing ones.
