Fundamental Limitations of Fixed-Budget Best-Arm Identification

• URL: http://arxiv.org/abs/2607.11635v1
• Date: Mon, 13 Jul 2026 14:50:32 GMT
• Title: Fundamental Limitations of Fixed-Budget Best-Arm Identification
• Abstract summary: In fixed-budget best-arm identification, also known as ranking and selection, an algorithm has a sampling budget to distribute across $K$ arms.<n>We show that for any algorithm, there is at least one instance where the error decay rate is at most $left( + fraclog(K)8right)-1$ times that of the static oracle.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In fixed-budget best-arm identification, also known as ranking and selection, an algorithm has a sampling budget to distribute across $K$ arms. Each sample provides noisy feedback about that arm's mean, and the goal is to identify the arm with the largest mean. A common performance benchmark is the static oracle: a non-adaptive strategy that knows the means in advance and chooses fixed sampling proportions to maximize the exponential decay rate of the probability of incorrect identification. Several adaptive algorithms have been constructed such that their sampling proportions converge to the static oracle proportions. However, it has remained open whether any algorithm could match the static oracle's error decay rate uniformly across all problem instances. We answer this in the negative. For any $K\ge 3$ and for rewards drawn from any one-parameter natural exponential family, we show that for any algorithm, there is at least one instance where the error decay rate is at most $\left(1 + \frac{\log(K)}{8}\right)^{-1}$ times that of the static oracle. This also answers the open question posed by Qin (2022), showing that fixed-budget best-arm identification does not admit a complexity.

Related papers

• Bayesian Best-Arm Identification with Abstention: A Polynomial-to-Exponential Phase Transition [51.253617466579335]
  We study the Bayesian fixed-budget best-arm identification problem in which a learner can abstain from making a terminal recommendation.<n>We analyze the probability of undetected error--the risk of recommending a suboptimal arm without abstaining.
  arXiv  Detail & Related papers  (2026-06-28T05:07:27Z)
• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  We introduce a novel algorithm for best feasible arm identification that guarantees an exponential decay in the error probability.<n>We validate our algorithm through comprehensive empirical evaluations across various problem instances with different levels of complexity.
  arXiv  Detail & Related papers  (2025-06-03T02:56:26Z)
• An Algorithm for Fixed Budget Best Arm Identification with Combinatorial Exploration [3.9901365062418312]
  We consider the best arm identification problem in the $K-$armed bandit framework.<n>Agent is allowed to play a subset of arms at each time slot instead of one arm.<n>We propose an algorithm that constructs $log K$ groups and performs a likelihood ratio test to detect the presence of the best arm.
  arXiv  Detail & Related papers  (2025-02-03T15:10:08Z)
• Optimal Top-Two Method for Best Arm Identification and Fluid Analysis [15.353009236788262]
  We propose an optimal top-2 type algorithm for the best arm identification problem.<n>We show that the proposed algorithm is optimal as $delta rightarrow 0$.
  arXiv  Detail & Related papers  (2024-03-14T06:14:07Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  We present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms. In particular, we present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms.
  arXiv  Detail & Related papers  (2023-12-19T13:17:43Z)
• On the Existence of a Complexity in Fixed Budget Bandit Identification [0.0]
  In fixed budget bandit identification, an algorithm sequentially observes samples from several distributions up to a given final time. We show that there is no such complexity for several fixed budget identification tasks including Bernoulli best arm identification with two arms.
  arXiv  Detail & Related papers  (2023-03-16T16:39:00Z)
• On the Sample Complexity of Representation Learning in Multi-task Bandits with Global and Local structure [77.60508571062958]
  We investigate the sample complexity of learning the optimal arm for multi-task bandit problems. Arms consist of two components: one that is shared across tasks (that we call representation) and one that is task-specific (that we call predictor) We devise an algorithm OSRL-SC whose sample complexity approaches the lower bound, and scales at most as $H(Glog(delta_G)+ Xlog(delta_H))$, with $X,G,H$ being, respectively, the number of tasks, representations and predictors.
  arXiv  Detail & Related papers  (2022-11-28T08:40:12Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  This paper proposes two algorithms, a gap-based algorithm and one based on the successive elimination, for best arm identification in sub-Gaussian bandits. Specifically, for the gap-based algorithm, the sample complexity is optimal up to constant factors, while for the successive elimination, it is optimal up to logarithmic factors.
  arXiv  Detail & Related papers  (2021-11-14T21:49:58Z)
• Robust Outlier Arm Identification [16.21284542559277]
  We study the problem of Robust Outlier Arm Identification (ROAI) The goal is to identify arms whose expected rewards deviate substantially from the majority. We compute the outlier threshold using the median and median absolute deviation of the expected rewards.
  arXiv  Detail & Related papers  (2020-09-21T16:13:01Z)
• Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
  We devise a simple algorithm whose sampling complexity matches known instance-specific lower bounds. Unlike existing best-arm identification strategies, our algorithm uses a stopping rule that does not depend on the number of arms.
  arXiv  Detail & Related papers  (2020-06-29T14:25:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.