技術要約：複数の正解および非回答可能推定値を伴うランキング・アンド・セレクション

問題定式化

本論文は、従来の「最良腕識別（best-arm identification）」のテンプレートでは対処が困難な、2つの特定の課題を特徴とする構造化された設定における**固定精度ランキング・アンド・セレクション（R&S）**問題に取り組んでいる。

1. 複数の正解: 正解の集合 $A^\star(\theta)$ は、複数の要素（例：許容誤差 $\epsilon$ 以内の「良好な」代替案のいずれかを選択すること）を含む可能性がある。
2. 非回答可能な推定値: ノイズの多い観測により、経験的推定値が一時的に「回答可能集合」$\Theta^\star$（有効な回答が存在しない領域）の外側に外れることがある。これは、マルチフィデリティR&S（経験的平均がバイアス制約に違反する場合）や、デュエリング・バンディット（推定された選好がサイクルを誘発し、コンドルセ勝者の存在を妨げる場合）のようなシナリオで発生する。

目標は、すべての $\theta \in \Theta^\star$ に対して正解を選択する確率が少なくとも $1-\delta$ となるような停止規則 $\tau_\delta$ および決定規則 $\hat{a}_{\tau_\delta}$ を設計し、期待総サンプリングコスト $E_\theta[B_{\tau_\delta}]$ を最小化することである。このフレームワークは、異なるコストを持つ異種混合の測定タイプを許容する。

手法：統一フレームワーク

著者らは、「ピットフォール適応型ノミネーション（pitfall-adapted nomination）」の視点（Qin and You, 2026）を一般化し、集合値の回答と一時的な非回答可能性を扱うための統一フレームワークを提案している。その中核となる構成要素は以下の通りである。

1. 回答ごとの受理集合とピットフォール

単一の真の回答に焦点を当てるのではなく、本フレームワークは候補となる回答 $a \in A$ ごとに問題を分解する。

• 受理集合 ($\Theta^\star_a$): 回答 $a$ が正しいパラメータの集合。
• 拒絶領域 ($Alt_a$): 回答可能であるが $a$ が正しくないインスタンスの集合。
• ピットフォール ($X_a$): 拒絶領域 $Alt_a$ は、インデックス付けされた「ピットフォール」$x$ による単純な凸集合の有限和として分解される。ピットフォールとは、回答が失敗する特定の方法（例：現在のノミニーに対して特定の挑戦者が勝利するケース）を表す。

2. 限定された一般化尤度比（GLR）停止

非回答可能な推定値を扱うために、著者らは各候補 $a$ に対して限定されたGLR統計量 $Z_n(a)$ を定義する：
$$Z_n(a) = \inf_{\vartheta \in Alt_a} \Gamma(N_n; \hat{\theta}_n, \vartheta) - \inf_{\vartheta \in \Theta^\star_a} \Gamma(N_n; \hat{\theta}_n, \vartheta)$$
ここで、$\Gamma$ は座標ごとのカルバック・ライブラー（KL）ダイバージェンスの総和であり、$\hat{\theta}_n$ は制約なしの最大尤度推定量（MLE）である。

• 推定値が非回答可能であっても、拒絶領域における最良の適合と受理領域における最良の適合を比較することで、統計量は定義され続ける。
• 停止規則 $\tau_\delta$ は、$\max_{a \in A} Z_n(a) \geq \beta_{n,\delta}$ となったときにトリガーされる。
• 決定規則はこの統計量を最大化する回答を選択し、未定義の経験的勝者に対する堅牢性を提供する。

3. Max-Max-Min 特性値

著者らは、特性値 $\Gamma^\star(\theta)$ に着想を得た、期待コストの下界を導出している：
$$\Gamma^\star(\theta) \triangleq \max_{p \in \Delta_U} \max_{a \in A} \min_{x \in X_a} D_{a,x}(p; \theta)$$
ここで、$D_{a,x}$ はピットフォール $x$ を排除するためのコスト正規化された情報率である。

• 内側のmin は、特定の回答に対して排除するのが最も困難なピットフォールを特定する。
• 真ん中のmax は、学習者が証明しやすい（certifyしやすい）回答を指名することを可能にする（これは推定値が非回答可能である場合や、複数の正解がある場合に極めて重要である）。
• 外側のmax は、サンプリング配分 $p$ を最適化する。
  この値は、停止予算の漸近的なスケーリングを規定する：$E_\theta[B_{\tau_\delta}] \gtrsim \log(1/\delta) / \Gamma^\star(\theta)$。

4. ENDS アルゴリズム

著者らは、ENDS（Estimation, Nomination, Detection, Selection）という一般的な手順を導入している：

1. 推定 (Estimate): 推定値 $\theta_n$（例：事後分布のサンプル）を計算する。
2. 指名 (Nominate): GLR統計量 $Z(a; p_n, \theta_n)$ を最大化する暫定的な回答 $a_n$ を選択する。
3. 検出 (Detect): $a_n$ に対する主要なピットフォール $x_n$（最も混乱を招く代替インスタンス）を特定する。
4. 選択 (Select): 特定されたピットフォールに対する最悪のケースの代替案と現在の推定値を区別するためのコストを最小化する、コストを考慮した情報指向サンプリング（IDS）分布 $H_{a_n, x_n}$ から次の測定値をサンプリングする。

主な貢献

1. 統一フレームワーク: 複数の正解と非回答可能な推定値を同時に扱う、コストを考慮した固定精度R&Sのための単一の構造的レシピ。これは、純粋探索型バンディットとシミュレーション最適化の間の溝を埋めるものである。
2. 理論的特性付け: 回答マップが集合値であり、推定値が一時的に無効になり得る設定において、既存の下界を一般化するmax-max-min特性値の導出。
3. アルゴリズム的レシピ (ENDS): 推定、指名、ピットフォール検出、およびIDSを組み合わせた移植可能なアルゴリズム。論文では、以下の3つの代表的な問題クラスに対する明示的なインスタンス化を提供している：
   • 良好な代替案の選択（$\epsilon$-best-arm）。
   • マルチフィデリティ・ランキング・アンド・セレクション。
   • コンドルセ勝者を伴うデュエリング・バンディット。
4. 明示的な公式: IDS分布およびGLR統計量の閉形式の表現の導出。

実験結果

広範な数値実験により、ENDSが質的に異なる問題に対して頑健かつ競争力があることが示された。

• 良好な代替案の選択: 分散が未知のガウス設定において、ENDSは（KN, Paulson, ZH-Proc2などの）最先端の手法や一様配分と比較して、一貫して最も低い期待停止予算を達成した。その優位性は代替案の数に応じて拡大する。
• マルチフィデリティR&S: ENDSは、ほとんどの合成インスタンスにおいてMF-GRADおよび高フィデリティのみの手法（TS-KKT-IDS, GRAD）を上回った。特に、低フィデリティの「誤導的な罠」を効果的に処理しており、高フィデリティのみ、あるいは連続最適化の追跡に依存する手法は高いコストを要した。
• デュエリング・バンディット: ENDSは、期待停止コストにおいてベースライン（SAVAGE, DK-WT, SEEBS）を大幅に上回った。著者らは、この優れた性能の一因として、ベースラインで使用されている排除型のルールと比較して、より強力でデカップルされたGLR停止規則を用いていることを挙げている。

意義と主張

本論文は、単一のアルゴリズム言語が幅広いモデル間で転用可能であることの概念実証として位置づけられている。

• 統一性: 複数の正解と非回答可能な推定値の共存は、従来は問題ごとに個別に対処されてきたが、本研究は「回答ごと」の分解を通じてこれらを一括して扱えることを主張している。
• 実用性: 提案された「統一レシピ」は、絶対的なスコアが得られない、あるいは推定値が構造的に制約されている純粋探索型問題に対する実用的なフレームワークを提供する。
• 謙虚な姿勢: 著者らは、停止規則の正確な閾値キャリブレーションが依然として問題依存の未解決課題であることを認めており（実験ではヒューリスティックを使用）、厳密な漸近的上界が特性値と一致することを示すことは今後の課題としている。また、計算負荷の観点から、ENDSは現時点では大規模な問題向けには設計されていないことも述べている。