The Gap-Entropy Conjecture: Entropy Is the Price of Not Knowing Which Arms Are Hard

Paper: 2609.10529 Authors: P. M. Aronow, Nathan Kallus, Patrick Lopatto Categories: cs.LG, stat.ML

The Gap

Fixed-confidence best-arm identification has a clean complexity measure. Given arms with gaps Delta_i from the optimal mean, define

   H  =  sum over suboptimal arms i of  Delta_i^{-2}

H is the textbook quantity: the harder the arms are to distinguish — the smaller the gaps — the larger H, and the story is that the sample complexity is H times a log term in the confidence level. It is a satisfying account because it says the difficulty is a sum of per-arm difficulties.

A conjecture held that this account is incomplete: H is not sufficient, and the entropy of the gap distribution appears as well. If true, the interesting implication is that difficulty is not purely additive over arms — the arrangement of gaps matters, not only their sizes.

   FIXED-CONFIDENCE BEST-ARM IDENTIFICATION

   arms with GAPS Delta_i from the optimal mean
   classical complexity measure:

     H  =  sum over suboptimal arms i of  Delta_i^{-2}

     -> the harder the arms are to DISTINGUISH (smaller gaps),
        the LARGER H
     -> story: sample complexity is H times a log term in the
        confidence level
     -> SATISFYING because difficulty is a SUM of PER-ARM
        difficulties

   [A CONJECTURE HELD THAT THIS IS INCOMPLETE]
     H is NOT SUFFICIENT, and the ENTROPY OF THE GAP
     DISTRIBUTION appears as well
        |
        v
   [THE INTERESTING IMPLICATION IF TRUE]
     difficulty is NOT PURELY ADDITIVE OVER ARMS
       -> the ARRANGEMENT of gaps matters, not only their SIZES

The Increment

One sentence: Before this paper, H was believed to characterise best-arm identification up to log factors; after it, the optimum is tight at H times the log confidence plus the gap-distribution entropy, and a single instance-independent algorithm attains it.

Core Mechanism

The setting is stated precisely, which matters for a tightness claim: independent unit-variance Gaussian arms, means in the interval from 0 to 1, and a unique optimal arm. The unit variance and bounded means fix the scale; the uniqueness condition rules out ties that would make identification ill-posed.

The entropy term is built from a gap histogram. For each suboptimal arm i, Delta_i is its gap from the optimal mean. Define p_r as the fraction of H contributed by arms whose gap lies in the dyadic band from 2^{-(r+1)} to 2^{-r} — so the bands are powers of two, and p_r weights each band by its share of H. Then

   Ent(I)  =  sum over bands r with p_r > 0 of  p_r log(1 / p_r)

which is the entropy of that weighted band distribution. Two things about the construction are worth noticing. Using dyadic bands is what makes the entropy term scale-free: gaps spanning orders of magnitude are compared by which power of two they fall in, not by their absolute values. And weighting by share of H means an arm contributes to the entropy in proportion to how much difficulty it brings.

The main result is a match, and the averaging is the subtle part: among all algorithms identifying the optimal arm with probability at least 1 - delta 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/delta) + Ent(I) )

The phrase “averaged over all permutations of the arm labels” is doing essential work and is easy to read past. It is the fair-comparison device: an algorithm cannot be blamed for the particular order in which arms happened to be presented, so the lower bound averages over label orderings. Without that averaging, an adversary could fix a pathological ordering and make any instance-independent algorithm look bad. So the entropy term is the price of not knowing which arms are hard — an algorithm that knew the gap structure could exploit it, and the entropy measures how much structure there is to exploit.

And the matching upper bound carries its own caveat, honestly stated. There is an algorithm independent of the instance whose expected samples are bounded by a constant multiple of that quantity plus g^{-2} log log(e^e/g), where g is the gap to the closest competitor. That extra term is not negligible in all regimes: when the closest competitor is very close, g^{-2} grows, and the algorithm pays a logarithmic-in-log penalty that the lower bound does not. So the characterisation is tight in the main term, with a stated additive slack in the hardest corner — which is the kind of precision that makes a “positive resolution” credible rather than merely announced.

   SETTING (stated precisely, which matters for a TIGHTNESS claim)
     independent UNIT-VARIANCE GAUSSIAN arms
     means in [0, 1]
     a UNIQUE optimal arm
       <- unit variance and bounded means FIX THE SCALE
       <- uniqueness rules out ties that would make identification
          ILL-POSED

   THE ENTROPY TERM IS BUILT FROM A GAP HISTOGRAM
     Delta_i = gap of arm i from the optimal mean
     p_r = THE FRACTION OF H CONTRIBUTED BY ARMS WHOSE GAP LIES IN
           THE DYADIC BAND  2^{-(r+1)} < Delta_i <= 2^{-r}
     Ent(I) = sum over bands r with p_r > 0 of  p_r log(1 / p_r)
       <- the entropy of that WEIGHTED BAND DISTRIBUTION
     TWO THINGS ABOUT THE CONSTRUCTION
       DYADIC BANDS make the term SCALE-FREE: gaps spanning orders
         of magnitude are compared by WHICH POWER OF TWO they fall
         in, not by absolute values
       WEIGHTING BY SHARE OF H means an arm contributes to the
         entropy IN PROPORTION to the difficulty it brings

   THE MAIN RESULT IS A MATCH (the averaging is the subtle part)
     among ALL algorithms identifying the optimal arm with
     probability at least 1 - delta on EVERY Gaussian instance,
     the optimal expected sample count on a given instance,
     AVERAGED OVER ALL PERMUTATIONS OF THE ARM LABELS, is within
     ABSOLUTE CONSTANT FACTORS of

       H ( log(1/delta) + Ent(I) )

     "AVERAGED OVER ALL PERMUTATIONS OF THE ARM LABELS" IS DOING
     ESSENTIAL WORK
       <- the FAIR-COMPARISON device: an algorithm cannot be blamed
          for the order in which arms happened to be presented
       <- without that averaging, an adversary could fix a
          PATHOLOGICAL ORDERING and make any instance-independent
          algorithm look bad
       -> the entropy term is the price of NOT KNOWING WHICH ARMS
          ARE HARD: an algorithm that knew the gap structure could
          exploit it, and the ENTROPY MEASURES HOW MUCH STRUCTURE
          THERE IS TO EXPLOIT

   AND THE MATCHING UPPER BOUND CARRIES ITS OWN CAVEAT, HONESTLY
     there is an INSTANCE-INDEPENDENT algorithm whose expected
     samples are bounded by a constant multiple of that quantity
     PLUS   g^{-2} log log(e^e/g)
       where g = the gap to the CLOSEST COMPETITOR
     <- that extra term is NOT NEGLIGIBLE in all regimes: when the
        closest competitor is very close, g^{-2} grows, and the
        algorithm pays a LOGARITHMIC-IN-LOG penalty the LOWER BOUND
        DOES NOT
     -> tight in the MAIN TERM, with a STATED ADDITIVE SLACK in the
        hardest corner: the precision that makes a "positive
        resolution" credible rather than merely announced

Think of it as sorting a pile of coins by weight when you do not know which are the tricky ones. If you know in advance that three coins are nearly identical and the rest are obvious, you can budget your weighing effort accordingly. If you do not, you must spend time discovering where the difficulty is concentrated — and that discovery cost is what the entropy term measures. A pile with uniform difficulty has low entropy: you learn the situation quickly and then proceed. A pile whose difficulty is spread across many scales has high entropy: there is more structure to find out before you can act efficiently. The averaging over label permutations is the fairness of the comparison — you cannot be judged on whether the tricky coins happened to be handed to you first.

Key Concepts

• H as the additive baseline: the sum of inverse squared gaps, which says difficulty is the sum of per-arm difficulty. It is the measure the conjecture said was incomplete.
• Dyadic gap bands: bins by powers of two, so the entropy term is scale-free. Gaps spanning orders of magnitude are compared by band rather than by absolute size.
• Ent(I) as structural difficulty: the entropy of the H-weighted band distribution. It measures how much there is to learn about which arms are hard, independently of how hard they are overall.
• Permutation averaging as fair comparison: the lower bound averages over arm-label orderings, so an algorithm is not penalised for the presentation order. It is what makes the entropy term interpretable as the price of not knowing the structure.
• Stated additive slack: the near-optimal algorithm includes a g^{-2} log log(e^e/g) term for the closest competitor. Honest reporting of a corner where matching does not hold is what makes the tightness claim precise.

Framework Shift

Before (H characterises difficulty up to log factors):
  complexity = H times a log term in the confidence level
  -> difficulty is a sum of per-arm difficulties
  -> the conjecture says this is incomplete, because the entropy
     of the gap distribution also appears

After (H times log confidence plus entropy, matched):
  gapped arms binned into dyadic bands, weighted by share of H
  -> optimal expected samples ~ H( log(1/delta) + Ent(I) )
     for the permutation-averaged instance
  -> an instance-independent algorithm attains it, up to a stated
     g^{-2} log log term
  -> the entropy is the price of not knowing which arms are hard

From a complexity measure that depends only on the sizes of the gaps, to one that also depends on their arrangement, the core shift is that learning which arms are hard is itself a cost, and it is quantified by the entropy of the gap distribution.

Expert Assessment

Problem choice: Excellent, and resolving a conjecture with a matched bound is the most conclusive form a result in this area can take. The conjecture was informative rather than marginal — it says the textbook measure is not just loose but structurally missing a term — so proving it changes how the problem should be described.

Method maturity: The dyadic banding is a well-chosen device, because it makes the entropy term scale-free and therefore comparable across instances whose gaps differ by orders of magnitude. The permutation averaging is the technically essential step, since it is what permits a lower bound that does not depend on a fortunate presentation order — and identifying that device is arguably as valuable as the bound itself. The treatment of the near-optimal algorithm is notably careful: reporting a g^{-2} log log slack in the hardest corner rather than claiming exact matching is what makes the characterisation trustworthy.

Experimental integrity: This is theory, so the scrutiny is on the setting and the tightness claim. The assumptions are minimal and stated — unit-variance Gaussians, bounded means, unique optimum — and the uniqueness condition in particular is a real restriction, since ties are where best-arm identification becomes ill-posed and where these techniques would need separate treatment. The permutation-averaged form of the lower bound is the main interpretive caveat: it is the right notion of a fair comparison, but a reader should note that the guarantee is about the averaged instance rather than about every ordering.

Writing quality: The abstract is unusually forthcoming: it defines H, defines the band fractions and the entropy, states the matched bound with its averaging explicit, and then states the algorithmic slack. That ordering lets a reader assess tightness without reconstructing it. Because the entropy term is the conceptual novelty, a sentence of intuition for why the entropy of the band distribution (rather than, say, the number of distinct bands) is the right functional would widen the readership considerably.

Verdict: strong accept — it proves a conjecture with a matched bound, introduces a scale-free entropy term that quantifies the cost of not knowing which arms are hard, and reports the algorithmic slack honestly rather than claiming exact tightness.

Takeaways

• Check whether a complexity measure depends on magnitudes or on arrangement. Here the textbook term captured the sizes of the gaps, and the missing term captured how they were distributed.
• Look for the fair-comparison device in a lower bound. Permutation averaging is what makes the bound about the instance rather than about a fortunate ordering.
• Report the corner where matching fails. A stated g^{-2} log log slack is more useful than a claim of exact tightness that a careful reader would distrust.
• Note which assumption removes ill-posedness. Uniqueness of the optimum is what keeps the problem well posed, and tied problems need separate treatment.