今回はマルチエージェント強化学習アルゴリズムの１つであるWoLF PHCについて紹介します。
Win or Learn Fast(WoLF)
まずWin or Learn Fast(WoLF)についてお話します。
WoLFはマルチエージェント強化学習における重要な学習原理です。
この原理は、名前にある通り、勝っている時(Win)はゆっくり学習。負けている時(Lose)は早く学習するといった原理(principle)です。
２つの学習率\(\delta_w, \delta_l (\delta_w > \delta_l)\)を用意します。勝っている時には\(\delta_w\)を用いて、負けている時は\(\delta_l\)用いて学習します。
ここで、言う勝つというのは、
現在の戦略（方策）\(\pi\)による期待報酬値が、ナッシュ均衡戦略をとった時の期待報酬値 を上回っていることをいいます。
この手法は2人2行動ゲームにおいて、各エージェントがWoLFを用いて利己的に学習する時に、ナッシュ均衡に収束することが
証明されています*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を適用します。
つまり、平均方策より現在の方策を用いた時の期待報酬が高ければ、ゆっくり学習し、
低ければ早く学習します。
以下にアルゴリズムを示します。
実験
問題設定
前回と同様にMatching Pennies を用いて実験します。
以下がMatching Penniesの利得表
| 1,2 | Heads | Tails |
|---|---|---|
| Heads | 1, -1 | -1,1 |
| Tails | -1,1 | 1,-1 |
ソースコード
ソースコードはgithubにあげました。
プログラムの構成は以下のようになっています。
run.pyを実行すれば実験が始まります。
├── matrix_game.py # Matching Pennies ├── run.py # 実験実行用プログラム └── wolf_agent.py # Win or Learn Fast Agent
wolf_agent.py
import numpy as np
class WoLFAgent():
"""
Policy hill-climbing algorithm(PHC)
http://www.cs.cmu.edu/~mmv/papers/01ijcai-mike.pdf
"""
def __init__(self, alpha=0.1, delta=0.0001, actions=None, high_delta=0.004, low_delta=0.002):
self.alpha = alpha
self.actions = actions
self.last_action_id = None
self.q_values = self._init_q_values()
self.pi = [(1.0/len(actions)) for idx in range(len(actions))]
self.pi_average = [(1.0/len(actions)) for idx in range(len(actions))]
self.high_delta = high_delta
self.row_delta = low_delta
self.pi_history = [self.pi[0]]
self.reward_history = []
self.conter = 0
def _init_q_values(self):
q_values = {}
q_values = np.repeat(0.0, len(self.actions))
return q_values
def act(self, q_values=None):
action_id = np.random.choice(np.arange(len(self.pi)), p=self.pi)
self.last_action_id = action_id
action = self.actions[action_id]
return action
def observe(self, reward):
self.reward_history.append(reward)
self.q_values[self.last_action_id] = ((1.0 - self.alpha) * self.q_values[self.last_action_id]) + (self.alpha * reward)
self._update_pi_average()
self._update_pi()
def _update_pi_average(self):
self.conter += 1
for aidx, _ in enumerate(self.pi):
self.pi_average[aidx] = self.pi_average[aidx] + (1/self.conter)*(self.pi[aidx]-self.pi_average[aidx])
if self.pi_average[aidx] > 1: self.pi_average[aidx] = 1
if self.pi_average[aidx] < 0: self.pi_average[aidx] = 0
def _update_pi(self):
delta = self.decide_delta()
max_action_id = np.argmax(self.q_values)
for aidx, _ in enumerate(self.pi):
if aidx == max_action_id:
update_amount = delta
else:
update_amount = ((-delta)/(len(self.actions)-1))
self.pi[aidx] = self.pi[aidx] + update_amount
if self.pi[aidx] > 1: self.pi[aidx] = 1
if self.pi[aidx] < 0: self.pi[aidx] = 0
self.pi_history.append(self.pi[0])
def decide_delta(self):
"""
comfirm win or lose
"""
expected_value = 0
expected_value_average = 0
for aidx, _ in enumerate(self.pi):
expected_value += self.pi[aidx]*self.q_values[aidx]
expected_value_average += self.pi_average[aidx]*self.q_values[aidx]
if expected_value > expected_value_average: # win
return self.row_delta
else: # lose
return self.high_delta
matrix_game.py
import numpy as np
class MatrixGame():
def __init__(self):
self.reward_matrix = self._create_reward_table()
def step(self, action1, action2):
r1, r2 = self.reward_matrix[action1][action2]
return None, r1, r2
def _create_reward_table(self):
reward_matrix = [
[[1, -1], [-1, 1]],
[[-1, 1], [1, -1]]
]
return reward_matrix
run.py
import numpy as np
import matplotlib.pyplot as plt
from wolf_agent import WoLFAgent
from matrix_game import MatrixGame
import pandas as pd
if __name__ == '__main__':
nb_episode = 1000
actions = np.arange(2)
agent1 = WoLFAgent(alpha=0.1, actions=actions, high_delta=0.0004, low_delta=0.0002)
agent2 = WoLFAgent(alpha=0.1, actions=actions, high_delta=0.0004, low_delta=0.0002)
game = MatrixGame()
for episode in range(nb_episode):
action1 = agent1.act()
action2 = agent2.act()
_, r1, r2 = game.step(action1, action2)
agent1.observe(reward=r1)
agent2.observe(reward=r2)
print(agent1.pi)
print(agent2.pi)
plt.plot(np.arange(len(agent1.pi_history)),agent1.pi_history, label="agent1's pi(0)")
plt.plot(np.arange(len(agent2.pi_history)),agent2.pi_history, label="agent2's pi(0)")
plt.ylim(0, 1)
plt.xlabel("episode")
plt.ylabel("pi(0)")
plt.legend()
plt.savefig("result.jpg")
plt.show()
実験結果
単純に何回か学習行動を行い、 方策が収束するかを見てみます。
PHCとは異なり、Headsを選択する確率が0.5で収束していることがわかります。
この問題でのナッシュ均衡方策は0.5なので、うまく学習できていることがわかります。
参考文献
Multiagent learning using a variable learning rate
Rational and Convergent Learning in Stochastic Games
コメント