Learning from Local Walks on Dynamic Graphs with Bandit Feedback

技術的要約：動的なグラフにおけるローカル・ウォークからの学習とバンディット・フィードバック

問題の定式化
本論文は、学習者が動的なグラフ上での**局所的な移動（local movement）**に制約されている状況における、確率的マルチアームド・バンディット（MAB）問題を扱う。あらゆるアームが毎ラウンド利用可能である古典的なMABモデルや、サイド観測が可能なフィードバック・グラフ・モデルとは異なり、ここでは学習者は、その時点でのグラフの連結性に基づき、現在のノードまたはその隣接ノードのみを選択できる。

• 設定: アームは、時変な無向グラフ $G_t = (A, E_t)$ の頂点 $A = \{1, \dots, n\}$ に対応する。
• 制約: ラウンド $t$ において、学習者は局所的な近傍 $L_t(a_{t-1})$ のみを観測し、$a_t \in L_t(a_{t-1})$ を選択しなければならない。グラフのプロセスはオブリービアス（学習者の行動に依存しない）である。
• 核心的な課題: この設定では、**最良アームの特定（best-arm identification）と搾取（exploitation）**が切り離されている。古典的なバンディットでは、最適なアーム $a^\star$ を特定すれば即座に搾取が可能となる。しかし、この動的な設定では、たとえ $a^\star$ が特定された後であっても、進化するトポロジーによって、学習者が $a^\star$ から構造的に孤立してしまう可能性がある。学習可能性（learnability）には、全期間のグラフの和集合が連結であることだけでなく、環境がナビゲーション可能な経路を一貫して提供していることが必要である。

手法と構造的条件
著者らは、探索（サンプリングの収集）とナビゲーション（特定されたターゲットへの到達）を分離する**「探索後コミット（explore-then-commit）」**のフレームワークを採用している。学習可能性を保証するために、カノニカル・ウォーク（canonical walk）（現在の位置に留まるか、一様に隣接ノースへ移動する単純なランダムウォーク）に基づく、プロセスに依存しない構造的条件を導入している。

• 共通定常分布を持つスライディング・ウィンドウ混合（定義1）: 本論文は、ホライゾン全体にわたる連結条件（例：全グラフの和集合が連結であること）は不十分であるとして退けている。なぜなら、それは任意の停止時刻における到達可能性を保証できないからである。代わりに、誘導されるランダムウォークに対して以下の条件を課している：
  1. 共通定常分布: すべてのグラフのスナップショット $G_t$ は、共通の定常分布 $\pi$ を持つ可逆なカーネル $U_t$ を誘導する（例：固定された次数列によって達成される）。
  2. スライディング・ウィンドウ混合: 長さ $W$ のすべての時間窓において、少なくとも割合 $\rho$ のラウンドでスペクトル・ギャップ $\ge \gamma$ が存在する。
     この条件は、探索がいつ終了したとしても、ウォークが $\pi$ へと一様に混合することを保証し、学習者が局所的な部分グラフに永久に閉じ込められることを防ぐ。

アルゴリズム
本論文では、このレジーム下で動作する一連のアルゴリズムを分析している：

1. LEX (固定予算による怠惰な探索): 混合パラメータと報酬ギャップによって決定される固定予算 $T_{exp}$ のためにカノニカル・ウォークを使用する。経験的なリーダー（empirical leader）にコミットし、ターゲットが即座に到達可能でない場合はカノニカル・ウォークを用いてナビゲートする。
2. CB-LEX (信頼度に基づく停止): 固定予算の代わりに、データ依存の停止ルールを用いる。経験的なリーダーの下限信頼限界（LCB）が、他のすべてのアーム（単なる次点の腕だけでなく）の上限信頼限界（UCB）を上回ったときに終了する。これにより、サンプリングの偏りに対する堅牢性を確保する。
3. RALEX (報酬認識型探索): カノニカル・ウォークを楽観的な提案（推定報酬に基づくソフトマックス）と混合する、報酬バイアスのかかったカーネルを導入する。極めて重要な点として、カノニカル・ウォークの構造的な混合特性を維持するために「カノニカル・フロア（$\epsilon_0$）」を維持し、ワーストケースの安全性を保証する。

主要な結果とリグレット界
$(W, \rho, \gamma, \pi)$-混合条件の下で、著者らは提案されたすべてのアルゴリズムについて劣線形な期待リグレット（$o(T)$）を確立している。リグレット界は、2つの明確な成分に分解される：

1. 学習リグレット: 統計的な困難さ（逆ギャップ $\Delta^{-2}$）と混合オーバーヘッド（$\tau_0$）にスケールする。これは、最良アームを特定するためのコストを表す。
2. ナビゲーション・リグレット: ホライゾン $T$ に依存しない構造的コストであり、停止点から特定された最適アームに到達するための期待時間を表す。

• LEX/CB-LEX: $O(\tau_0 \cdot \Psi \cdot \log T)$ のオーダーのリグレットを達成する。ここで $\Psi$ はギャップと定常質量（stationary masses）の複雑さを捉える。
• RALEX: 報酬認識型のバイアスが劣線形リグレットと両立可能であることを証明する。ワーストケースの境界は保守的であるが（カノニカル・フロアのため）、論文では別の定理（Theorem 4）を提供しており、もし報酬認識型のバイアスが「近接ボトルネック」のアームの訪問確率を増加させることに成功した場合、証明可能な性能向上（学習項における乗法的改善）が得られることを示している。

意義と主張
本論文は、特定のグラフファミリー（完全グラフなど）におけるリグレット最小化の近接性を提案するのではなく、局所的に制約された動的グラフ上の学習可能性に関する構造的特性化であると位置づけている。

• シフト不変性: 主要な貢献は、シフト不変なスライディング・ウィンドウ混合条件である。これにより、探索のランダムな停止時刻の後でも、ナビゲーションに必要な構造的仮定が保持されることが保証される。これは、ホライゾン全体の条件が失敗する要件である。
• デカップリング: 本研究は、学習の統計的コストとナビゲーションの構造的コストを明示的に分離しており、動的な環境のためのクリーンな理論的枠組みを提供している。
• プロセス非依存性: i.i.d. エルデシュ・レーニ・グラフやエッジ・マルコフ過程などの特定のグラフプロセスに依存する先行研究とは異なり、本論文はウォーク中心の混合条件を満たすあらゆるグラフ列に対して成立する定理を提供しており、回転する正則オーバーレイや次数保存型の再配線（rewiring）といった自然なプロセスをカバーしている。
• 安全性 vs ゲイン: RALEXの分析は、「安全性定理（いかなるバイアスパラメータを用いても劣線形リグレットを保証する）」と「ゲイン定理（報酬認識型の提案に関する特定の条件下で性能向上を証明する）」を区別している。

著者らは、彼らの研究が、固有のカノニカル・ウォークが学習に十分であることを示す「ポジティブなレジーム」を確立しており、メトロポリス型ウォークのようなより複雑なカーネルへの拡張のための基礎を提供するものであると結論づけている。