Multi-Agent Deep Reinforcement Learning (MADRL)の入門として第一回は, Foerster 先生らによる「Couterfactual Multi-Agent Policy Gradients」を取り上げる.
いわゆるCTDE(Centeralized Training Decentralized Execution)と言われるMADRLでは主流の問題設定で, 訓練時は各エージェントが自由に情報を共有していいが, テスト時は自分の観測のみしか行動決定に用いてはいけないという設定である.

導入

TD法と方策勾配法について復習する.

TD法

強化学習で頻繁にマルコフ過程は仮定する. となれば, ある状態$s$の価値関数$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}))$が得られるので, これらを使って価値関数を学習させていく. モデルを$\hat{V}(s)$と表記する. TD法は各ステップ$t = 1, \ldots, T$についてTD誤差

    \delta := r_t + \hat{V}(s_{t + 1}) -\hat{V}(s_{t})

を計算し, モデルを更新する:

    \hat{V}(s_t) \leftarrow \hat{V}(s_{t}) + \alpha \times \delta.

ただし, $\alpha$は学習率である.

方策勾配法

方策勾配法は主にactor-criticベースの手法で使われる. actorがpolicy(方策) ${\pi}_{{\theta}}( {a} | {s})$を司り, ある状態${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)$とする.)

次回は本論文の中身に入っていく.