Skip to content

Bayesian Fixed-Confidence Best-Arm Identification with Abstention

Oct 2026 · 0 citations
Computer Science Mathematics

TL;DR

The Bayesian fixed-confidence best-arm identification problem in which a learner can abstain from making a terminal recommendation is studied and Screen-and-Confirm (S&C) is proposed and its expected stopping time is analyzed.

Abstract

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.

View source

Similar papers

Preprint Oct 2026

The Price of Choice in Selective Prediction

A selective classifier may be claimed to satisfy a risk-coverage contract if some rule from a predeclared menu (a threshold or a union of $K$ score intervals) attains coverage at least $\kappa$ and error at most $\alpha$. Refuting this existential claim requires ruling out every permitted rule. The intersection-union t...

Daniel Cieslak, Andrzej Czyzewski · 0 citations
#machine learning Preprint Oct 2026

Reliable Scale-Free Bandits via Empirical Likelihood

The exact exponent of linear regret deviations on two-armed Gaussian instances with common variance is determined and a matching lower bound among policies satisfying the same expected-regret budget on every such Gaussian instance is established.

Pratham Gupta, Alhad Sethi, Shubhada Agrawal · 1 citation
#artificial intelligence Preprint Sep 2026

Sharp Limits for Honest Uncertainty in Hard-Budget Repeated Evaluation

Repeated evaluation can estimate a benchmark score accurately while still requiring replication to certify narrow uncertainty. We characterize that requirement on a fixed grid of $M$ tasks with $L$ binary paths per task under the hard budget $(M+t)K$, where each path costs at most $K$ responses or episodes. For fixed $...

Ye-Zhou Cheng, Run-Jia Du, Ze-Ming Liu et al. · 0 citations
#machine learning Preprint Oct 2026

The Price of Current-Effect Inference in Nonstationary Multi-Armed Bandits

Adaptive experiments use bandit algorithms to favor interventions with higher expected rewards. However, decision-makers also require reliable inference on current treatment effects: differences between intervention and reference-arm mean rewards at the present time, rather than historical averages. These objectives co...

Sharan Sahu, Martin T. Wells · 0 citations
#machine learning Preprint Sep 2026

Posterior Tempering Explains Variance Inflation in Linear and Generalized Linear Thompson Sampling

This work introduces a variant of the Thompson Sampling algorithm that uses a fractional or $\alpha$-posterior instead of the standard posterior, and identifies general regularity conditions on the prior and reward distributions that enable a regret analysis of $\alpha$-TS without assuming any tractable approximation o...

Prateek Jaiswal, D. Pati, A. Bhattacharya et al. · 0 citations

Related blog posts

MIT News · Artificial Intelligence Nov 17, 2026

Learning the language of machine learning

By studying the computational foundations of language learning, Associate Professor Jacob Andreas builds intelligent systems that can communicate effectively with humans.

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.