技術要約：マルチエージェント追跡・回避ゲームにおけるプリミティブ誘導型木探索

1. 問題設定

本論文は、グラフ上におけるマルチエージェント追跡・回避ゲーム（Pursuit-Evasion Games: PEGs）において、ナッシュ均衡ポリシーを計算するという課題に取り組んでいる。これらのゲームでは、追跡者（Pursuer/赤）のチームが、回避者（Evader/青）のチームが指定された出口ノードに到達する前に、彼らを捕獲することを目指す。核心的な困難は、エージェント数の増加に伴い、結合状態および行動空間が指数関数的に増大することにある。

既存のアプローチには、以下のようなトレードオフが存在する：

• オフライン手法（例：PSRO, MAPPO）：オフラインでポリシーを学習するが、学習中に見られなかった敵対的挙動への適応性に欠けることが多く、学習の複雑さも高い。
• オンライン計画手法（例：MCTS）：現在の状態に適応できるが、同時マルチエージェントゲームに特有の膨大な分岐因子に直面し、深い探索が計算量的に不可能になる。
• ハイブリッド手法（例：AlphaZeroのバリアント）：正確な価値関数やポリシーの近似学習に依存するため、大量のデータを必要とするか、あるいは2プレイヤーの設定に限定されることが多い。

目標は、オフラインでの均衡計算による戦略的深さと、オンライン探索による適応性を組み合わせた、スケーラブルで堅牢なフレームワークを開発することである。

2. 手法：プリミティブ誘導型木探索 (Primitive-Guided Tree Search: PGTS)

著者らは、複雑なマルチエージェントゲームを扱いやすいサブゲームへとオフラインで分解し、それらの解をオンラインの同時移動モンテカルロ木探索（Simultaneous-Move MCTS: SM-MCTS）に統合するハイブリッドフレームワーク、Primitive-Guided Tree Search (PGTS) を提案している。

2.1 オフラインフェーズ：プリミティブ・サブチーム・ゲーム

ゲーム全体を直接解く代わりに、PGTSはエージェントのサブセットを含む、代表的かつ小規模な「プリミティブ（基本要素）」となるサブゲームの厳密なナッシュ均衡を事前計算する：

• 1v1: 1人の追跡者 vs 1人の回避者。
• 2v1: 2人の追跡者 vs 1人の回避者。
  これらは、制限された状態空間（$V \times V$ および $V^2 \times V$）上でシャプレイ値反復法を用いて解かれる。出力には、実行時にキャッシュして使用するための最適混合ポリシー（$\pi^*$）と価値関数（$V^*$）が含まれる。

2.2 オンラインフェーズ：木探索

各タイムステップにおいて、PGTSは現在の結合状態から木探索を実行する。このアルゴリズムは、標準的なSM-MCTSを以下の2つの重要な方法で修正している：

1. プリミティブ誘導型展開 (Primitive-Guided Expansion):
   指数関数的な分岐因子を抑制するため、アルゴリズムはすべての結合行動を展開するのではなく、オフラインのプリミティブ・ポリシーを使用して探索を誘導する：

   • 各回避者に対して、アルゴリズムはその最も近い $k_r$ 人の追跡者を特定する。
   • 事前計算されたナッシュ・ポリシー（$\pi^*_{1v1}, \pi^*_{2v1}$）に基づき、局所的な相互作用（1v1および2v1のグループ）のための結合行動をサンプリングする。
   • これらのサンプルは、事前分布への過度な依存を防ぐため、ヒューリスティックな最短経路行動やランダムな探索によって拡張された、制限された候補行動セットを形成する。

2. サブチーム・サロゲートによるリーフ値推定:
   高コストなモンテカルロ・ロールアウトをホライゾンまで実行する代わりに、アルゴリズムはオフラインのプリミティブ価値関数を用いてリーフノードの価値を推定する。

   • アルゴリズムは、現在の状態を一連のプリミティブ・サブチームへと分解することで、ゲーム全体の価値を近似する。
   • 逐次マッチング戦略を採用する：まず、ハンガリアン法を用いて2v1の価値行列に基づき、2v1の相互作用（共同での追い込みといった高次の協調を捉えるため）を形成するようにエージェントを貪欲にマッチングさせる。
   • 残りのエージェントは1v1の相互作用へとマッチングされる。
   • リーフ値は、これらプリミティブ価値の集計和となり、これにより、正確な結果の推定を維持しながら、より浅い深さで探索を終了させることが可能になる。

2.3 行動選択

フレーム構想は、木をトラバースするための2つの選択オペレータをサポートしている：

• 後悔マッチング (Regret Matching: RM): 各ノードにおける推定行列ゲームに後悔マッチングを適用し、混合ポリシーを計算する。
• デカップルドUCT (Decoupled UCT: DUCT): 各チームの限界行動価値に対して、独立してUpper Confidence Boundを適用する。

3. 主な貢献

• ハイブリッドフレームワーク: 小規模な再帰的局所相互作用（プリミティブ）の厳密なオフライン・ナッシュ解を、オンライン木探索に統合するという、独自のPGTSを導入した。
• 構造化された展開: 単なるランダムまたは純粋なヒューリスティック・サンプリングではなく、オフラインの均衡計算から得られた戦略的事前分布に基づいて行動をサンプリングすることで、分岐因子を削減するメカニズムを実現した。
• スケーラブルなリーフ評価: 深いロールアウトを行わずに、リーミティブな価値関数と逐次マッチングアルゴリズム（2v1を1v1より優先する）を活用してリーフノードを評価する、サロゲート価値推定法を確立した。
• 協調性の維持: サブチームを独立して扱う単純な分解手法とは異なり、PGTSはプリミティブに導かれたフル行動空間内での結合行動ロールアウトを行うことで、チームレベルの協調性を維持する。

4. 実験結果

著者らは、4つのグラフトポロジー（2つの7x7グリッド（Easy/Hard）、200ノードのスコットランドヤード・グラフ、151ノードの実世界のAtlantaグラフ）を用いてPGTSを評価した。追跡者チームは、様々な回避者挙動に対してテストされた。

ベースライン:

• MT-PSRO: マルチタスク・ポリシー・スペース・レスポンス・オラクル（学習ベース）。
• NSGZero: ネットワークセキュリティのためのニューラル誘導型MCTS。
• Decomposition (分解): 木探索を用いない、サブチーム分解のみのベースライン。
• Intercepting (遮断): ヒューリスティックな最短経路ベースライン。

知見:

• 堅牢性: PGTS（RMおよびDUCTの両バリアント）は、すべてのトポロジーにおいて一貫して最も高い最悪ケース・ユーティリティ (Worst-Case Utility: WCU) を達成し、最短経路型の回避者に過学習の兆候が見られた学習ベースのベースライン（MT-PSRO, NSGZero）を大幅に上回った。
• 協調性: PGTSは純粋な「Decomposition」ベースラインを上回り、木探索のコンポーネントが、静的な分解では捉えられないチームレベルの協調を効果的に捉えていることを示した。
• アブレーション解析: プリミティブ誘導型展開または2v1プリミティブを除去すると、特に大規模で複雑なグラフ（Scotland Yard, Atlanta）において大幅な性能低下が見られ、効果的な探索と価値推定における両コンポーネントの必要性が確認された。

5. 意義と主張

本論文は、PGTSがマルチエージェントPEGsにおける「次元の呪い」に対するスケーラブルな解決策を提供すると主張している。小規模で頻出する局所的相互作用（プリミティブ）の厳密な解を利用してグローバルな探索をガイドすることで、本手法は以下を実現する：

1. 計算の実行可能性: 分岐因子と探索深度を効果的に制御する。
2. 適応性: 静的な分解とは異なり、フル結合行動空間における協調的なポリシーについて推論する能力を保持する。
3. 堅牢性: 学習された分布ではなくゲーム理論的原理に依拠しているため、学習フェーズで見られなかった多様な敵対的戦略に対しても良好に機能する。

著者らは、このアプローチがオフラインの均衡計算の理論的最適性と、オンライン計画の実践的な適応性の間の溝を埋めるものであると結論付けており、今後は部分観測性およびより広範なマルチエージェントゲームへの拡張が示唆されている。