Gap Entropy and Almost Instance-Wise Optimal Best-Arm Identification
Jiarui Yao, Jiaxi Zhao, Xiangxin Zhou
cs.CC · cs.AI · cs.LG
Quick verdict
Resolves the Chen–Li gap-entropy conjectures; rigorous Lean 4-verified theory with original-instance lower bound; huge constants, AI-assisted writing.
Summary
The paper resolves two open conjectures of Chen and Li (COLT 2016) on fixed-confidence best-arm identification with n Gaussian arms (unit variance, means in [0,1]). Letting H(I) denote the sum of inverse squared gaps and Ent(I) the Shannon entropy of the normalized complexities of dyadic gap groups, it proves that the order-oblivious instance-wise lower bound is Θ(H(I)[log(1/δ) + Ent(I)]) for every 0<δ<0.1 (Theorem 2.1), removing the dyadic-gap restriction and the monotonicity-based sub-instance transfer of Chen et al. (2017). The lower bound symmetrizes over label permutations, couples the target instance to two-best-arm instances through a latent-variable construction, and charges all distribution changes to expected sample counts on the original instance (Appendix B). It also gives a single δ-correct algorithm — taking only arms and δ — with expected sample complexity O(H(I)[log(1/δ)+Ent(I)] + Δ_[2]^{-2}·ℓ(Δ_[2]^{-2})) (Theorem 2.2), eliminating the polylog(n, δ⁻¹) factor of the prior best bound, while the two-arm term remains additive as conjectured; correctness rests on stochastic domination by independent Bernoulli variables over a fixed nested family of near-optimal arm sets (Appendix E). All main theorems are machine-checked in Lean 4/Mathlib with explicit constants (Appendix I), which are, however, astronomically large (e.g., 6.4×10¹³). An AI-use statement discloses that derivations and formalization were primarily LLM-generated with model-based checking. Main limitations: constants preclude practical use, and part of the comparison to concurrent work sits outside the provided excerpt.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 2
● low 2
5 strengths · 4 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- For Gaussian best-arm identification with a unique best arm, the order-oblivious instance-wise lower bound is Θ(H(I)[log(1/δ)+Ent(I)]) for every 0<δ<0.1 (Theorem 2.1), with no dyadic-gap or monotonicity restrictions.
- A single δ-correct algorithm taking only the arms and δ achieves expected sample complexity O(H(I)[log(1/δ)+Ent(I)] + Δ_[2]^{-2}·ℓ(Δ_[2]^{-2})) (Theorem 2.2), matching the instance-wise lower bound up to the additive two-arm term.
- Together, Theorems 2.1 and 2.2 resolve Conjectures 3.5 and 3.2 of Chen and Li (COLT 2016), under an explicit positive truncation of the two-arm term.
- The main theorems, with explicit constants and the Appendix H algorithm-model extensions, are fully formalized and machine-checked in Lean 4/Mathlib (Appendix I).
Strengths
Full resolution of two open problems
Theorems 2.1 and 2.2 settle Conjectures 3.5 and 3.2 of Chen and Li (COLT 2016) for arbitrary positive gaps, all 0<δ<0.1, without the dyadic-gap restriction and monotone-algorithm transfer that limited Chen et al. [2017, Thm 1.12–1.13]; the polylog(n, δ⁻¹) factor on the two-arm term of Chen et al.'s Theorem 1.11 is removed.
Machine-checked main theorems with honest scope
Appendix I reports Lean 4/Mathlib verification with explicit constants (lower bound factor 1/5; instance-wise upper bound 6.4×10¹³; single algorithm 12(10¹²+1)) and precisely documents three deliberate deviations between formal and prose proofs, e.g., a supermartingale argument replacing the Poisson-coupling proof of Lemma E.1.
Lower bound charged entirely on the original instance
Unusually careful convention hygiene
Quantifier distinction made explicit
Weaknesses
Astronomical explicit constants
LLM-generated derivations with model-based checking
Substantial overlap with concurrent work
Delicate, analysis-driven correctness machinery with no visible empirical check
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
This theory paper (arXiv 2609.13703; cs.CC/cs.AI/cs.LG) resolves two open conjectures that Chen and Li posed at COLT 2016 for fixed-confidence best-arm identification with n≥2 independent unit-variance Gaussian arms, means in [0,1], and a unique maximum. Theorem 2.1 proves the order-oblivious instance-wise lower bound L(I,δ) = Θ(H(I)[log(1/δ)+Ent(I)]) for every 0<δ<0.1, where H(I)=Σ_{i≥2}Δ_[i]^{-2} and Ent(I) is the Shannon entropy of normalized dyadic gap-group complexities (Eq. 2.2). Theorem 2.2 gives a single δ-correct algorithm — inputs: arms and δ only — with expected sample complexity O(H(I)[log(1/δ)+Ent(I)] + Dℓ(D)), D=Δ_[2]^{-2}. Relative to Chen et al. [2017, Thm 1.11–1.13], the lower bound drops the dyadic-gap restriction and the monotone-algorithm transfer, and the upper bound drops the polylog(n, δ⁻¹) factor on the two-arm term. All main statements are machine-checked in Lean 4/Mathlib (Appendix I). An AI-use statement discloses that derivations and formalization were primarily produced by 'gpt-6-astra' and checked by 'claude-fable-5.1'.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 4 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is the gap entropy conjecture in best-arm identification?
In 2016, Chen and Li conjectured that the number of samples needed to find the best of n Gaussian arms with confidence 1−δ is characterized by H(I)·[log(1/δ)+Ent(I)], where H(I) sums inverse squared gaps and Ent(I) measures how many distinct gap scales carry comparable complexity — plus an additive two-arm term. This paper proves matching lower and upper bounds, resolving the conjecture.
Are the proofs computer-verified?
Yes — the main theorems, with explicit constants, are formalized and proved in Lean 4 on top of Mathlib; the code is public at github.com/zhouxiangxin1998/GapEntropy. Appendix I documents what is verified and where formal proofs differ from the printed prose. The paper also states that derivations and formalization were primarily produced by large language models.
Is the proposed algorithm practical?
Not by the stated bounds: the machine-checked constants include factors like 12(10¹²+1) for the single algorithm and 6.4×10¹³ for the instance-wise upper bound, and the authors note constants are not optimized. The contribution is structural — establishing the correct complexity shape — and no experimental evaluation appears in the provided text.
What is still left open after this paper?
The additive two-arm term Δ_[2]^{-2}·ℓ(Δ_[2]^{-2}) remains, as the original conjecture itself allows; results are specific to unit-variance Gaussian rewards with means in [0,1]; and the visible portion of Appendix G warns that plugging non-Gaussian scores (e.g., reused validation metrics) into the procedure is not justified by these theorems.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- The provided text is a sampled excerpt with marked '[...sampling gap...]' regions: the middle of Appendix D (Eqs. D.6–D.13 and the full call sequence), the end of Appendix F (including the constant C* of Eq. F.12), most of Appendix G, part of the Section 3.1 comparison with Aronow et al., and part of Appendix A (around Lemma A.5) were skipped by sampling; this review avoids reliance on those regions.
- No experiments or figures were visible in the provided text; whether the full paper contains any within the skipped regions is unknown, so 'no empirical evaluation' is asserted only about the provided excerpt.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.