Nearly Tight Bounds for Cross-Learning Contextual Bandits with Graphical Feedback

技術要約：グラフフィードバックを伴うクロス学習コンテキスト・バンディットにおける、ほぼタイトな境界

1. 問題設定

本論文は、グラフフィードバックを伴うクロス学習コンテキスト・バンディットという、以下の3つの異なる学習パラダイムを組み合わせたモデルを取り扱っている：

• コンテキスト・バンディット（Contextual Bandits）: 学習者は、有限集合 $[M]$ 上の未知の分布 $\nu$ から独立同一（i.i.d.）に描画されるコンテキスト $c_t$ の連続するラウンドに直面する。
• グラフフィードバック（Graphical Feedback）: 学習者はアーム $a_t$ を選択し、選択したアームの損失だけでなく、固定された既知の有向フィードバックグラフ $G = ([K], E)$ におけるそのアウト・ネイバー（out-neighbors）の損失も観測する。
• クロス学習（Cross-Learning）: 決定的なことに、フィードバックはコンテキスト間で「再利用可能」である。コンテキスト $c_t$ におけるアーム $a$ の損失を観測することで、学習者は任意のコンテキスト $c \in [M]$ の下でのアーム $a$ の反事実的（counterfactual）な損失を評価できる。

フィードバックグラフ $G$ は**強観測可能（strongly observable）であると仮定されている（すべての腕は自己ループを持つか、あるいは他のすべての腕によって観測される。すなわち $N_{in}(a) = [K] \setminus \{a\}$）。目標は、損失テーブル $\ell_{t,c}(a) \in [0,1]$ を事前に固定する無意識のアドバーサリ（oblivious adversary）**に対し、期待後悔（expected regret）を最小化することである。ただし、アドバーサリは学習者のランダム化については知らないものとする。

中心的な問い： アルゴリズムは、コンテキストの数 $M$ に対する多項式的な依存性を負うことなく、$\tilde{O}(\sqrt{\alpha T})$（ここで $\alpha$ は $G$ の独立数、$T$ はホライゾン）のレグレット境界を達成できるか？ 従来の研究では、非コンテキスト型のグラフ・バンディット、およびグラフなしのクロス学習の設定ではこのレートが確立されていたが、これらが組み合わさった設定、特に自己ループを持たないアームを含むグラフの場合については未解決のままであった。

2. 手法

提案されるアルゴリズムは、未知のコンテキスト分布とグラフフィードバック特有の課題に対処するため、負のエントロピー正則化を用いたFollow-The-Regularized-Leader (FTRL) を、エポックベースの構成と統合して利用する。

主要な技術的構成要素：

• エポック構成と棄却サンプリング（Rejection Sampling）：
  未知の分布 $\nu$ を扱うため、アルゴリズムは時間をエポックに分割する。各エポック内では、2つ前のエポックからの「遅延スナップショット」としての FTRL ポリシーを使用し、固定されたターゲット分布を定義する。これにより、学習者は棄却サンプリングを用いて、固定された分布からプレイしている状況をシミュレートできる。この手法は、プレイに使用されるポリシーと、推定に使用されるデータをデカップル（分離）させ、コンテキストの観測確率を推定するために使用されるコンテキストが、現在のポリシーの軌跡とは独立かつ新鮮であることを保証する。

• 自己ループを持たないアーム（特殊なアーム）の処理：
  グラフ・バンディットにおける主要な障害は、自己ループを持たないアームは、学習者がそれを頻繁にプレイすると、その観測確率が消失してしまう可能性があることである。アルゴリズムは、各エポックにおいて、自己ループを持たないアームの中で最も高い経験的質量を持つ**「特殊なアーム」** $j_e$ を特定する。

  • 悲観的補正（Pessimistic Correction）: 特殊なアームに対してバイアス項 $\beta / W_e(j_e)$ が追加される。これは、暗黙的な探索（観測頻度の低いアームの損失を過小評価すること）によって生じる一次の推定ドリフトを相殺する。
  • 損失の変換（Loss Translation）: 二乗された補正項が FTRL 解析において制御不能な二次コストを導入することを防ぐため、アルゴリズムは特殊なアームの入力をすべての座標から減算する。この変換は FTRL のイテレート（反復値）自体は変えないが、特殊なアームがローカルノルムに寄与しないようにし、二次コストを残りのアームへとシフトさせる。

• ランダム分母と結合安定性（Random Denominator and Joint Stability）：
  観測確率の推定値が分母に現れ、かつポリシーがこれらの推定値に依存しているため、軌跡と分母には相関が生じる。解析では、**集団分母疑似推定器（population-denominator pseudo-estimator）と理想的な軌跡（ideal trajectory）を導入する。スナップショットとセレクターで条件付けることにより、証明は、座標ごとのスカラー・ランダム分母・モーメント境界を適用し、さらに結合 Softmax 積安定性不等式（joint Softmax product-stability inequality）**を用いることで、アーム間の独立性を仮定することなく、相関のある軌跡誤差を周辺の二次モーメントの和へと変換する。

3. 主な貢献

1. コンテキスト非依存レグレット問題の解決： 本論文は、i.i.d. コンテキストおよび無意識のアドバーサリ損失に対して、期待レグレット $\tilde{O}(\sqrt{\alpha T})$ を達成するアルゴリズムを提供する。この境界は、（対数因子を除いて）コンテキストの数 $M$ に依存しない。これは、非コンテキスト型の強観測可能グラフ・バンディットのミニマックスレートと一致する。
2. すべての強観測可能グラフへの一般化： すべてのアームが自己ループを持つことを要求していた従来の結果とは異なり、本手法は自己ループを持たないアームを含むグラフを扱う。これは、自己ループのないアームを高い確率でプレイすることが、観測確率の消失を招くという特有の困難に対処している。
3. 依存関係のある推定器のための新しい解析： クロス学習の存在下で、適応的なポリシーと経験的な観測確率の間の相関を扱うための、「ランダム分母および結合安定性」解析フレームワークを開発した。
4. 形式化： 主要な定理は Lean で形式的に検証されている。100,000行を超えるエンドツーエンドの開発により、複雑な確率論的議論の正当性が保証されている。

4. 結果

• 理論的保証： アルゴリズムは $\tilde{O}(\sqrt{\alpha T})$ のレグレット境界を達成する。隠れた係数は $M, K, T$ に関して対数的である。これは、クロス学習が、複雑なグラフフィードバックが存在する場合でも、コンテキスト空間のサイズ $M$ への依存性を効果的に排除できることを裏付けている。
• 実験的検証： 制御された合成実験により、グラフフィードバックのみ、あるいはクロス学習のみを利用するベースラインよりも、本アルゴリズムが優れていることが示された。結果は、ホライゾン $T$ および独立数 $\alpha$ の両方に対して、予測通りの平方根スケーリングを示している。
• 堅牢性： 本手法は、コンテキスト分布が未知である場合でも正しく機能する。これは、分布 $\nu$ が既知であると仮定するウォームアップ・シナリオに対する大きな改善である。

5. 意義

本論文は、コンテキスト付きバンディットの構造化されたフィードバックにおける中心的な未解決問題を解決したと主張している。無意識のアドバーサリ損失の下でコンテキスト非依存のレート $\tilde{O}(\sqrt{\alpha T})$ が達成可能であることを証明することで、本研究は、フィードバックが制限されているもののコンテキスト間で再利用可能な、繰り返し第一価格オークションのようなアプリケーションの理論的限界と実用的なニーズの間の溝を埋めるものである。

その意義は二重である：

1. 理論的側面： 最適なレートを達成するためにアームが自己ループを持つ必要があるという制約を取り除き、グラフ・バンディット理論の適用範囲をより広いクラスのフィードバック構造へと拡張した。
2. 実用的側面： コンテキスト分布が未知であるという、現実世界の一般的な制約下でも、クロス学習とグラフフィードバックの両方の効率的な利点を活用できる堅牢なアルゴリズムを提供している。

著者らは、彼らの結果が（確率的損失は無意識のアドバーサリ損失の特殊なケースであるため）確率的損失に対する直接的な系であることを強調しており、Lean による形式化が、依存関係のある推定器とエポックベースのサンプリングを含む複雑な証明の正確性に対して高い信頼性を提供しているとしている。