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

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

MENU

【マルチエージェント強化学習】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{eqnarray} 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{eqnarray} $$

Nash Q Valueは以下のように計算します。 $$ \begin{eqnarray} NashQ_i(s') = \pi_0(s') \cdots \pi_n(s') Q_i(s') \end{eqnarray} $$

$\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体エージェント用になります。

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

.
├── matrix_game.py    
├── nash_q_learner.py # Nash Q Learning 
├── policy.py         # epsilon-greedy
└── run.py            # 実験実行用プログラム
nash_q_learner.py

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

import numpy as np
import nashpy

class NashQLearner():
    def __init__(self, 
                 alpha=0.1, 
                 policy=None, 
                 gamma=0.99, 
                 ini_state="nonstate", 
                 actions=None):

        self.alpha = alpha
        self.gamma = gamma
        self.policy = policy
        self.actions = actions
        self.state = ini_state

        # q values (my and opponent)
        self.q, self.q_o = {}, {}
        self.q[ini_state] = {}
        self.q_o[ini_state] = {}

        # nash q value
        self.nashq = {}
        self.nashq[ini_state] = 0

        # pi (my and opponent)
        self.pi, self.pi_o = {}, {}
        self.pi[ini_state] = np.repeat(1.0/len(self.actions), len(self.actions))
        self.pi_o[ini_state] = np.repeat(1.0/len(self.actions), len(self.actions))

        self.previous_action = None
        self.reward_history = []
        self.pi_history = []

    def act(self, training=True):
        if training:
            action_id = self.policy.select_action(self.pi[self.state])
            action = self.actions[action_id]
            self.previous_action = action
        else:
            action_id = self.policy.select_greedy_action(self.pi)
            action = self.actions[action_id]

        return action

    def observe(self, state="nonstate", reward=None, reward_o=None, opponent_action=None, is_learn=True):
        if is_learn:
            self.check_new_state(state)
            self.learn(state, reward, reward_o, opponent_action)

    def learn(self, state, reward, reward_o, opponent_action):
        self.reward_history.append(reward)
        self.q[state][(self.previous_action, opponent_action)] = self.compute_q(state, reward, opponent_action, self.q)
        self.q_o[state][(self.previous_action, opponent_action)] = self.compute_q(state, reward_o, opponent_action, self.q_o)

        self.pi[state],self.pi_o[state] = self.compute_pi(state)
        self.nashq[state] = self.compute_nashq(state)

        self.pi_history.append(self.pi[state][0])

    def compute_q(self, state, reward, opponent_action, q):
        if (self.previous_action, opponent_action) not in q[state].keys():
            q[state][(self.previous_action, opponent_action)] = 0.0
        q_old = q[state][(self.previous_action, opponent_action)]
        updated_q = q_old + (self.alpha * (reward+ self.gamma*self.nashq[state]- q_old))

        return updated_q

    def compute_nashq(self, state):
        nashq = 0
        for action1 in self.actions:
            for action2 in self.actions:
                nashq += self.pi[state][action1]*self.pi_o[state][action2] * self.q[state][(action1, action2)]

        return nashq

    def compute_pi(self, state):
        """
            compute pi (nash)
        """
        q_1, q_2 = [], []
        for action1 in self.actions:
            row_q_1, row_q_2 = [], []
            for action2 in self.actions:
                joint_action = (action1, action2)
                row_q_1.append(self.q[state][joint_action])
                row_q_2.append(self.q_o[state][joint_action])
            q_1.append(row_q_1)
            q_2.append(row_q_2)

        game = nashpy.Game(q_1, q_2)
        equilibria = game.support_enumeration()
        pi = []
        for eq in equilibria:
            pi.append(eq)

        return pi[0][0], pi[0][1]

    def check_new_state(self, state):
        if state not in self.q.keys():
            self.q[state] = {}
            self.q_o[state] = {}
        for action1 in self.actions:
            for action2 in self.actions:
                if state not in self.pi.keys():
                    self.pi[state] = np.repeat(1.0/len(self.actions), len(self.actions))
                    self.v[state] = np.random.random()
                if (action1, action2) not in self.q[state].keys():
                    self.q[state][(action1, action2)] = np.random.random()
                    self.q_o[state][(action1, action2)] = np.random.random()

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

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 = self.reward_matrix[0][action1][action2]
        r2 = self.reward_matrix[1][action1][action2]

        return None, r1, r2

    def _create_reward_table(self):
        reward_matrix = [
                            [[1, -1], [-1, 1]],
                            [[-1, 1], [1, -1]]
                        ]

        return reward_matrix
policy.py

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

import copy
import numpy as np

class EpsGreedyQPolicy():
    def __init__(self, epsilon=.1, decay_rate=1):
        self.epsilon = epsilon
        self.decay_rate = decay_rate

    def select_action(self, q_values):
        assert q_values.ndim == 1
        nb_actions = q_values.shape[0]

        if np.random.uniform() < self.epsilon:  
            action = np.random.random_integers(0, nb_actions-1)
        else:
            action = np.argmax(q_values)

        return action

    def select_greedy_action(self, q_values):
        assert q_values.ndim == 1
        nb_actions = q_values.shape[0]
        action = np.argmax(q_values)

        return action
run.py

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

import numpy as np
import matplotlib.pyplot as plt
from nash_q_learner import NashQLearner 
from policy import EpsGreedyQPolicy
from matrix_game import MatrixGame

if __name__ == '__main__':
    nb_episode = 1000

    agent1 = NashQLearner(alpha=0.1, policy=EpsGreedyQPolicy(), actions=np.arange(2))
    agent2 = NashQLearner(alpha=0.1, policy=EpsGreedyQPolicy(), actions=np.arange(2))

    game = MatrixGame()
    for episode in range(nb_episode):
        action1 = agent1.act()
        action2 = agent2.act()

        _, r1, r2 = game.step(action1, action2)

        agent1.observe(reward=r1, reward_o=r2, opponent_action=agent2.previous_action)
        agent2.observe(reward=r2, reward_o=r1, opponent_action=agent1.previous_action)

    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.xlabel("episode")
    plt.ylabel("pi(0)")
    plt.legend()
    plt.savefig("result.jpg")
    plt.show()

実験

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

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