Fundamental Limitations of Fixed-Budget Best-Arm Identification

技術要約：固定予算における最良腕識別（Best-Arm Identification）の根本的な限界

問題定式化
本論文は、固定予算における最良腕識別（Best-Arm Identification: BAI）、別名ランキング・アンド・セレクション（Ranking and Selection）の問題を扱う。この設定では、意思決定者は $K$ 個の腕から逐次的にサンプリングを行うが、各腕は未知の平均 $\mu_k$ を持つ分布から独立した報酬を生成する。目標は、総サンプリング予算 $T$ を用いて、最大の平均を持つ腕 $i^*(\mu)$ を特定することである。性能指標は、誤識別確率 $p_{\mu, T}$、具体的には $T \to \infty$ におけるその指数減衰率である：
$$\liminf_{T \to \infty} \frac{1}{T} \log \frac{1}{p_{\mu, T}}$$

中心となる理論的問いは、この問題に「複雑性（complexity）」が存在するかどうかである。複雑性とは、以下の2つの条件を満たす関数 $\Gamma^*(\mu)$ として定義される：

1. 普遍的上界（Universal Upper Bound）: すべてのアルゴリズムおよびすべてのインスタンス $\mu$ に対して、誤差減衰率は $\Gamma^*(\mu)$ によって上から抑えられる。
2. 一様達成可能性（Uniform Achievability）: すべてのインスタンス $\mu$ に対して一様にこの減衰率 $\Gamma^*(\mu)$ を達成する単一のアルゴリズムが存在する。

本論文では、スタティック・オラクル（static oracle） のレート $\Gamma^*_{so}(\mu)$ が、この複雑性として機能するかどうかを調査している。スタティック・オラクルとは、真の平均 $\mu$ を事前に知っており、減衰率を最大化するためにサンプリング比率を固定値に割り当てる非適応的な戦略によって達成可能な、最適な誤差減衰率を表す。適応的アルゴリズムは、サンプリング比率がこれらの最適な静的な比率に収束するように設計されているが、任意の適応的アルゴリズムが、すべてのインスタンスに対してスタティック・オラクルの誤差減衰率を一様に一致させることができるかどうかは、未解決の問いであった。

手法
著者らは、背理法を用いて、$K \geq 3$ の場合において、単一のアルゴリズムがすべてのインスタンスに対してスタティック・オラクル・レートを一様に達成することはできないことを証明する。その手法は、以下の構成要素に基づいている：

1. 困難度比（Difficulty Ratios）: Degenne (2023) に従い、本論文では、ベンチマークとなる困難度関数 $H(\mu)$ に対するアルゴリズム $A$ の性能を測定する困難度比 $R_{H, \infty}(A, \mu)$ を用いる。もし複雑性が存在するならば、この比率の全インスタンスにおける上限が $\leq 1$ となるアルゴリズムが存在しなければならない。
2. 定理 1 (Degenne 2023): 証明には、一貫した適応的アルゴリズム・ファミリーの性能を制限する Degenne (2023) の重要な不等式を利用する。任意のベンチマーク $H$ と代替インスタンスの集合 $D(\mu)$ に対して、最悪ケースの困難度比の逆数は、サンプリング比率 $\omega$ に関する静的な最適化問題によって以下のように抑えられる：
   $$\left( \sup_{\lambda \in D(\mu)} R_{H, \infty}(A, \lambda) \right)^{-1} \leq \sup_{\omega \in \Delta_K} \inf_{\lambda \in D(\mu)} \left( H(\lambda) \sum_{k=1}^K \omega_k \text{KL}(\mu_k, \lambda_k) \right)$$
3. インスタンスの構成: 複雑性の非存在を証明するために、特定の「ベースライン」インスタンス $x$ と、代替インスタンスの族 $D(x) = \{\lambda_A, \lambda_{B,3}, \dots, \lambda_{B,K}\}$ を構成する。
   • $\lambda_A$: $x$ とは腕1と腕2のみが異なる。$x$ と $\lambda_A$ を区別するには、腕1と腕2の多大なサンプリングを必要とする。
   • $\lambda_{B,j}$ (for $j \in \{3, \dots, K\}$): $x$ とは腕 $j$ のみが異なる。これにより、腕 $j$ が新たな最良の腕となる。$x$ と $\lambda_{B,j}$ を区別するには、腕 $j$ の多大なサンプリングを必要とする。
     この構成により、「最も区別が困難な」腕がこのファミリー内で変化するようにしている。単一のサンプリング割り当て $\omega$ は、必要な情報が互いに素な腕の集合に集中しているため、同時に $x$ と $D(x)$ の全メンバーを区別するための最適解となることはできない。

主要な結果
本論文は、固定予算における BAI に関する根本的な負の結果を確立している：

• ガウス報酬（Gaussian Rewards）: $K \geq 3$ 個の腕（分散1のガウス報酬）について、著者らは、任意の整合的なアルゴリズム・ファミリー $A$ に対して、スタティック・オラクルに対する困難度比が1を超えるようなインスタンス $\mu$ が存在することを証明した。具体的には：
  $$\inf_{A \in \mathcal{C}_{cons}} \sup_{\mu} R_{H_{so}, \infty}(A, \mu) \geq 1 + \sum_{j=3}^K \frac{1}{(1 + \sqrt{j-1})^2} > 1 + \frac{1}{8} \log(K)$$
  この下限はすべての $K \geq 3$ において1を厳密に上回っており、単一のアルゴリズムがスタティック・オラクルを一様に一致させることは不可能であることを証明している。

• 自然指数族（Natural Exponential Families: NEF）への一般化: 本結果は、任意の1パラメータ自然指数族（NEF）に拡張される。カルバック・ライブラー（KL）ダイバージェンスの局所的な二次近似を用いることで、ガウス分布の結果がすべての正則な1パラメータNEFに対しても同様の制限を課すことを示している。

• 未解決問題への回答: 本研究は、Qin (2022) によって提起され、Degenne (2023) によって定式化された未解決の問いに決定的な回答を与える。すなわち、固定予算における BAI は、$K \geq 3$ のとき複雑性を備えていない。スタティック・オラクルは誤差減衰率の下限を提供するものの、単一の適応的アルゴリズムがすべての問題インスタンスに対して一様にこの下限を達成することはできない。

意義と主張
本論文は、固定予算における BAI の理解における根本的な理論的ギャップを解消することを主張している。

• 適応性の限界: サンプリング比率がスタティック・オラクルに収束すること（適応的アルゴリズムの一般的な設計目標）は、スタティック・オラクルの誤差減衰率を一致させるための十分条件ではないことを示している。固定予算の設定における「適応の代償」とは、アルゴリズムがすべてのインスタンスに対して同時に最適であることはできないという点にある。
• 範囲: この結果は、ガウス報酬の場合の $3 \leq K < e^{80/3}$ の範囲における文献の空白を埋め、複雑性の非存在をすべての1パラメータNEFに拡張する。
• 理論的境界: 本研究は、スタティック・オラクル・レートが $K \geq 3$ のときの固定予算 BAI における普遍的な複雑性ではないことを確立している。著者らは、スタティック・オラクルが一様に達成不可能であることから、代替的な理論的目標やベンチマークが必要であることを示唆している。

本論文は、この限界を克服するための新しいアルゴリズムを提案するものでも、ランキング・アンド・セレクションやマルチアームド・バンディットへの具体的な応用を提案するものでもない。その貢献は、この設定において達成可能なものの根本的な限界を定義する、厳格な負の結果である。