# Rate-optimal Design for Anytime Best Arm Identification

arXiv: https://arxiv.org/abs/2510.23199 · HTML: https://mlsanity.com/paper/2510.23199/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Oct 2025.

## Built on by (most cited first, 1 of 1)

- [Does 1/2-Tsallis-INF Also Work Well for Best-Arm Identification?](https://mlsanity.com/paper/2608.15365/) (2026)

## Abstract (arXiv)

We consider the best arm identification problem, where the goal is to identify the arm with the highest mean reward from a set of K arms under a limited sampling budget. This problem models many practical scenarios such as A/B testing. We consider a class of algorithms for this problem, which is provably minimax optimal up to a constant factor. This idea is a generalization of existing works in fixed-budget best arm identification, which are limited to a particular choice of risk measures. Based on the framework, we propose Almost Tracking, a closed-form algorithm that has a provable guarantee on the popular risk measure H1. Unlike existing algorithms, Almost Tracking does not require the total budget in advance nor does it need to discard a significant part of samples, which gives a practical advantage. Through experiments on synthetic and real-world datasets, we show that our algorithm outperforms existing anytime algorithms as well as fixed-budget algorithms.