【マルチエージェント強化学習】Joint Action Learners

今回はJoint Action Learners(JAL)と呼ばれるマルチエージェント強化学習手法を紹介します。

Joint Action Learners

JALはマルチエージェント強化学習の手法の中でも非常にシンプルなものになります。
Joint Actionとある通り、各エージェントはすべてのエージェントの行動を観測できます。
期待報酬値は\(Q(\textbf{a})\)といったようにすべてエージェントの行動を用います。
つまり以下のようになります。
$$
\begin{eqnarray}
Q_i(\textbf{a}) \leftarrow Q_i(\textbf{a}) + \alpha (r_i – Q_i(\textbf{a}))
\end{eqnarray}
$$

ちなみに\(\textbf{a}=\{ a_0,\cdots, a_N \}\)といったように全エージェントの行動の集合となります。

各エージェントは自分以外のエージェントの方策を過去の経験から推定します。
推定自体はシンプルで、エージェント\(i\)がエージェント\(j\)の方策\(\hat{\pi}_j(a)\)を推定する場合には以下のように推定します。

$$
\begin{eqnarray}
\hat{\pi}_j(a_j) = \frac{n(a_j)}{T}
\end{eqnarray}
$$
ここで、\(n(a_j)\)はエージェント\(j\)が行動\(a_j\)を選択した回数、
\(T\)は総行動回数を表しています。
単純に\(a_j\)の選択確率で方策を推定しています。

そして、各エージェントは、相手の推定方策と期待報酬値を用いて、
行動選択に用いる値\(EV\)を以下のように計算します。
今回は簡略化するためにエージェントが\(i, j\)の２体の問題とします。

$$
\begin{eqnarray}
EV(a_i) = \sum_{a_j \in A_j}\hat{\pi}_j(a_j) Q(a_i, a_j)
\end{eqnarray}
$$

各エージェントは、この$EV$を用いて行動選択を行います。
(例、\(\epsilon\) -greedyで言えば、\(\epsilon\)の確率でランダム、それ以外の場合\(a = arg max_{a_i} EV_i(a_i)\)の行動を行います。)

実験

今回以下のようなゼロサムゲームを用いて実験を行います。

各エージェントはAかBどちらか行動を選択し、
選択された行動に応じて報酬が得られます。

この問題では両エージェントの各行動の選択確率が0.5になった時がナッシュ均衡になります。
つまり、AとBをだいたい交互に出すような時にナッシュ均衡になります。

ソースコード

ソースコードはgithubにあげました。

GitHub – tocom242242/joint_action_learners_sample

ファイル構成は以下のようになります。

├── README.md
├── jal.py  # Joint Action Learner
├── policy
├── run.py  # 実験実行用ディレクトリ
└── simple_game.py # ゲームクラス

run.pyを実行すれば実験を行えます。

実験結果

上記のグラフは横軸がエピソード、
縦軸は各エージェントの２つの行動の選択優位度の差の絶対値\(|EV(a_1)-EV(a_2)|\)となります。
つまり、この値が０に近づく程、行動\(a_1 , a_2\)の選択確率が0.5ずつとなり、ナッシュ均衡となります。

グラフから両エージェントの\(|EV(a_1)-EV(a_2)|\)が0に近づているため、ゼロサムゲームではナッシュ均衡に収束していそうです。

今後

今後はJALをゼロサムゲーム以外でも実験してみます。