技術要約：Tree-Guided Identify-Then-Exploit (TG-ITE)

問題定式化

本論文は、コンドルセスの勝者（Condorcet winner）仮定の下での $N$-アーム・ストカスティック・デュエリング・バンディット問題を取り扱う。この設定では、学習者は一対のアーム $(i, j)$ を選択し、未知の選好行列 $P$ に支配されたバイナリの結果（どちらのアームが勝利したか）を観測する。核心となる仮定は、唯一のコンドルセスの勝者 $a^\star$ が存在することであり、これはすべての $j \neq a^\star$ に対して $P(a^\star, j) > 1/2$ を満たす。一方、勝者ではないアーム間の選好は循環的である可能性がある。

本研究は、以下の3つの異なる目的を単一のフレームワーク内で統合することに焦点を当てている：

1. 最良アーム識別 (Best Arm Identification: BAI): データ依存の停止時刻において、高い信頼度 ($1-\delta$) で $a^\star$ を返す。
2. 弱レグレット最小化 (Weak Regret Minimization): 選択された2つのアームのうち少なくとも一方が $a^\star$ である場合にレグレットがゼロとなる累積レグレットを最小化する。
3. 強レグレット最小化 (Strong Regret Minimization): 選択された2つのアームの両方が $a^\star$ である場合にのみレグレットがゼロとなる（自己対戦：self-play）レグレットを最小化する。

中心的な研究課題は、探索（BAIに必要）と活用（レグレット最小化に必要）の間の伝統的なトレードオフを克服しつつ、これら3つの目的すべてにおいて最適な性能を同時に達成できる統一的なアルゴリズム・フレームワークが存在するかどうかである。

手法：Tree-Guided Identify-Then-Exploit (TG-ITE)

提案される解決策である TG-ITE は、Identify-Then-Exploit（識別してから活用する） パラダイムを採用している。これは、問題を共有された識別フェーズと、目的に応じた活用戦略へと分離するものである。

1. 共有識別プリミティブ：TREEASCENT

核心となる革新は、TREEASCENT と呼ばれるツリー誘導型識別（Tree-Guided Identification） アルゴリズムである。標準的な「Explore-Then-Commit (ETC)」戦略は、累積レグレットにおいて最適とは限らないことが多いが、TREEASCENT は決定論的でバランスの取れた二分木構造を利用して、コンドルセスの勝者の探索をガイドする。

• メカニメント: 任意の腕 $b$ から開始し、固定された二分木の祖先パスを辿る。各レベル $h$ において、「兄弟ブロック（sibling block）」（そのレベルで新たに結合されたアームの集合）に対してノックアウト・トーナメントを行い、代表者を決定する。
• マージ（統合）: 兄弟ブロックから選ばれた代表者は、逐次的なペアワイズ・テスト（DUELTEST）を用いて、現在の「チャンピオン」（前のレベルの勝者）と比較される。
• 効率性: 兄弟ブロックのサイズ（幾何級数的に増加するサイズ）に比例して信頼度予算を割り当てることで、アルゴリズムは $O(N)$ のサンプル複雑度で高信頼度のインカンベント（現時点での暫定勝者）を特定する。これは、強ストカスティック推移性や強ストカスティック・トライアングル不等式のような強い仮定を必要とせず、コンドルセスの勝者の存在とグローバルなギャップ $\Delta$ のみに依存することで達成される。

2. 目的別活用戦略

TREEASCENT によって高信頼度のインカンベントが特定されると、フレームワークは特定の活用ポリシーへと切り替わる：

• BAI 用 (TG-ITE-BAI): アルゴリズムは単に TREEASCENT を実行し、特定されたアームを返して停止する。これにより、$O(N)$ のサンプル複雑度を達成し、BAIの理論的下限と一致する。
• 弱レグレット用 (TG-ITE-WEAK): アルゴリズムは TREEASCENT を定数信頼度の「ウォームスタート」として使用し、初期の勝者を見つける。その後、Winner-Stays (WS) スタイルの戦略である SCREENANDREPLACE を採用する。各エポックにおいて、現在のインカンベントがすべての挑戦者に対してスクリーニングされる。もし挑戦者がインカンベントを破ったように見える場合、置換トーナメントが行われる。このアプローチにより、$O(N)$ の弱レグレットを達成し、従来の $O(N \log N)$ の結果を改善する。
• 強レグレット用 (TG-ITE-STRONG): アルゴリズムは TREEASCENT を通じて信頼できるインカンベントを特定した後、自己対戦（self-play）（インカンベント自身との比較）を行う。
  • 既知のホライゾン: $1/(H+1)$ の信頼度で TREEASCENT を実行し、その後、自己対戦を行う。
  • 任意のホライロン: 信頼度が上昇していく識別パスと、次第に長くなる自己対戦ブロックを交互に実行する。
  • これにより、$O(N \log T)$ の強レグレットを達成し、特化した強レグレット・アルゴリズムと一致する。

主な貢献と結果

1. 統一フレームワーク

TG-ITEは、共有された識別プリミティブを用いて、BAI、弱レグレット、および強レグレットを統一する初のフレームワークである。これは、デュエリング・バンディットの設定において、一つのアームを探索に、もう一つのアームを活用に用いることができるため、探索と活用の間のトレードオフが「ベナイン（有益）」であることを示している。

2. 改善されたサンプル複雑度とレグレット境界

• BAI: 強ストカスティック推移性や全順序の仮定を必要とせずに $O(N)$ のサンプル複雑度を達成し、BAIにおける最良の既知の結果と一致する。
• 弱レグレット: $O(N)$ の弱レグレットを達成し、従来の共同最適化アプローチ（例：Ma et al., 2025）で見られた $O(\log N)$ のギャップを解消し、最良のインスタンス非依存境界に一致させた。
• 強レグレット: $O(N \log T)$ のレグレットを達成し、WS-S や RUCB といった特化したアルゴリズムの保証と一致する。
• 共同最適化: 本フレームワークは、BAI と弱レグレットの同時最適化を可能にし、両方に対して $O(N)$ の保証を提供することで、先行研究に見られた劣った $O(\log N)$ の要因を排除する。

3. 理論的保証

論文は、TREEASCENT およびその後の活用フェーズの正当性とコストに関する厳密な証明を提供している。

• 定理 1: TREEASCENT は、確率 $1-\epsilon$ で $O(N)$ 回の比較を用いてコンドルセスの勝者を特定する。
• 定理 2: TG-ITE-WEAK の弱レグレットは $O(N/\Delta^2)$ で抑えられ、これは $N$ に対して線形であり、時間ホライゾン $T$ に依存しない。
• 定理 3 & 4: 強レグレット境界は、既知および未知のホライゾンの両方において $O(N \log T)$ である。

4. 拡張

論文では、既知ギャップ予算付き拡張 (Known-Gap Budgeted Extension)（セクション5）も提示している。コンドルセス・ギャップの下限 $g$ が既知である場合、アルゴリズムは任意の DUELTEST を固定予算のテストに置き換えることができる。これにより、境界から $\log(1/\Delta)$ の因子を取り除き、決定論的な比較予算とよりタイトな保証を提供できるが、引き換えにギャップの事前知識が必要となる。

実験による検証

著者らは、非推移性や非対称なギャップをストレス・テストするように設計された合成インスタンスを用いて、代表的なベースライン（WS-W, WS-S, RUCB, WR-TINF, WSW-PE を含む）に対する TG-ITE の評価を行っている。

• BAIのスケーリング: TG-ITE-BAI は $N$ に対してほぼ線形にスケールし、循環的なインスタンスにおいて適応的なペアワイズ除去手法を上回る性能を示す。
• 弱レグレット: TG-ITE-WEAK は最も低い累積レグレットを達成し、急速にプラトー（横ばい）に達し、ウォームスタート戦略の有効性を実証している。
• 強レグレット: TG-ITE-STRONG はベースラインを大幅に上回り、自己対戦が始まると曲線が平坦化することから、理論的な $O(N \log T)$ の挙動を確認している。

意義と主張

本論文は、TG-ITE が、デュエリング・バンディットにおける最良アーム識別とレグレット最小化の間のトレードオフが比較的ベナイン（有益）であるという理論的証拠を提供すると主張している。デュエリング・バンディットのユニークな構造（2つのアームを選択できること）を活用することで、本フレームワークは、標準的なマルチアームバンディットで見られるような劣った結果を招くことなく、探索フェーズと活用フェーズをうまく分離することに成功している。

著者らは、彼らのアプローチが以下の点において重要であることを強調している：

1. 共有された再利用可能な識別プリミティブ（TREEASCENT）の下で、3つの異なる目的を統合している。
2. $O(\log N)$ の因子を除去し、全順序の仮定を緩和することで、弱レグレットの最先端技術を改善している。
3. 従来の最適アルゴリズムが依存していた、より強い構造的仮定（強ストカスティック推移性など）を必要とせずに、BAI および強レグレットの最適レートに一致させている。

この研究は、「識別してから活用する（Identify-Then-Exploit）」というテンプレートが、ツリーベースのトーナメント分解によって導かれる場合、選好ベースの学習において強力かつ汎用性の高い戦略であることを示唆している。