始めに
世の中のほとんどのタスクは、一般的にマルチエージェント環境です。 例えば、ネットワークルーター、自動運転環境、リアルタイムストラテジーゲームなど、多くのシステムがマルチエージェント環境と言えるでしょう。そこで今回から**MARL（Multi-Agent Reinforcement Learning、以下MARL）**シリーズの投稿を始めたいと思います。
環境と制約
今後の投稿は、次の3つの条件のもとで進めたいと思います。
- 1つ目は、各エージェントは全体ではなく一部しか観測できない、いわゆる**部分観測（partial-observation）**であることです。
- 2つ目は、各エージェント同士が観測情報（observation）を共有しないという点です。 以下の図を見ると、青い円はエージェントが観測可能な範囲、赤い点線の円は攻撃可能な射程範囲を示しています。つまり、全体を把握できず、一部のみを見ながら行動している状況です。
-
- 最後に3つ目の条件ですが、報酬は各エージェント個別ではなく、チーム全体に対して与えられるという点です。
このような環境において最終的な目標は、複数のエージェントがそれぞれの役割に応じた行動を行い、効率的に協力プレイを実現することです。
以前のアプローチ
MARL（Multi-Agent Reinforcement Learning）の最初のアプローチの一つとして挙げられるのが、**IQL（Independent Q-Learning, Ming Tan 1993）**という手法です。この論文は以下のリンクから参照できます。
この手法の基本的なメカニズムは、各エージェントが独立してQ学習（Q-Learning）を行うというものです。つまり、各エージェントは自身の部分観測情報（partial-observation）のみに基づいて行動を選択します。 その名の通り、完全に独立したQ学習を進める方法です。 この手法は単純な状況ではある程度うまく機能しますが、エージェントの数が多い場合やエージェントごとに役割が異なる場合など、状況が複雑になるとパフォーマンスが急激に低下します。 これとは別に、Actor-Critic手法を用いたアプローチも存在します。 Q-Learningの代わりにPolicy Gradientを利用し、パラメータを拡張して適用する方法です。 この手法は IAC（Independent Actor-Critic）と呼ばれます。 また、Advantageの与え方によってIAC-QやIAC-Vに分けることもできます。
しかし、この手法も各エージェントが自身の部分観測情報だけで学習するため、性能はあまり良くありません。 このような課題を改善するために提案されたのが、COMAという手法です。
COMA（Counterfactual Multi-Agent Policy Gradients）
IQLやIACの状況を振り返ると、エージェントは部分観測しかできず、その情報を互いに共有しません。 このような環境において、すべての情報を収集し制御する機能の必要性が高まりました。 そこでCOMAでは、**中央集権的学習（Centralized Learning）**の手法を導入しています。 また、この環境ではチーム全体の報酬のみが与えられるため、各エージェントの行動を評価することが難しい問題があります。 そこで、**クレジットアサインメント（credit assignment）**を解決する方法が採用されています。 該当の論文は以下のリンクからご覧いただけます。
先に述べたIAC手法では、各エージェントがそれぞれActorとCriticを持っています。 これに対して、各エージェントのActorはそのままにし、Criticを1つに統合して、各エージェントのPolicyに対してAdvantageを付与します。以下のアーキテクチャ図はそれを反映したものです。
図を見ると、各エージェントのActorはそれぞれ自身の部分観測（O）に基づいて行動（action）を選択していることが分かります。 一方で、Criticは環境の状態情報（state）、報酬、各エージェントのPolicyおよび行動のすべての情報を受け取り、各エージェントにAdvantageを与えています。 この仕組みにより、各エージェントは部分観測しかできず、エージェント間の通信も不可能な状況でも、すべての情報を把握できるCriticの役割によって効率的な協調プレイが可能になるのです。
クレジットアサインメントの解決
ここからは、クレジットアサインメント問題を解決するためのAdvantage付与の過程について説明します。 クレジットアサインメント問題とは、エージェント個別に報酬を与えず、チーム単位でのみ報酬が与えられる場合に、各エージェントの実際の貢献度を評価する問題のことです。 これを解決するために、COMAではAdvantageを用いて対応しています。 一般的に強化学習でAdvantageを計算するには報酬情報が必要ですが、本環境ではチーム報酬のみが与えられるため、各エージェントのポリシーに対する報酬を直接測定できません。 そこで間接的に推定する手法が提案されており、以下の数式を見ると、状態(state)とジョイントアクション(joint-action)の報酬値（チーム報酬）から、対象エージェント自身のデフォルトアクションに基づく報酬値との差で推定していることが分かります。
以下の数式でAdvantageを定義します。
D^a = r(s, u) - r(s, (u^{-a}, c^a))
a : 特定のエージェント自身
−a : 自身を除く他のエージェント
u : ジョイントアクション（全エージェントの行動の組み合わせ）
𝑐^a : デフォルトアクション（対象エージェントの基準となる行動）
この方法の問題点は、自分の行動だけでなく他のエージェントの行動もすべて考慮して計算しなければならず、効率が悪いことです。 そこで、**カウンターファクチュアル（counterfactual）部分を利用して推定する手法が導入されました。 これがいわゆるカウンターファクチュアルベースライン（counterfactual baseline）**です。 この方法では、他のエージェントのジョイントアクションを固定した状態で、自分の行動に基づく価値を推論します。 この手法に基づいて各エージェントにAdvantageを付与する数式は以下の通りです。
A^a(s, u) = Q(s, u) - \sum_{u'^a} \pi^a(u'^a \mid \tau^a) Q(s, (u^{-a}, u'^a))
以下の数式を見ると、個別ではなくチーム全体の視点でのQ値から、他のエージェントのジョイントアクションを固定し、自身の行動に応じた場合を総合してAdvantageを算出していることがわかります。 しかし、この方法はディープラーニングのネットワークを用いると計算負荷が非常に高くなる可能性があります。 そこで、Critic Representationを導入しました。 これは、すべての情報をCriticに入力して近似的に算出する方法を意味します。 次のアーキテクチャ図がこれを説明しています。
これにより、計算負荷の効率化と各エージェントの役割に対する間接的な推論が可能となりました。
要約
これまで見てきた内容をまとめると、以下の通りです。 従来のIQLやIACの状況では、各エージェントが自身の部分的な情報しか参照できず、全体の情報を見ることができませんでした。 そのため、学習効率が低下していました。 そこで、全ての情報を参照できる中央Criticを導入し、各エージェントのポリシーに基づくAdvantageを付与する手法が提案されました。 このとき、チーム報酬のみが与えられる環境でAdvantageをどのように算出するかという問題から、**カウンターファクチュアル（counterfactual）**手法が導入されました。 さらに、より効率的な計算のために、カウンターファクチュアルベースライン（counterfactual baseline）とCritic Representationが採用されました。 このCOMA手法は、後に紹介される多くのMARLの基盤となるため、確実に習得しておくことが望ましいでしょう。
以下のリンクは、該当手法で学習させた結果の動画です。