Rate-optimal Design for Anytime Best Arm Identification
Junpei Komiyama, Kyoungseok Jang, Junya Honda · 2025
Read Rate-optimal Design for Anytime Best Arm Identification by Junpei Komiyama, Kyoungseok Jang, Junya Honda (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-23199.txt.
Introduction
Junpei Komiyama, Kyoungseok Jang, and Junya Honda design rate-optimal methods for finding the best arm among many options under a sampling budget. The problem models A/B testing, where each arm has an unknown average reward and samples are limited. Their framework covers algorithms that are minimax optimal up to a constant factor, generalizing fixed-budget work limited to one risk measure.
They propose Almost Tracking, a closed-form algorithm with a provable guarantee for anytime identification. Users need not fix the budget in advance to trust the answer. The results give testers a principled way to stop early with known error risk.
Catalog record
| CREATOR | Junpei Komiyama, Kyoungseok Jang, Junya Honda |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 113 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-23199
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Rate-optimal Design for Anytime Best Arm Identification Junpei Komiyama, Kyoungseok Jang, Junya Honda Abstract 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 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 H 1 H_{1} . 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. 1 Introduction In the Best Arm Identification (BAI) problem a learner sequentially samples from K arms with unknown means P_{1},\dots,P_{K} and wishes to output the arm with the largest mean. This classical pure exploration task underpins applications in A/B testing ( Li et al., 2010 ; Johari et al., 2017 ; Xiong et al., 2024 ) , clinical trials ( Villar et al., 2015 ; Aziz et al., 2021 ; Wang and Tiwari, 2023 ) , and adaptive control ( Koval et al., 2015 ; Paudel and Stein, 2023 ) . The fixed-budget setting, which aims to maximize identification accuracy after exactly T samples, captures scenarios where evaluation may be stopped externally (traffic shifts, budget exhaustion). Formally, an anytime algorithm consists of • Sampling strategy, which selects the sampling arm I(t) given the history up to round t-1 . • Recommendation strategy, which selects the recommendation arm J(t) , which is the estimate of the best arm given the history up to round t . Popular fixed-budget algorithms (SR ( Audibert et al., 2010 ) , SH ( Karnin et al., 2013 ) ) rely on elimination schedules that presuppose T ; anytime adaptations via doubling ( Zhao et al., 2023 ) sacrifice statistical efficiency by discarding earlier samples. We propose an alternative, Almost Tracking, that (i) never requires the horizon T , (ii) avoids elimination, and (iii) retains all observations while (iv) has provable minimax rates as desribed below. A natural performance measure of a BAI algorithm is the probability of error \mathrm{PoE}(\bm{P}):=\mathbb{P}(J(T)\neq i^{*}(\bm{P})) , which is the probability that the recommendation arm J(T) does not match the true best arm 1 1 1 In this paper, we identify the mean of the distribution P_{i} with the distribution itself, and assume the uniqueness of i^{*}(\bm{P}) . i^{*}(\bm{P})=\argmax_{i}P_{i} when the (unknown) true model is \bm{P} . The smaller \mathrm{PoE}(\bm{P}) is, the better the algorithm is. On this performance measure, it is generally important to consider the minimax optimality. This is because the performance of an algorithm typically involves a trade-off across different problem instances. 2 2 2 This contrasts with uniform optimality in the fixed-confidence setting; see Section 1.3 for a comparison. Specifically, an algorithm that performs exceptionally well for one problem instance \bm{P} may perform poorly for another problem instance \bm{P}^{\prime} ( Wang et al., 2024 ) . Consequently, in fixed-budget BAI, there is no universal notion of optimality. In view of this, minimax optimality is the following objective: Given a risk measure, minimize the risk of the algorithm in the worst-case instance. In fact, existing line of works ( Audibert et al., 2010 ; Karnin et al., 2013 ; Carpentier and Locatelli, 2016 ; Zhao et al., 2023 ) can be viewed as special classes of minimax optimal algorithms with a particular choice of risk measure (Section 1.3 ). In this context, Komiyama et al., 2022 derived a fundamental lower bound for any given risk measure, which implies that the optimal exploration allocation–i.e., the sampling proportions across arms–should be a function of the empirical means. However, establishing the corresponding theoretical rates for such an adaptive allocation is generally challenging due to the trackability issues discussed below, and hence most existing algorithms resort to less flexible exploration schedules than the theoretical optimum. A notable exception is a minimax optimal algorithm called delayed optimal tracking (DOT, Komiyama et al., 2022 ). However, DOT is completely intractable. It needs to solve a dynamic programming, and each step of the dynamic programming involves a non-convex optimization over K functions. 3 3 3 See Section J for the non-convexity of the objective. We desire a more practical algorithm that is easy to compute and implement. Contributions. Summary of our results: • Establish constant-factor approximation of the one-shot game optimum and a matching (up to factor two) achievability bound linking adaptive allocations to minimax rates (Section 2 ). • Introduce Almost Tracking: a closed-form, anytime sampling rule that attains minimax rate optimality (constant-factor) without knowing T , without discarding samples, and without any horizon-calibrated hyperparameter (Section 3 ). • Almost Tracking requires a constant-factor approximation of the optimal allocation function. For the canonical H_{1} risk measure, we derived a closed-form allocation formula (Section 4 ) • Demonstrate in synthetic minimax benchmarks and real datasets (OBD, MovieLens) consistent gains over anytime (DSH/DSR) and fixed-budget baselines (SR/SH/CR), despite using neither the budget T nor T -dependent tuning (Section 5 ). • Derive a tight characterization of Successive Rejects by deriving the exact error exponent (Section 6 ). 1.1 Minimax optimality The raw worst-case \mathrm{PoE} is not very meaningful since the identification of the best arm can be arbitrarily hard when the gap between the best arm and the other arms is small. A reasonable target to optimize is the minimax rate of the risk. Let H(\bm{P}):\mathcal{P}^{K}\rightarrow\mathbb{R}^{+}\cup\{\infty\} be a risk measure, where \mathcal{P} is the set of distributions. We then discuss the best possible rate R>0 such that \mathrm{PoE}(\bm{P})\leq\exp\left(-\frac{RT}{H(\bm{P})}+o(T)\right)\text{for all $\bm{P}$}. Definition 1 (Rate) . We use \mathrm{PoE}_{\mathcal{A}}(\bm{P}) to represent the probability of error when we use algorithm \mathcal{A} . The rate of algorithm \mathcal{A} is defined as R_{\mathcal{A}}:=\inf_{\bm{P}\in\mathbb{R}^{K}:|i^{*}(\bm{P})|=1}H(\bm{P})\liminf_{T\to\infty}\frac{1}{T}\log(1/\mathrm{PoE}_{\mathcal{A}}(\bm{P})). Since it takes the minimum over all instances of K arms, the rate R_{\mathcal{A}} depends on K . For the most widely-studied risk measure H_{1}(\bm{P}) (Section 4 ), the best algorithm has R_{\mathcal{A}}=\Theta(1/(\log K)) . Definition 2 . (Rate-optimality) An algorithm is rate-optimal (or minimax optimal up to a constant factor) if there exists a universal constant 4 4 4 A constant is universal if it is independent of model parameters, such as K and \mathcal{P} . C>0 such that, for any K and for any other algorithm \mathcal{A}^{*} , R_{\mathcal{A}}\geq CR_{\mathcal{A}^{*}} holds. 1.2 Large deviation Let n_{i} be the number of samples on arm i . It is known as a large deviation theory ( Dembo and Zeitouni, 2010 ) that the empirical mean Q_{i} becomes Q with probability roughly given as \mathbb{P}[Q_{i}\approx Q]=\mathrm{poly}(n_{i})\exp\left(-n_{i}D(Q\|P_{i})\right), where \mathrm{poly}(n_{i}) is a polynomial factor and D(\cdot\|\cdot) is the Kullback-Leibler (KL) divergence. It applies to a broad class of distributions, including members of the exponential family such as Bernoulli, Multinomial, and Gaussian distributions. Accordingly, our results in Section 2