Where Does the Union Bound Go? Best-Arm Identification and Strong FWER Control

技術的要約：「Union Bound（和事象の上界）はどこへ行ったのか？ 最良腕識別と強固なFWER制御」

問題提起
固定信頼度（fixed-confidence）の最良腕識別（Best-Arm Identification; BAI）において、アルゴリズムは $K$ 個の腕の中で平均 $\mu_{i^\star}$ が最大となる唯一の腕 $i^\star$ を、誤差確率が最大 $\delta$ 以下となるように特定することを目指す。文献における繰り返される謎は、union bound（和事象の上界）を用いて導出された誤差境界の中に、$K-1$ に関連する因子（しばしば停止閾値における $\log(K-1)$ として現れる）が存在することである。

多重検定の観点から見ると、これは矛盾しているように見える。もしパラメータ空間が「正確に一つの腕が最良である」という制約の下にあるならば、「腕 $i$ が最良である」という仮説のうち、真であるものは一つだけである。標準的な多重検定理論（例：ボンフェローニ補正）によれば、もし真の帰無仮説が一つしか存在しないのであれば、誤差率は $K-1$ 個の対立仮説を合計する補正因子を必要としないはずである。しかし、標準的なBAIの証明では、一貫して $K-1$ 個の競合するイベントに対して誤差予算を割り当てている。本論文はこの明白な矛盾の源を調査する。

手法および理論的枠組み
本論文は、ユニーク・ベスト・アームのパラメータ空間 $\Theta_{\text{uniq}}$ における仮説の向き付け（orientation）の暗黙的な選択によって、この謎が解決されることを示し、解決する。著者は、以下の2つの異なる仮説の定式化を分析している：

1. 向き付け1：「腕 $i$ は最良ではない」

   • 仮説： 仮説 $H_i^- := \{ \mu \in \Theta_{\text{uniq}} : i \neq i^\star(\mu) \}$ を定義する。帰無仮説 $H_i^-$ は、腕 $i$ が最良ではないことを主張する。
   • 論理： 真の最良腕が $i^\star$ であるとき、$H_{i^\star}^-$ は偽であるが、$i \neq i^\star$ であるすべての $i$ に対して $H_i^-$ は真となる。
   • 多重性： この定式化では、正確に $K-1$ 個の真の帰無仮説が同時に存在する。したがって、Familywise Error Rate (FWR) を制御するためには、これら $K-1$ 個の真の帰無仮説に対する標準的なunion boundが論理的に必要となる。BAIの誤差イベント $\{ \hat{b}_\tau \neq i^\star \}$ は、このファミリーにおける少なくとも一つの真の帰無仮説を棄却するというイベントに正確に対応する。

2. 向き付け2：「腕 $i$ は最良である」

   • 仮説： 仮説 $G_i := \{ \mu \in \Theta_{\text{uniq}} : i = i^\star(\mu) \}$ を定義する。これらは、正確に一つだけが真となるパラメータ空間の分割を形成する。
   • 論理： ここでは、真の帰無仮説は一つしか存在しない。排除アルゴリズムは、腕 $i$ が最良ではないことを示す十分な証拠が得られた場合に $G_i$ を棄却する。
   • 多重性： ここでは真の帰無仮説は一つであるが、その $G_i$ に対する検定の構成自体が多重性を導入する。「腕 $i$ が最良である」という言明は、$K-1$ 個のペアごとの言明の共通部分である：$G_i = \bigcap_{j \neq i} \{ \mu_i > \mu_j \}$。
   • メカニズム： ペアごとの排除ルールは、任意の競合者 $j$ がそれに対して十分な証拠を提供した場合に $G_i$ を棄却する。したがって、単一の真の複合帰無仮説 $G_{i^\star}$ に対する棄却イベントは、$K-1$ 個のペアごとの棄却イベントの和集合である：$\{ G_{i^\star} \text{ が棄却される} \} = \bigcup_{j \neq i^\star} R_{j, i^\star}$。
   • 結果： Union bound（およびそれに伴う $K-1$ の因子）は消失しない。それは単一の真の複合仮説の検定の「内部」へと移動する。誤差確率は、$K-1$ 個のペア比較の確率の和によって抑えられる。

主な貢献

• 明示的な等価性： 本論文は、BAIの誤差解析と強固なFWER制御の間の論理的等価性を、BAIコミュニティと多重検定コミュニティの両方の用語を用いて明示的に示した。これにより、「$K-1$ の因子」という謎が、これら2つの仮説の向き付けを切り替えた結果であることを明らかにした。
• 多重性の明確化： 多重性はBAIの不備な証明技術によるアーティファクトではなく、問題構造の根本的な特性であることを示している。問題を「多くの真の帰無仮説を持つもの」と見るか、「一つの真の複合帰無仮説を論破するための $K-1$ 個の潜在的な証拠を持つもの」と見るかにかかわらず、組合せ論的な因子は依然として残る。
• ランクと証拠（Witnesses）の区別： 本論文は、問題の「ランク（rank）」（BAIにおいては、候補を否定するために2つの腕があれば十分であるためランクは2である）と、「証拠（witnesses）の数」（これは $K-1$ である）の区別を明確にしている。ランクはなぜペアごとの統計量で十分なのかを説明し、証拠の和集合は非漸近的な誤差較正における $K-1$ 項を説明する。

既存文献の分析と結果
本論文は、この二重性が具体的なアルゴリズムや境界にどのように現れるかを分析している：

• Garivier and Kaufmann (2016)： 閾値 $\beta(t, \delta) = \log(2t(K-1)/\delta)$ は、真の最良腕を固定した後、誤った勝者の数である $K-1$ を明示的に加算している。
• Kaufmann and Koolen (2021)： 彼らの改良された時間一様混合マルチンゲール境界は、ペア内の集中度を鋭敏にするが、依然として $\{1, j\}$ という $K-1$ 個のサブセットに対して重み付きunion boundを適用している。多重性は、時間依存性が以前の境界よりも鋭いにもかかわらず、較正関数における $\log((K-1)/\delta)$ 項を通じて現れる。
• サンプル複雑性： 本論文は、非漸近的な境界に $K-1$ の因子が現れるものの、それが固定された $K$ に対して $\delta \to 0$ とした際のサンプル複雑性の乗法的な $K-1$ 倍の損失を必ずしも意味しないことを指摘している。主要な項は依然として $\log(1/\delta)$ によって支配されている。

意義と主張
本論文は、新しいアルゴリズムや実験結果を提案するのではなく、論理的等価性を明確にすることを目的とした「ノート（注釈）」であると控えめに主張している。その主な意義は以下の通りである：

1. 視点の統一： BAIの文献（多くの場合、問題を唯一の勝者を特定することとして扱う）と、多重検定の文献（FWER制御や論理的制約に焦点を当てる）の間の溝を埋める。
2. Union Boundの解明： Union boundはBAIの証明において「無駄に」されているのではなく、問題の特定の論理構造に対して正しいツールであることを主張している。それは、問題を「多くの真の帰無仮説を持つもの」と見るか、「一つの真の帰無仮説を持つ、多くの潜在的な反証者を持つもの」と見るかにかかわらず、同様である。
3. 今後の方向性： 本論文は、全集合の幾何学的構造を利用した結合検定（Katz-Samuelsら、2020による純粋探索問題に見られるようなもの）を用いることで、明示的な腕ごとのunion boundを回避できる可能性があることを示唆している。しかし、証拠（witnesses）の組合せ論的な性質自体は、問題の幾何学における主要な特徴であり続ける。

結論として、両方のコミュニティは論理的に関連する候補となる回答に対して誤差を整理しているが、多重性を配置する論理的なレベルが異なっているのである。