Pith. sign in

REVIEW 5 minor 20 references

Fundamental Limitations of Fixed-Budget Best-Arm Identification

T0 review · 0 major / 5 minor · reviewed 2026-07-14 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For three or more arms, no fixed-budget algorithm can match the static oracle's error-decay rate on every problem instance, so the problem admits no complexity.

desk verdict Clean negative answer to Qin’s open question: fixed-budget BAI has no complexity for K≥3 under any one-parameter NEF. read the letter →

arxiv 2607.11635 v1 pith:5DEHJ3YF submitted 2026-07-13 cs.LG stat.ML

Motti Goldberger This is my paper
classification cs.LGstat.ML
keywords fixed-budgetbest-armidentificationrankingandselectionstaticoraclecomplexitymulti-armedbanditsnaturalexponentialfamilydifficultyratiolargedeviations
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

In fixed-budget best-arm identification an algorithm must spread a fixed number of samples across K arms and then name the arm with the highest mean. The natural benchmark is the static oracle: a non-adaptive strategy that already knows the means and picks the sampling proportions that maximize the exponential rate at which the chance of a wrong answer goes to zero. Many adaptive algorithms have been designed so that their sampling fractions converge to those oracle proportions, yet it was unknown whether any single procedure could actually attain the oracle rate on every instance. This paper proves that the answer is no whenever K is at least three and the rewards come from any regular one-parameter natural exponential family. For every consistent algorithm there exists at least one mean vector on which the error probability decays at most a factor (1 + log(K)/8)^(-1) times as fast as the static oracle. Consequently the problem cannot possess a complexity in the sense that a single hardness function is both a universal upper bound and uniformly achievable.

What carries the argument

The difficulty-ratio inequality of Degenne (Theorem 1) together with an explicit family of instances (a baseline x^(L) and alternatives λ_A, λ_B,3,…,λ_B,K) that force any fixed sampling allocation to leave at least one alternative under-sampled; local quadratic approximation of KL divergence then extends the Gaussian calculation to all regular one-parameter NEFs.

What would settle it

Exhibit a single algorithm family whose asymptotic difficulty ratio R_{H_so,∞} stays ≤ 1 on every instance in the constructed family {λ_A} ∪ {λ_B,j} for arbitrarily large L, or show that the right-hand side of Degenne's max-min expression can be made ≥ 1 for that family.

Watch

Extended reading notes

Core claim

When there are K ≥ 3 arms whose rewards belong to any regular one-parameter natural exponential family, every consistent algorithm family satisfies sup_μ R_{H_so,∞}(A,μ) ≥ 1 + Σ_{j=3}^K 1/(1+√(j-1))^2 > 1+(1/8)log(K). Therefore no algorithm attains the static-oracle decay rate Γ*_so uniformly over all instances, and fixed-budget best-arm identification admits no complexity.

Load-bearing premise

The argument assumes that the class of algorithms under consideration contains every static-proportion strategy, including the static oracle itself at each instance; without that inclusion, failure of the static oracle would not rule out every possible complexity.

Editorial extensions

If this is right

  • No adaptive procedure can be rate-optimal with respect to the static oracle uniformly over all mean vectors when K ≥ 3.
  • Any candidate complexity function H must fail either the universal lower-bound condition or the uniform-achievability condition.
  • Convergence of empirical sampling proportions to the static-oracle proportions does not imply matching the oracle's exponential error rate on every instance.
  • The same negative result holds for every regular one-parameter natural exponential family, not merely Gaussians or Bernoullis.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Algorithm designers should abandon the hope of a single 'optimal' hardness measure and instead study restricted classes (elimination methods, oracle-tracking methods) and large-deviation admissibility within those classes.
  • The logarithmic factor in the lower bound suggests that the price of not knowing the instance grows, albeit slowly, with the number of arms; tighter constructions may improve the constant 1/8.
  • The reduction via local quadratic approximation of KL indicates that the obstruction is geometric and should appear in any exponential-family model whose Fisher information is finite and continuous.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper proves that fixed-budget best-arm identification admits no complexity for K≥3 when rewards belong to any regular one-parameter natural exponential family. Using Degenne’s change-of-measure theorem, the authors construct explicit hard-instance families (baseline x^(L) together with alternatives λ_A and λ_B,j) on which every consistent algorithm family A satisfies sup_μ R_{H_so,∞}(A,μ) ≥ 1 + Σ_{j=3}^K 1/(1+√(j-1))^2 > 1+(1/8)log K. Consequently no algorithm can match the static-oracle decay rate Γ*_so uniformly, answering Qin’s open question. The Gaussian case (Theorem 2) is proved by direct calculation of KL sums and explicit upper bounds on H_so via concrete allocations (Lemma 2); the NEF extension (Theorem 3) reduces to the Gaussian case by a local quadratic approximation of KL (Lemma 3) after suitable rescaling.

Significance. The result closes a fundamental gap left by Degenne (2023) for 3≤K≤e^{80/3} and extends the negative answer from Gaussians/Bernoulli to all regular one-parameter NEFs. It rigorously shows that the static-oracle benchmark widely used in ranking-and-selection cannot be attained uniformly by any adaptive procedure when K≥3. The proofs are fully constructive (explicit instances, explicit allocations, elementary max-min lemma), contain no free parameters, and rely only on standard large-deviation and change-of-measure tools. The discussion of alternative targets (minimax, large-deviation admissibility) is a useful pointer for future work. These strengths make the paper a clear contribution to the theoretical foundations of fixed-budget BAI.

minor comments (5)
  1. Page 6, Step 1: the notation L_k for the sequence of means is never formally defined; a short sentence “let L_k = L^{k} (or any super-linear sequence)” would remove ambiguity.
  2. Lemma 2(a): the allocation α^A assigns mass (L-K+2)/(2L) to arms 1 and 2; a parenthetical remark that this is asymptotically 1/2 each would help the reader see the balancing immediately.
  3. Appendix A.1, Lemma A.2: the integral lower bound starts from 2 rather than 3; while correct, writing the sum from j=4 and handling the j=3 term separately would make the constant 1/8 slightly cleaner.
  4. Section 5: the citation “Imbens et al. (2025)” is listed as arXiv:2506.05329; confirm the year/status before final publication.
  5. Throughout: the o_L(1) notation is used both for sequences vanishing as L o∞ and inside (1+o_L(1)) factors; a single sentence defining the convention would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: pure existence proof via change-of-measure and explicit hard-instance constructions with no fitted quantities or self-referential definitions.

full rationale

The paper's central claim (no complexity for fixed-budget BAI when K≥3) is obtained by (i) recalling the standard definition that any candidate complexity H must dominate H_so because C_cons contains all static-proportion algorithms (Def. 1 and §2.2), (ii) invoking Degenne's external change-of-measure theorem (Thm. 1) to convert uniform achievability into a max-min expression over allocations and alternatives, and (iii) exhibiting an explicit family of instances (baseline x^(L) together with λ_A and λ_B,j) for which that max-min is bounded by (1+∑ 1/c_j)^(-1)+o_L(1) with c_j=(1+√(j-1))^2. The Gaussian case (Thm. 2) uses only the closed-form KL and an explicit allocation to upper-bound H_so; the NEF extension (Thm. 3) reduces to the same calculation via the elementary local quadratic approximation of KL (Lem. 3, Taylor expansion). No parameter is fitted to data, no quantity is defined in terms of the claimed lower bound, and the only external results used (Glynn-Juneja static oracle, Degenne Thm. 1, standard KL calculus) are independent of the present author and of the target constant 1+(1/8)log K. The derivation is therefore self-contained and non-circular.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central impossibility rests on standard large-deviation / change-of-measure machinery, the classical static-oracle characterization, and the definition of complexity imported from Degenne. No free parameters are fitted; the numerical factor 1/8 is an analytic lower bound. No new physical or statistical entities are postulated.

assumptions (5)
  • domain assumption Degenne (2023) Theorem 1: for any consistent algorithm the inverse difficulty ratio is bounded by a static max-min involving KL divergences (change-of-measure + data-processing).
    Invoked as the sole bridge from adaptive algorithms to a static optimization; used in both Theorem 2 and Theorem 3.
  • standard math For Gaussian variance-1 rewards, KL(N(a,1)||N(b,1))=(a-b)^2/2 and the static-oracle rate is min_j (ω_b ω_j/(ω_b+ω_j))·(μ_b-μ_j)^2/2 (Glynn-Juneja / Lemma 1).
    Exact closed form used throughout Section 3.
  • standard math Regular one-parameter NEFs admit a local quadratic approximation of KL: near any θ_0, KL(θ,θ')=(1±δ)(θ-θ')^2/(2v_0) (Lemma 3).
    Standard Taylor expansion of the log-partition function; enables the reduction of Theorem 3 to the Gaussian geometry.
  • domain assumption The admissible class C_cons contains all static-proportion algorithms that put positive mass on every arm; therefore any complexity H must satisfy H_so/H ≥ 1.
    Stated in §2.2; without it, failure of H_so would not rule out every possible complexity.
  • domain assumption Best arm is unique (instances restricted to Θ_u^K) and algorithms are consistent (error probability →0 on every such instance).
    Built into the definitions of C_cons and of complexity; standard for asymptotic BAI analyses.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fundamental Limitations of Fixed-Budget Best-Arm Identification." pith.science (2026). https://pith.science/paper/5DEHJ3YF

@misc{pith2026260711635,
  author       = {Pith},
  title        = {Pith review of: Fundamental Limitations of Fixed-Budget Best-Arm Identification},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5DEHJ3YF}},
  note         = {Machine review of arXiv:2607.11635}
}
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.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

20 extracted references · 2 linked inside Pith

  1. [1]

    Proceedings of the Conference On Learning Theory

    Audibert JY, Bubeck S, Munos R (2010) Best arm identification in multi-armed bandits. Proceedings of the Conference On Learning Theory

    2010

  2. [2]

    Proceedings of the 2021 Winter Simulation Conference

    Avci H, Nelson B, W \"a chter A (2021) Getting to ``rate-optimal'' in ranking & selection. Proceedings of the 2021 Winter Simulation Conference

    2021

  3. [3]

    Proceedings of the Conference on Learning Theory

    Carpentier A, Locatelli A (2016) Tight (lower) bounds for the fixed budget best arm identification bandit problem. Proceedings of the Conference on Learning Theory

    2016

  4. [4]

    Advances in Applied Probability 51(1):209--235

    Chen Y, Ryzhov I (2019) Complete expected improvement converges to an optimal budget allocation. Advances in Applied Probability 51(1):209--235

    2019

  5. [5]

    Management Science 69(6):3457--3473

    Chen Y, Ryzhov I (2023) Balancing optimal large deviations in sequential selection. Management Science 69(6):3457--3473

    2023

  6. [6]

    Proceedings of the 36th Annual Conference on Learning Theory

    Degenne R (2023) On the existence of a complexity in fixed budget bandit identification. Proceedings of the 36th Annual Conference on Learning Theory

    2023

  7. [7]

    Proceedings of the 29th Annual Conference on Learning Theory

    Garivier A, Kaufmann E (2016) Optimal best arm identification with fixed confidence. Proceedings of the 29th Annual Conference on Learning Theory

    2016

  8. [8]

    Mathematics of Operations Research 44(2):377--399

    Garivier A, M\' e nard P, Stoltz G (2019) Explore first, exploit next: The true shape of regret in bandit problems. Mathematics of Operations Research 44(2):377--399

    2019

Show all 20 references
  1. [9]

    Proceedings of the 2004 Winter Simulation Conference

    Glynn P, Juneja S (2004) A large deviations perspective on ordinal optimization. Proceedings of the 2004 Winter Simulation Conference

    2004

  2. [10]

    Proceedings of the 2011 Winter Simulation Conference

    Glynn P, Juneja S (2011) Ordinal optimization: A nonparametric framework. Proceedings of the 2011 Winter Simulation Conference

    2011

  3. [11]

    ArXiv preprint arXiv:2506.05329

    Imbens G, Qin C, Wager S (2025) Admissibility of completely randomized trials: A large-deviation approach. ArXiv preprint arXiv:2506.05329

    2025 arXiv

  4. [12]

    Proceedings of the 30th International Conference on Machine Learning

    Karnin Z, Koren T, Somekh O (2013) Almost optimal exploration in multi-armed bandits. Proceedings of the 30th International Conference on Machine Learning

    2013

  5. [13]

    JMLR 17(1):1--42

    Kaufmann E, Capp\' e O, Garivier A (2016) On the complexity of best-arm identification in multi-armed bandit models. JMLR 17(1):1--42

    2016

  6. [14]

    Proceedings of the 36th Conference on Neural Information Processing Systems

    Komiyama J, Tsuchiya T, Honda J (2022) Minimax optimal algorithms for fixed-budget best arm identification. Proceedings of the 36th Conference on Neural Information Processing Systems

    2022

  7. [15]

    Journal of the Royal Statistical Society 97(4):558--625

    Neyman J (1934) On the two different aspects of the representative method: The method of stratified sampling and the method of purposive selection. Journal of the Royal Statistical Society 97(4):558--625

    1934

  8. [16]

    Proceedings of the 35th Annual Conference on Learning Theory

    Qin C (2022) Open problem: Optimal best arm identification with fixed budget. Proceedings of the 35th Annual Conference on Learning Theory

    2022

  9. [17]

    Operations Research 66(6):1693--1712

    Shin D, Broadie M, Zeevi A (2018) Tractable sampling strategies for ordinal optimization. Operations Research 66(6):1693--1712

    2018

  10. [18]

    Proceedings of the 41st International Conference on Machine Learning

    Wang PA, Ariu K, Proutiere A (2024) On universally optimal algorithms for A/B testing. Proceedings of the 41st International Conference on Machine Learning

    2024

  11. [19]

    Proceedings of the 37th Conference on Neural Information Processing Systems

    Wang PA, Tzeng RC, Proutiere A (2023) Best arm identification with fixed budget: A large deviation perspective. Proceedings of the 37th Conference on Neural Information Processing Systems

    2023

  12. [20]

    ArXiv preprint arXiv:1811.12183

    Wu D, Zhou E (2018) Analyzing and provably improving fixed budget ranking and selection algorithms. ArXiv preprint arXiv:1811.12183

    2018 arXiv

Pith tools

Reviewed July 14, 2026 · model on record in the stance chip above.