{"id":"a0c3ddbc-f778-47dd-8dc8-437cf7e422a2","arxiv_id":"2607.11635","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For K≥3 arms from any one-parameter natural exponential family, every algorithm falls short of the static oracle error-decay rate by a factor at least (1+log(K)/8) on some instance, so fixed-budget BAI admits no complexity.","lead":"No algorithm for fixed-budget best-arm identification can match the static oracle's error-decay rate on every problem when there are three or more arms. This settles an open question: the problem has no single instance-dependent complexity that is both a universal upper bound and uniformly achievable.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader correctly isolates the only non-trivial modeling choice—the inclusion of static algorithms inside C—and notes that it is the conventional one for the open question being answered. The technical development (instance family, application of Degenne’s change-of-measure bound, local quadratic approximation of KL) contains no load-bearing soft spot that would overturn the impossibility. The concrete check above merely reconfirms an intermediate coefficient; even if that coefficient were slightly worse the qualitative statement “no complexity for K≥3” would survive. Hence the ACCEPT verdict stands.","tokens_in":17540,"tokens_out":488,"duration_ms":4950,"concrete_test":"Independently re-derive the upper bound on H_so(λ_{B,j}) in Lemma 2(b) for the explicit allocation α given in the appendix (balancing the j-1 close arms and vanishing mass on distant arms); confirm that the resulting min over challengers is still L^{2j+1}/(2(1+√(j-1))^2)(1+o_L(1)). If the coefficient is larger, the log-K lower bound weakens but the qualitative claim (ratio >1 for all K≥3) remains.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central impossibility is self-contained and correctly reduces non-existence of complexity to non-uniform achievability of H_so. The reduction in §2.2 / Def. 1 is the standard one used by the literature the paper addresses (Degenne 2023, Qin 2022): any candidate complexity H must satisfy H_so(μ)/H(μ)≥1 because C_cons contains every static-proportion algorithm (including the static oracle at each μ). The Gaussian construction (Thm. 2) produces an explicit family D_L on which the max-min of Thm. 1 is bounded by (1+Σ 1/c_j)^{-1}+o_L(1) with c_j=(1+√(j-1))^2, and the NEF extension (Thm. 3) is a routine localization via the quadratic approximation of KL (Lem. 3). No hidden assumption, circularity, or gap in the chain appears.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","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.","tokens_in":17766,"tokens_out":819,"duration_ms":14115,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"Section 5: the citation “Imbens et al. (2025)” is listed as arXiv:2506.05329; confirm the year/status before final publication.","section":null},{"comment":"Throughout: the o_L(1) notation is used both for sequences vanishing as L\to∞ and inside (1+o_L(1)) factors; a single sentence defining the convention would improve readability.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is technically solid and resolves a clean open question. I see no reason to request major changes; the empty major-comments list reflects that the central derivation is correct and self-contained. Fit for a theory-oriented ML/OR journal is excellent."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This paper settles the open question from Qin (2022) and Degenne (2023): fixed-budget best-arm identification does not admit a complexity when there are three or more arms. For any consistent algorithm and any regular one-parameter NEF, there is always some instance where the error-decay rate is at most roughly 1/(1+(1/8)log K) times the static-oracle rate. That is the punchline, and it is new for the full range K≥3 and for the whole NEF class.\n\nWhat is actually new is the explicit hard-instance family that works for every K≥3 (not just the huge-K Gaussian regime Degenne already had) together with the local-quadratic reduction that carries the same bound over to every regular NEF. The Gaussian proof is fully expanded: concrete means that grow with L, explicit allocations that upper-bound H_so, collapse of the KL sums to linear terms in the weights, and an elementary max-min lemma. The NEF step is the standard localization argument; nothing fancy, but correctly done.\n\nThe soft spots are minor and proportional. The constant 1/8 is not claimed to be tight; it comes from a crude integral lower bound and could probably be improved. Everything is asymptotic (large-T exponential rates), which is the right language for this problem but means the result says nothing about moderate budgets. The reduction that “failure of H_so implies no complexity at all” rests on the algorithm class containing the static-proportion oracles; that is exactly the convention used by the papers the author is answering, so it is not a hidden assumption.\n\nThis is for theorists who care about the foundations of fixed-budget BAI and ranking-and-selection. Anyone who has been tracking whether the static oracle is a uniform target will get immediate value. The math is self-contained, the citations are precise, and there is no data-fitting or circularity. I would send it to a serious referee without hesitation; the central claim holds up.","headline":"Clean negative answer to Qin’s open question: fixed-budget BAI has no complexity for K≥3 under any one-parameter NEF.","tokens_in":18396,"tokens_out":510,"would_cite":true,"duration_ms":8213,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"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.","keywords":["fixed-budget best-arm identification","ranking and selection","static oracle","complexity","multi-armed bandits","natural exponential family","difficulty ratio","large deviations"],"falsifier":"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.","tokens_in":18427,"feed_emoji":"🎯","tokens_out":1025,"duration_ms":12287,"temperature":0.7,"pith_summary":"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.","feed_headline":"Fixed-budget BAI has no complexity for three or more arms","feed_subtitle":"Every algorithm falls short of the static oracle rate on some instance, by a log(K) factor","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Fixed-budget BAI has no complexity for K≥3","No algorithm matches static-oracle rate on all BAI instances","Every BAI algorithm trails static oracle by log(K) factor somewhere","Fixed-budget best-arm ID admits no complexity for three or more arms","Static-oracle decay rate is unattainable uniformly in fixed-budget BAI"],"cache_read_input_tokens":128,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Fixed-budget BAI has no complexity for K≥3","No algorithm matches static-oracle rate on all BAI instances","Every BAI algorithm trails static oracle by log(K) factor somewhere","Fixed-budget best-arm ID admits no complexity for three or more arms","Static-oracle decay rate is unattainable uniformly in fixed-budget BAI"]},"model":"grok-4.5","effort":"low","cost_usd":0.003624,"raw_usage":{"total_tokens":1164,"prompt_tokens":792,"num_sources_used":0,"completion_tokens":97,"cost_in_usd_ticks":36240000,"prompt_tokens_details":{"text_tokens":792,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":275,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":792,"tokens_out":97,"duration_ms":2664,"temperature":1.0,"reasoning_tokens":275,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-14T04:13:12.042138+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"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.","supporting_citations":[],"review_version":1}