【マルチエージェント強化学習】Win or Learn Fast-PHC

今回はマルチエージェント強化学習アルゴリズムの1つであるWoLF PHCについて紹介します。

Win or Learn Fast(WoLF)

まずWin or Learn Fast(WoLF)についてお話します。
WoLFはマルチエージェント強化学習における重要な学習原理です。

この原理は、名前にある通り、勝っている時(Win)はゆっくり学習。負けている時(Lose)は早く学習するといった原理(principle)です。
2つの学習率\(\delta_w, \delta_l (\delta_w > \delta_l)\)を用意します。勝っている時には\(\delta_w\)を用いて、負けている時は\(\delta_l\)用いて学習します。

ここで、言う勝つというのは、
現在の戦略(方策)\(\pi\)による期待報酬値が、ナッシュ均衡戦略をとった時の期待報酬値 を上回っていることをいいます。

この手法は2人2行動ゲームにおいて、各エージェントがWoLFを用いて利己的に学習する時に、ナッシュ均衡に収束することが
証明されています*1。そのため、マルチエージェント強化学習では重要な原理の1つになっています。

WoLF-PHC

WoLF-PHCとは、前回紹介したPolicy Hill Climbing アルゴリズムにWoLFの原理を適用したものになります。*2

Policy Hill ClimbingはQ Learning のQ値を用いて、方策を修正していく手法です。
www.tcom242242.net

WoLF-PHCでは、PHCアルゴリズムの方策を更新する速度を、WoLFの原理を用いて調整します。

この時に勝つをどのように定義するかがポイントです。 通常のマルチエージェント強化学習で、各エージェントが各々の行動や状態を観測できない場合には、
各エージェントがナッシュ均衡戦略を知る(or 計算する)ことは基本的には不可能です。
そのため、ナッシュ均衡方策以外の方策を用いてWoLFの原理を適用しなければなりません。

WoLF-PHCでは、平均方策 をナッシュ均衡方策の代わりに用いています。 この平均方策というのは単純にこれまでの方策の平均です。

この平均方策より現在の方策を用いた時の期待報酬が高ければWin、
低ければLoseとして、WoLFを適用
します。
つまり、平均方策より現在の方策を用いた時の期待報酬が高ければ、ゆっくり学習し、
低ければ早く学習します。

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

f:id:ttt242242:20180716182026j:plain

実験

問題設定

前回と同様にMatching Pennies を用いて実験します。

以下がMatching Penniesの利得表

1,2 Heads Tails
Heads 1, -1 -1,1
Tails -1,1 1,-1

ソースコード

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

GitHub - tocom242242/wolf_phc

プログラムの構成は以下のようになっています。
run.pyを実行すれば実験が始まります。

wolf_agent.py

matrix_game.py

run.py

実験結果

単純に何回か学習行動を行い、 方策が収束するかを見てみます。

f:id:ttt242242:20180711193657p:plain

PHCとは異なり、Headsを選択する確率が0.5で収束していることがわかります。
この問題でのナッシュ均衡方策は0.5なので、うまく学習できていることがわかります。

参考文献

Multiagent learning using a variable learning rate

Rational and Convergent Learning in Stochastic Games

コメント

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