機械学習、強化学習の調査録

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

【マルチエージェント強化学習】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を実行すれば実験が始まります。

├── 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()
実験結果

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

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