技術要約：共同経験最良応答を用いたサンプル効率の高い方策空間応答オラクル

1. 問題設定

マルチエージェント強化学習（MARL）は、厳密なゲーム理論的分析に代わるスケーラブルな選択肢を提供しますが、「非定常性」（独立した学習がエージェントの更新に伴って環境を変化させてしまう現象）と、「非推移的な相互作用を捉えるための多様な戦略集団の維持」という2つの主要な課題に直面しています。**方策空間応答オラクル（PSRO）**フレームワークは、近似的な最良応答（Best Response, BR）を用いて制限されたゲームを反復的に拡張することで、これらの課題に対処します。

しかし、標準的なPSROは、計算コストおよびサンプルコストが極めて高いという問題を抱えています。各イテレーションにおいて、各エージェントは他のエージェントの現在のメタ戦略プロファイルに対して、独立して最良応答を計算しなければなりません。これは、各エージェントが残りのエージェントの完全なシミュレーションを必要とする、数多くの強化学習（RL）問題を解くことに相当します。プレイヤー数が多いドメインやシミュレータが高コストなドメインでは、このエージェントごとの学習構造により、PSROの実用性が損なわれます。

2. 手法

コア概念：共同経験最良応答（Joint Experience Best Response, JBR）

著者らは、全エージェント間で相互作用データを再利用するPSROの修正版である**共同経験最良応答（JBR）**を提案しています。各エージェントの最良応答を独立して訓練する代わりに、JBRは以下の手順を踏みます：

1. 現在のメタ戦略プロファイル $\sigma = (\sigma_j)_{j \in N}$ の下で、軌跡（trajectory）を一度だけ収集する。
2. 遷移 $(s_t, a_{1,t}, \dots, a_{n,t}, r_{1,t}, \dots, r_{n,t}, s_{t+1})$ を含む共有の共同データセット $\mathcal{D}_\sigma$ を構築する。
3. この単一のデータセットから、すべてのエージェントの最良応答を同時に計算する。

これにより、最良応答の計算をオンラインRL問題から、固定されたデータセットから方策を最適化するオフラインRL問題へと変換します。これはサンプル効率を劇的に向上させますが、データセットが現在のメタ戦略の下で生成されているため、真の最良応答に関連する状態・行動領域をカバーしていない可能性があり、分布シフト・バイアスを引き起こします。

オフラインRLバイアスへの対処

オフラインRLの限界（特に分布シフト）を軽減するために、本論文では3つの補完的な救済策を導入しています。

1. 保守的JBR（安全な方策改善）:

   • 学習された方策 $\pi_i$ が、データセットによって十分にカバーされている（カウント $N_D(s, a_i) \ge N^\wedge$）状態・行動ペアにおいてのみ、ベースラインとなるメタ戦略 $\sigma_i$ から逸脱することを強制する制約を課します。
   • サンプリング不足の領域では、方策は $\sigma_i$ に回帰し、パフォーマンスがベースラインを下回らないことを保証します。
   • 限界: 安全ではあるものの、過度に慎重であり、独立したBRと比較して大幅な改善を見出す能力を制限します。

2. 探索拡張型JBR:

   • カバレッジを向上させるために、データ収集プロセスを摂動（perturbation）させます。エージェントは厳密に $\sigma$ に従って行動するのではなく、$\delta$-摂動を加えたメタ戦略に従います：
     $$\tilde{\sigma}_j(a_j|s) = (1-\delta)\sigma_j(a_j|s) + \delta\nu_j(a_j|s)$$
   • 2つの探索戦略が提案されています：
     • $\delta$-ランダム ($\delta$-R): $\nu_j$ は一様ランダム方策です。
     • $\delta$-ターゲット ($\delta$-T): $\nu_j$ は現在の最良応答候補（$\pi^{BR,cur}_j$）です。これは探索を有望な軌跡へと向け、実質的に一種の相手モデル（opponent modeling）として機能します。
   • 理論的保証: 本論文では、有限な二人零和ゲームにおいて、エージェントが摂動された戦略 $\tilde{\sigma}$ に対して $\epsilon$-最良応答を計算する場合、結果として得られるメタ戦略は、元のゲームの $(\epsilon + 2R\delta)$-ナッシュ均衡になることを証明しています（ここで $R$ は報酬の範囲）。

3. ハイブリッド最良応答（Hybrid Best Response, HBR）:

   • JBRと標準的な独立最良応答（Independent BR, IBR）を交互に実行します。
   • ほとんどのイテレーションでは、効率性のためにJBRが使用されます。$k$ 回に一度のイテレーションごとに、エージェントは近似誤差を修正するために標準的な独立BR更新を行います。
   • これは、JBRのサンプル効率とIBRの正確性を組み合わせることを目的としています。

3. 主な貢献

1. JBRフレームワーク: 共有の軌跡を再利用してすべてのエージェントの最良応答を同時に計算する、PSROのドロップイン（そのまま置き換え可能な）修正版である共同経験最良応答の導入。これにより、サンプル効率が大幅に向上します。
2. オフラインバイアスへの救済策: JBRに内在するオフラインRLの限界を特定し、3つの具体的な救済策（保守的JBR、探索拡張型JBR、およびハイブリッドBR）を提案・評価しました。
3. 包括的な実証研究: 離散的（ポーカー）および連続的（パーティクル）な環境における、標準的なPSRO（独立BR）および主要なMARL（独立学習およびCTDE）に対する厳格な比較。

4. 実験結果

環境

• 離散的: Kuhn Poker（小規模で完全にカバーされた状態空間）および Leduc Poker（より大きな状態空間、不完全情報）。
• 連続的: Simple Tag, Simple Adversary, および Simple Push（マルチエージェント・パーティクル環境）。

知見

• 単純なドメインにおける実現可能性: 状態空間が小さく完全にカバーされているKuhn Pokerでは、JBRは標準的なPSROと同等の収束挙動を示し、実現可能性が確認されました。
• ナイーブなJBRの失敗: Leduc Pokerでは、探索や保守性を持たないナイーブなJBRは、オフライン学習バイアスにより均衡精度を維持できず、PSROと比較して高い搾取性（exploitability）で停滞しました。
• 各バリアントの有効性:
  • 保守的JBRは安定していますが、過度な慎重さゆえにPSROと比較してパフォーマンスが低くなります。
  • 探索拡張型JBR ($\delta$-R) は中程度の改善を示しますが、方向性に欠けます。
  • 探索拡張型JBR ($\delta$-T) は最良のトレードオフを実現し、PSROに近い均衡精度に、より少ないサンプル数で到達します。ターゲット型の探索は相手の更新を予測し、初期の収束を加速させます。
  • ハイブリッドBR (HBR-PSRO) は、サンプルコストをわずかに増加させるだけで、PSROとの残りの精度ギャップを埋めます。
• サンプル効率: JBR-PSRO-$\delta$Tは、標準的なPSROが必要とする合計最良応答エピソードの約半分で、PSROに近いNashConvを達成します。
• MARLとの比較: すべての環境において、PSROベースの手法（JBRバリアントを含む）は、戦略的堅牢性と均衡精度の点で、標準的なMARLパラダイム（独立学習およびCTDE）を一貫して上回りました。

5. 意義と主張

本論文は、JBRが戦略的学習の堅牢性を維持しながら、PSROを大幅に実用的なものにすると主張しています。

• スケーラビリティ: エージェント間で環境との相互作用を償却することにより、JBRは最良応答計算のサンプルコストを削減し、多人数またはシミュレータが重い設定におけるPSROの主要なボトルネックを解消します。
• 堅牢性: 戦略的に根ざした学習（PSROスタイル）は、サンプル効率を高めたとしても、標準的なMARLアプローチよりも戦略的に堅牢であることを結果は裏付けています。
• 実用的な展開: 提案されたバリアント、特に JBR-PSRO-$\delta$T と HBR-PSRO は、学習された均衡の質を損なうことなく、環境との相互作用コストが実行時間の支配的な要因となるドメインにおいて、PSROをデプロイするための実行可能な経路を提供します。

著者らは、JBRは効率を向上させるものの、PSROとそのバリアントは依然として典型的なMARL手法よりも多くのイテレーションとサンプルを必要とし、高次元の連続ドメインへのスケーラビリティは今後の課題であると述べています。