技術的サマリー：Graph-SND：マルチエージェント強化学習における行動多様性のための疎集約

1. 問題定義

マルチエージェント強化学習（MARL）において、**システム神経多様性（SND）**は、エージェント間の行動分布のペアごとのワッサーシュタイン距離を平均化することで、エージェント間の行動の異質性を測定するために用いられる指標である。SND は多様性の制御（例えば DiCo アルゴリズムを介して）を可能にするが、その計算には深刻なスケーラビリティのボトルネックが存在する。完全な SND の計算には、すべての $\binom{n}{2}$ 個のエージェントペアの評価が必要であり、エージェント数 $n$ に対して二次的な $O(n^2)$ の計算複雑性を生じる。この集約コストは大規模なチームに対しては過大となり、多様性を意識したトレーニングや制御の実用的な応用を制限している。本論文は、「サブグループからシステムへの集約」段階を主要な未解決課題として特定しており、既存の指標は全ペアの平均を固定された、交渉の余地のない要件として扱っていると指摘している。

2. 手法：Graph-SND

著者らは、完全グラフの平均を任意のグラフ $G = (A, E, w)$ のエッジ上の重み付き平均に置き換える SND の一般化であるGraph-SNDを導入する。

定義

$d(i, j)$ をエージェント $i$ と $j$ 間のモンテカルロ行動距離とする。Graph-SND は以下のように定義される：
$$\text{SND}_G(D, G) = \frac{1}{W(G)} \sum_{\{i,j\} \in E} w_{ij} d(i, j)$$
ここで、$W(G) = \sum_{\{i,j\} \in E} w_{ij}$ は全エッジ重みである。

3 つの運用領域

このフレームワークは、グラフ $G$ の選択に基づき、3 つの明確な領域をサポートする：

1. 正確な回復（$G = K_n$）： $G$ が単位重みを持つ完全グラフである場合、Graph-SND は元の SND を正確に回復する。
2. 局所的多様性（固定疎グラフ）： $G$ が固定された疎グラフ（例：$k$-最近傍、通信トポロジー）である場合、この指標はタスクに関連する相互作用のみにおける多様性を測定する。これにより計算コストは $O(|E|)$ に削減される。
3. 疎推定（ランダムグラフ）： エッジがランダムにサンプリングされる場合（例：ベルヌーイサンプリング）、Graph-SND は完全な SND の疎推定量として機能する。
   • 不偏推定： ホルヴィッツ＝トンプソン重み（$w_{ij} = 1/p$）を使用すると、推定量は無条件に不偏となる。
   • 集中性： 正規化された標本平均（一様重み）はホエッディング型の集中不等式を満たし、$O(1/\sqrt{m})$ のレートで真の SND に収束する。ここで $m$ はサンプリングされたエッジの数である。

理論的バウンド

• 決定論的歪み： 固定された連結グラフに対して、論文は $\text{SND}_G$ と $\text{SND}$ の関係をエッジ転送インデックス $\pi(G)$ を用いて導出したバウンドを導出する。具体的には、$|\text{SND}_G - \text{SND}|$ は $\pi(G)$ を含む因子によって有界となる。
• エクスパンダグラフ： ランダムな $d$-正則エクスパンダグラフにおいて、転送インデックスは $O(n \log n / d)$ としてスケーリングする。著者らは、$d = \Theta(\log n)$ の場合、最悪ケースの相対歪みが $O(\log n)$ であることを証明した。
• スペクトル的精緻化： 低ランク距離構造（制御された正規化核ノルム）の下では、エクスパンダに対する誤差バウンドは $O(\rho^*/\sqrt{d})$ に改善され、経験的なほぼ 1 の比率を説明する。
• 確率的バウンド： ランダムな $d$-正則グラフに対して、$\tilde{O}(D_{\max}/\sqrt{n})$ の無条件確率的バウンドが確立された。

3. 主要な貢献

1. Graph-SND の定義： 完全グラフ上で SND を回復し、事前計算されたグラフ上で $O(|E|)$ のコストを要する疎集約レイヤー。
2. 理論的保証： 回復性、非負性、グラフ自己同型不変性、ホルヴィッツ＝トンプソン不偏性、および集中不等式（ホエッディング/サーフリング）の証明。また、固定グラフに対する決定論的歪みバウンドと、ランダム正則グラフに対する無条件確率的バウンドも確立されている。
3. 実証的検証：
   • 回復性と不偏性： VMAS 環境で検証され、$K_4$ における正確な回復と、$n=8$ におけるホルヴィッツ＝トンプソン推定量の不偏性が確認された。
   • スケーリング： $n=500$ まで、サンプリング確率 $1/p$ に比例してウォールクロック時間の高速化が線形にスケーリングすることが示された。
   • 閉ループ制御： Graph-SND を DiCo 多様性コントローラーに統合した。$n=50$ において、ベルヌーイ -0.1 Graph-SND は 1% 未満の相対誤差でセットポイントを追跡し、完全な SND と比較して報酬の差を 0 と区別できないレベルに抑えつつ、呼び出しごとの指標コストを約 $9.5$ 倍削減した。
   • エクスパンダのパフォーマンス： ランダムな $d$-正則エクスパンダは $\Theta(n \log n)$ 個のエッジにおいて $\text{SND}_G/\text{SND} \in [0.9987, 1.0013]$ を達成し、歪み対コスト比において他の疎ベースラインを大幅に上回った。

4. 結果

• 効率性： $n=100$ の 500 反復 PPO 実行において、ベルヌーイ -0.1 Graph-SND は完全な SND を追跡しつつ、呼び出しごとの指標時間を約 $10$ 倍削減した。
• スケーラビリティ： $n=500$ までの固定ポリシー GPU タイミングは、予測された $\binom{n}{2}/|E|$ の高速化を確認し、エッジ密度 10% で $n=500$ において指標時間を約 15.5 秒から約 1.5 秒に削減した。
• 制御の安定性： $n=50$ における DiCo 実験において、疎コントローラーはセットポイント追跡を維持し、9 つのマッチングされたセル全体でペアリングされた報酬差が 0 付近に中心を持ち、平均報酬差は $-6.2 \times 10^{-4}$ であった。
• ロバスト性： この手法は非ガウス設定（カテゴリカルポリシーと総変動距離を伴う PettingZoo MPE）へ転移し、小さなバイアスとコスト削減を維持した。

5. 意義と主張

本論文は、Graph-SND が、指標の意味論を変更したり、ポリシーアーキテクチャやトレーニングアルゴリズムの変更を要求したりすることなく、SND の集約ボトルネックを成功裡に除去したと主張している。

• ドロップイン代替案： 完全グラフ SND を超えてスケーリング可能な「ドロップイン疎代替案」を提供し、受動的測定と閉ループ多様性制御の両方をサポートする。
• 意味論的柔軟性： グラフ $G$ は nuisance パラメータではなく、測定対象を決定する意図的な選択として提示される：
  • 完全なシステム多様性を推定するにはベルヌーイサンプリングを使用する。
  • 特定の相互作用構造に関連する多様性を測定するには固定局所グラフ（例：通信、$k$-NN）を使用する。
  • 決定論的かつほぼ線形の疎代理変数として、強力な最悪ケース構造保証を持つエクスパンダグラフを使用する。
• 限定的な限界： 著者らは、エクスパンダに対する理論的バウンドが $O(\log n)$ である一方、観測されたほぼ 1 の比率はデータ依存であり、MARL 距離行列のスペクトル特性によって部分的に説明されると認めている。また、現在の実験は独立 PPO に焦点を当てており、中央化クリティックアルゴリズムは将来の課題として残されているとも述べている。

要約すると、Graph-SND は多様性集約をグラフ選択問題として再定義し、MARL における行動多様性のために計算効率と理論的保証を両立させる統合フレームワークを提供する。