# Fundamental Limitations of Fixed-Budget Best-Arm Identification

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 20 references that are in the map.
- First posted on arXiv 13 Jul 2026.

## Builds on (most cited first, 11 of 11)

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Explore First, Exploit Next: The True Shape of Regret in Bandit Problems](https://mlsanity.com/paper/1602.07182/) (2016)
- [Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem](https://mlsanity.com/paper/1605.09004/) (2016)
- [Minimax Optimal Algorithms for Fixed-Budget Best Arm Identification](https://mlsanity.com/paper/2206.04646/) (2022)
- [On the Existence of a Complexity in Fixed Budget Bandit Identification](https://mlsanity.com/paper/2303.09468/) (2023)
- [Open Problem: Optimal Best Arm Identification with Fixed Budget](https://mlsanity.com/paper/2303.00950/) (2023)
- [Best Arm Identification with Fixed Budget: A Large Deviation Perspective](https://mlsanity.com/paper/2312.12137/) (2023)
- [On Universally Optimal Algorithms for A/B Testing](https://mlsanity.com/paper/2308.12000/) (2023)
- [Analyzing and provably improving fixed budget ranking and selection algorithms](https://mlsanity.com/paper/1811.12183/) (2018)
- [Admissibility of Completely Randomized Trials: A Large-Deviation Approach](https://mlsanity.com/paper/2506.05329/) (2025)

## Abstract (arXiv)

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≥ 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 + fraclog(K)8right)-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.