技術要約：固定予算（Fixed Budget）は、対数因子を除けば固定信頼度（Fixed Confidence）よりも困難ではない

1. 問題設定

本論文は、マルチアームド・バンディットにおける**最良腕識別（Best-Arm Identification: BAI）**問題を取り扱う。これは、学習者が最も高い平均報酬を持つ腕を特定しなければならない、インタラクティブな機械学習における基本的なタスクである。問題は以下の2つの異なる設定下で研究されている：

• 固定信頼度（Fixed-Confidence: FC）: 学習者は目標失敗率 $\delta$ を与えられ、正解の確率 $P(\hat{J} \neq 1) \leq \delta$ を保証する腕 $\hat{J}$ を出力できるまで腕を抽出し続ける。性能は停止時間（サンプル複雑性）によって測定される。
• 固定予算（Fixed-Budget: FB）: 学習者は合計サンプリング予算 $B$ を与えられ、正確に $B$ 回の試行後に推定された最良の腕 $\hat{J}$ を出力しなければならない。性能は予算に対するエラー確率によって測定される。

核心となる問い： FB設定は、本質的にFC設定よりも困難なのか？
非構造的な $K$-アーム・バンディットにおいて、最適なサンプル複雑性は対数因子を除いて一致するが、文献によれば、特定の事例においてFBアルゴリズムはFCアルゴリズムと比較して余分な対数因子に苦しむ可能性があることが示唆されている。さらに、構造化された問題（例：線形バンディット、不均一ノイズ）において、既知の最良のFBサンプル複雑性は、時としてそのFC対応物よりもオーダーとして劣る場合がある。本論文は、FBが本質的に困難なのか、それともこの差が単に現在のアルゴリズム構成によるアーティファクト（副産物）に過ぎないのかを調査している。

2. 手法

著者らは、FBは対数因子を除いてFCよりも困難ではないことを示すための、構成的なリダクション（還元）フレームワークを提案している。その手法は、主に2つのコンポーネントで構成される。

2.1. FC2FB メタアルゴリズム

核となる貢献は、任意の「強力な」FCアルゴリズム $\mathcal{A}$ をFBアルゴリズムへと変換するメタアルゴリズム FC2FB (Fixed Confidence to Fixed Budget) である。

• 入力: 強力なFCアルゴリズム $\mathcal{A}$（$\delta$-正当性を保証するサンプル複雑性 $T^*_\delta = A \ln(1/\delta) + C$ を持つもの）および総予算 $B$。
• メカニズム: アルゴリズムは $R$ 個のステージにわたって $\mathcal{A}$ を実行する。各ステージ $r$ において、予算の一部（$B' \approx B/R$）を割り当て、増加する失敗率 $\delta_{L_r} = \delta_0^{2^{R-r}}$ を用いて $\mathcal{A}$ を実行する。
• 終了: もし $\mathcal{A}$ が割り当てられた予算内で自己終了した場合、その出力を即座に返す。もし終了前に予算が尽きた場合は、そのステージは破棄され、より高い失敗率（より少ないサンプルを必要とする）を持つ次のステージへと移行する。
• 主要な特徴: このアルゴリズムは、FCアルゴリズムに固有の、問題依存の定数 $A$ および $C$ に関する知識を必要としない。これは、対数多項式因子を除いて、FCのサンプル複雑性と一致するエラー確率境界を達成する。

2.2. FCW2S メタアルゴリズム (Weak to Strong)

一部の既存のFCアルゴリズムが「弱い」保証（例：特定の定数 $\delta$ または $1/\delta$ に対する多項式依存性）しか満たさないことを認識し、著者らは FCW2S を導入している。

• メカニズム: このアルゴリズムは、$L$ 個の独立した弱いFCアルゴリズムを並列に（ラウンドロビン方式で）実行する。
• 投票: 自己終了したインスタンスは、推奨する腕に対して投票を行う。過半数のインスタンスが終了した時点で、最も多くの票を得た腕が選択される。
• 結果: この「ブースティング」技術は、弱いFCアルゴリズム（潜在的に $1/\delta$ への依存性が低いもの）を、$\delta$ に対して対数依存性を持つ強力なFCアルゴリズムへと変換し、FC2FBの入力としての使用を可能にする。

3. 主要な貢献と結果

3.1. 理論的保証

本論文は、最適なFCサンプル複雑性が、対数因子を除いて最適なFBサンプル複雑性の上界として機能することを確立している。

• 定理 3.2: 強力なFCアルゴリズム（複雑性 $T^*_\delta \approx A \ln(1/\delta)$）に対し、FC2FBはエラー確率 $P(\hat{J} \neq 1) \leq 3 \exp\left(-\frac{B}{4Q \ln(1/\delta_0) + 4A \log_2(B/Q)}\right)$ を生成する。
• サンプル複雑性: これは、FBサンプル複雑性が $O(A \ln(1/\delta) \cdot \text{polylog}(A, \ln(1/\delta)))$ であることを意味する。
• 汎用性: この結果は、構造化バンディット（線形、単峰型、カスケード型）および非構造化の設定の両方に適用される。

3.2. 特定の問題に対する改善された境界

最先端のFCアルゴリズムにFC2FBを適用することで、著者らは、従来のFB境界が劣っていたいくつかのFB問題に対して、改善されたサンプル複雑性の境界を導き出している。

1. 既知の不均一ノイズ: PE-KHN（フェーズ除去アルゴリズム）にFC2FBを適用すると、グローバルなワーストケースの量に依存する既存のFBアルゴリズム（SHVar）を改善し、サンプル複雑性 $\tilde{O}(\sum \sigma_i^2 / \Delta_i^2)$ を達成する。
2. 未知の不均一ノイズ: VD-BESTARMIDにFC2FBを適用することで、個々の腕の分散とギャップに依存する境界が得られ、特定のレジームにおいて既存のFBアルゴリズム（VBR, SHAdaVar）を $K$ 倍の係数で上回る。
3. 線形バンディット: Fixed Confidence PeaceアルゴリズムにFC2FBを適用することで、最適なFC複雑性 $\gamma^* + \rho^* \ln(1/\delta) + d$ をFB設定において回収し、従来のFB特化型線形バンディットアルゴリズム（例：OD-LinBAI）に見られる余分な対数因子を取り除く。
4. 単峰型バンディット: 本フレームワークは、局所的な情報理論的複雑性 $T^*(\mu)$（FCに最適）と、グローバルなギャップ $\Delta^{-2}$（FBでしばしば引用される）の間の溝を埋め、FBが対数因子を除いて局所的な複雑性を達成できることを示している。

3.3. 実証実験

$K=32$ の腕を持つガウス型バンディットを用いた実験により、FC2FB(PE-KHN) が、予算サイズや腕の数に関わらず、誤識別確率において Sequential Halving (SH) およびその分散適応型バリアント (SHVar) を一貫して上回っていることが示された。ただし、理論的境界における $\ln(B)$ 項が無視できない非常に小さな予算のレジームにおいては例外である。

4. 意義と主張

本論文は、FBとFC設定の相対的な困難さに関する根本的な未解決問題を解決したと主張している：

• 根本的な関係: 著者らは、FBは対数因子を除いてFCよりも困難ではないと断言している。サンプル複雑性に知覚される差は、FB設定自体の固有の限界ではなく、既存のFB特化型アルゴリズム設計の限界である。
• 構成的なリダクション: 本研究は、問題固有の定数を知ることなく、優れたFCアルゴリズムのサンプル複雑性の保証をFB設定へと転送するための、実用的かつ構成的な手法（FC2FB）を提供している。
• アルゴリズムの改善: このフレームワークは、広範な構造化BAI問題に対して改善されたサンプル複雑性の保証を即座にもたらし、既存のFCアルゴリズムを、近最適な性能を持つFB設定へと効果的に「アップグレード」させる。

著者らは、このリダクションは非漸近的であり、普遍的に指数最適なFBアルゴリズムの存在を主張するものではない（微妙な未解決問題である）ものの、両設定の関係に関する理解を根本的に変え、アルゴリズム設計のための強力なツールを提供すると結論づけている。