技術的サマリー：1-識別のサンプル複雑性のギャップの解消

問題定式化

本論文は、多腕バンディット（MAB）フレームワークの純粋探索バリエーションである1-識別問題を取り扱います。目的は、$K$個の腕の集合において、その平均報酬 $r_a$ が既知の閾値 $\mu_0$ を超える少なくとも 1 つの腕 $a$ が存在するかどうかを決定することです。

• 陽インスタンス: $\max_a r_a > \mu_0$。アルゴリズムは、そのような腕を（少なくとも）1 つ特定しなければなりません。
• 陰インスタンス: $\max_a r_a < \mu_0$。アルゴリズムは「なし（None）」を出力しなければなりません。
• 保証: アルゴリズムは $\delta$-確率的に近似正解（PAC）でなければならず、正しい決定を行う確率が少なくとも $1-\delta$ であることを保証します。主な関心対象は、期待サンプル複雑性 $E[\tau]$ です。

この問題は、すべての腕をランク付けしたり、単一の最良の腕を特定したりすることを要求する標準的な最良腕識別（BAI）とは異なり、閾値を超える任意の腕を見つけることを目的としています。陰インスタンスにおけるサンプル複雑性はよく理解されており（BAI と密接に関連）、陽インスタンス、特に複数の合格した腕（$m > 1$）を持つ場合の複雑性は、既存の境界が緩いままの未解決問題となっていました。

手法

1. 下限解析

著者らは、複雑なインスタンスに対してしばしば緩い境界をもたらす従来の「シミュレータ」フレームワークから離れ、新しい最適化定式化を用いて陽インスタンスに対する新しい下限を導出しました。

• 対称性の縮小: 証明の冒頭では、下限の目的においては、腕のラベルの置換に対して不変である対称アルゴリズムに注目することを制限できることが示されます。
• 凸最適化: 下限証明の核心は、凸最適化問題を構築することにあります。期待サンプル複雑性 $E[\tau]$ は、この問題の最適値によって下方から抑えられることが示されます。
• 双対解: 特定の実行可能な双対解を構築することで、著者らは信頼度パラメータ $\delta$ とインスタンス依存のギャップの両方に依存するtightな下限を導出しました。この境界は以下のように表されます：
  $$\Omega\left( \min_{1 \le j \le m} \left\{ \frac{\log(1/\delta)}{\Delta_{j,0}^2} + \frac{H(j)}{\log^2(m+1)} \right\} \right)$$
  ここで、$\Delta_{j,0} = \mu_j - \mu_0$ であり、$H(j)$ は腕間のギャップを含む複雑性項です。

2. アルゴリズム設計：PSEEB

下限に一致させるため、本論文は**括弧付き並列逐次探索・活用（Parallel Sequential Exploration–Exploitation on Brackets, PSEEB）**を提案します。

• 括弧化メカニズム: アルゴリズムは、腕の単一のランダムな置換に基づいて、入れ子になった「括弧（腕の部分集合）」の族 $\{B_b\}$ を生成します。$B_1 \subset B_2 \subset \dots \subset B_{\lceil \log_2 K \rceil + 1} = [K]$ であり、$|B_b| \approx 2^b$ です。
• 並列実行: アルゴリズムは、基本となる逐次探索・活用（SEE）アルゴリズム（Li and Cheung, 2025 から適応）の $\lceil \log_2 K \rceil + 1$ 個の独立したコピーを実行します。各コピーは、1 つの括弧 $B_b$ のみに対して排他的に動作します。
• ラウンドロビンスケジューリング: コピーはラウンドロビン方式で実行されます。グローバルなアルゴリズムは、いずれかのコピーが有効な腕または「なし」を出力するとすぐに終了します。
• 停止規則:
  • 腕の全集合（$B_{\lceil \log_2 K \rceil + 1}$）上で動作するコピーのみが「なし」を出力することを許可されます。
  • より小さな括弧上で動作するコピーは、自身の部分集合内に合格した腕が存在しないと疑う場合でもサンプリングを継続し、より大きな括弧にある可能性のある合格した腕を見逃さず、早期に終了しないようにします。

主要な貢献と結果

1. Tight な下限

本論文は、$\delta$ 依存項（$\log(1/\delta)$）と $\delta$ 非依存項の両方において共同最適である新しい陽インスタンスの下限を確立しました。

• 以前の研究（例：Degenne and Koolen, 2019; Li and Cheung, 2025）は、単一の合格した腕（$m=1$）の場合、または制限された設定でのみ近似的な最適性を達成していました。
• 新しい境界は、複数の合格した腕（$m > 1$）を持つインスタンスの複雑性に関する未解決問題を解決し、$\min_{1 \le j \le m} \{ \frac{\log(1/\delta)}{\Delta_{j,0}^2} + H(j) \}$ を正しいインスタンス依存の複雑性尺度として特定しました。

2. ほぼ最適な上限

提案された PSEEB アルゴリズムは、$K$ とギャップに関する多項式対数因子まで新しい下限に一致する、期待サンプル複雑性に関する上限を達成します。

• 陽インスタンス: $E[\tau] \le O\left( \log K \cdot \min_{1 \le j \le m} \left\{ \frac{\log(1/\delta)}{\Delta_{j,0}^2} + \text{poly}(\log K, \log(1/\Delta)) \cdot H(j) \right\} \right)$。
• 陰インスタンス: アルゴリズムは、陰インスタンスに対する既知の最適境界 $O(H_1^{neg} \log(1/\delta))$ を維持します。
• 強 $\delta$-PAC: アルゴリズムは強 $\delta$-PAC であることが証明されており、すべてのインスタンスに対して期待サンプル複雑性が有限であることを意味し、$E[\tau] = \infty$ となるような病理的な振る舞いを排除します。

意義と主張

本論文は、複数の合格した腕を持つ一般的なケースにおいて、初めて 1-識別のサンプル複雑性におけるギャップを解消したと主張しています。

• 未解決問題の解決: これは、$m > 1$ に対する $\delta$ 非依存項の改善可能性に関する Li and Cheung (2025) が残した未解決問題を明示的に解決します。
• 方法論的進展: 下限の導出を凸最適化問題への帰着として提示することは、よりtightで一般的な結果をもたらす従来の「シミュレータ」フレームワークに対する重要な簡素化として提示されています。
• アルゴリズム的効率性: 並列括弧化戦略を利用することで、PSEEB は特定の「最良の」合格した腕を特定する必要なく、どの腕が合格しているかという不確実性を効率的に処理し、1-識別を標準的な BAI に帰着させることに関連する不要なサンプリングコストを回避します。

著者らは、境界がほぼ最適である一方で、対数因子の精緻化は将来の研究の方向性であると指摘しています。この研究は、陽インスタンスと陰インスタンスの両方における 1-識別のサンプル複雑性の風景を完全に特徴づけています。