aiqbench analysis
This is a theoretical machine learning paper on sequential decision-making: a bandit-style learner that can abstain from its final recommendation. It proves matching upper and lower bounds on expected sampling cost for Gaussian priors and rewards, and improves a known logarithmic factor from prior work under those assumptions. For ML readers, the main takeaway is that nearly tied options drive sampling cost, and the results are mathematical and tied to specific modeling assumptions rather than to practical systems.
Bayesian Fixed-Confidence Best-Arm Identification with Abstention
arXiv:2610.30384v1 Announce Type: new 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.
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.
Machine Learning (cs.LG)
arXiv:2610.30384 [cs.LG]
(or arXiv:2610.30384v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2610.30384 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 256 words