【DL輪読会】マルチエージェント強化学習における近年の 協調的方策学習アルゴリズムの発展

DEEP LEARNING JP [DL Papers] マルチエージェント強化学習における近年の 協調的方策学習アルゴリズムの発展 Shota Imai（東⼤ 松尾研） @ImAI_Eruel DL輪読会2022/11/25 http://deeplearning.jp/ 1

• http://deeplearning.jp/

書誌情報 2 以下の論⽂の内容が中⼼ n The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games - NeurIPS2022 n Trust Region Policy Optimisation in Multi-Agent Reinforcement Learning - ICLR2022 n Multi-Agent Reinforcement Learning is a Sequence Modeling Problem - NeurIPS2023 Shota Imai | The University of Tokyo

発表概要 3 n マルチエージェント強化学習は，シングルRLとは異なる概念に基づきアルゴリズムが発 展し，2021年までは⼀部の概念に基づく⼿法が⽀配的だった n ⼀⽅2022年以降，シングルRLのアルゴリズムの強みの再評価と新たな⽅策学習のパラダ イムが主流になり，Transformerも本格的に使⽤されるように n 今回の発表では上記のアルゴリズムの発展の整理と各アルゴリズム/概念を紹介 Transformer is All you Need Shota Imai | The University of Tokyo

深層強化学習以降のマルチエージェント強化学習のアルゴリズム Shota Imai | The University of Tokyo 4

深層強化学習以降のマルチエージェント強化学習のアルゴリズム 本⽇の発表に関係する⼿法 Shota Imai | The University of Tokyo 5

マルチエージェント深層強化学習
n 深層強化学習によって、複数エージェントが絡むタスクで⾼い性能を発揮するエージェ
ントの⽅策のセットを獲得することが⽬標
n 環境内の複数エージェントが同時に強化学習を⾏なっている設定
n 特に、実機を⽤いた難しい協調タスクへの応⽤が期待され、現在は計算機上での⽐較的
難しいタスクをベンチマークとしてアルゴリズムの研究が進む
n 有名な⼿法
-

MADDPG (Multi-Agent Deep Deterministic Policy Gradients)
COMA (Counterfactual Multi-Agent Policy Gradients)
VDN (Value-Decomposition Networks)
QMIX
AlphaStar

マルチエージェント深層強化学習に関する記号の定義
• 環境の状態：𝑠 ∈ 𝑆
• ⾏動：各エージェント𝑎 ∈ 𝐴 ≡ {1, … , 𝑛}の⾏動u! ∈ 𝑈
• 共同⾏動（joint action）：𝐮 ∈ 𝑈 ≡ 𝑈 "
• 状態遷移関数：𝑃(𝑠′|𝑠, 𝑢): 𝑆×𝑈×𝑆 → [0,1]
• 部分観測関数：𝑂(𝑠, 𝑎): 𝑆×𝐴 → 𝑜
• 報酬関数：𝑟(𝑠, 𝑢): 𝑆×𝑈 → 𝑅

6

マルチエージェント強化学習の問題設定の分類 7 n 中央集権型学習-中央集権型実⾏ (AlphaStar等) - 環境内にエージェントは複数いるが、各エージェントの⽅策を 出⼒するモデルは単⼀で、モデルへの⼊⼒も、各エージェント の観測をまとめて受け取る設定 - ⽅策モデルの処理能⼒に左右され、個別エージェントの観測の 情報の共有が無制限という仮定が必要 n 分散型学習-分散型実⾏（IQL, その他古典的⼿法） - ⼀番難しい設定で、全てのエージェントが学習/テスト時ともに 個別の観測を受け取って学習・⾏動する - 深層学習以前のマルチエージェント強化学習や、DQN登場直後 の問題設定はこれ 学習時 - IQL (Independent Q-Learners)としてまとめられることも ⽅策モデル： ! ! "! $ ! ) ⽅策モデル： ! " "" $ " ) ⽅策モデル： ! # "# $ # ) テスト時 n 中央集権型学習-分散型実⾏（MADDPG, COMA等） - 現在のMARLの主流設定（後述） - 学習時に追加の中央情報を使うが、 テスト時は分散的 ⽅策モデル： ! ! "! $ ! ) ⼊⼒ ⽅策モデル： ! " "" $ " ) 勾配 中央学習器： Q(! | $)等 損失計算 ⽅策モデル： ! # "# $ # ) ⽅策モデル： ! ! "! $ ! ) ⽅策モデル： ! " "" $ " ) ⽅策モデル： ! # "# $ # )

中央集権型学習分散型実⾏ CTDE; Centralized Learning Distributed Execution n 現在のMARLの最重要概念 n 中央集権型学習：学習時のみ，勾配を計算する時に全体のエージェントの情報を含む環境の「グローバルな情 報」を使う （e.g, 各エージェントの⽅策パラメータの勾配計算に部分観測に加え真の状態sを使う） n 分散型実⾏：テスト時には，各エージェントは⾃⾝の部分観測のみを⼊⼒として⽅策を実⾏ (例) 学習時には，全エージェントの情報sやuを使って，⽅策勾配を のように計算し，テスト時には各エージェントは⽅策𝜋(𝑢! |𝜏 ! )のみを使い，グローバルな情報の⼊⼒を必要とし ない n COMA[Foerster+ 2017]以降，特に⽤いられるアプローチで， “in many cases, learning can take place in a simulator or a laboratory in which extra state information is available and agents can communicate freely”[Foerster+ 2016] つまり，「マルチエージェントの学習は，研究的な環境でシミュレータ等を使えるため，学習を促進するために 追加の状態の情報を使ってもよい」という仮定によるアプローチ n 本来エージェントが動作するテスト環境（Execution時）は，基本的に各エージェントが個別の観測だけを受け 取って強調しているため，グローバルな情報は使えない Shota Imai | The University of Tokyo 8

深層強化学習以降のマルチエージェント強化学習のアルゴリズム Shota Imai | The University of Tokyo 9

深層強化学習以降のマルチエージェント強化学習のアルゴリズム 本⽇の発表に関係する⼿法 Shota Imai | The University of Tokyo 10

初期のCTDE型⼿法 11 n COMA（Counterfactual Multi-Agent Policy Gradients） - CTDEが導⼊された⼿法 - シングルRLの⽅策勾配をCTDEで改良 n MADDPG（Multi-Agent Deterministic Policy Gradients） - DDPGをCTDEで改良 Shota Imai | The University of Tokyo

IGM原理に基づく価値分解型の⼿法 n VDN - 価値分解型⼿法の元祖 - 各エージェントの個別価値の和とCTDEの勾配計算時に⽤いる共同価値を⼀致させる n QMIX - 最もよく使われるMARLの代表的アルゴリズム - HypernetworkベースのMixing networkで共同価値を計算 n QTRAN - IGM原理が提唱された⼿法 - 共同価値を学習しやすい形に変換 n QPLEX - シングルRLでも使われたDueling Networkを使⽤ - 個別価値と共同価値の両⽅にDueling Networkの機構を組み込む Shota Imai | The University of Tokyo 12

IGM原理（Individual Global-Max Principle） n 各エージェント𝑎が個別の観測𝑜! （または観測の履歴𝜏! ）を基に出⼒する⾏動価値𝑄! と， CTDE型の⼿法で勾配を計算する時に⽤いる𝑄"# (𝜏, 𝒖)について以下の関係を満たす場合， この⼿法における⾏動価値はIGMを満たす n つまり各エージェント個体がそれぞれ「最適だと思っている」（=⾏動価値が最も⾼い） ⾏動をまとめた共同⾏動が，エージェント全体としても現在の状態（or軌道）の下で最 も⾼い⾏動価値を持つ，という状況を満たす n IGMを満たさない場合，学習時の共同価値が最⼤の時と個別のエージェントの価値の最 ⼤の時がずれるため，分散型実⾏時に各エージェントが個別価値ベースで⾏動を選択す ると，全体としての最適⾏動にならない n QTRANで提唱される前のVDNやQMIXも，実はこの性質を持っていた Shota Imai | The University of Tokyo 13

IGM原理を満たす⼿法の無双 n QMIX以降は，MARL⼿法の主要ベンチマークにおいて，IGMを満たすアルゴリズムの無 双が続く（Q〇〇や〇MIX等の⼿法が⼤量に出現） Shota Imai | The University of Tokyo 14

新たな潮流 MARLにおけるシングルRLのアルゴリズムの強さの発⾒ n そもそも初期のMARLでは，DQN，PPOなどのシングルRLで使われていたアルゴリズム をそのまま適⽤する⼿法が普通だった n あまり性能が出ないため，価値分解，IGM原理，役割学習など，MARL特化型の⼿法が誕 ⽣ 疑問 実はシングルRLをMARLに適⽤しても性能が出なかったのは，シングルRL における実装・ハイパーパラメータが良くなかっただけで，この辺を ちょっと変えればMARLでも機能するのでは? Shota Imai | The University of Tokyo 15

MAPPO（Multi-Agent Proximal Policy Optimization） n シングルRLでよく使われるPPOを，学習アルゴリズムはそのままにハイパラや実装を MARL向けに調整した⼿法 n MARLで重要とされてきたIGM原理を満たさず，役割学習などの機構も持たないが，既存 のMARLアルゴリズムを圧倒する性能を発揮 Shota Imai | The University of Tokyo 16

おさらい / PPO 17 n TRPOを改良した⼿法で，より実装を単純にし，強⼒にしたもの - TRPO（Trust Region Policy Optimization）：⽅策勾配において適切な勾配の更新幅を保証 n 更新前の⽅策と新しい⽅策の確率密度⽐が，ある値1 − 𝜖, 1 + 𝜖の範囲に収まるよう制約 をかけて学習 Shota Imai | The University of Tokyo

MAPPOの⼯夫 18 n 基本的なアルゴリズムはシングルRLのPPOとまったく同じで，やったことは価値の計算 にCTDE的な⼿法を取り⼊れたことと，ハイパーパラメータをMARL向けに調整したのみ n 論⽂で指摘された重要な⼯夫要素 1. 価値関数の標準化をしよう 2. CTDEにおけるグローバルな情報と個別エージェントの情報を両⽅うまく使ou 3. 学習のエポック数はとても重要 4. PPOのクリッピングに使うεは0.2以下にしよう 5. バッチサイズは⼤きく使⽤ Shota Imai | The University of Tokyo

実験結果 / MAPPOの強さ n SMACの各タスクで実験（実際には他にもタスクをやってますが割愛） n 実質的に全てのタスクでSOTA n 今までのMARL界隈の努⼒はなんだったのか Shota Imai | The University of Tokyo 19

実装上の⼯夫の効果 / 価値関数の標準化 Shota Imai | The University of Tokyo 20

実装上の⼯夫の効果 / グローバル情報と個別情報の使い⽅ n CTDEで使うグローバルな情報についての定義をいくつか設定し，それを学習に使った場 合でどう性能が変化するかを分析 - CL（concatenation of local observations）：全てのエージェントの観測をconcatしたものを グローバル情報とする - EP（EnvironmentProvided global state ）：環境・全エージェントの要約情報をグローバル情 報とする - AS（Agent-Specific Global State ）：各エージェント固有の観測とグローバル情報を組み合 わせる - FP（Featured-Pruned Agent-Specific Global State）：ASで，各エージェントで被っている う情報を削除したもの Shota Imai | The University of Tokyo 21

実装上の⼯夫の効果 / エポック数の調整 Shota Imai | The University of Tokyo 22

実装上の⼯夫の効果 / クリッピングのεの調整 Shota Imai | The University of Tokyo 23

実装上の⼯夫の効果 / バッチサイズ Shota Imai | The University of Tokyo 24

HAPPO（Heterogeneous-Agent Proximal Policy Optimization） n MAPPOはアルゴリズムの性質上，全てのエージェントが同じパラメータを共有する Homogeneousな設定でしか使⽤できない - この設定はParameter Sharingと呼ばれるMARLにおける代表的な⼯夫 n ⾏動空間が違うエージェントで構成されるMARLのタスクでもMAPPOのようなやり⽅で 学習するため，HAPPOを提案 n 新たにAdvantage Decompositionという概念と，それをベースにしたsequential policy updateをPPOに取り⼊れた n かなり理論的なことも議論している論⽂（今回は割愛） ※実際にはHATRPOの導⼊がメインの論⽂だが，TRPOを簡単にしたHAPPOの⽅が⼀般的 Shota Imai | The University of Tokyo 25

MAPPOの問題点と改良 26 MAPPOの更新式 𝜃は全てのエージェントで同じパラメータなので，⾏動空間が異なるなどしてパラメータを 共有できない場合は適⽤できない n いい感じに異なるパラメータを持つエージェントをPPO的に⽅策学習できるやり⽅はな いか？ n 𝐴$ を各エージェントでいい感じにして，個別に⽅策更新すればいけそう？ Shota Imai | The University of Tokyo

Multi-Agent Advantage Decomposition n 𝑖%:' をエージェントの順列とすると以下が成り⽴つ n 各エージェントが正のアドバンテージを持つ⾏動aを選択し，続くエージェントも先の エージェントの⾏動を考慮した上で正のアドバンテージを持つ⾏動を選択・・・と繰り ( 返すと，全体の共同アドバンテージ𝐴$":$ は正の値になることが保証される n この性質を利⽤して，各エージェントのPPOの更新を以下のように⾏う Shota Imai | The University of Tokyo 27

HAPPOの⽅策学習 28 n アルゴリズムは⾮常に単純 n 各イテレーションでエージェントの順番をランダムに決めて，その順に⽅策更新を繰り 返す Shota Imai | The University of Tokyo

HAPPO / 実験結果 29 MA Mujoco SMAC Shota Imai | The University of Tokyo

MAT（Multi-Agent Transformer） n HAPPOで提案されたAdvantage DecompositionとSequential Policy Updateをベースに， MARLの⾏動⽣成・学習を系列モデリングとして定式化 - 論⽂タイトル: Multi-Agent Reinforcement Learning is A Sequence Modeling Problem n 系列モデリングの最強⼿法であるTransformerを取り⼊れることで， MARLの様々なタ スクで圧倒的な性能を発揮 n さらに，Transformerが得意とする事前学習についても検討を⾏い，MARLでエージェン ト数が違うタスクへのFew/Zero-shot学習が成功することも証明 Shota Imai | The University of Tokyo 30

系列モデリング問題としてのMARL 左：従来のMARL．各エージェントの⾏動に系列的な関係はない 右：各エージェントの⾏動が系列的で，出⼒⾏動が順に別エージェントに影響を与える Shota Imai | The University of Tokyo 31

MATのアーキテクチャ 32 n 従来のTransformerの機構はそのままに，⼊⼒トークンを各エージェントの観測にし，エ ンコーダで価値の出⼒を追加，出⼒が各エージェントの⾏動の⾃⼰回帰的な⽣成 n ⽅策の学習アルゴリズムはMAPPOを踏襲 Shota Imai | The University of Tokyo

MAT / 実験結果（SMAC） n ほとんど全てのタスクで上限に近い圧倒的な性能 Shota Imai | The University of Tokyo 33

MAT / 実験結果（MAMujoco） Shota Imai | The University of Tokyo 34

MAT / 事前学習の実験 35 n 複数環境で性能が出るようにMATで学習したエージェントが，エージェント数を変える などした別タスクでも性能を発揮できるかどうか 【実験設定】 n SMAC：3m, 8m vs 9m, 10m vs 11m, 25m, 3s vs 3z, 2s3z, 3s5z, MMMで学習したモデル をエージェント数が異なる5m vs 6m, 8m, 27m vs 30m, 2s vs 1sc, 1c3s5z, MMM2に適⽤ n MA Mujoco：全ての部位が揃ったHalfCheetahで学習したモデルを，⼀部の部位が動か なくなったHalfCheetahに適⽤ n 事前学習のサンプル数は10M Shota Imai | The University of Tokyo

事前学習の実験結果 36 n SMAC n MA Mujoco Shota Imai | The University of Tokyo

所感 37 n やっぱりTransformerは最強 n MARLにおけるTransformerを使った⼿法は始まったばかりで，今後関連研究が量産され そうな気配 n MAT⾃体はものすごくシンプルなTransformerベースなので，もともと別界隈で Transformerをいじくり回していた⼈間が合流しれ少し改良すればMARLに⾰命を起こせ るかも（？） Shota Imai | The University of Tokyo