Randomness is sometimes necessary for coordination

技術的サマリー：ランダム性駆動型協調のためのダイヤモンド・アテンション

問題定義
協調型マルチエージェント強化学習（MARL）において、均質なエージェントに対する完全なパラメータ共有は標準的なアプローチであり、中央集権的訓練と分散実行（CTDE）と組み合わせて用いられることが多い。しかし、このアプローチは、複数の同等に最適な共同戦略が存在するマルチモーダルな報酬構造を持つタスクでは機能しない。置換対称な観測条件下では、共有された決定論的方策はすべてのエージェントに対して同一の行動分布を生成するため、役割の分化が不可能となる。Angluin（1980）および Case ら（2005）の理論的研究は、匿名プロセッサ間の対称性の破れは決定論的には不可能であることを確立しており、エージェントが固有の識別子を持たない場合、協調には共有ランダムビットへのアクセスが必要条件である。既存の解決策の多くは実行時に決定論的であり（理論的要件を満たさない）、あるいは逐次実行を通じて対称性を破るが、これにより $O(N)$ の推論遅延が生じ、外部から課された実行順序が必要となる。これは真に分散された設定における循環的依存関係である。

手法：ダイヤモンド・アテンション
著者らは、単一のブロードキャストラウンドで対称性を破るために理論的に必要とされる共有ランダム性を実装する、クロス・アテンション・アーキテクチャである「ダイヤモンド・アテンション」を提案する。

• 中核メカニズム: 各タイムステップにおいて、各エージェントはスカラーのランダム数 $r_i \sim \text{Uniform}[0, 1]$ をサンプリングする。これらのスカラーは単一のブロードキャストを通じてチーム全体と共有される。
• 構造化されたマスキング: ランダム数はエージェント間に一時的かつ厳密なランク順序を誘起する。エージェント間クロス・アテンション機構に対して構造化されたアテンション・マスクが適用される：
  • エージェント $j$ のランクがエージェント $i$ よりも低い場合（$r_j < r_i$）、エージェント $i$ はエージェント $j$ をマスクする。
  • エージェント $i$ は、ランクが同等または高いエージェントのみにアテンションを向ける。
  • タスクからエージェントへのアテンションは完全にマスクされず、すべてのエージェントがグローバルな目標構造へのアクセスを維持する。
• 生じる非対称性: このマスキングにより、動的かつタイムステップごとの階層性が創出される。高ランクのエージェントは主にタスク埋め込みへのアテンションに依存してほぼ独立して行動し、低ランクのエージェントは高ランクの仲間たちの行動に基づいて行動を条件付ける。これにより、同一のネットワークパラメータであっても、分化された潜在表現と行動分布が誘起される。
• スケーラビリティ: このアーキテクチャはエージェントとタスクの埋め込みの集合上で動作するため、修正なしに任意数のエージェントとタスクを受け入れることができ、異なるチームサイズへのゼロショット一般化を可能にする。

主要な貢献

1. 理論的定式化: 本論文は、XOR 協調とランダムビット共有の等価性を定式化し、アーキテクチャ設計を Case ら（2005）の不可能性結果に基づいている。
2. アーキテクチャ的革新: ダイヤモンド・アテンションは、逐次実行や外部エージェント識別子を必要とせず、単一のブロードキャストラウンドでランダムビット協調プロトコルを実現する。外部からの順序付けの必要性を、内部的な構造化された確率性によって置き換える。
3. 実証的検証: この手法は、特定の協調病理を分離した 3 つの異なる領域で検証されている：
   • 対称性の破れ（XOR ゲーム）: 完全に対称な XOR ゲームにおいて、決定論的ベースラインはランダム行動の下限（$N=2$ で成功率 0.5）付近で頭打ちになる。ダイヤモンド・アテンションは 1.0 の成功率を達成する。
   • ゼロショットスケーラビリティ（VMAS）: $N=4$ のエージェントで訓練された方策は、静的（Simple Spread）および動的（Food Collection）の両環境において、$N \in [2, 8]$ のチームにゼロショットで一般化し、未見のチームサイズで劣化するベースラインを上回る。
   • 敵対的転移（SMACLite）: このアーキテクチャは、標準的なベースラインが構造的制限により完全に失敗する 2s3z から 3s5z へのシナリオへのゼロショット転移を達成する。

結果とアブレーションからの知見

• 構造の必要性: 構造化されたマスクを標準的なドロップアウトに基づくランダム性に置き換えると、SMAC 転移タスクにおける勝率は 0% となる。これは、作動する要素が単なる確率的ノイズではなく、ランダム順序の「プロトコル空間における構造」であることを確認する。
• 一般化の限界: この手法は連続制御（VMAS）ではよく一般化するが、行動空間の厳密な部分集合（例：$N=2, K=3$）で訓練され、XOR ゲームにおいてより大きなチーム（$N=3, K=3$）に展開された場合は脆さを示す。これは、環境信号が追加の非対称性を提供する動的環境における堅牢性とは対照的である。
• 自己回帰的手法との比較: 逐次実行を通じて対称性を破る自己回帰モデル（例：MAT）とは異なり、ダイヤモンド・アテンションは $O(N)$ の遅延や外部順序付けの仮定なしに 1.0 の成功率を達成する。

意義と主張
本論文は、ダイヤモンド・アテンションが、環境信号に依存するのではなく、内部で生成され、ステップごとに確率的に生成される作動状態を提供する協調プリミティブであると主張する。著者らは、このアプローチがグローバルな同期や固定されたエージェント識別子なしに分散協調を可能にすることを強調している。

その意義は、決定論的最適化や非構造化ノイズではなく、「構造化されたランダム性」が、対称的で匿名の環境における協調の決定的要因であることを実証する点にある。この研究は、災害対応などの信頼性の低いインフラにおける時間的制約の厳しい展開において、観測可能な環境の手がかりに依存する方式よりも、内部でサンプリングされた協調状態の方が通信障害や敵対的ジャミングに対して耐性が高いことを示唆している。ただし、著者らは、可変な行動空間を表現能力を犠牲にすることなく処理するための適応的投影層の必要性や、PPO 下での高次元かつスパース報酬の設定（$N > 5$）における現在の学習ボトルネックなど、限界を控えめに指摘している。