Bayesian Fixed-Confidence Best-Arm Identification with Abstention

概要

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.

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

# 論文・記事
Bayesian Fixed-Confidence Best-Arm Identification with Abstention

# 概要
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…

# 原典
https://arxiv.org/abs/2610.30384

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。