反証的な複数エージェントの強化学習を読む

複数エージェントの強化学習の論文を読むと必ず参照される「反証的複数エージェントモデル」(Counterfactual Multi-Agent：COMA)の論文を読んでみた。

[1705.08926] Counterfactual Multi-Agent Policy Gradients

表題にある反証的(counterfactual)とは、複数エージェントの一員として自分の行動の寄与を計算するため、協調した場合と非協調の場合の比較を行っており、この比較を反証的と称している。

この論文のもう一つ価値としては、Suttonの単独エージェントでの方策勾配法(Policy gradient)の理論を複数エージェントに拡張して数学的に正しいことを証明している点にある。

COMAでは複数エージェントでのActor-Critic方式を以下で構築している。

　Actor：非中央制御型　各エージェントの反証的価値 $A^c$ から方策のパラメータ $\theta^\pi$ を計算

　Critic：中央制御型　各エージェントの状態を統合して、 $TD(\lambda)$ 法でQ価値関数を算出するパラメータ $\theta^c$ の計算と各エージェントの反証的価値 $A^a$ を計算

下図の全体構成ではCriticは環境からは状態と報酬を得て、また各エージェントのActorから次の最適協調行動 $u^a$ と方策関数 $\pi$ を受取り、反証的価値 $A^a$ をActorに戻している。各エージェントのActorは反証的価値 $A^a$ 及び部分観察 $o^a$ を得て最適行動 $u^a$ を求めている。ここで大事なのはActorはGRU(Gated reccurent unit)の時系列モデルを採用しており、時系列の隠れ変数 $h$ を更新していることである。

f:id:mabonki0725:20181215165519p:plain — COMAの全体構成

①方策勾配法（Actorロジック）

　論文ではSuttonの方策勾配法での勾配 $g$ は以下で示されている。

　　 $g=\mathbb{E}_{s_{0:\infty},u_{0:\infty}} [ \sum_{t=0}^T R_t \nabla_{\theta^\pi} \log \pi(u_t|s_t)]$ (1)

　ここで

　　　 $s_t$ は状態

　 $u_t$ は行動（一般的には $a$ を使うが複数エージェントの場合は $u$ で表記する)

　　　 $\pi$ は方策

$t$ 時点の平均報酬 $J_t$ を使うと式(1)は以下の式A～Eの手続きで式(1)を示せる。

　 $J_t = \mathbb{E}_\pi [R_t] = \sum_{s_t}d(s_t) \sum_{u_t} \pi(u_t|s_t) R_t$ 　　式A

　ここで　 $d(s_t)$ は状況 $s_t$ になる確率

これを使うと(1)式は以下に変形できる。

　 $g=\mathbb{E}_{s_{0:\infty},u_{0:\infty}} [ \sum_t^T \nabla_{\theta^\pi} J_t$ ] 　式B

　式Aを $\theta^\pi$ で微分すると

　 $\nabla_{\theta^\pi} J_t = \sum_{s_t}d(s_t) \sum_{u_t} \nabla_{\theta^\pi} \pi(u_t|s_t)$ 　　式 C

　ところで対数の微分公式を使って

　 $\nabla_{\theta^\pi} \log \pi(u_t|s_t) = \frac{1}{\pi(u_t|s_t)} \nabla_{\theta^\pi} \pi(u_t|s_t)$

　両辺を $\pi(u_t|s_t)$ を乗じると以下となる。

　 $\nabla_{\theta^\pi} \pi(u_t|s_t) = \pi(u_t|s_t) \nabla_{\theta^\pi} \log \pi(u_t|s_t)$

　上式を式Cに代入すると

　　 $\nabla J_{\theta^\pi} = \sum_{s_t}d(s_t) \sum_{u_t} \pi(u_t|s_t) \nabla_{\theta^\pi} \log \pi(u_t|s_t)$ 　　式D

　ここで次の確率の総和は１であることを使うと

　　 $\sum_{s_t}d(s_t) \sum_{u_t} \pi(u_t|s_t) = 1$

　以下となる。

　　 $\nabla J_{\theta^\pi} = \nabla_{\theta^\pi} \log \pi(u_t|s_t)$ 式E　

　一方式Bは以下なので

　 $g=\mathbb{E}_{s_{0:\infty},u_{0:\infty}} [\sum_t^T R_t \nabla J_{\theta^\pi}]$

式Eを式Bに代入すると式(1)が示せた。

②反証的ロジックによる価値 $R_t$ の設定

複数のエージェントがあり、特定のエージェントの全体に対して寄与度を計測できれば、特定エージェントが採った行動について全体に及ぼす価値を計算することができる。即ち、特定のエージェントが協調に反する行動を起こした場合の価値関数を反証的として求めて、協調行動との差を寄与度 $A^a(s,\vec{u})$ とする方法である。

　Suttonの方策勾配の $R_t$ は何を使ってもよいことが知られており、本論文でもlemma1でこの証明がある。 $R_t$ は価値関数とベースラインとの差を使う場合が多い。ベースラインを使うのは $R_t$ の大きな変動を抑止するためである。

　　 $R_t = Q(s_t,u_t) - b(s_t)$

本論文では反証的な寄与度 $A^a(st,\vec{u})$ を使う。

　　 $R_t = A^a(s,\vec{u}) =Q(s,\vec{u}) - \sum_{u'^a} \pi^a(u'^a|\tau^a) Q(s,(\vec{u}^{-a},u'^a)$ 　　(4)

上式で分る様にベースラインは反証的な価値関数となっている。

　　 $bs(s_t) = \sum_{u'^a} \pi^a(u'^a|\tau^a) Q(s,(\vec{u}^{-a},u'^a)$

論文には記述していないが式(４)で $\pi(u|s)$ の代わりに $\pi^a(u|\tau^a)$ を使うのは、複数エージェントモデルでは全体的な状況 $s$ よりも個別エージェントが把握している経路 $\tau$ の方が適切と考えられる。

下図の様にCOMAでは各エージェント毎に方策勾配法で求めるパラメータ $\theta^\pi$ を計算するのにGRU(gated Reccurent Unit)を使って時系列の影響を反映できる様にしている。

f:id:mabonki0725:20181215172346p:plain — GRUを使ったActorのモデル

③価値関数のパラメータ最適化（Criticロジック）

Criticは中央制御型なので、COMAではSuttonの教科書通りの単体エージェント型の $TD(\lambda)$ 法によって全エージェントの情報(features)を集めて次の損失関数 $\mathcal{L}_t$ を最小にするパラメータ $\theta^c$ 計算している。

　 $\mathcal{L}_t = (y^{(\lambda)} - Q(features_t,\theta^c))^2$

$y{(\lambda)} = (1-\lambda) \sum_{n=1}^{n-1} \lambda A^{n-1} G_t^{(n)}$

$G_t^{(n)} = \sum_{i=1}^n \gamma^(n-1) r_{t+i} + \gamma^n Q(features_{t+n},\theta^c)$

ここで　

　 $\gamma$ は割引係数　

　 $r_t$ はｔ時点の全エージェントで獲得した報酬

f:id:mabonki0725:20181216093559p:plain — Figure of Sutton's TD(λ)

次にCOMAのCriticでは全体の価値関数 $Q(s,\vec{u})$ から各エージェント毎に式(4)の反証的ロジックより各エージェントの価値を $A^a(s,\vec{u})$ を計算する。

f:id:mabonki0725:20181215172725p:plain — Criticモデル

上図での $o_{t'}^a$ は各エージェントの部分観察を示している。これも本論文で記述していないが価値関数 $Q(s,\vec{u})$ は便宜的な記述で、本来は全エージェントが観察できる特徴量を使った $Q(features;\theta^c)$ が正しいと考えられる。

④チーム対チーム型ゲームStarCraftでのCOMAの実験

StarCraft環境ではチーム対戦（攻撃、回避、待機）をする。自己チームはCOMAモデルで動作するが対戦相手はStarCraftが用意している経験ルールに基づいた動作をする。

COMAの性能実験では下図の様に対戦相手を認識する範囲を故意に設けている。これは部分観察データを使うためと、近接戦に限定することで方策の探査空間を狭めるためである。下図では２匹の竜と３匹のzealosでチームを構成している。

f:id:mabonki0725:20181215200841p:plain — Starcraftでの近接戦範囲の設定

⑤StarCraftでの実験結果

COMAで採用した方法の効果の確認のためモデル比較している。

　(1) Criticで中央制御型の採用　

　　IAC-V：ActorもCriticも非中央制御型(協調行動しない）でQ関数を計算

　　IAC-Q：ActorもCriticも非中央制御型(協調行動しない）でV関数を計算

但しIACの深層学習の最終層は同じパラメータを使用している。

(2) Q関数の採用

　　central-V：Criticは中央制御型でQ関数の代わりにV関数を使用

　(3) Actorで行動価値評価にの反証的方法を採用

　　central-VQ：Criticは中央制御型でActorの行動の価値評価に $Q(s,\vec{u}) -V(s)$ を使用

　下図では縦軸に勝率、横軸に訓練回数をしめしてありチームの編成が異なる。各方法の薄い色は実験結果の変動１σの範囲を示し、実線は平均である。

　3mは3人の海兵隊　5mは５人の海兵隊　5wは5人の生霊(wraith) 2d_3zは２匹の竜に３匹のZealosである。

　なおheuristicは経験的なルールによる行動での勝率を示す。

f:id:mabonki0725:20181215202031p:plain — StarCraftでのCOMAの性能比較

　図(a)の3mでは非協調型のIAC型の性能が悪く中央制御型による協調行動が有意なことが分る。

　図(b)の5mではIAC型も学習が進めば差が出ない。論文に記述はないが５人だと協調行動の必要性が少なくなると考えられる。

　図(d)の2d_3zは異なる種のチーム編成であり、特徴を生かした協調行動が有意なことを示している。

下表のheur(経験的なルールで行動）で判明する様に接近戦が遠隔戦（遠くから攻撃する）より勝つことが難しいことを示している。またGMEZOは中央制御型で記録保持モデルである。

f:id:mabonki0725:20181215211735p:plain — 接近戦と遠隔戦での勝率比較