arXiv preprint ·
Bayesian Fixed-Confidence Best-Arm Identification with Abstention
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 $(δ,α)\downarrow(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 $α\in (0,1)$ and (ii) $α/δ\to\infty$, which are also achieved by S&C.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning
PQ-Vault: Provably Quantum-Safe Asset Custody for Unmodified Ethereum
One-shot entanglement generation and distillation via Petz recovery and binary hypothesis testing
Generalization Bounds via Vector-Valued $L_p$ Correlation $V_α$
SILMARILS-MV: Information-Theoretically Secure Multi-Verifier Signatures with Dealer-Free Key Issuance and Linear Aggregation for Permissioned Blockchains
Recursive Code Evolution for Task-Oriented Semantic Communications
Get the few papers worth your time in Machine Learning every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.