Fixing the Loose Brake: Exponential-Tailed Stopping Time in Best Arm Identification

The best arm identification problem requires identifying the best alternative (i.e., arm) in active experimentation using the smallest number of experiments (i.e., arm pulls), which is crucial for costefficient and timely decision-making processes. We consider the fixed confidence setting where an algorithm repeatedly selects arms until it decides to stop and then returns the estimated best arm with a correctness guarantee. Since this stopping time is random, we desire its distribution to have light tails. Unfortunately, many existing studies focus on guarantees that hide the issue of allowing heavy tails or even not stopping at all. Indeed, we show that the never-stopping event can indeed happen for standard algorithms. Motivated by this, we make two theoretical contributions. First, we show that there exists an algorithm that attains a desirable exponential-tailed stopping time guarantee that is strictly better than the polynomial tail bound of Kalyanakrishnan et al. (2012) and the exponential guarantee obtained by uniform sampling. Our guarantee is more fundamental than existing ones in the sense that our guarantee implies that it achieves existing optimal guarantees up to logarithmic factors. Second, we show that there exists a meta algorithm that takes in any fixed confidence algorithm with a high probability stopping guarantee and turns it into one that enjoys an exponential-tailed stopping time with a matching instance-dependent complexity up to logarithmic factors. Our results imply that there might be much more to be desired for contemporary fixed confidence algorithms.