強化学習、マルチエージェント強化学習、その他機械学習全般

機械学習関連のことをまとめていきます。強化学習関連が多いかもしれません

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

Win or Learn Fast

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

この手法は2人2行動ゲームにおいて、ナッシュ均衡に収束することが

証明されていることから、マルチエージェント強化学習では、重要な原理の1つになっています。

この原理自体は、

名前にある通り、勝つかもしくは早く学習 するといった原理(principle)です。

もう少し具体的にいうと、勝っている時は、ゆっくり学習。負けている時は早く学習するということです。

ここで、言う勝つというのは、

証明が行われた2人2行動ゲームでは、ナッシュ均衡方策をとった時の期待値に、

現在の方策による期待報酬値が上回っていることをいいます。

不思議なことに、この方策を用いることで、

ナッシュ均衡戦略に収束することが証明されています。*1

WoLF-PHC

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

www.tcom242242.net

WoLF-PHCでは、PHCアルゴリズムの方策を更新する速度を

WoLFの原理を用いて、調整します。

この時に勝つをどのように定義するかがポイントです。

通常のマルチエージェント強化学習では、

各エージェントが独立で学習している場合には、

WoLF-IGAを証明したときのように、

各エージェントがナッシュ均衡方策を知る(or 計算する)ことは基本的には不可能なので、

別の方策を用いる必要があります。

WoLF-PHCでは、平均方策ナッシュ均衡方策の代わりに用いています。

平均方策 は現在の方策に追従していくように、更新していくのですが、

更新していく毎に、更新幅が小さくなっていきます。

つまり最終的には、収束させます。

そのため、環境が動的に変化する場合などには、

単純にこの平均方策ではいけません。

ちなみに、なぜ、この方策で良いのかは実は僕はちょっとわかっていません・・・

(これは平均なの?)

まぁアルゴリズム的には、非常にシンプルです。

アルゴリズム

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.com

実験結果

単純に何回か学習行動を行い、

方策が収束するかを見てみます。

f:id:ttt242242:20180711193657p:plain

前回と異なり、Headsを選択する確率が0.5で収束していることがわかります。

さらに平均報酬も見てみます。

agent0s average reward:0.0007
agent1s average reward:-0.0007

お互いに同じぐらいの報酬になっていることがわかります。

うまく均衡戦略を得ることができています。

参考文献

Multiagent learning using a variable learning rate

Rational and Convergent Learning in Stochastic Games