はじめに．
強化学習/MDP モデルを理解している人を対象に、MADDPG (https://arxiv.org/abs/1706.02275) の概要をまとめています。
MADDPG の立ち位置．
MADDPG は multi-agent 向けの強化学習手法です．
派生元は Deep determinastic policy gradient (DDPG)で、Multi-agent 向けに派生させたものになっています。
準備．
必要な知識
Single-Agent RL に加えて Multi-Agent RL を理解するためには、
- CTDE / DTDE / DTCE
の知識が必要になります．T は training、E は execution を意味しています。
日本語に直訳すると、
- 集中学習分散実行 / 分散学習分散実行 / 分散学習集中実行
となります。
これらは、学習/実行時に 他 Agent 情報をどれだけ利用するモデルを想定しているかによって分類されます。
MADDPG は CTDE (集中学習分散実行) に属します。これは、学習時には他 Agent の方策/行動 を利用し、実行時には自身の状態のみを利用する特性をもつからです。
詳細は MADDPG の学習アルゴリズム部分に記載しています。
Multi-agent の難しさ
強化学習に限らず、Multi-Agent 問題の難しさは環境の Non-Stationary (非定常性)に由来することが多いです．
つまり、あるエージェント $i$ が時刻 $t$ で観測できる情報 $o_{i,t}$ から最適と判断した行動 $a_{i,t}$ が、同時刻に他エージェントが行動を行うことで最適性を失う可能性が存在するということです．
例えば経路問題においては、２台のエージェントの最短経路に交錯が存在すれば、衝突が生じてしまいます。
MADDPG
損失関数と勾配
派生元の DDPG が利用している DPG algorithm では、
\nabla_{\theta}J(\theta) = \mathbb{E}_{s\sim D} [\nabla_\theta \mu_\theta (a|s) \nabla_a Q^\mu (s,a) |_{a=\mu_{\theta}(s)}]
と方策の学習方向 $\nabla_{\theta}J(\theta)$ を得ます．ここで、$J(\theta)=\mathbb{E}_{s}[R(s,a)]$ です．この方策勾配は「方策勾配定理」と「determinastic policy gradient」で示されています。
DDPG は DPG algorithm の Acotr function $~\mu_\theta (a|s)$ と Critic function $~Q^\mu_\phi(s,a)$ を深層ニューラルネットで推論するように拡張したモデルです．学習安定化のために DQN の技術が多少利用されていたりもします．
先ほど述べた Non-Stationary を回避するために、MADDPG では CTDE の考え方を利用します．具体的にはシナリオに応じて２種類が本論文では提案されています．
１つ目は、「collaborative」なシナリオで、通信あるエージェント間が協調しながらタスクを行うことを想定しています．他エージェントの方策/行動を CTDE には利用します．
２つ目は、「competitive」なシナリオで、通信あるエージェントのうちに競争的/敵対的なエージェントが存在するシナリオです．他エージェントの方策を直接利用できないため、CTDE では他エージェントの方策を行動から推論した「方策推論器(本記事の勝手な命名)」(本論文4.2節)を学習に利用します．
注意ですが、この論文において $\color{red}{Centralized}$ とあるのは、全エージェントが共通の Critic を持つという意味ではありません．
DPG algorithm の結果を multi-agent に拡張すると、エージェント $i$ の方策勾配について、
\nabla_{\theta_i}J(\theta_i) = \mathbb{E}_{x,a\sim D} [\nabla_{\theta_i} \mu_{\theta_i} (a_i|o_i) \nabla_a Q_i^\mu (x,a_1,...a_N) |_{a_i=\mu_{\theta_i}(o_i)}]
となります．ここで、$x$ は、他エージェントの方策以外の情報を利用できる場合を想定して、$o_i$ を拡張するように表現されているものです．方策以外の追加の情報共有がない場合は $x=o_i$ とできます．Critic は全エージェントの方策の影響を受けた行動 ${a_1,...a_N }$ を利用するため、上付き記号に添え字 $i$ がありません．
Single-Agent の DDPG と Multi-Agent の MADDPG を並べて書くと、
\nabla_{\theta}J(\theta) = \mathbb{E}_{s\sim D} [\nabla_\theta \mu_\theta (a|s) \nabla_a Q^\mu (s,a) |_{a=\mu_{\theta}(s)}]
\nabla_{\theta_i}J(\theta_i) = \mathbb{E}_{x_i,a\sim D} [\nabla_{\theta_i} \mu_{\theta_i} (a_i|o_i) \nabla_a Q_i^\mu (x_i,a_1,...a_N) |_{a_i=\mu_{\theta_i}(o_i)}] \quad,~o_i \in x_i
となります。行動価値関数 $Q$ (つまり Critic ) に他エージェントの情報を利用している一方で、方策 $\mu$ (つまり Actor ) は自身の観測情報のみを利用しています。実行時に 行動価値関数 $Q$ は利用されないため、CTDE の名前の通り、集中学習 かつ 分散実行が実現されています。
同様に、Critic の損失関数の勾配も DDPG を拡張して、
\mathcal{L}(\phi_i) =\mathbb{E}_{x,a,r,x'}\left[r_i + \gamma Q_i^{\mu'}(x',a_1',...,a_N')|_{a_j'=\mu_j'(o_j)} - Q_i^{\mu}(x,a_1,...a_N)^2 \right]
となります．ここで、$\mu'$ は全エージェントの Actor のターゲットネットワークです．
こちらも DDPG と MADDPG の Critic 損失関数を並べて書くと、
\mathcal{L}(\phi) =\mathbb{E}_{o,a,r,o'}\left[r + \gamma Q^{\mu'}(o',a')|_{a'=\mu'(o)} - Q^{\mu}(o,a)^2 \right]
\mathcal{L}(\phi_i) =\mathbb{E}_{x,a,r,x'}\left[r_i + \gamma Q_i^{\mu'}(x',a_1',...,a_N')|_{a_j'=\mu_j'(o_j)} - Q_i^{\mu}(x,a_1,...a_N)^2 \right]
となります。DDPG について、行動空間を、他エージェントの行動と自身の行動をまとめたもの (Multi-Agent 系の論文では joint action space と記載されることが多いです。)に変更したものが MADDPG となることがわかります。
テクニック
competitive なエージェントの方策を推測する．
MADDPG は competitive なシナリオであっても「方策推論器(本記事の勝手な命名)」を用いて相手の方策を推測することで対処します．具体的には、エージェント $j$ の方策について、
\mathcal{L}(\phi_i^j) = -\mathbb{E}_{o_j,a_j}[\log \hat{\mu}_i^j(a_j|o_j)+\lambda H(\hat{\mu}_i^j)]
という損失関数を用いて、パラメータ $\phi_i^j$ で方策を $\mu_{\phi_i^j}$ とパラメータライズします．$H(\cdot)$ はエントロピーです．
この方策推論器を用いるとエージェント $i$ の Criti 損失 $\mathcal{L(\phi_i)}$は、
\mathcal{L}(\phi_i) =\mathbb{E}_{x,a,r,x'}\left[(r_i + \gamma Q_i^{\mu'}(x',a_1',...,a_N')|_{a_j'=\phi_i^j(o_j)} - Q_i^{\mu}(x,a_1,...a_N)^2 \right]
となります．見ての通り、他エージェントの観測が利用出来るという仮定は解消されません．あくまで他エージェントの方策が利用出来るという仮定のみ解消されます．
過学習を防ぐ．
MADDPG では、エージェント群全体の報酬を個々の報酬に分割するような機構を持ちません(reward+decomposed という研究分野もあります)．つまり、あるエージェントがとびぬけて素早く学習してしまうと、全体としての最適方策を学習し損ねる可能性があります．この傾向は特に competitive なシナリオでよくみられるそうで、こうした状態を防ぐために、通常の過学習に対する対応のように方策をアンサンブルする工夫がなされます．
完結に述べると、エピソードごとにサブポリシーから選択して、バッファと更新も分けるよ！というわけです．詳しくは、本論文の 4.3節をご覧ください．
$\color{red}{テスト時にどのサブポリシーを選択すべきかは記載ありません、、、．どゆこっちゃ}$
コメント
DDPG を少しの変更で Multi-Agent に拡張したものが MADDPG です。 TD3 は DDPG を少し変更して Q 値の過学習を防ぐために提案された Single-Agent 向けの手法です。当然、DDPG -> MADDPG と拡張されたように、TD3 -> MATD3 と拡張された手法も存在します。