PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Best Arm Identification with Fixed Confidence

Aurélien Garivier, Emilie Kaufmann

arXiv:1602.04589v2math.STcs.LGstat.ML

TL;DR

Best-arm identification asks how to identify the highest-mean arm with controlled error while minimizing samples. The paper derives a tight lower bound, then proposes Track-and-Stop, which tracks the lower bound’s optimal proportions and uses Chernoff stopping; it asymptotically matches that bound.

  • Problem

    The paper addresses fixed-confidence best-arm identification, where the goal is to identify the largest-mean arm accurately while minimizing expected draws.

  • Method

    Track-and-Stop combines tracking of estimated optimal arm-draw proportions with a Chernoff stopping rule based on a generalized likelihood-ratio test.

  • Results

    Track-and-Stop asymptotically matches the paper’s tight lower bound, while numerical experiments show that the MDL stopping rule clearly improves performance.

  • Takeaways & Limitations

    The lower bound characterizes optimal draw proportions, providing a basis for asymptotically optimal fixed-confidence best-arm identification.

  • Takeaways & Limitations

    The analysis is restricted to one-parameter bandit models with a single best arm, and general characteristic times lack closed-form formulas.

Abstract

from arXiv · show

We give a complete characterization of the complexity of best-arm identification in one-parameter bandit problems. We prove a new, tight lower bound on the sample complexity. We propose the `Track-and-Stop' strategy, which we prove to be asymptotically optimal. It consists in a new sampling rule (which tracks the optimal proportions of arm draws highlighted by the lower bound) and in a stopping rule named after Chernoff, for which we give a new analysis.

1. Introduction

The paper studies fixed-confidence best-arm identification: finding the arm with the largest mean quickly and accurately while minimizing draws. It derives a tight lower bound and introduces Track-and-Stop, whose sampling and stopping rules are designed to attain it asymptotically.

  • Motivation: Best-arm identification seeks the arm with the largest mean while minimizing the number of draws, rather than maximizing cumulative reward.The fixed-confidence objective requires error probability at most δ while minimizing expected stopping time.
  • Motivation: In the fixed-confidence setting, a δ-PAC strategy stops with error probability at most δ and aims to minimize expected sample complexity.
  • Setting: The paper focuses on one-parameter bandit models with a single arm having the highest expectation, ordered as µ1 > µ2 ≥ ··· ≥ µK.
  • Gap: Existing racing and confidence-bound strategies reflect problem difficulty but were not proved to satisfy an optimality property.
  • Contributions: The first result is a tight, non-asymptotic lower bound on Eµ[τ], expressed through a characteristic time obtained from an optimization problem.
  • Contributions: Track-and-Stop asymptotically achieves the lower bound by tracking optimal arm-draw proportions and using a Chernoff stopping rule.The stopping rule has generalized likelihood-ratio, Minimal Description Length, and optimal-transport interpretations.

2. Lower Bounds on the sample complexity

The lower-bound analysis relates arm-draw proportions to information against alternative bandit models with different optimal arms. Its characteristic time and optimal proportions can be computed through a finite-dimensional optimization and efficient numerical procedures.

  • General Lower Bound: The lower-bound method transports the bandit parameters to alternative models with different optimal arms, with cost measured by Kullback–Leibler divergences.
  • Model and Divergence: For exponential-family bandits, the divergence d(µ, µ′) is the Kullback–Leibler divergence between distributions with means µ and µ′.
  • General Lower Bound: Theorem 1 gives every δ-PAC strategy a lower bound on expected stopping time through a characteristic time determined by optimal arm-draw proportions.The asymptotic factor uses kl(δ, 1 −δ) ∼ log(1/δ).
  • General Lower Bound: The optimal proportions w∗ are the draw proportions required by a strategy that matches the lower bound.
  • Characteristic Time and Proportions: The optimal proportions can be characterized using inverse functions xa and a unique solution y∗ of Fµ(y) = 1.Their computation uses bisection and the resolution of K smooth scalar equations, with complexity roughly proportional to the number of arms.
  • Characteristic Time and Proportions: The proportions are continuous in µ and, when µ1 > µ2 ≥ ··· ≥ µK, satisfy w∗2(µ) ≥ ··· ≥ w∗K(µ).
  • Special Cases and Scope: In general, T∗(µ) and w∗(µ) lack closed-form formulas, and T∗(µ) cannot be expressed as a sum of individual arm-complexity terms.The paper nevertheless gives algebraic or rational-equation characterizations in selected two-armed and Gaussian cases.

3. The Track-and-Stop Strategy

Track-and-Stop combines sampling that tracks optimal arm-draw proportions with a Chernoff stopping rule based on statistical evidence for identifying the best arm.

  • 3.1. Sampling Rule: Tracking the Optimal Proportions: The strategy tracks optimal draw proportions through plug-in estimates of w∗(µ), using C-Tracking or D-Tracking sampling rules.C-Tracking projects target proportions to ensure exploration, while D-Tracking forces exploration when an arm is under-sampled.
  • 3.1. Sampling Rule: Tracking the Optimal Proportions: Naive plug-in sampling can abandon an arm after poor initial estimates, so forced exploration ensures continued observations and convergence of ˆµ(t).The resulting tracking rules guarantee convergence of each arm’s empirical draw proportion to its optimal proportion.
  • 3.2. Chernoff’s Stopping Rule: The stopping rule tests whether the observations provide sufficiently reliable evidence that one arm exceeds all others.It uses pairwise Generalized Likelihood Ratio statistics Za,b(t), with the final decision given by the unique maximizer.
  • 3.2. Chernoff’s Stopping Rule: Chernoff’s stopping rule stops when one arm’s statistic exceeds the threshold against every other arm.The rule has equivalent statistical, information-theoretic, and optimal-transport interpretations connected to the lower bound.
  • 3.2. Chernoff’s Stopping Rule: E[τδ] is of order T∗(µ) log(1/δ) when the proposed sampling rule is used.The lower bound suggests the characteristic-time scale T∗(µ), while the sampling rule achieves the corresponding asymptotic order.
  • 3.2. Chernoff’s Stopping Rule: The stopping rule also admits an MDL interpretation: it waits until separating arms gives a shorter description of the observed rewards.For Bernoulli arms, Za,b(t) measures the difference between joint and separate ideal code lengths.

4. Choosing the Threshold in the Stopping Rule

The paper calibrates Chernoff’s stopping threshold to control error uniformly over time, combining a risk term with a fluctuation term.

  • The Informational Threshold: The threshold must include log(1/δ) to reflect the risk level and log(t) to control fluctuations in adaptive counts.The paper presents both information-theoretic and self-normalized deviation approaches to establishing PAC guarantees.
  • The Informational Threshold: Theorem 10 states that, for Bernoulli bandits, Chernoff’s stopping rule ensures Pµ(τδ < ∞, ˆaτδ̸ = a∗) ≤δ.This guarantee holds whatever the sampling strategy, provided the stated threshold is used.
  • The Informational Threshold: The PAC proof bounds an incorrect stop by the event that a suboptimal arm’s pairwise statistic crosses the threshold against the optimal arm.It introduces first-crossing times Ta,b and reduces the error event to a union over suboptimal arms and times.
  • The Informational Threshold: Universal coding supplies a probability-law workaround for maximum-likelihood expressions and yields tight uniform approximations in the Bernoulli case.The Krichevsky–Trofimov distribution is used as a universal distribution for successive Bernoulli observations.
  • The Deviational Threshold: For general exponential-family bandits, a deviation-based threshold also provides PAC guarantees, although its exploration rate is larger and less explicit.The paper states this result for any sampling strategy under the corresponding threshold.

5. Sample Complexity Analysis

The analysis shows that Chernoff stopping combined with sampling proportions converging to the optimal allocation yields almost-sure termination and asymptotically optimal expected sample complexity.

  • For sufficiently small δ, Chernoff’s stopping rule and optimal-tracking sampling approach the lower bound T∗(µ) log(1/δ).This establishes the target asymptotic sample complexity of the strategy.
  • Any sampling rule whose arm proportions converge almost surely to w∗, combined with β(t, δ) = log(r(t)/δ), guarantees almost-surely finite stopping.The stated result applies for α ∈ [1, e/2] and r(t) = O(t^α).
  • The expectation analysis uses Chernoff’s stopping rule with β(t, δ) = log(r(t)/δ) and the C-Tracking or D-Tracking sampling rules.Theorem 14 provides the upper-bound analysis for exponential family bandit models.
  • For Bernoulli bandits, β(t, δ) = log(2(K −1)t/δ) makes Chernoff’s rule δ-PAC, while suitable tracking gives near-optimal expected stopping time for small δ.The stopping time is almost surely finite, and its expectation is close to T∗(µ) log(1/δ).
  • More generally, for exponential family bandits and every α > 1, an exploration rate exists that makes the combined strategy δ-PAC and asymptotically optimal.

6. Discussion and Numerical Experiments

The discussion examines Track-and-Stop’s practical behavior and numerical performance, including an experimentally efficient challenger-based sampler and limits of racing strategies.

  • Practical behavior: Forced exploration is rarely useful but is necessary when µ2 = µ3, preventing a positive probability that Track-and-Stop never terminates.
  • Practical behavior: An experimentally more efficient rule samples the empirical champion or its best challenger according to the target allocation proportions, with forced exploration as in D-Tracking.
  • Numerical experiments: The simulations use two Bernoulli scenarios with δ = 0.1 and compare D-Tracking and BestChallenger against KL-LUCB and KL-Racing.The experiments are intended to assess performance at a relatively high risk value, although optimality is proved only for small risks.
  • Numerical experiments: The MDL stopping rule clearly improves performance, while Chernoff-Racing significantly improves over KL-Racing and approaches the optimal algorithms.
  • Numerical experiments: Table 1 reports expected draws for δ = 0.1 over 3000 experiments and lists the optimal allocation vectors for both scenarios.The displayed allocations are w∗(µ1) = [0.417 0.390 0.136 0.057] and w∗(µ2) = [0.336 0.251 0.177 0.132 0.104].
  • Racing limitation: Racing algorithms cannot generally attain the lower bound because they force the final two surviving arms to be sampled equally, which is usually sub-optimal.Equal sampling is sub-optimal unless the relevant optimal allocation proportions coincide.

7. Conclusion

The paper characterizes fixed-confidence best-arm identification through a tight lower bound and an asymptotically matching Track-and-Stop strategy. The strategy tracks optimal arm-draw proportions and uses Chernoff’s stopping rule.

  • The lower bound reveals efficiently computable optimal proportions for drawing the arms.
  • Track-and-Stop combines tracking of these proportions with Chernoff’s stopping rule to asymptotically match the lower bound.
  • The fixed-confidence characterization applies to a large class of bandit models whose arms are parameterized by their means.
  • The fixed-budget setting remains future work, with the paper conjecturing an exponential error-probability behavior.

A.1. Proof of Lemma 3

The proof reduces the lower-bound optimization under a wrong-order constraint to a convex problem. Its minimizer and value are then expressed using the arm divergences and a parameterized Jensen-Shannon function.

  • For a suboptimal arm a, minimizing w1d(µ1, λ1) + wad(µa, λa) subject to λa ≥ λ1 is a convex optimization problem.
  • The constrained minimum is obtained analytically under the wrong-order condition λa ≥ λ1.
  • The minimum value is rewritten as (w1 + wa)I_{w1/(w1+wa)}(µ1, µa), using the parameterized divergence Iα.

A.2. Proof of Theorem 5

The proof establishes structural properties of the optimal sampling proportions and develops tracking results for approximating them. These results support convergence and efficient computation of the proportions used by Track-and-Stop.

  • The functions ga(x) are strictly increasing, so their inverses xa(y) are defined on [0, d(µ1, µa)[.
  • The optimal proportions are characterized through a unique solution y∗ of an equation involving Fµ, with continuity inherited by w∗.
  • When µ1 > µa ≥ µb, the proof uses ga(x) ≤ gb(x) to obtain xa(y) ≥ xb(y), and hence an ordering of optimal proportions.
  • In the Gaussian case, d(x, y) = (x−y)^2/(2σ^2), and the characteristic expression becomes more explicit.
  • The tracking analysis notes that its generic upper bound can depend on K and may be overly pessimistic.
  • The tracking lemmas guarantee minimum exploration counts and eventual approximation of changing target proportions under stated conditions.

B.3. Proof of Proposition 9

The proof analyzes the sampling proportions and stopping statistic to establish the Track-and-Stop guarantees. Forced exploration ensures arm sampling, while likelihood-based bounds control erroneous stopping decisions.

  • Forced exploration makes every arm sampled infinitely often, enabling the law of large numbers for empirical means.
  • C-Tracking yields Na(t)/t → w∗a(µ), while D-Tracking reaches the same target through continuity and tracking arguments.
  • The probability of stopping with an incorrect best arm is bounded by the probability that a pairwise statistic crosses β(t, δ).
  • The proof controls pairwise likelihoods using integrated likelihoods and a Beta(1/2, 1/2) prior under an alternative model.

C.2. Proof of Proposition 12.

The proof bounds the probability of selecting a suboptimal arm by relating the stopping event to empirical-mean deviations and applying concentration arguments. With an exploration rate β(t,δ)=log(Ct^α/δ) for α>1 and suitable C, the error probability is at most δ.

  • The proof reduces incorrect stopping to an event where a suboptimal arm’s empirical mean exceeds the optimal arm’s and the stopping statistic crosses β(t,δ).
  • This crossing event implies that the weighted divergence deviations of the competing empirical means exceed β(t,δ).
  • A union bound and a concentration theorem generalized to one-parameter exponential families control the resulting deviation probability.
  • With β(t,δ)=log(Ct^α/δ), α>1, and suitable C, the probability of error is upper bounded by δ.

D.1. Proof of Theorem 14

The proof combines concentration from forced exploration with tracking properties of C-Tracking and D-Tracking. It shows that empirical best-arm identification stabilizes near the true means and derives an upper bound on the stopping time.

  • Empirical best arm: Whenever the empirical means lie in I_ε, the empirical best arm is arm 1.The neighborhood I_ε is defined around the true means, under the ordering μ1>μ2≥···≥μK.
  • Forced exploration: Forced exploration ensures that every arm is sampled at least on the order of t at round t.
  • Tracking: For sufficiently large T, both C-Tracking and D-Tracking satisfy the required tracking property on the event E_T.
  • Stopping statistic: On E_T after time h(T), the empirical best arm is 1, allowing the Chernoff stopping statistic to be rewritten and bounded.
  • Stopping-time bound: The resulting upper bound on T0(δ) holds for every η>0 and ε>0, after which η and ε are sent to zero using continuity arguments.
Loading 1602.04589v2…