PaperlayerView exact revision on arXiv

Source-linked AI summary

Bayesian Fixed-Confidence Best-Arm Identification with Abstention

Yuqi Huang, Yunlong Hou, Vincent Y. F. Tan

arXiv:2610.30384v1cs.LG

TL;DR

Bayesian fixed-confidence best-arm identification asks how to control error while allowing abstention from a terminal recommendation. The paper proposes Screen-and-Confirm and derives matching bounds on the minimum expected stopping time. Under Gaussian priors and rewards, it establishes rate and exact-constant results across several abstention regimes.

  • Problem

    Bayesian fixed-confidence best-arm identification asks how to minimize expected sampling while controlling incorrect recommendations and allowing abstention under a known prior.

    Source: §1 · pp. 1–2

  • Method

    Screen-and-Confirm combines successive uniform screening with a confirmation batch allocated using conservative empirical gap estimates.

    Source: §1 · p. 2

  • Results

    For Gaussian priors and rewards, S&C attains the optimal rate up to constants as α+δ↓0 and matches exact leading constants for fixed positive abstention and shrinking abstention with α/δ→∞.

    Source: §6 · p. 12

  • Takeaways & Limitations

    With α=0, S&C removes the additional log(1/δ) factor from the upper bound of Jang et al. (2024), yielding the Θ(1/δ) dependence for fixed model parameters.

    Source: §1 · p. 2, §6 · p. 12

    The analysis is under independent Gaussian priors and Gaussian rewards; extending the results to non-Gaussian rewards and dependent priors is left for future work.

    Source: §2.1 · p. 3, §6 · p. 12

Abstract

from arXiv · show

We study the Bayesian fixed-confidence best-arm identification problem in which a learner can abstain from making a terminal recommendation. Subject to a target error probability $\delta$ and an abstention budget $\alpha$, we propose Screen-and-Confirm (S&C) and analyze its expected stopping time. We further derive the minimum expected stopping time for any algorithm that satisfies these constraints. For Gaussian priors and rewards, as $(\delta,\alpha)\downarrow(0,0)$, we establish matching upper and lower bounds up to multiplicative constants, with rate $\kappa_\nu^2[1+\log((\alpha+\delta)/\delta)]/(\alpha+\delta)$, where $\kappa_\nu$ is the prior density of the top-two gap at zero, highlighting that nearly tied instances govern the sampling cost. When abstention is disallowed ($\alpha=0$), S&C yields the optimal $\Theta(1/\delta)$ dependence for fixed model parameters, removing the additional $\log(1/\delta)$ factor in the upper bound of Jang et al. (2024) under our Gaussian assumptions. We further characterize the exact multiplicative constant of the minimum expected stopping time for practical regimes including (i) fixed $\alpha \in (0,1)$ and (ii) $\alpha/\delta\to\infty$, which are also achieved by S&C.

1 Introduction

The introduction frames Bayesian fixed-confidence best-arm identification with abstention as a way to leave difficult, nearly tied instances unresolved while controlling prior-averaged error and abstention. It positions the work as combining sampling and selection, with S&C, matching bounds, and exact-constant results for specified regimes.

1 Introduction

  • Nearly equal best and second-best means can require too many observations for reliable identification, making an inconclusive outcome potentially preferable.The introduction illustrates this with A/B testing and drug screening, where a decision may be deferred.Source: §1 · p. 1
  • Bayesian constraints let the learner distribute error and abstention budgets across instances, addressing how much evidence to collect and which instances to leave unresolved.The model averages performance over a known prior on the means and permits either an arm recommendation or abstention.Source: §1 · pp. 1–2
  • The paper introduces Screen-and-Confirm (S&C), combining successive uniform screening with a confirmation batch allocated using conservative empirical gap estimates.The analysis establishes matching upper and information-theoretic lower bounds, including exact leading constants in two practical regimes.Source: §1 · p. 2

1.1 Related Work

  • The work studies Bayesian FC-BAI with abstention alongside prior research on fixed-confidence lower bounds, characteristic time, and Bayesian sampling rules.It derives lower bounds under prior-averaged error and abstention constraints, whereas cited Bayesian sampling studies use different objectives.Source: §1.1 · p. 2
  • For Bayesian FC-BAI without abstention, Jang et al. (2024) gives a lower bound of order κν^2/δ and an upper bound with an additional log(1/δ) factor; this work removes that factor at α=0.The introduction also notes that the fixed-budget Bayesian literature studies misidentification probability and simple regret (Atsidakou et al., 2023).Source: §1.1 · p. 2
  • The paper’s abstention formulation also relates to reject-option decision theory, while abstention analysis in a fixed-budget Bayesian setting is discussed separately.The cited fixed-budget work identifies a polynomial-to-exponential transition in error probability (Huang et al., 2026).Source: §1.1 · p. 2
  • The related-work discussion distinguishes deterministic budget bounds from the expected cost of adaptive stopping and notes that the joint limit depends on both risk budgets.It says the fixed-abstention result requires trimming by the full characteristic time.Source: §1.1 · p. 3
  • The paper notes an analogy between abstention and erasure decoding in information theory.The introduction points readers to Appendix H for this connection.Source: §1.1 · p. 3

2 Problem Formulation and Preliminaries

The paper formulates Bayesian best-arm identification with error and abstention budgets, then uses the top-two gap and characteristic time to describe prior difficulty and optimal trimming.

2.1 Model and Bayesian Risk Constraints

  • The model draws arm means from a known product Gaussian prior with fixed, known prior means and common variance; conditional rewards are independent Gaussian observations.The best arm is the arm with largest mean and is unique almost surely.Source: §2.1 · p. 3
  • A policy specifies adaptive sampling, stopping, and a terminal decision; the decision is either an arm or abstention, and the sample size is a stopping time.The terminal decision is measurable at the stopping time.Source: §2.1 · p. 3
  • Bayesian probabilities and expectations average over the prior on the instance means, as well as observation and algorithmic randomness.For a fixed instance, probability and expectation are over observations and internal randomization.Source: §2.1 · p. 3
  • The optimization defines the minimum prior-averaged expected sample size among policies satisfying error and abstention constraints.Feasible policies stop almost surely and obey the prescribed budgets.Source: §2.1 · p. 3

2.2 Prior Mass near Ties and the Characteristic Time

  • The top-two gap Γ is the difference between the largest and second-largest means, and κν is identified as its density at zero.The near-tie density measures prior mass near a tie between the two best arms and is finite and strictly positive.Source: §2.2 · p. 4
  • The a-trimmed expectation Vν(a) is related to the characteristic time, and αVν(α) converges to 8κν^2 as α decreases to zero.After normalization by 1−a, Vν(a) is the lower-tail conditional mean of H, described as a lower-tail analogue of CVaR.Source: §2.2 · p. 4
  • For fixed K, the characteristic time H(µ) is proportional to Γ^-2 up to constants independent of the instance.Under unit-variance Gaussian rewards, H is the reciprocal of the largest achievable information per observation against an alternative best arm.Source: §2.2 · p. 4

3 Algorithm and Upper Bounds

Screen-and-Confirm screens arms in stages, uses estimated difficulty to decide whether to confirm a recommendation, and otherwise applies a terminal rule. Its guarantees include feasible stopping and sampling-cost bounds across abstention regimes.

3.1 Screen-and-Confirm (S&C)

  • At the first successful screening stage, S&C constructs conservative gap estimates and uses the estimated characteristic time for a hardness check and allocation.If the hardness check passes, it collects an independent confirmation batch allocated using the estimated gaps; otherwise, or if confirmation fails, it applies the terminal rule.Source: §3.1 · pp. 4, 6, 7
  • The stage allowance qj controls inaccurate screening and also informs confirmation-batch size; normalization Z accounts for the probabilities of reaching stages.The choices bound the combined probability of inaccurate screening and failed confirmation by 2η(α+δ).Source: §3.1 · pp. 5–6
  • A finer screening stage is reached mainly on nearly tied instances, because its inverse-square threshold cost is offset by the small prior probability of those instances.If reached stages are accurate, reaching a finer stage requires Γ≤3dj; the prior probability of this event is bounded proportionally to dj.Source: §3.1 · p. 6
  • Screening samples every arm at geometrically increasing stages; each failed check halves the gap threshold and advances to a finer stage.The finest threshold is chosen so that, if reached stages are accurate, failure at stage zero implies H(µ)≥ha.Source: §3.1 · pp. 5–6
  • The terminal rule randomizes between recommending the last candidate and abstaining, returning the candidate with probability δ/(α+δ).It is used if screening never succeeds, the hardness check fails, or confirmation fails.Source: §3.1 · p. 7

3.2 Feasibility and Upper Bounds Analysis

  • S&C is (δ, α)-feasible and has a deterministically bounded stopping time.The theorem also provides uniform and regime-specific expected stopping-time upper bounds.Source: §3.2 · p. 8
  • S&C achieves O(κν^2/δ) expected samples with no abstention, O(log(1/δ)) for fixed α, and O(δ^-p log(1/δ)) when α=δ^p.The no-abstention upper bound removes the additional log(1/δ) factor in Jang et al. (2024); matching lower bounds establish rate optimality, with sharp leading constants in the fixed-positive and vanishing-abstention-dominant regimes.Source: §3.2 · p. 8
  • As α/δ→∞, screening, rounding, and inaccurate-screening costs are lower order than β/(α+δ); for shrinking α with α/δ→∞, β scales as log(α/δ).For fixed α, the expected stopping-time expression involves Vν(α), with β/log(1/δ)→1.Source: §3.2 · p. 9

4 Lower Bounds

The section establishes information-theoretic lower bounds for any adaptive randomized policy satisfying the Bayesian risk constraints, then compares them with Screen-and-Confirm’s upper bounds. The bounds establish rate optimality and sharp leading constants in the fixed-positive-abstention and vanishing-abstention-dominant regimes.

4 Lower Bounds

  • The lower bounds apply to any adaptive randomized policy satisfying the Bayesian risk constraints, covering arbitrary budget ratios and exact-constant regimes.The analysis first establishes rates for arbitrary budget ratios, then exact leading constants in practical regimes.Source: §4 · p. 9
  • For near-tie instances, the proof compares paired positive- and negative-gap distributions and uses change of measure to obtain a sample-size lower bound.The subprior is restricted to a near-tie interval with width proportional to (α+δ)/κν.Source: §4 · p. 10
  • For fixed α, the lower-bound argument compares instances with alternatives where their best arm is suboptimal, then integrates instance-wise bounds after trimming.The resulting coefficient is Vν(α) as δ ↓ 0.Source: §4 · p. 10
  • For shrinking α, truncating a feasible fixed-confidence policy yields a fixed-budget policy whose tail probabilities support the lower bound.The truncation abstains when the stopping time exceeds T, giving abstention at most α + Pν(τ > T).Source: §4 · p. 10
  • Matching lower bounds show that Screen-and-Confirm is rate-optimal for sufficiently small δ and α, with sharp leading constants in two practical regimes.The sharp-constant regimes are fixed positive abstention and vanishing abstention with α/δ → ∞.Source: §4 · p. 10
  • Uniform frequentist constraints yield an asymptotic sample complexity of (1−α)H(µ) log(1/δ), with fixed abstention improving the benchmark only by factor 1−α.Unlike the Bayesian constraint, the frequentist abstention probability is bounded by α at every instance.Source: §4 · p. 11

5 Numerical Experiments

The experiments compare Screen-and-Confirm across abstention and error budgets with a no-abstention baseline. Increasing the abstention budget lowers observed sampling cost, while empirical error and abstention probabilities remain within their targets.

Experimental Setup

  • The Gaussian experiment uses K = 5 arms with ν = (5, 5, 3, 3, 2), and compares α ∈ {10^-1, 10^-2, 10^-3} against SE-early.The tested δ values range from 10^-2 to 10^-5, including intermediate values; each setting uses M = 10^5 prior-generated trials.Source: §5 · p. 11

Benefit of Abstention

  • At every tested δ, increasing α reduces Screen-and-Confirm’s observed mean sample size.Figure 2 (left) illustrates the sampling-cost reduction.Source: §5 · p. 11
  • When δ is small relative to α, Screen-and-Confirm’s mean sample size grows logarithmically as δ decreases, unlike SE-early’s order-1/δ growth.For fixed α > 0, the abstention budget controls the contribution of nearly tied instances.Source: §5 · pp. 11–12
  • Empirical error probabilities stay below δ and empirical abstention probabilities stay below α at every tested δ.The middle panel marks the target error probability; the right panel shows abstention probability.Source: §5 · p. 12

6 Conclusion

The paper establishes optimal sample-complexity rates for Screen-and-Confirm under independent Gaussian priors and Gaussian rewards, including exact leading constants in two abstention regimes. Its conclusion also contrasts Bayesian abstention with uniform frequentist constraints.

6 Conclusion

  • Screen-and-Confirm achieves the optimal rate up to constants as α + δ ↓ 0 and matches exact leading constants for fixed positive α and α ↓ 0 with α/δ → ∞.The fixed-α coefficient Vν(α) retains the easiest prior fraction 1−α as measured by characteristic time H; in the shrinking regime, κν determines the sharp constant 8κν^2.Source: §6 · p. 12
  • The results are established for independent Gaussian priors and Gaussian rewards; non-Gaussian rewards and dependent priors remain directions for future work.Source: §6 · p. 12
  • Any fixed positive abstention budget changes the optimal δ dependence from 1/δ to log(1/δ), because Bayesian abstention can concentrate on difficult instances.Under uniform frequentist constraints, fixed abstention improves only the leading constant, while vanishing abstention gives no leading-order improvement.Source: §6 · p. 12

AI Disclosure

The appendix develops the Gaussian-prior properties used to analyze the characteristic time, including the near-zero density of the top-two gap and continuity of the characteristic time on unique-best instances.

AI Disclosure

  • The manuscript reports that Claude Code (Opus 5.5) and GPT-6 Astra assisted with mathematical arguments, proof strategies, and exposition, with the author retaining responsibility for the final manuscript.Source: AI Disclosure · p. 12

A Prior Distribution of the Characteristic Time

A.1 The Density of the Top-Two Gap

  • The top-two gap Γ has a continuous, strictly positive density, with fΓ(x) approaching κν > 0 as x decreases to zero.The density at zero is defined as fΓ(0) = κν.Source: §A.1 · pp. 14–15

A.2 Bounds and Continuity of the Characteristic Time

  • For every unique-best instance, the maximum information allocation is attained with strictly positive weights, and the characteristic time H is continuous within each unique-best region.For two arms, H(µ) = 8/Γ².Source: §A.2 · pp. 16–17

A.3 The Distribution and Quantiles of the Characteristic Time

The appendix characterizes the distribution and trimmed expectation of the characteristic time, then derives tail and small-gap properties used for asymptotic limits.

A.3 The Distribution and Quantiles of the Characteristic Time

  • H is finite, positive, and atomless almost surely, and every positive interval has positive prior probability, yielding a unique tail quantile ha for each a in (0, 1).Source: §A.3 · p. 17

A.5 The Tail, Quantile, and Trimmed-Expectation Limits

  • The trimmed expectation Vν(a) is attained by retaining instances with H(µ) ≤ ha, while the tail behavior of H is tied to the near-zero density κν of the top-two gap.The minimizing indicator gives Vν(a) = (1 − a)Eν[H | H ≤ ha].Source: §A.3 · p. 18, §A.5 · pp. 20–21

A.4 The Characteristic Time when the Third-Best Arm is Separated

  • When the third-best arm is separated by at least ε and 2(K − 2)Γ²/ε² < 1, the characteristic time is bounded using an allocation that limits weight on arms ranked third or lower.The bound uses ρ, the total allocation weight on arms 3 through K.Source: §A.4 · p. 19

B Proof of the Error and Abstention Guarantees

The proof establishes risk guarantees by linking accurate screening to the true best arm and controlling confirmation errors conditional on the complete screening record. It then bounds screening and confirmation costs across admissible risk budgets.

B Proof of the Error and Abstention Guarantees

  • An accurate successful screening stage identifies the true best arm, and its recorded gap estimates are relatively accurate, bounding the characteristic time used for confirmation.The proof also relates reaching finer stages to small true top-two gaps.Source: B Proof of the Error and Abstention… · pp. 22–23

B.1 Conditioning on the Complete Screen

  • Conditional on the complete screening record, the probability that confirmation comparisons fail is bounded by the stage allowance qj, enabling the bound to be averaged over reached stages.Source: §B.1 · p. 25

B.2 The Rejection Coin and Completion of the Risk Proof

  • The terminal rejection coin divides rejection events between recommendation and abstention, completing the error and abstention risk bounds.Abstention occurs only through this terminal coin.Source: §B.2 · p. 27

C.1 Bounds for the Screening Scales

C.2 Probabilities of Reaching the Screening Stages

  • The probability of reaching finer screening stages is controlled by the prior probability of small top-two gaps, which bounds the expected sums over reached stages.Source: §C.2 · pp. 29–30

C.3 Expected Number of Screening Observations

  • The expected number of screening observations admits a uniform bound for every admissible pair of risk budgets.Source: §C.3 · p. 30

C.4 Expected Number of Confirmation Observations

The appendix bounds the confirmation cost through the characteristic time used to size its batch, derives a uniform expected-cost bound, and gives asymptotic upper bounds for specified abstention regimes.

C.4 Expected Number of Confirmation Observations

  • At a successful screening stage, the characteristic time used to size the confirmation batch is bounded in terms of the screening threshold.No confirmation batch is collected when screening is not accepted.Source: §C.4 · p. 31

C.5 The Uniform Upper Bound

  • For all admissible budgets, the expected stopping time has a uniform upper bound with a constant depending on the fixed model parameters.Source: §C.5 · p. 32

D Asymptotic Upper Bounds on the Expected Cost

D.1 Fixed Positive Abstention

  • For fixed positive α, the appendix provides an asymptotic upper bound on expected stopping time as δ tends to zero.Source: §D.1 · p. 34

D.2 Shrinking Abstention with α/δ →∞

This section develops upper-bound results for shrinking abstention when α/δ→∞, including power-path and iterated-limit cases, and lower-bound tools for Bayesian best-arm identification based on a flat local subprior. It treats small risk budgets and transfers the lower bound to the minimum expected stopping time.

D.2 Shrinking Abstention with α/δ →∞

  • Theorem 4 gives an algorithmic upper bound as α↓0 with α/δ→∞, with corollaries for α=δ^p, 0<p<1, and the iterated limit δ↓0 before α↓0.For fixed p, the corollary uses log(α/δ)=(1−p)log(1/δ).Source: §D.2 · pp. 34–35

E.1 The Lower Bound at Fixed Positive Abstention

  • For every fixed α∈(0,1), Theorem 5 establishes a lower bound whose limiting scale is Vν(α) as δ↓0.The proof bounds the policy’s expected sample size divided by log(1/δ), then takes δ↓0, ε↓0, and R↑∞.Source: §E.1 · pp. 36, 39

E.2 A Submeasure: Flat Local Subprior

  • The flat local subprior Qρ is dominated by the true Gaussian prior, has constant local gap density κρ→κν as ρ↓0, and assigns fair conditional signs to the gap.Its support keeps the designated arm pair as the top two arms.Source: §E.2 · pp. 41–42
  • The local subprior has a constant top-two gap density κρ, and every (δ, α)-feasible policy has error and abstention masses under Qρ at most δ and α.Its gap density follows by integrating over the background and summing over the two gap signs.Source: §E.2 · p. 42

E.3 The Lower Bound for Arbitrary Budget Ratios

  • For all sufficiently small α+δ, every feasible policy and the minimum expected stopping time obey a lower bound with a numerical constant independent of K, ν, and σ0.The small-budget threshold may depend on K, ν, and σ0.Source: §E.3 · pp. 43, 46

E.4 A Sharp Lower Bound When the Abstention Budget Tends to Zero

  • For α→0 with α/δ→∞, Theorem 6 establishes a lower bound on the minimum expected stopping time.The finite-horizon argument also gives A_T(v)+B_T(v) ≥ 1−η and min{A_T(v), B_T(v)} ≥ (1−η)Φ(−|v|).Source: §E.4 · pp. 47–48
  • The lower bound also holds for the minimum expected stopping time T⋆ρ, completing the proof of (E.36).Source: §E.4 · p. 51

E.5 Proof of Corollary 2

The lower bounds and Screen-and-Confirm upper bounds match across shrinking-budget paths, including vanishing abstention-dominant and fixed positive abstention regimes.

E.5 Proof of Corollary 2

  • Matching lower and Screen-and-Confirm upper bounds establish the optimal expected sampling cost up to constants along every path with α + δ ↓0.Source: §E.5 · p. 51
  • For αn →0 with αn/δn →∞, Theorems 6 and 4 yield the matching result; the power path α = δ^p, 0 < p < 1, is included.Source: §E.5 · p. 51
  • For fixed α ∈(0, 1), the optimal-value limit exists and equals Vν(α), and the iterated limit follows by taking δ ↓0 before α ↓0.Source: §E.5 · p. 52

F Frequentist Fixed-Confidence Comparison

Under uniform frequentist constraints, abstention changes fixed-instance sample complexity by a factor tied to the abstention budget, while Gaussian-prior averaging can yield infinite cost. The section also gives a scalar computation of the optimal allocation.

F Frequentist Fixed-Confidence Comparison

  • For fixed α, the optimal frequentist sample complexity has sharp leading coefficient (1 − α)H(µ), while along paths with α, δ →0 its ratio to H(µ)log(1/δ) tends to one.The coefficient is attainable by abstaining initially with probability α and otherwise running a classical fixed-confidence policy.Source: F Frequentist Fixed-Confidence… · p. 52, §F.2 · p. 55, §F.3 · p. 55

F.1 Removing Abstention by Restarting

  • Restarting independent copies after each abstention gives a non-abstaining policy with error at most δ/(1 − α), linking abstaining and ordinary fixed-confidence BAI.The construction terminates almost surely and preserves the feasible policy's sampling-cost comparison.Source: §F.1 · pp. 53–54

F.2 The Finite Lower Bound and the Fixed-Abstention Limit

  • The finite lower bound follows by applying the classical change-of-measure lower bound after the restart reduction, and its fixed-α asymptotic coefficient is sharp.The construction that attains the coefficient abstains initially with probability α and otherwise uses error budget δ/(1 − α).Source: §F.2 · pp. 54–55

F.3 Vanishing Abstention and Prior-Averaged Cost

  • Under the Gaussian prior, every uniformly frequentist-feasible policy has infinite prior-averaged sample size when α + 2δ < 1.Uniform constraints require recommendation probability at least 1 − α even on arbitrarily small-gap instances, unlike Bayesian constraints that allow budgets to concentrate across instances.Source: F Frequentist Fixed-Confidence… · p. 52, §F.3 · p. 55

G.1 A Scalar Equation for the Optimal Allocation

  • The allocation computation reduces the Gaussian optimal-allocation problem to a scalar equation, with challenger weights set to their lower bounds at the optimum.Source: §G.1 · pp. 56–58
  • For Gaussian rewards, bisection computes the unique scalar optimizer z*, whose substitution gives the optimal allocation w*(µ) and characteristic time H(µ).For Screen-and-Confirm, the calculation is applied to the instance µℓ in (3.6).Source: §G.1 · pp. 56, 58

G.2 Computation of the Prior Quantile

The prior quantile can be computed before collecting bandit observations, using a small-budget approximation or Monte Carlo estimation. Its approximation applies as the algorithm’s parameter a tends to zero, while continuity governs the fixed-abstention regime.

G.2 Computation of the Prior Quantile

  • The quantile depends only on the prior and a, so it can be computed before bandit observations; Monte Carlo estimation draws independent prior mean vectors and sorts their gap-based values.The best arm is unique and the gaps are positive almost surely.Source: §G.2 · pp. 58–59
  • For every fixed a in (0,1), the empirical Monte Carlo quantile converges almost surely to the target quantile.Source: §G.2 · p. 59
  • As a decreases to zero, ν/a^2 approximates the quantile with vanishing relative error, and κν is computable by one-dimensional numerical quadrature.In the algorithm, a=(1−4η)(α+δ), so a tends to zero when α+δ does.Source: §G.2 · p. 59
  • For fixed α in (0,1) as δ decreases to zero, a tends to α and continuity of the quantile map gives h_a tending to h_α.Source: §G.2 · p. 59

H Related Work: Erasure Decoding

  • Abstention in best-arm identification is analogous to erasure decoding, but adaptive arm sampling and stopping make sampling cost part of the objective.Erasure decoding distinguishes incorrect decisions from inconclusive outcomes; cited analyses study tradeoffs between total and undetected error probabilities.Source: H Related Work: Erasure Decoding · p. 59

Related papers

Loading 2610.30384v1…