技術要約：棄権を伴うベイズ的最良腕識別

1. 問題定式化

本論文は、ベイズ設定における**固定予算最良腕識別（Fixed-Budget Best-Arm Identification: FB-BAI）**問題を取り扱う。標準的なFB-BAIでは、学習者は未知の平均報酬を持つ$K$個の腕から適応的にノイズを含む観測値を収集するためのサンプリング予算$T$を与えられ、平均が最も高い腕を推奨しなければならない。

本研究の新規性は、終末棄却（terminal abstention）オプションの導入である。学習者は、特定の腕の推奨ではなく、結論不能な決定（「？」で示される）を出力することが許される。このオプションは、規定された棄却予算$\alpha \in (0, 1)$によって制約されており、これは棄却する確率が$\alpha$を超えてはならないことを意味する。

性能指標は、**未検出エラー確率（probability of undetected error）**であり、これは学習者が棄却を行わず、かつ劣位の腕を推奨してしまう確率として定義される。目的は、$P(\text{abstain}) \le \alpha$という制約の下で、この未検出エラー確率を最小化することである。

問題は、各腕の平均 $\mu_i$ が $N(\nu_i, \sigma_0^2)$ から、報酬 $Y_{i,s}$ が $N(\mu_i, 1)$ から生成されるガウス事前分布の下で定式化されている。分析は、$T \to \infty$ とした後に $\alpha \downarrow 0$ とする漸近的な領域に焦点を当てている。

2. 手法と主要概念

困難度パラメータ：トップ2ギャップ密度

本論文は、問題の根本的な困難さが、トップ2ギャップ $\Gamma = \mu_{(1)} - \mu_{(2)}$ がゼロ付近にある密度によって支配されていることを特定している。著者らは、困難度パラメータ $\kappa_\nu$ を以下のように定義する：
$$\kappa_\nu = \sum_{i \neq j} \int_{\mathbb{R}} f_i(x)f_j(x) \prod_{k \neq i,j} F_k(x) \, dx$$
ここで、$f_i$ および $F_i$ は腕 $i$ の事前密度および累積分布関数である。このパラメータは、上位2つの腕がほぼ同値であるインスタンスに対して割り当てられた「事前確率質量」を表している。論文では、$\varepsilon \downarrow 0$ のとき $P_\nu(\Gamma \le \varepsilon) = \kappa_\nu \varepsilon + o(\varepsilon)$ となることが示されている。

アルゴリズム：PGWS

著者らは、**事後ギャップ重み付きサンプリング・ウィズ・アブステンション（Posterior Gap Weighted Sampling with Abstention: PGWS）**と呼ばれる適応的アルゴリズムを提案している。

• サンプリング規則: PGWSは、腕の平均に対するガウス事後分布を維持する。すべての腕が十分にサンプリングされることを保証するために「強制探索（forced exploration）」フェーズを採用する。その後のラウンドでは、現在のリーダーと他の腕 $i$ との間の事後平均ギャップの逆二乗に比例して、腕 $i$ をサンプリングする：
  $$p_i(t) \propto \hat{\Delta}_i(t)^{-2}$$
  この割り当て戦略は、リーダーとその最も近い挑戦者にサンプルを集中させる。
• 終末決定規則: 時刻 $T$ において、アルゴリズムはリーダーとその挑戦者を分離する、最小のペアワイズ事後ガウス指数を表す統計量 $R_T$ を計算する。アルゴリズムは、$R_T$ が較正された閾値 $r_{T,\alpha}$（$R_T$ の下位 $\alpha$ 分位点）を下回る場合に棄却を行う。これにより、棄却確率が正確に $\alpha$ になることが保証される。

理論的枠組み

分析は、パラメータ空間を、特定の腕のペアがトップ2となる領域に分解することに基づいている。著者らは、複雑な $K$ 腕の問題を、ギャップに関する一様事前分布を持つ単純な2腕仮説検定問題に還元するために、**フラット局所副事前分布（flat local subprior）**の手法を用いている。これにより、タイトな情報理論的境界の導出が可能となる。

3. 主要な結果

相転移：多項式から指数関数へ

中心的な知見は、未検出エラー確率の減衰率における相転移である。

• 棄却なし ($\alpha = 0$): 最適なベイズエラー確率は、予算 $T$ に対して多項式的に減衰する。具体的には、$E_T(0) = \Omega(T^{-1/2})$ である。この遅い減衰は、トップ2ギャップが $T^{-1/2}$ のオーダーである「ニア・タイ（僅差）」のインスタンスによって引き起こされる。これらは稀ではあるが、有限のサンプルでは統計的に区別不可能である。
• 棄却あり ($\alpha > 0$): わずかな正の棄却予算を導入することで、エラーの減衰は指数関数的へと移行する。最適な未検出エラー確率は以下のようになる：
  $$\lim_{\alpha \downarrow 0} \lim_{T \to \infty} \frac{1}{\alpha^2 T} \log E_T(\alpha) = -\frac{1}{8\kappa_\nu^2}$$
  これは、$E_T(\alpha) \approx \exp\left(-\frac{\alpha^2 T}{8\kappa_\nu^2}\right)$ であることを意味する。

最適性

本論文は、一致する情報理論的下界とアルゴリズム的上界を確立している。

• 下界: 棄却制約を満たすいかなる方策も、エラー指数 $-1/(8\kappa_\nu^2)$ よりも優れた結果を得ることはできない。
• 上界: PGWSアルゴリズムはこの指数を達成し、$\alpha^2 T$ の対数スケールにおいて漸近的に最適であることを証明している。

頻度論的 vs ベイズ的対比

本論文は、この多項式から指数関数への改善が排他的にベイズ的な現象であることを示している。

• 頻度論的設定（正のギャップを持つ固定されたインスタンス）では、標準的なFB-BAIはすでに指数関数的なエラー減衰を示す。棄却オプションを追加しても、指数の低次項（具体的には $O(\alpha\sqrt{T})$ のオーダーの項）を改善するだけであり、主要な指数レートは変わらない。
• ベイズ的設定では、エラーは「ニア・タイ」の事前確率によって支配される。棄却によって、学習者はこれらの曖昧なインスタンスを「破棄」することができ、これがエラーのスケーリングを根本的に変化させる。

一般化

結果は、ガウスモデルを超えて、正則な1パラメータ指数族（例：ベルヌーイ、ポアソン）にも拡張される。この一般的な設定において、指数は、フィッシャー・ラオ情報座標における $\kappa$ を用いた $-1/(8\kappa^2)$ の形をとる。

4. 意義と主張

本論文は、ベイズ的純粋探索における棄却の利点を厳密に特徴付けたものであると主張している。その意義は以下の点にある：

1. メカニズムの特定: 強制決定型のベイズ的FB-BAIにおけるエラーの根本的な原因として「ニア・タイ」のインスタンスを特定し、棄却がいかにしてこれらのケースを標的にして指数関数的な改善を誘発するかを示した。
2. 最適なアルゴリズム設計: 事後ギャップに基づいて動的にサンプルを割り当て、理論的限界を達成するために棄却を較正する適応的アルゴリズム、PGWSを導入した。
3. 理論的区別: 棄却の価値に関するベイズ的設定と頻度論的設定の根本的な違いを明確にし、劇的な改善が、ニア・タイの困難な構成を含む事前分布を平均化することの結果であることを示した。

著者らは、棄却は希少なリソースであるが、統計的に曖昧なニア・タイのインスタンスに対してそれを使用することが、固定予算のベイズ的設定においてエラー確率を多項式的な小ささから指数関数的な小ささへと変貌させるための最適な戦略であると結論付けている。