PaperlayerView exact revision on arXiv

Source-linked AI summary

A positive resolution of the gap-entropy conjecture

P. M. Aronow, Nathan Kallus, Patrick Lopatto

arXiv:2609.10529v1cs.LGstat.ML

TL;DR

The paper asks how much additional sampling fixed-confidence best-arm identification requires to learn the configuration of arm gaps, beyond distinguishing the best arm at confidence δ. It proves matching gap-entropy bounds and constructs an instance-independent algorithm whose extra adaptation cost depends only on the smallest gap. Together, these results establish the conjectured instance-wise complexity up to absolute constants.

  • Problem

    The central question is whether the additional cost of discovering gap scales is captured by gap entropy, uniformly over instances and confidence levels.

  • Method

    The paper proves Gaussian lower bounds using label-permutation averaging and constructs both target-instance and uniform algorithms for the sub-Gaussian class.

  • Results

    The optimal expected sample size is within absolute constant factors of H(log(1/δ) + Ent(I)), while one instance-independent algorithm adds only g^-2 log log(e^e/g).

  • Takeaways & Limitations

    Gap entropy is the correct instance-dependent adaptation cost, and the conjectured benchmark can be attained uniformly up to a smallest-gap additive term.

  • Takeaways & Limitations

    The main theorems assume independent arms with means in [0,1], a unique optimum, and 1-sub-Gaussian rewards, with Gaussian specialization for the lower-bound class.

Abstract

from arXiv · show

We prove the gap-entropy conjecture for fixed-confidence best-arm identification with independent unit-variance Gaussian arms, means in $[0,1]$, and a unique optimal arm. For each suboptimal arm $i$, let $Δ_i=μ_*-μ_i$ be its gap from the optimal mean, and write $H=\sum_{i\ne *}Δ_i^{-2}$. Let $p_r$ be the fraction of $H$ contributed by arms with $2^{-(r+1)}<Δ_i\le2^{-r}$, and let $\mathrm{Ent}(I)=\sum_{r:p_r>0} p_r\log(1/p_r)$. Among all algorithms that identify the optimal arm with probability at least $1-δ$ on every Gaussian instance, the optimal expected number of samples on a given instance, averaged over all permutations of the arm labels, is within absolute constant factors of $H(\log(1/δ)+\mathrm{Ent}(I))$. Moreover, there is an algorithm, independent of the instance, whose expected number of samples is bounded by a constant multiple of this quantity plus $g^{-2}\log\log(e^e/g)$, where $g=\min_{i\ne *}Δ_i$ is the gap to the closest competitor.

1. Introduction

The paper resolves the gap-entropy conjecture for fixed-confidence best-arm identification, proving matching instance-wise lower and upper bounds and constructing a single near-optimal algorithm. The results quantify the cost of learning gap scales beyond the baseline H log(1/δ) term.

  • 1. Introduction: H = sum of inverse squared gaps gives the baseline identification cost, while gap entropy measures how sampling effort is distributed across geometric gap scales.Entropy is zero when all gaps share one scale and equals log d when d scales contribute equally to H.
  • 1. Introduction: The conjectured instance-wise benchmark is H(log(1/δ) + Ent(I)), averaged over permutations of arm labels, with an absolute-constant factor guarantee.The framework assumes independent arms, means in [0,1], a unique optimum, and δ-correctness on the relevant model class.
  • 1. Introduction: The paper proves the gap-entropy conjecture, removing prior restrictions on Gaussian instances and algorithms while eliminating the earlier polylogarithmic overhead.The result applies to the Gaussian model and establishes both conjectured lower and upper bounds.
  • 1. Introduction: The lower bound is proved directly on the original Gaussian instance after label-permutation averaging, while the matching upper bound may select an algorithm for the target instance.The uniform algorithm then extends near-optimality to every individual Gaussian instance.
  • 1. Introduction: A single instance-independent algorithm achieves the same main benchmark plus g^-2 log log(e^e/g), with no additional factor depending on K or δ.Here g is the smallest suboptimality gap, and the algorithm is δ-correct across the sub-Gaussian class.
  • 1. Introduction: For equally weighted gap groups, the entropy contribution is H log d, exposing the extra cost of discovering gap scales even at fixed confidence.This complements the baseline distinction cost and explains why fixed-instance asymptotic optimality does not settle the nonasymptotic problem.

2. The instance-wise lower bound

The lower bound combines the standard H log(1/δ) cost with an additional gap-entropy term, proved by comparing sample-count events across gap groups through common tied reference laws.

  • Conclusion: The lower-bound proposition is converted to the stated logarithmic confidence dependence because kl(1−δ,δ) is uniformly comparable to log(1/δ).This establishes the lower half of Theorem 1.1 over the stated confidence range.
  • Lower-bound strategy: Theorem 1.1’s lower bound contains both the confidence cost H log(1/δ) and the additional gap-entropy cost.The confidence term follows from Gaussian change of measure, while the entropy term compares sampling events across gap groups.
  • Symmetry and changes of measure: A permutation-equivariant reduction makes expected sampling costs invariant to which labels carry fixed arm identities.Randomly permuting labels preserves δ-correctness and removes any advantage from a favorable labeling.
  • A common reference law: The proof uses reference laws with two tied optimal arms, although these laws lie outside the unique-optimum model class.Finite-horizon truncation and data processing allow the tied laws to compare different gap groups without assuming stopping under ties.

3. The instance-wise upper bound

The paper constructs an instance-wise elimination procedure using gap-scale mixtures, proves its correctness and expected cost, and obtains the target H(log(1/δ)+Ent(I)) bound up to constants.

  • Main result: Proposition 3.1 gives a δ-correct algorithm whose relabeling-averaged expected cost is at most C H(log(1/δ)+Ent(I)).The constant C is absolute, and the guarantee holds for every target instance in the stated class.
  • Instance-specific parameters and a trial: The procedure chooses gap-scale weights proportional to |G_r|4^r, making the entropy of its testing weights comparable to Ent(I).The proof establishes W Ent(q) ≤ H Ent(I) ≤ 4W Ent(q).
  • Instance-specific parameters and a trial: Each trial cycles through active arms and eliminates an arm when a mixture of exponential statistics crosses its rejection threshold.The component indexed by r targets departures below the threshold on scale 2^-r.
  • Correctness and cost of a trial: The trial is incorrect with probability at most η on every input instance, including inputs whose gap structure differs from the target instance.If some arm is above the threshold, error requires eliminating the optimal arm; if all are below it, fresh confirmation samples control false returns.
  • Correctness and cost of a trial: The uncapped trial has expected cost bounded by 2000W[log(1/η)+Ent(q)+1], while deterministic limits and repeated trials preserve correctness and yield almost-sure stopping.On the target instance, each trial succeeds with probability at least 3/4, so later trials are reached with geometrically decreasing probability.

4. The uniform algorithm

The uniform algorithm learns the relevant gap scales through independent, budget-limited stages built from estimation, median, fraction, and elimination subroutines.

  • Uniform algorithm: The uniform construction runs independent stages with geometrically increasing budgets and deterministic sample limits, discovering the instance structure from data.Each stage either returns an arm or rejects and passes control to the next stage.
  • Sampling subroutines: Mean, Median, Fraction, and Eliminate provide the stage’s estimation, selection, proportion-testing, and pruning operations with controlled costs and errors.Eliminate also terminates almost surely and supports empty input sets.
  • Sampling subroutines: The analysis controls simultaneous loss of multiple good arms using independent estimation blocks and a product bound across arms.An incorrect Fraction result may trigger unnecessary deletion, but accurate estimates prevent deletion of arms whose means are at least the threshold.
  • Stage and round structure: Within each stage, rounds use accuracy ε_r=2^-r, select a near-best active arm, test the fraction of substantially lower arms, and eliminate when warranted.The stage returns when one arm remains and rejects when budget checks or its round limit prevent completion.
  • Budget control: Two cumulative budget tests track stage-wide costs separately from the deterministic per-stage sample limit.The running totals U_r and V_r determine whether a round can continue, while M bounds samples on every path.

5. Progress and error control

The comparison process corrects selected outer-call outputs for analysis, couples them to the actual algorithm, and tracks invalid calls without conditioning on universal validity. Successful rounds preserve the optimum, shrink active sets, and eventually isolate it once the round scale is below the smallest gap.

  • The analysis corrects outer Mean and Fraction outputs measurably, couples actual and comparison processes until disagreement, and bounds disagreement through per-call failure probabilities.
  • Successful valid Eliminate calls retain the optimal arm, so induction preserves it throughout the comparison process.
  • A successful Median round followed by False leaves most active arms within gap 2εr of optimal, while True yields a comparable bound at scale εr.
  • Once 2εr < g, every successful Median round leaves a singleton containing the optimal arm.
  • The cumulative budget analysis bounds removed suboptimal-arm weight, while stagewise union bounds and a sufficiently small error constant deliver the target correctness probability.

6. The expected sample complexity

The expected-cost analysis controls outer-call and inner-call spending, shows sufficiently large geometric-budget stages accept with high probability, and sums restart costs. It yields the stated entropy-sensitive sample bound and the corresponding lower-bound corollary.

  • Outer Mean and Fraction calls use at most Bt/100 samples in every stage, leaving the principal budget for the remaining procedures.
  • Stages with Bt ≥ AF accept with probability at least 199/200, after controlling budget rejection, final-round failure, invalid calls, and the sample cap.
  • The expected costs of Median and Eliminate calls are bounded by CB, and outer calls add at most B/100, giving an O(B) uncapped-stage cost.
  • Geometric stage budgets and conditional acceptance bounds make the algorithm stop almost surely and control the total cost of restarts.
  • ET ≤ C {H(log(1/δ) + Ent(I)) + D log log(ee/g)} establishes the instance-independent algorithm’s expected sample bound.
  • Applying Theorem 1.1’s lower bound to Theorem 1.2 proves the matching corollary for H(log(1/δ) + Ent(I)).

Appendix A. Conventions in the original conjectures

The paper adopts the original conjectures’ formulation with minor convention differences and explains why its theorems still establish those conjectures.

  • The formulation differs from the original conjectures only by minor conventions, which the paper records before relating the theorems to those statements.

A.1. Gap-group boundary conventions.

The paper’s gap-group partition differs from the original boundary convention only locally, so the resulting entropy values differ by at most an additive constant.

  • Each cell of either gap partition meets at most two cells of the other, allowing the two group-index conventions to be compared directly.
  • |Ent(R) − Ent(S)| ≤ log 2, so the corresponding H Ent(I) terms differ by O(H), absorbed by H log(1/δ).

A.2. Iterated logarithm.

Clipping the iterated logarithm changes the bound by only a constant, while making the sample-complexity convention explicit at large gaps. The upper-bound algorithms stop almost surely on every instance in the stated class.

  • A.2. Iterated logarithm.: Clipping changes the iterated-logarithm term by at most a constant, producing only an O(H) change absorbed by H log(1/δ).The unregularized logarithm is undefined at g = 1 and may be negative for large gaps.
  • A.2. Iterated logarithm.: The upper-bound algorithms stop almost surely on every instance in SK, satisfying either correctness convention.The cited correctness definition requires probability at least 1 −δ but does not itself require almost-sure stopping.

A.3. Stopping conventions.

The paper shows that alternative stopping conventions preserve the stated bounds up to absolute constants. Its subroutine guarantees are established under explicit independence and sampling assumptions for 1-sub-Gaussian rewards.

  • A.3. Stopping conventions.: The comparisons preserve all bounds up to absolute constants and recover the stated formulations of the original conjectures.This conclusion is stated together with Corollary 1.3.
  • A.3. Stopping conventions.: The subroutine analysis allows tied optimal arms, uses fresh samples across calls, and assumes independent sampling and estimation blocks.Sample sizes are rounded up, and accuracy parameters and threshold differences are bounded by one.
  • A.3. Stopping conventions.: For independent samples from a 1-sub-Gaussian arm, the sample-mean analysis begins by applying independence before concentration bounds.The passage introduces the independent-sample setup used in the estimation proof.

B.1. Mean estimation.

Mean estimation uses Chernoff-based sub-Gaussian concentration for sample averages. The resulting sample count is deterministic and scales as e^-2 log(1/α), with the guarantee preserved under fresh sampling and conditioning on prior history.

  • B.1. Mean estimation.: P(X̄_n − µ ≥ x) and P(X̄_n − µ ≤ −x) are each at most e^-nx^2/2 for x > 0.This is the standard sub-Gaussian sample-mean bound used to set estimation accuracy and failure probability.
  • B.1. Mean estimation.: The estimator uses independent samples and returns their average, with Equation (B.1) supplying its error guarantee.The procedure is defined for accuracy e and error level α.
  • B.1. Mean estimation.: The deterministic sample count is O(e^-2 log(1/α)) on the stated parameter range.Fresh samples preserve the same bound conditional on the history before the call.

B.2. Median elimination.

Median elimination repeatedly estimates current arm means, retains the half with the largest estimates, and returns one remaining arm. The analysis bounds the probability of losing all near-optimal arms at each round, yielding a 0.99-accuracy guarantee.

  • B.2. Median elimination.: The procedure estimates each current mean, retains ⌈|S_j|/2⌉ arms with the largest estimates, and returns the remaining arm.Fixed tie-breaking is used throughout the elimination rounds.
  • B.2. Median elimination.: The probability that the maximum true mean drops by more than e_j in one round is at most a_j.This follows by combining the optimal-arm estimation error with Markov’s inequality for inaccurate retained-arm estimates.
  • B.2. Median elimination.: The returned arm has mean within e of the original maximum with probability at least 0.99.The same guarantee holds conditional on an arbitrary history before the call when fresh samples are used.

B.3. Fraction testing.

The fraction-testing procedure samples uniformly chosen arms, estimates whether their means fall below a midpoint, and uses the resulting Bernoulli outcomes to decide between two fraction regimes. Independent estimates and Hoeffding’s inequality provide the stated error guarantee under explicit parameter restrictions.

  • Fraction testing: Independent arm draws and fresh mean estimates produce Bernoulli indicators for whether sampled means fall below the midpoint.The procedure draws arms with replacement, estimates each to accuracy ε/2 and error level d/6, and records the threshold comparison.
  • Fraction testing: If many arms have means below l, the indicators have sufficiently large expectation; if few have means below u, their expectation is sufficiently small.These two cases are separated using the bounds on the fraction of low-mean arms and the resulting expectation inequalities.
  • Guarantees: Invalid True or False answers require a Bernoulli deviation of at least d/3, so Hoeffding’s inequality bounds their probability by exp(−2mF d2/9).The deviation argument establishes the stated True/False guarantees for the fraction test.
  • Guarantees: The construction applies for 0 < ε ≤1, 0 < d ≤0.1, and 0 < α <0.1, with explicit rounding in the stated algorithm.The passage identifies the procedure as Algorithm 2 and Fact 5.3 of the cited reference, with rounding made explicit.
  • Implementation: The elimination procedure uses separate samples for fraction testing and deletion while retaining arms at the deletion threshold.This separates the sampling used to classify the current set from the samples used to remove arms.

B.4. Elimination.

The elimination procedure repeatedly tests the active set and, when warranted, retains arms whose estimates exceed a threshold above the midpoint. Its analysis combines contraction, independent estimation errors, and summable stage error levels to establish termination, cost, and arm-retention guarantees.

  • B.4. Elimination: At each internal stage, Fraction either stops with the current set or triggers independent estimation and retains arms with estimates at least v + ε/4.The stage uses thresholds l, v, fraction thresholds 0.05 and 0.1, and error level qj.
  • Active-set contraction: When a valid True answer occurs, more than 0.05|Sj| arms have means below v, so independent filtering contracts the active set in expectation.A False answer makes the next active set empty for the cost calculation, while invalid answers are also covered by the contraction argument.
  • Cost analysis: The contraction can be iterated without conditioning on correctness, and summing conditional stage costs yields an unconditional expected sample bound.The Fraction cost is absorbed while the active set is nonempty, and the resulting stage series is used for the total cost calculation.
  • Termination: Because the relevant stage probability tends to zero as j increases, the elimination subroutine terminates almost surely.This conclusion follows from the displayed limiting bound in the analysis.
  • Correctness guarantees: The probability that any internal Fraction answer is invalid is bounded separately before combining the subroutine’s guarantees.The analysis explicitly begins by controlling invalid Fraction answers and then verifies the fraction and removal guarantees.
  • Correctness guarantees: With independent estimation blocks, each arm of mean at least u is removed only through an inaccurate estimate, giving probability at most α/10 per arm.Independence across arms yields a bound of (α/10)^k for removing all k specified arms, while the designated optimal arm’s failure probability is at most α/5.
Loading 2609.10529v1…