PaperlayerView exact revision on arXiv

Source-linked AI summary

Simple Bayesian Algorithms for Best Arm Identification

Daniel Russo

arXiv:1602.08448v4cs.LG

TL;DR

The paper asks how to allocate noisy measurements adaptively to identify the best design efficiently. It proposes three simple Bayesian top-two rules and shows that their posterior identification converges exponentially, with the best possible exponent under suitable tuning and robust near-optimality with unbiased sampling.

  • Problem

    The problem is to identify the best among finitely many designs from noisy sequential measurements while using measurement effort efficiently.

  • Method

    The paper proposes top-two probability sampling, top-two value sampling, and a top-two Thompson-sampling rule that adaptively allocate measurements using posterior beliefs.

  • Results

    The proposed algorithms achieve exponential posterior convergence; with optimal tuning the exponent is optimal, while unbiased top-two sampling is uniformly within a factor of two of optimal.

  • Takeaways & Limitations

    Simple top-two rules can automatically allocate effort among competing designs in a way linked to optimal adaptive allocation limits.

  • Takeaways & Limitations

    The results require strong prior regularity, including priors defined over a compact set, and simple automatic tuning of β remains an open problem.

Abstract

from arXiv · show

This paper considers the optimal adaptive allocation of measurement effort for identifying the best among a finite set of options or designs. An experimenter sequentially chooses designs to measure and observes noisy signals of their quality with the goal of confidently identifying the best design after a small number of measurements. This paper proposes three simple and intuitive Bayesian algorithms for adaptively allocating measurement effort, and formalizes a sense in which these seemingly naive rules are the best possible. One proposal is top-two probability sampling, which computes the two designs with the highest posterior probability of being optimal, and then randomizes to select among these two. One is a variant of top-two sampling which considers not only the probability a design is optimal, but the expected amount by which its quality exceeds that of other designs. The final algorithm is a modified version of Thompson sampling that is tailored for identifying the best design. We prove that these simple algorithms satisfy a sharp optimality property. In a frequentist setting where the true quality of the designs is fixed, one hopes the posterior definitively identifies the optimal design, in the sense that that the posterior probability assigned to the event that some other design is optimal converges to zero as measurements are collected. We show that under the proposed algorithms this convergence occurs at an exponential rate, and the corresponding exponent is the best possible among all allocation

1 Introduction

The paper studies adaptive measurement allocation for confidently identifying the best design and proposes simple Bayesian rules with sharp optimality guarantees. Its algorithms achieve exponential posterior convergence, with optimality or near-optimal robustness depending on tuning.

  • Motivation: The paper frames best-arm identification as efficiently allocating noisy sequential measurements among finitely many designs before committing to a decision.The motivating settings include A/B testing, simulation optimization, and clinical trials.
  • Main contributions: Three Bayesian rules are proposed: top-two probability sampling, top-two value sampling, and top-two Thompson sampling.The first uses posterior optimality probabilities, the second also considers expected quality advantages, and the third modifies Thompson sampling for identification.
  • Main contributions: Exponential posterior convergence is achieved by the proposed algorithms, and the exponent is characterized relative to the best possible adaptive allocation.The posterior probability that a nonoptimal design is optimal converges to zero at this rate.
  • Main contributions: With an unbiased coin, top-two sampling attains an exponent within a factor of two of an optimal allocation uniformly across problem instances.Across fourteen instances, unbiased top-two Thompson sampling performs similarly to a version using the best instance-specific tuning parameter.
  • Main contributions: Among rules allocating half of asymptotic measurement effort to the true best design, no alternative achieves a larger exponential posterior-convergence rate on any problem instance.An analogous result holds for biased-coin top-two sampling.
  • Main contributions: The main structural insight is that simple top-two rules automatically allocate measurements among the k −1 alternatives optimally, reducing the problem to choosing the coin bias.Adaptive tuning can attain a fully optimal exponent, but the proposed tuning method is complex.
  • Scope and related work: The theory requires strong regularity properties of the prior, including that priors be defined over a compact set.The paper also notes that expected improvement attains only polynomial posterior convergence in the discussed setting.

2 Problem Formulation

The problem formulation treats design qualities as fixed but unknown and measurements as independent noisy observations selected adaptively. Bayesian posteriors quantify which design is optimal, while the target is exponential convergence toward the true best design.

  • Sequential measurement model: At each time, the decision-maker adaptively selects one design and observes a noisy measurement, seeking to identify the design with the highest mean.The measurement vector is drawn independently across time from a fixed, unknown distribution.
  • Measurement distributions: The model uses canonical one-dimensional exponential-family measurement distributions, including Bernoulli, normal with known variance, Poisson, exponential, chi-squared, and Pareto distributions.The parameter-to-mean mapping is assumed strictly increasing.
  • Best design: The unknown true parameter vector determines the unique best design, with an indifference-zone extension allowing identification of an ϵ-optimal design.The main analysis assumes a unique maximizer, while the extension permits tolerance ϵ > 0.
  • Prior and posterior: A prior over possible parameters is updated after each adaptive observation to form a posterior that may allow correlations among design qualities.The posterior is the central state variable for the policies studied.
  • Posterior objectives: The analysis tracks the posterior probability that each design is optimal and the posterior probability that some design other than the true best is optimal.The latter quantity is 1 − α_I∗ and is shown to converge to zero essentially optimally.

3 Algorithms

All three algorithms use a top-two principle: measure the estimated best design with probability β and an alternative with probability 1 − β. They differ in how the two designs are selected, while adaptively reallocating alternative measurements toward difficult comparisons.

  • Common principle: Each algorithm estimates the best design, measures it with probability β, and otherwise measures the alternative most likely to be best.The tuning parameter β is often set to 1/2.
  • Asymptotic allocation: Asymptotically, the best design receives fraction β of measurements and the remaining effort is distributed among alternatives according to their difficulty of distinction.Clearly inferior designs receive less effort, while harder-to-distinguish designs receive more.
  • Top-two probability sampling: Top-two probability sampling selects the two designs with the highest posterior probabilities of optimality, randomizing between them using β and 1 − β.The two designs can change as posterior beliefs update.
  • Top-two value sampling: Top-two value sampling ranks designs by expected posterior value, accounting for both optimality and the expected amount by which quality exceeds competitors.Its value function can encode the utility of discovering a design with quality θ_i or mean μ(θ_i).
  • Top-two Thompson sampling: Standard Thompson sampling can converge only polynomially for best-arm identification because it rarely samples alternatives once one design appears likely best.For example, if α_n,i = .95, another action is selected roughly once every 20 periods.
  • Top-two Thompson sampling: Top-two Thompson sampling samples a design from the posterior, then repeatedly samples until a distinct alternative appears before choosing between the two.The resampling step prevents standard Thompson sampling from focusing almost exclusively on one design.
  • Implementation: Posterior probabilities and values can be approximated from posterior samples, enabling efficient implementations when posterior sampling is available.For independent priors, relevant probabilities reduce to one-dimensional integrals; one implementation scales as O(kn).

4 A Numerical Experiment

In a five-design binary-outcome experiment, the proposed top-two algorithms reached posterior confidence levels with substantially fewer measurements than uniform allocation. Despite different procedures, the proposed methods converged to similar measurement distributions and posterior evidence patterns.

  • Measurement efficiency: Fewer than half the measurements were required by the proposed algorithms to reach the same confidence levels as uniform allocation.The comparison used average measurements needed for the posterior to reach fixed confidence levels across repeated trials.
  • Measurement efficiency: All top-two rules attained the same asymptotic convergence rate, although top-two probability sampling was slightly outperformed in this experiment.The experiment compared top-two probability sampling, top-two value sampling, and top-two Thompson sampling.
  • Measurement efficiency: Over 60% more measurements were needed by Thompson sampling to reach confidence .95, and over 250% more to reach confidence .99.Thompson sampling was especially slow at high confidence and required an onerous number of measurements at confidence .999.
  • Allocation patterns: At confidence .999, TTTS, TTPS, and TTVS settled on essentially the same distribution of measurement effort across designs.Figure 2 examined average measurements collected from each design and posterior beliefs at the first time confidence .999 was reached.
  • Allocation patterns: Uniform allocation gathered much more evidence to rule out the poorest design than to rule out a near-best alternative.The posterior evidence comparison was plotted using log(1/αn,i), interpreted as the magnitude of evidence that alternative i is not optimal.
  • Allocation patterns: The allocation concentrated effort on the true best design and on alternatives that remained plausibly optimal.Effort shifted away from designs once posterior evidence indicated they were clearly suboptimal.

5 Main Theoretical Results

The proposed top-two algorithms achieve exponentially fast posterior convergence, with optimally tuned versions attaining the best possible rate under any adaptive allocation. Their tuning parameter controls effort assigned to the true best design, while the algorithms adaptively allocate remaining effort among suboptimal designs.

  • The posterior probability assigned to nonoptimal designs converges to zero exponentially under TTPS, TTVS, and TTTS, with a nearly best-possible exponent.
  • The optimal exponent Γ* is an upper bound on the convergence rate achievable by any adaptive allocation rule, and optimally tuned TTPS, TTVS, and TTTS attain it.
  • For a fixed β, each proposed algorithm allocates asymptotically a fraction β of measurements to the true best design I*, with the remaining effort governed by a constrained exponent Γ*β.
  • The top-two algorithms are optimal among adaptive rules that allocate the same asymptotic fraction β of effort to the true best design.
  • With β = 1/2, the attained exponent is never more than a factor of two below the optimal exponent across problem instances.
  • Adaptive tuning can recover the optimal rate when βn converges to β*, but the proposed numerical tuning procedure is complex and may undermine the algorithms’ simplicity.

6 Analysis

The analysis characterizes posterior convergence under adaptive measurement and identifies the optimal error exponent. It then shows that simple top-two algorithms converge to allocations achieving this exponent.

  • Posterior consistency: If a design receives infinite measurement effort, its marginal posterior concentrates around its true quality; unmeasured designs need not concentrate.Finite evidence cannot rule out any value with certainty.
  • Posterior large deviations: Posterior mass on alternatives decays according to the information accumulated under the adaptive allocation rule.The relevant information measure is the average Kullback–Leibler divergence under the allocation proportions.
  • Optimal allocation: The optimal allocation solves a max-min problem that maximizes the worst evidence rate for distinguishing the true best design from alternatives.The hardest-to-distinguish alternative determines the asymptotic exponent.
  • Optimal allocation: Under the optimal fixed allocation, error decays as e^-nΓ*, and no adaptive allocation can achieve a faster asymptotic rate.The result establishes Γ* as the optimal error exponent.
  • Optimal allocation: Optimal measurement effort equalizes the evidence gathered against suboptimal alternatives rather than allocating equally across designs.The optimal allocation adjusts sampling until the relevant certification rates are equal.
  • Top-two algorithms: Instead of solving the allocation optimization directly, TTTS, TTPS, and TTVS adaptively converge to optimal allocations and attain the error exponent Γ*.With parameter β > 0, the allocation proportions converge to ψβ.

7 Further Simulation Experiments

The simulations examine tuning robustness and comparisons with omniscient allocation policies across 14 problem settings. Top-two Thompson sampling performs strongly, often outperforming both its optimal-tuning variant and large-deviations-based oracles.

  • Experimental setup: Across 14 experiments, simulations measure the samples needed for posterior confidence levels c = .9 and c = .99.Results are averaged over 400 trials and use confidence-level comparisons.
  • Experimental setup: The experiments compare top-two Thompson sampling with an ad-hoc β = 1/2 against an oracle using the optimal problem-dependent tuning parameter β*.They also compare against policies implementing asymptotically optimal fixed allocations, including the large deviations and OCBA oracles.
  • Tuning robustness: Top-two Thompson sampling with β = 1/2 generally performs similarly to the optimally tuned version.The largest observed advantage for optimal tuning occurs on slippage configurations, where it saves up to 15% of samples on average.
  • Oracle comparisons: The large deviations and OCBA oracles require at least 19% more samples on average than TTTS(1/2) across all 14 experiments.In their worst experiments, they use more than 200% and 300% of TTTS(1/2)'s average sample count, respectively.
  • Interpretation: The reasons TTTS(1/2) outperforms the oracle policies remain an open question.Possible explanations include exact posterior sampling and adaptation to unusual observations, but these explanations are not formally established.

8 Extensions and Open Problems

The paper presents top-two sampling as a general design principle and discusses extensions, implementation variants, and open problems. These include top-m identification, correlated designs, tuning, and adaptive stopping.

  • Extensions and Open Problems: Top-two sampling measures one of the two designs that appear most promising given current evidence.The paper frames this as a general design principle beyond its original scope.
  • Top-Two Sampling Via Constrained MAP Estimation: MAP-based top-two sampling predicts the best design with MAP estimation and finds the leading alternative with constrained MAP estimation.The method may simplify computation by avoiding the posterior normalizing constant, but formal asymptotic guarantees remain open.
  • Top m–arm identification: For top-m identification, the proposed extension samples designs differing between the top-m sets under two posterior draws.When m = 1, it coincides with TTTS with β = 1/2; the paper conjectures a rate within a factor of 2 of optimal for general m.
  • Extremely Correlated Designs: Extremely correlated designs can make the proposed algorithms wasteful when many designs have nearly identical qualities.A suggested linear-bandit modification samples a second action only after its feature direction differs sufficiently from the first.
  • Tuning β and Adaptive Stopping: The choice of tuning parameter β is an open gap: optimal rates can be achieved by time-varying optimization, but simple automatic selection remains unresolved.The paper also notes that top-two allocation can be paired with a stopping rule, while frequentist error and expected-sample optimality remain open questions.

B An Implementation of TTPS

This appendix implements top-two probability sampling for Beta priors and binary observations. It approximates posterior optimality probabilities numerically, selects between the leading designs, and updates the posterior after each observation.

  • Model and Prior: The implementation assumes independent Beta priors for design qualities and binary observations whose success probabilities equal the corresponding qualities.The prior is updated after observations using the Beta-binomial conjugate structure.
  • Posterior Computation: Quadrature approximates each design’s posterior probability of being optimal on a grid of M points in (0, 1).The algorithm stores posterior PDFs, CDFs, and their product to evaluate the optimality probabilities.
  • Output and Computation: After N time steps, the implementation returns posterior Beta parameters summarizing the evidence gathered during measurement.Most operations can be vectorized in MATLAB, NumPy, and Julia.
  • Action Selection: At each step, the algorithm identifies the two largest optimality probabilities, flips a Bernoulli(β) coin, and samples one of those designs.The observed binary outcome then updates the selected design’s posterior statistics.
  • Related Allocation Rules: The appendix also reviews links between expected-improvement sampling and OCBA, while noting that the cited sampling ratios are not optimal for finite k.The paper’s main innovation is building on such bandit allocations to obtain near-optimal best-arm identification rates.

E.2 Posterior Consistency: Proof of Prop. 4

This proof establishes posterior consistency when each design receives unbounded cumulative measurement effort. It uses likelihood concentration and posterior comparisons to show that inferior designs lose posterior mass.

  • Posterior Comparison: A bounded prior density allows the dependent posterior to be compared with a product-measure likelihood construction.This comparison makes marginal posterior concentration tractable even without independent priors across designs.
  • Uniform Bounds: Uniform continuity and compactness arguments extend pointwise likelihood bounds to posterior mass over parameter regions.The proof uses finite δ-covers and uniform control of the normalized log posterior.

F.2 Proof of Proposition 7

The proof characterizes the unique allocation solving the asymptotic exponent optimization problem. It then shows that adaptive rules converging to this allocation achieve the optimal exponent for the chosen top-two balance.

  • Optimal Allocation: Proposition 7 states that the exponent optimization problem has a unique optimal allocation ψ∗.The solution equalizes the relevant competing rate terms under the fixed top-two probability β.
  • Adaptive Allocation: Any adaptive allocation whose best-design sampling fraction converges to β has an asymptotic exponent characterized by the corresponding allocation limit.This links allocation convergence to posterior convergence rates.
  • Exponent Optimization: The optimal exponent Γ∗ is obtained by maximizing the rate function over probability allocations.Homogeneity and monotonicity extend the analysis from normalized allocations to non-negative measurement-budget vectors.

F.4 Sub-Gaussian Bound: Proof of Proposition 1

This section derives a sub-Gaussian lower bound on KL divergence and applies it within the proof of Proposition 1.

  • The variational representation expresses KL divergence through a supremum over random variables satisfying integrability conditions.
  • For common-variance normal distributions, KL divergence equals (θ − θ′)^2/(2σ^2).
  • For sub-Gaussian observations, the proof applies the variational form with X = λ(Y − Eθ′[Y]) and bounds the log moment-generating function.
  • Choosing λ = (Eθ[Y] − Eθ′[Y])/σ^2 minimizes the resulting bound.
  • The argument then uses exponential-family identities linking A′(θ) to the mean when T(y) = y, followed by the normal KL formula.

G Analysis of the Top-Two Allocation Rules: Proof of Proposition 8

This section establishes convergence of the allocation proportions under the three top-two algorithms to the allocation ψβ that Proposition 7 identifies as optimal.

  • Under TTTS, TTPS, or TTVS with β > 0, the allocation proportions ψn converge to ψβ.
  • Continuity of each Ci transfers convergence of ψn to convergence of Ci(ψn,I∗,ψn,i).
  • The limiting allocation ψβ satisfies the optimality relation established by Proposition 7.
  • The proof treats the three algorithms through common intermediate results before analyzing each rule separately.

G.1 Results for a general allocation rule

This section develops general conditions for asymptotically optimal allocation and uses posterior behavior under finite or excessive measurement to analyze the top-two rules.

  • General allocation results: If the best design receives asymptotic fraction β and over-allocated inferior designs receive exponentially negligible posterior probability, the allocation is optimal.
  • General allocation results: Over-allocation of an inferior design makes its posterior optimality probability exponentially small relative to the largest inferior-design probability.
  • General allocation results: Designs receiving infinite measurement effort are identified to arbitrary precision, whereas finite-measurement designs retain posterior probability of substantially higher quality.
  • Top-two rules: These posterior properties imply that every design receives infinite measurement effort under the proposed top-two allocation rules.
  • Top-two rules: Consequently, the posterior concentrates on the truth and the best design's allocation fraction converges to β for TTTS, TTPS, and TTVS.
  • Top-two rules: The proofs show that each top-two rule satisfies the general sufficient condition by combining convergence of the best-design allocation with negligible allocation to over-sampled inferior designs.

H Results on Adaptive Tuning

This section extends the analysis to adaptive tuning parameters, showing that when the tuning sequence converges, the allocation proportions converge to the corresponding limiting optimum.

  • If βn is adapted to past information and converges to β∗, the proposed algorithms retain their asymptotic allocation result almost surely.
  • The proof first establishes that every design receives infinite measurement effort, extending the fixed-β argument.
  • For TTPS and TTVS, the best design eventually receives fraction βn; for TTTS, its allocation fraction also approaches βn as its posterior optimality probability approaches one.
  • Algorithm 3 yields βn → β∗ almost surely, and the posterior probability of nonoptimal parameters vanishes.
  • Posterior consistency and continuity of the optimal allocation correspondence imply convergence of the updated tuning parameter to β∗.
Loading 1602.08448v4…