A positive resolution of the gap-entropy conjecture
P. M. Aronow, Nathan Kallus, Patrick Lopatto
cs.LG · stat.ML
Quick verdict
Proves the 2016 gap-entropy conjecture for Gaussian best-arm identification: instance-optimal cost is Θ(H(log(1/δ)+Ent(I))); complete proofs provided.
Summary
This theory paper fully resolves the gap-entropy conjecture for fixed-confidence best-arm identification. In the Gaussian setting (unit-variance arms, means in [0,1], unique best arm), with H = ΣΔ_i^{-2} and gap shells (2^{-(r+1)}, 2^{-r}] whose H-mass fractions p_r define the entropy Ent(I), Theorem 1.1 proves that the permutation-averaged instance-optimal expected sample count L(I,δ) lies within absolute constant factors of H(log(1/δ)+Ent(I)) for all δ<0.1 — affirming Chen and Li's 2016 conjecture 3.5. The lower bound (Section 2) symmetrizes over labelings, compares sample-count events across gap scales under a common tied-optimum reference law (Lemma 2.3), and converts a counting bound (Lemma 2.5) into an entropy inequality via Gibbs. The upper bound (Section 3) is an instance-tailored sequential elimination using exponential mixture supermartingales with weights proportional to shell masses, plus a confidence-interval fallback ensuring almost-sure stopping. Theorem 1.2 further gives a single instance-independent algorithm, δ-correct on all 1-sub-Gaussian instances, costing C(H(log(1/δ)+Ent(I)) + g^{-2}log log(e^e/g)), proving the uniform conjecture up to that additive term (Corollary 1.3). Limitations: unspecified absolute constants, the instance-optimal construction presupposes the target's gap structure, and scope is restricted to sub-Gaussian rewards.
Review complete
Assessment at a glance
3
risk flags identified
● high 0
● medium 0
● low 3
4 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 every Gaussian instance I and δ<0.1, the permutation-averaged instance-optimal expected sample count L(I,δ) is within absolute constant factors of H(log(1/δ)+Ent(I)) (Theorem 1.1).
- A single algorithm, given only K and δ, is δ-correct on all 1-sub-Gaussian instances and uses at most C(H(log(1/δ)+Ent(I)) + g^{-2}log log(e^e/g)) samples in expectation (Theorem 1.2).
- Combining the two, one instance-independent algorithm is within an additive g^{-2}log log(e^e/g) term of the instance-wise optimum on every Gaussian instance (Corollary 1.3).
- These results prove Chen-Li conjecture 3.5 and Chen-Li-Qiao conjecture 1.9, removing the polylog(K,1/δ) factor and the instance/algorithm restrictions of all prior bounds ([3], thms 1.11-1.12).
Strengths
Resolves a decade-old open problem in full generality
Proves [2, conjecture 3.5] and [3, conjecture 1.9]: Theorem 1.1 shows L(I,δ) = Θ(H(log(1/δ)+Ent(I))) for every Gaussian instance and δ<0.1, removing the polylog(K,1/δ) factor from Chen-Li-Qiao's upper bound (their thm 1.11) and the power-of-two-gaps and deletion-stability restrictions from their lower bound (their thm 1.12/cor 1.13).
Genuinely new lower-bound technique
Section 2 builds a common reference law Q_s with two tied optimal arms via a two-mean swap whose KL cost is (α_r+α_s)/2 (Lemma 2.3); sample-count windows [c0·4^r, 4a·4^r] become disjoint under one law, yielding N(a) ≤ 32ae^{2a} and Σe^{-8α_r} ≤ 448e^{-6}/9 < 1 (Lemma 2.5), then Gibbs' inequality gives Ent(I) ≤ 8Σp_rα_r ≤ 32E T (Prop 2.1) — an instance-wise lower bound without deleting arms.
Complete, self-contained proof chain
Stronger scope than conjectured, with careful convention reconciliation
Weaknesses
No explicit constants
Instance-optimal upper bound is a characterization device
No released code despite claimed computational verification
Narrow model class and averaged benchmark
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
This is a pure mathematics paper in bandit algorithms / statistical learning theory. It resolves the gap-entropy conjecture posed by Chen and Li (COLT 2016 open problem, their conjecture 3.5) and the uniform-algorithm variant (conjecture 1.9 of Chen, Li and Qiao, COLT 2017). The setting is fixed-confidence best-arm identification with K independent unit-variance Gaussian arms, means in [0,1], a unique optimum; upper bounds hold for the larger class of 1-sub-Gaussian rewards. The key quantities: H = Σ_{i≠*} Δ_i^{-2}; geometric gap shells G_r = {i : 2^{-(r+1)} < Δ_i ≤ 2^{-r}} with H-mass fractions p_r; Ent(I) = Shannon entropy of (p_r). Theorem 1.1: the permutation-averaged instance-optimal expected sample count L(I,δ) (eq. 1.2, following [2, definition 3.1]) satisfies cH(log(1/δ)+Ent(I)) ≤ L(I,δ) ≤ CH(log(1/δ)+Ent(I)) for δ < 0.1. Theorem 1.2: one instance-independent algorithm is δ-correct on all 1-sub-Gaussian instances with E T_A ≤ C(H(log(1/δ)+Ent(I)) + g^{-2}log log(e^e/g)). Corollary 1.3 combines them. Claims match the abstract precisely, and Appendix A reconciles three convention gaps (shell-boundary shifts cost ≤ log 2 of entropy, absorbed as O(H); clipped vs shifted iterated log; stopping conventions) so the original conjecture statements are genuinely implied.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 4 strengths & 4 weaknesses, analyzed in detail
- 3 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?
A 2016 conjecture of Chen and Li stating that the fewest samples a fixed-confidence best-arm identification algorithm needs on a given bandit instance equals, up to constant factors, H(log(1/δ)+Ent(I)) — the baseline cost H (the sum of inverse squared gaps to the best arm) times the confidence term log(1/δ), plus an entropy term Ent(I) measuring how the inverse-squared-gap mass spreads across geometrically spaced gap scales. This paper proves the conjecture for Gaussian arms.
What does Ent(I) measure in this paper?
It is the Shannon entropy of the fractions of H contributed by arms grouped into gap shells (arms whose gap to the optimum lies between 2^{-(r+1)} and 2^{-r}). It is zero when all gaps lie on one geometric scale and equals log d when d shells contribute equally — it quantifies the extra sampling needed merely to discover the scale structure of the gaps, even at fixed confidence.
Is the algorithm in this paper practical?
Not directly. The instance-optimal construction behind Theorem 1.1's upper bound is built from the target instance's known gap structure and serves as a proof device for optimality. The single uniform algorithm of Theorem 1.2 needs no instance knowledge, but its guarantee carries unspecified absolute constants and an additive g^{-2}log log(e^e/g) term, so it is a theoretical benchmark rather than an engineering recipe.
What was previously known before this paper?
Chen, Li and Qiao (2017) had an upper bound of order H(log(1/δ)+Ent(I)) plus g^{-2}log log(1/g) times a polylog(K,1/δ) factor, and a matching lower bound only for Gaussian instances with power-of-two gaps and only for algorithms whose cost does not increase when suboptimal arms are deleted. This paper removes both the extra polylogarithmic factor and those restrictions.
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.
- PDF extraction linearizes the mathematical notation (subscripts, exponents, radical layout are garbled in places); the assessment is based on this linearized text, which is otherwise complete from title through reference [13].
- No code or repository URL appears anywhere in the provided text; the footnote's computational-verification code is not linked.
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.