Bayesian Fixed-Confidence Best-Arm Identification with Abstention

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 δ and an abstention budget α, 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 (δ,α)↓(0,0), we establish matching upper and lower bounds up to multiplicative constants, with rate κ_ν²[1+log((α+δ)/δ)]/(α+δ), where κ_ν is the prior density of the top-two gap at zero, highlighting that nearly tied instances govern the sampling cost. When abstention is disallowed (α=0), S&C yields the optimal Θ(1/δ) dependence for fixed model parameters, removing the additional log(1/δ) 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 α∈ (0,1) and (ii) α/δ→∞, which are also achieved by S&C.

Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback
Khang Luong, Dinh Thai Son, Hoang Ta +2
arXiv2 Oct 2026PreprintarXiv licenceFull textStatisticsarXiv
Asymptotically Optimal Best Arm Identification with Fixed-Budget under Differential Privacy
Keqin Chen, Jie Bian, Yulian Wu +1
arXiv3 Oct 2026PreprintCC BY 4.0Full textGeneral mathematicsarXiv
FOCUS: Fixed-Confidence Online Causal Learning Using Sequential Adaptive Interventions
Haijie Xu, Chen Zhang
arXiv26 Sep 2026PreprintarXiv licenceFull textStatisticsarXiv
Cost-Aware Best-LLM Identification using Dueling Feedback
Sarvesh Gharat, Nikhil Karamchandani, Jayakrishnan Nair
arXiv24 Sep 2026PreprintCC BY 4.0Full textStatisticsarXiv
Tight Sample Complexity Bounds for Entropic Best Policy Identification
Amer Essakine, Claire Vernade
arXiv21 Sep 2026PreprintarXiv licenceFull textStatisticsarXiv

Cite

BibTeX RIS

BibTeX

@misc{huang2026bayesian,
  title = {{Bayesian Fixed-Confidence Best-Arm Identification with Abstention}},
  author = {Yuqi Huang and Yunlong Hou and Vincent Y. F. Tan},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.30384},
  eprint = {2610.30384},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.30384},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Bayesian Fixed-Confidence Best-Arm Identification with Abstention
AU  - Yuqi Huang
AU  - Yunlong Hou
AU  - Vincent Y. F. Tan
PY  - 2026
DA  - 2026/10/21
PB  - arXiv
DO  - 10.48550/arxiv.2610.30384
UR  - https://arxiv.org/abs/2610.30384
AB  - 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 δ and an abstention budget α, 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 (δ,α)↓(0,0), we establish matching upper and lower bounds up to multiplicative constants, with rate κ_ν^2[1+log((α+δ)/δ)]/(α+δ), where κ_ν is the prior density of the top-two gap at zero, highlighting that nearly tied instances govern the sampling cost. When abstention is disallowed (α=0), S&C yields the optimal Θ(1/δ) dependence for fixed model parameters, removing the additional log(1/δ) 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 α∈ (0,1) and (ii) α/δ→∞, which are also achieved by S&C.
ER  -

Abstract

Related

Cite