この記事ではマルチエージェント深層学習の初期のアルゴリズムであるCOMAアルゴリズムを紹介します。
元の論文はFoerster et al. Counterfactual Multi-Agent Policy Gradients. AAAI, 2018.です。
導入
TD法と方策勾配法について復習します。
TD法
強化学習で頻繁にマルコフ過程は仮定します。となれば, ある状態 [tex: s] の価値関数[tex: V(s)] を知りたい. 各episodeでtrajectory (履歴)として
$$
\{ (s_0, a_0, r_0), (s_1, a_1, r_1), \ldots, (s_{T - 1}, a_{T - 1}, r_{T - 1}) \}
$$
が得られるので、これらを使って価値関数を学習させていきます。
方策勾配法
方策勾配法は主にactor-criticベースの手法で使われます。actorがpolicy(方策) ${\pi}_{{\theta}}( {a} | {s})$を司り、ある状態[tex: s]でどのような行動$a$をするかを出力する. criticは価値関数$V(s)$や行動価値関$Q({s}, {a})$を推定する. 重要な定理として, 以下の方策勾配定理がある.
方策勾配定理(informal)
方策$\pi_{\theta}(a|s)$の下での累積報酬の期待値を$J(\theta)$とする. 以下が成り立つ.
$$
\nabla_{\theta}J(\theta) = \mathbb{E}_{\pi_{\theta}} \left[ \sum_{t = 1}^{T} \nabla_{\theta} \log (\pi_{\theta}(a_{t} | s_{t}) (Q^{\pi_{\theta}}(s, a) - b(s)) \right].
$$
詳しい解説などは「強化学習」（森村哲郎著, 講談社）に載っています。
ここで, $b(s)$は状態$s$にのみ依存するベースライン関数と呼ばれるものです。ベースライン関数の選び方で分散の大きさが決まってくる. 様々なベースライン関数が研究されている.
方策勾配法を用いたものに, REINFORCE法(Williams, 2019)がある. 各エピソードの履歴$(s_0, a_0, r_0), (s_1, a_1, r_1), \ldots, (s_{T - 1}, a_{T - 1}, r_{T - 1})$を得るたびに,
$$
c_{t} := \sum_{l = t}^{T - 1}r_{l}, \quad \forall t \in { 0, 1, \ldots, T - 1 }
$$
と計算して, パラメータを以下のように更新する:
$$
\theta \leftarrow \theta + \alpha \frac{1}{T} \sum_{t = 0}^{T - 1} (c - b(s_{t}))\nabla \log \pi_{\theta}(s_{t}, a_{t})
$$
注意するべき点は、モンテカルロサンプリングによって$Q$を推定していることから, REINFORCEはactor-criticではなく、criticなしの方策勾配法ということです。
actor-criticメソッドの場合は, $b(s) = V(s)$として, アドバンテージ関数 $ A(a_{t}, s_{t}) = r_{t} + V(s_{t + 1}) - V(s_{t}) $を用いて, 以下のようにパラメータを更新する.
$$
\theta \leftarrow \theta + \frac{1}{T} \sum_{t = 0}^{T - 1} \nabla_{\theta}\log \pi_{\theta}(a_{t}|s_{t}) A(a_{t}, s_{t})
$$
ここで使われる$V(s)$はcriticが推定したものを使うのである. (off-policyの場合はアドバンテージ関数として, $A(a_{t}, s_{t}) = r_{t} + \max_{a \in \mathcal{A}} Q^{\pi_{\theta}}(s_{t + }, a)$とする.)
本題
N体のエージェントについて考える. 素朴な方法として各$i\in \{ 1, \ldots, N \}$番目のエージェントの方策勾配を一律
$$
G = \nabla_{\theta}\log \pi_{\theta}(a_{t} | s^{i}_t) \left( Q(s_{t}, a_{t}) - V\left( s_t \right) \right)
$$
と定めたとします。ここで, $s_{t}$と$a_t$はそれぞれ全エージェントのjoint stateとjoint actionであり, $r_t$は全エージェント共通のrewardです。これだとそのエージェントの行動がどれくらい全体の報酬に貢献したかうまく推論しづらい ("Credit Assignment Problem")が発生します。他のエージェントがうまい方策を探索している最中だと, $G$はノイジーになり, 自分の方策をうまく改善できない場合があります。
提案手法
学習を安定させるためにアドバンテージ関数を工夫しなければいけないというのが出発点です。ベースライン関数を変更します。直観的には, 「ほかのエージェントがそのままの行動を取った時に自分（エージェント$i$）の今の方策はどれくらい良いか」が知りたいです。COMAはこの直観を以下のアドバンテージ関数を構築することで知ろうとします。
$$
A^{i}(s, a) = Q(s, a) - \sum_{u_{i} \in \mathcal{A}} \pi_{\theta} (u_{i}, H_{i} ) Q(s, (\mathbf{u}^{- i}, u_{i}))
$$
ここで$u_{i}$はエージェント$i$の行動, $\mathbf{u}^{-i}$はエージェント$i$以外の行動を固定した時の行動ベクトル, $H_{i}$はエージェント$i$の行動・観測履歴です。
実験
最後にCOMAアルゴリズムを動かしてみたいと思います。コードはこちらにあります。
実験環境
考える環境は以下の通りです。
図のように、4つのエージェント（紫、青、緑、オレンジ）がそれぞれ自分の色と同じ色で塗られているマスに移動したいとします。
具体的には、紫、青、緑、オレンジはそれぞれ座標(0, 0)、(0, 5), (6, 0), (5, 6)を出発して、それぞれの対角線上である座標（5, 6）, (5,. 0), (0, 6), (0, 0)に移動したいという状況です。
エージェントたちは各時間ステップでそのマスにとどまるか、左右上下のマスに移動することができます。
黒く塗られているマスには移動できません。アクションは1だと上、2だと右に、３だと下に、４だと左に、０だとその場にとどまる、という具合です。
各時間ステップの報酬は以下のように、ゴールまでのユークリッド距離とします。つまり、
$$
\sum_{i = 1}^{4} ( x_{i} - x^{goal}_{i} ) ^2 + (y_{i} - y^{goal}_{i}) ^{2}
$$
です。
モデル
- Actor: 二次元の座標を入力として、5ステップまでを記憶して、GRUで行動を出力する
- Critic: 入力は盤面全体を9チャネルの画像として見ます. 1~4チャネルが各エージェントの位置を、5~10チャネルが行動を各エージェントの行動を表します. この入力をCNNで行動価値関数の値を出力します.
結果
結論から言うと結果は微妙です。まずサンプル効率性が良くないし, トレーニング中の分散も大きいです。
以下のように、上手くいくと４人のエージェントがうまくそれぞれのゴールに到達する場合がありますが（下図参照）, 大半の場合はこうはならず、誰かしらが同じ場所にとどまってしまったりします.
感想
COMAアルゴリズムはマルチエージェント深層強化学習の分野では最先端の技術とは言えません. しかし, "Counterfactual"というアイデアは面白いです. 人間も「自分がもし仮に他の行動をしていたら、チーム全体のパフォーマンスはどうなっていただろう」と考えることはよくあると思います。
このブログは株式会社EfficiNet Xのテックブログです。