【マルチエージェント強化学習】Minimax Q Learning

今回はMinimax Q Learning というマルチエージェント強化学習のアルゴリズムについて紹介しようと思います。
Minimax Q Learningは一言で言ってしまえば、Q Learning とゲーム理論のMinimax戦略を組み合わせた手法になります。

前提知識として、Q Learningについては知っているとしています。
Q Learningについて知らない方は以下の記事を参考にしてもらえればと思います。

www.tcom242242.net

Minimax Q Learning

Minimax Q LearningはQ Learning とゲーム理論のMinimax戦略を組み合わせた手法であり、
ゼロサムゲームでは最適なQ値に収束することが証明されている手法です。

Minimax Q Learningを2体のエージェント(1, 2)の時で説明します。
Minimax Q LearningではJALsと同様に、自分以外エージェントの直近の行動を観測でき、 エージェント1の\(Q_1\)を以下のように更新します。

$$
\begin{aligned}
Q_1 (s, a_1, a_2) \leftarrow Q_1 (s, a_1, a_2) + \alpha (r + \gamma \color{red}{V_1(s’)} – Q_1 (s, a_1, a_2))
\end{aligned}
$$

\(a_1\)はエージェント1、\(a_2\)はエージェント2の行動を表してします。

Minimax Q Learningでは\(V_1(s’)\)にMixmax値を用いることが大きな特徴となります。 つまりエージェント1の\(V_1(s’)\)は以下のような式となり、線形計画法を用いて計算します。

$$
\begin{aligned}
V_1(s) = \underset{\pi_1 \in PD(A_1)}{max} \ \ \underset{a_2 \in A_2}{min} \sum_{a_1 \in A_1}\pi_1(s,a_1)Q_1(s, a_1, a_2)
\end{aligned}
$$

PD(A)は行動の集合Aに対する確率分布となります。

そして、エージェント1の戦略\(\pi_1\)も\(V(s)\)と同様にはMinimaxとなるように戦略を計算します。

$$
\begin{aligned}
\pi _1(s, \cdot) = \underset{\pi_1 \in PD(A_1)}{argmax}\ \ \underset{a_2 \in A_2}{min} \sum_{a_1 \in A_1}\pi_1(s,a_1)Q_1 (s, a_1, a_2)
\end{aligned}
$$

Minimax Q Learningはゼロサムゲームにおいて最適Q値に収束することが証明されています。
さらに探索率を0に近づけていけば最適方策に収束することが知られています。

アルゴリズム

アルゴリズムを以下に示します。

f:id:ttt242242:20190627170510j:plain

出典:Multiagent Reinforcement Learning for Multi-Robot Systems: A Survey

上記のアルゴリズムで注意する点は、\(V(s)\)を計算する前に、\(\pi\)をMinimax化するように線形計画法を用いて計算しているので、
\(V(s)\)については、事前に計算した\(\pi\)を用いることでもう一度線形計画法をしないですんでいます。

ちなみに線形計画法で解く時には最小化最大化問題として解きます。(これは自分用のメモ)

$$
\begin{aligned}
& \text{maxmize} && m \\ &\text{subject to} && \sum_{a_1 \in A_2}\pi(s, a_1)Q(s, a_1, a_2) \leq m && \forall a_2 \in A_2
\end{aligned}
$$

実験

最もシンプルな以下のようなゼロサムゲームを用いて実験します。

1,2 A B
A 1, -1 -1,1
B -1,1 1,-1

プログラム

プログラムはgithubにあげました。

github.com

以下ディレクトリ構成

run.py

run.pyを実行するれば、Minimax Q Learningの実験を開始します。

minimax_q_learner.py

Minimax Q Learning エージェントになります。

線形計画法を用いるのでPuLPを用いています。

policy.py

方策になります。\(\epsilon\)-greedyが記述してあります。

matrix_game.py

ゼロサムゲームが記述してあります。

結果

両エージェントがMinimax Q Learningにより行動選択をした時の方策の推移をプロットします。

f:id:ttt242242:20190627171621j:plain

横軸がエピソード(つまり、行動選択回数)、縦軸が確率を表しています。
それぞれのグラフは各エージェントの行動Aの方策\(\pi_1(A)\)(選択確率)をプロットしています。
ちなみに、行動はA, Bだけなので、行動Bの選択確率は\(\pi_1(B) = 1 – \pi_1(A)\)となります。
このゲームでは均衡解がお互いの行動A, Bの方策(選択確率)が0.5の時です。
グラフを見ると両エージェント共に0.5にきれいに収束していることがわかります。

参考文献

Markov games as a framework for multi-agent reinforcement learning

Multiagent Reinforcement Learning for Multi-Robot Systems: A Survey

コメント

タイトルとURLをコピーしました