技術要約: ACPO: Agent-Chained Policy Optimization for Multi-Agent Reinforcement Learning

問題提起

協調型マルチエージェント強化学習（MARL）は、共有されたリターンを共同で最大化する分散型ポリシーを見出すことを目的としている。中央集中型学習・分散実行（CTDE）のパラダイムの下では、ジョイント・ポリシー・グラディエントを直接計算することが困難であるという根本的な課題が依然として存在する。既存のアプローチは概して以下の2つのカテゴリに分類されるが、いずれも重大な限界を抱えている：

1. 独立型ポリシー最適化（例：MAPPO, MADDPG）: エージェントは中央集中型クリティックを用いて、自身のポリシーを独立して更新する。スケーラブルではあるが、これらの手法は、他のエージェントの変化するポリシーによって導入される非定常性を考慮できていないため、ジョイント・ポリシー改善の一般的な保証を欠いている。収束は、値分解（value decomposition）のような強力な構造的仮定の下でのみ保証される。
2. 交互最良応答最適化（例：HAPPO, HATRIO）: エージェントは他者のポリシーを固定したものとして扱い、逐次的に更新を行う。これは各ステップにおけるジョイント・リターンの単調な改善を保証するが、その不動点はナッシュ均衡（NE）である。協調的な設定において、NEは真の社会的最適解と比較して任意に劣ったものになり得るため、エージェントにはこれらの劣った均衡から脱出するメカニズムが存在しない。

本論文は、どちらのアプローチも、制限的な仮定なしに、あるいは劣った均衡への収束を避けることなく、基礎となるマルチエージェントMDP（MMDP）の最適なジョイント・ポリシーを効果的に標的にできていないと主張している。

手法: Agent-Chained Policy Optimization (ACPO)

本論文の核心的な貢献は、ジョイント・ポリシー・グラディエントの厳密な分散分解の導出である。これは、新しい形式である**Agent-Chained Belief MDP (AC-BMDP)**を導入することにより、同時並行的なジョイント決定問題を、不完全情報下での直列化された決定プロセスへと変換することで達成される。

1. Agent-Chained Belief MDP (AC-BMDP)

「同時ゲームは不完全情報を持つ直列プロセスとして再構成できる」というゲーム理論の結果に着想を得て、著者らは各環境タイムステップ $t$ を、$N$ 個のエージェント $i \in \{1, \dots, N\}$ ごとに $N$ 個のマイクロステップへと分解する。

• 直列化 (Serialization): エージェントは単一のタイムステップ内で逐次的に行動を決定する。エージェント $i$ は、エージェント $1$から$i-1$ までの行動の後にアクションを実行する。
• 状態拡張 (State Augmentation): エージェント $i$ の状態は、先行するエージェントの実現されたアクション $\vec{a}^{<i}_t$ に対する信念（belief） $b^{(i)}_t$ によって拡張される。
• 分散実行 (Decentralized Execution): 実行時には先行するエージェントの実現されたアクションは観測されないため、信念は先行するエージェントのアクション分布 ($\phi^{(j)}_t$) から構築される。これらの分布は共有状態とエージェントのポリシーの決定論的な関数であり、通信なしにアクセス可能である。
• 連鎖型ベルマン演算子 (Chained Bellman Operators): エージェント $i$ の価値関数 $Q^{(i)}$ は再帰的に定義される。エージェント $i$ の価値は、次のエージェント（チェイン内の次のエージェント）の価値に依存する。最終エージェント ($N$) のみが環境報酬を受け取り、最初のエージェントの次のタイムステップの価値へとブートストラップを行う。この「連鎖（chaining）」により、ジョイント価値関数の分解可能性を仮定することなく、クレジット割り当てが可能になる。

2. 理論的基礎

本論文は2つの主要な定理を確立している：

• Agent-Chained Policy Gradient Theorem: AC-BMDPのポリシー・グラディエントは、標準的なスコア関数と、自身の状態および先行するアクションへの信念のみに条件付けられた分散型クリティック $Q^{(i)}$ を用いて計算できる。
• Multi-Agent Policy Gradient Decomposition Theorem: 元のMMDPのジョイント・ポリシー・グラディエントは、AC-BMDPから導出される $N$ 個の独立したエージェントごとの項の和と厳密に等価であることが示される。
  $$\nabla_\theta J(\vec{\pi}_\theta) = \frac{1}{(\gamma')^{N-1}} \sum_{i=1}^N \mathbb{E} \left[ \nabla_\theta \log \pi^{(i)}_\theta(a^{(i)} | s, b^{(i)}) \cdot Q^{(i)}([s, b^{(i)}], a^{(i)}) \right]$$
  決定的なことに、この分解は、ジョイント価値関数に対する構造的な仮定を一切必要とせず（VDNやQMIXとは異なる）、かつ劣った不動点への収束を回避する。

3. アルゴリズムの実装

著者らはACPOを2つの実用的な形式で実装している：

• ACPPO (On-Policy): 各エージェントが、エージェント・チェインに沿った累積TD残差を合計する一般化アドバンテージ推定（GAE）を介して、クリップされたサロゲート目的関数を最適化するPPOベースのアルゴリズム。
• ACTD3 (Off-Policy): 連鎖型ベルマン構造に従うツイン・クリティックを保持する、連続制御のためのTD3ベースのアルゴリズム。

信念の近似 (Belief Approximation):

• 完全観測 (MMDP) 設定: エージェントは、先行するエージェントのポリシーネットワークにクエリを投げることで、信念を正確に計算する。
• 部分観測 (Dec-POMDP) 設定: エージェントは、自身のローカルな履歴に基づいて先行するエージェントのアクション分布を予測するAction Belief Networkを採用し、これは中央集約型のターゲットに対するKLダイバージェンス損失を用いて学習される。

主な貢献

1. AC-BMDPの定式化: 直列化と信念拡張を組み合わせた形式的なフレームワークを導入し、値分解の仮定なしに、CTDEの下での最適なジョイント・ポリシー学習を可能にした。
2. 厳密なグラディエント分解: ジョイント・ポリシー・グラディエントが、エージェントごとの項への厳密な分解が可能であることを証明し、個別の更新がジョイント目的関数に対する単一の勾配ステップを構成することを可能にした。
3. 最適ジョイント・ポリシーへの収束: 交互更新の手法がナッシュ均衡に収束するのに対し、本論文は、テーブル形式の設定において、Agent-Chained Policy Iteration (ACPI) が基礎となるMMDPの最適ジョイント・ポリシーに収束することを証明している。
4. スケーラブルなアルゴリズム: ACPPOおよびACTD3の開発により、エージェント・チェイニングがオンポリシーおよびオフポリシーの両方のディープ強化学習アルゴリズムに適用可能であることを示した。

実験結果

著者らは、RWARE、SMACv2、MA-MuJoCoの3つの標準的なベンチマークでACPOを評価した。

• パフォーマンス: ACPO（特にACPPO）は、MAPPO（独立型最適化）、HAPPO/HATRPO（交互型最適化）、および値分解手法（VDN, QMIX）を含む強力なベースラインを一貫して上回った。
• エージェント数によるスケーリング: 重要な知見として、ACPOとベースラインの性能差はエージェントの数が増えるにつれて拡大することが挙げられる。RWAREにおいて、その優位性は8エージェントおよび12エージェントのシナリオで最も顕著であり、ACPOが高層の調整が必要な混雑した環境において特に効果的であることを示唆している。
• オフポリシー性能: オフポリシー・バリアントであるACTD3もMA-MuJoCoにおいてベースライン（MADDPG, HATD3）を上回り、エージェント・チェイニング・メカニズムの汎用性を実証した。
• アブレーション研究: エージェント・チェイニング機構を取り除いた場合（ACPPOを信念入力を持つMAPPOに縮小した場合）、MAPPOと同等の性能となった。これにより、得られた利得が単なる信念状態の追加ではなく、連鎖型アドバンテージ計算によるものであることが確認された。
• 効率性: ACPOは逐次的な信念計算を必要とするが、ウォールクロック・トレーニング時間はMAPPOと同程度であり、逐次的なエージェント更新を必要とする交互型手法（HAPPO/HATRPO）よりも大幅に高速である。

意義と主張

本論文は、ACPOがCTDEの下での協調型MARL問題に対する原理的な解決策を提供すると主張している。その意義は以下の通りである：

• ギャップの架け橋: 独立型更新の利点（スケーラビリティ）と、交互型更新の利点（単調な改善の保証）を統合し、それぞれの欠点（非定常性と劣ったナッシュ均衡）を回避している。
• 理論的厳密性: 値分解の仮定に依存しない、ジョイント・ポリシー・グラディエントの最初の厳密な分解を提示しており、テーブル形式の設定において社会的最適への収束を理論的に保証している。
• 実用的な有効性: 実験結果は、明示的な信念による連鎖を通じた調整が、現在の最先端手法と比較して、複雑なマルチエージェント調整タスクを扱うための優れたメカニズムであることを示唆している。

著者らは、信念計算がエージェント数に対して線形にスケールすること（$O(N^2)$ のフォワードパスを要する）や、現在の理論的保証が完全観測（MMDP）に依存していることなど、限界についても謙虚に述べており、これらを一般的なDec-POMDPへの拡張に関する今後の課題としている。