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

今回はNash Q Learning(Nash Q学習)について紹介します。

背景

マルチエージェント強化学習では、ナッシュ均衡戦略が1つの目標となります。
各エージェントが単純に強化学習を行うILsなどでは、ナッシュ均衡戦略への収束は保証されません。
そこで、ナッシュ均衡戦略への収束を目標としたNash Q Learningが提案されました。

Nash Q Learningとは

Nash Q Learningとは名前の通り、Q LearningとNash均衡戦略を組み合わせた手法になります。
Nash Q Learningでは以下の式のように、Nash Q ValueというNash均衡時の期待報酬値(\(NashQ_i(s’)\))を、Q値\(Q_i (s, a_0, \cdots, a_n)\)の更新時に用います。

$$
\begin{aligned}
Q_i (s, a_0, \cdots, a_n) = (1-\alpha )Q_i (s, a_0, \cdots, a_n) + \alpha (r_i + \gamma \color{red}{NashQ_i(s’)})
\end{aligned}
$$

Nash Q Valueは以下のように計算します。

$$
\begin{aligned}
NashQ_i(s’) = \pi_0(s’) \cdots \pi_n(s’) Q_i(s’)
\end{aligned}
$$

\(\pi_i\)はナッシュ均衡戦略となります。
各エージェントはこのナッシュ均衡戦略群\(\pi_0, \cdots, \pi_n\)を計算するために、
自分以外のエージェントのQ値も計算しなければなりません
つまり、各エージェントは全エージェントの行動群\(a_0, \cdots, a_n\)と報酬群\(r_0, \cdots, r_n\)を観測して、
\(Q_0, \cdots, Q_n\)を計算する必要があります。
なので、エージェント数が増加すればするほど、メモリ量、計算量ともに増大していまいます。

また、ナッシュ均衡解は複数存在することがあるので、
どのナッシュ均衡解を選択するかも自分で決めなければなりません。

しかしながら、
この手法はナッシュ均衡解に収束することが証明されています。
(かなり厳しい条件の元でですが)
マルチエージェント強化学習アルゴリズムでナッシュ均衡戦略に収束することが証明されていることは、
非常に重要なので、この手法は広く研究されています。
証明に関しては参考文献の論文を参照していただければと思います。

アルゴリズム

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

f:id:ttt242242:20190712144534j:plain

出典:http://www.jmlr.org/papers/volume4/hu03a/hu03a.pdf

実装と実験

ソースコード

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

github.com

python3で書かれています。
このコードは2体エージェント用になります。

ディレクトリ構成は以下のようになります。

nash_q_learner.py

Nash Q Learning のソースコードです。

compute_piメソッド内で、Nash 均衡戦略を計算しています。
ここでは、Nashpyというライブラリを用いてナッシュ均衡戦略を計算しています。

matrix_game.py

policy.py

方策のコードです。\(\epsilon\)-greedyが実装されています。

run.py

実験実行用のプログラムです。

実験

以下のようなゼロサムゲーム実験してみます。

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

ナッシュ均衡戦略は各行動の選択確率が0.5となるときです。
Nash Q Learningによって学習した結果を以下に示します。

f:id:ttt242242:20190712145448j:plain

正しく学習できているようです。

今後の課題

今回はゼロサムゲームでのみNash Q Learningの性能を確認しました。

次はマルチなstateでの実験も行っていきます。

ゼロサムゲームでしか確認していないので、
もしバグや間違っている点があれば教えていただければと思います。

参考文献

Nash Q-Learning for General-Sum Stochastic Games

コメント

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