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

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

MENU

【マルチエージェント強化学習】Minimax Q Learning

今回はMinimax Q Learning というマルチエージェント強化学習アルゴリズムについて紹介しようと思います。
Minimax Q Learningは一言で言ってしまえば、Q Learning とゲーム理論のMinimax戦略を組み合わせた手法になります。

前提知識として、Q Learningについては知っているとしています。
Q Learningについて知らない方は以下の記事を参考にしてもらえればと思います。

www.tcom242242.net

Minimax Q Learning

Minimax Q LearningはQ Learning とゲーム理論のMinimax戦略を組み合わせた手法であり、
ゼロサムゲームでは最適なQ値に収束することが証明されている手法です。

Minimax Q Learningを2体のエージェント(1, 2)の時で説明します。
Minimax Q LearningではJALsと同様に、自分以外エージェントの直近の行動を観測でき、 エージェント1の$Q_1$を以下のように更新します。

$$ \begin{eqnarray} Q_1 (s, a_1, a_2) \leftarrow Q_1 (s, a_1, a_2) + \alpha (r + \gamma \color{red}{V_1(s')} - Q_1 (s, a_1, a_2)) \end{eqnarray} $$

$a_1$はエージェント1、$a_2$はエージェント2の行動を表してします。

Minimax Q Learningでは$V_1(s')$にMixmax値を用いることが大きな特徴となります。 つまりエージェント1の$V_1(s')$は以下のような式となり、線形計画法を用いて計算します。 $$ \begin{eqnarray} V_1(s) = \underset{\pi_1 \in PD(A_1)}{max}\ \ \underset{a_2 \in A_2}{min} \sum_{a_1 \in A_1}\pi_1(s,a_1)Q_1(s, a_1, a_2) \end{eqnarray} $$ PD(A)は行動の集合Aに対する確率分布となります。

そして、エージェント1の戦略$\pi _1$も$V(s)$と同様にはMinimaxとなるように戦略を計算します。 $$ \begin{eqnarray} \pi _1(s, \cdot) = \underset{\pi_1 \in PD(A_1)}{argmax}\ \ \underset{a_2 \in A_2}{min} \sum_{a_1 \in A_1}\pi_1(s,a_1)Q_1 (s, a_1, a_2) \end{eqnarray} $$

Minimax Q Learningはゼロサムゲームにおいて最適Q値に収束することが証明されています。
さらに探索率を0に近づけていけば最適方策に収束することが知られています。

アルゴリズム

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

f:id:ttt242242:20190627170510j:plain

出典:Multiagent Reinforcement Learning for Multi-Robot Systems: A Survey

上記のアルゴリズムで注意する点は、$V(s)$を計算する前に、$\pi$をMinimax化するように線形計画法を用いて計算しているので、
$V(s)$については、事前に計算した$\pi$を用いることでもう一度線形計画法をしないですんでいます。

ちなみに線形計画法で解く時には最小化最大化問題として解きます。(これは自分用のメモ)

$$ \begin{aligned} & \text{maxmize} && m \\ &\text{subject to} && \sum_{a_1 \in A_2}\pi(s, a_1)Q(s, a_1, a_2) \leq m && \forall a_2 \in A_2 \end{aligned} $$

実験

最もシンプルな以下のようなゼロサムゲームを用いて実験します。

1,2 A B
A 1, -1 -1,1
B -1,1 1,-1

プログラム

プログラムはgithubにあげました。

github.com

以下ディレクトリ構成

├── matrix_game.py
├── minimax_q_learner.py
├── policy.py
└── run.py
run.py

run.pyを実行するれば、Minimax Q Learningの実験を開始します。

import numpy as np
import matplotlib.pyplot as plt
from minimax_q_learner import MiniMaxQLearner 
from policy import EpsGreedyQPolicy
from matrix_game import MatrixGame

if __name__ == '__main__':
    nb_episode = 100

    agent1 = MiniMaxQLearner(aid=0, alpha=0.1, policy=EpsGreedyQPolicy(), actions=np.arange(2))  # agentの設定
    agent2 = MiniMaxQLearner(aid=1, alpha=0.1, policy=EpsGreedyQPolicy(), actions=np.arange(2))  # agentの設定

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

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

        agent1.observe(reward=r1, opponent_action=agent2.previous_action)
        agent2.observe(reward=r2, opponent_action=agent1.previous_action)
    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()
minimax_q_learner.py

Minimax Q Learning エージェントになります。

線形計画法を用いるのでPuLPを用いています。

import numpy as np
import pulp
import sys

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

        self.aid = aid
        self.alpha = alpha
        self.gamma = gamma
        self.policy = policy
        self.actions = actions
        self.state = ini_state
        self.q = {}
        self.q[ini_state] = {}
        self.pi = {}
        self.pi[ini_state] = np.repeat(1.0/len(self.actions), len(self.actions))
        self.v = {}

        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, opponent_action=None, is_learn=True):
        if is_learn:
            self.check_new_state(state)
            self.learn(state, reward, opponent_action)

    def learn(self, state, reward, opponent_action):
        self.reward_history.append(reward)
        self.q[state][(self.previous_action, opponent_action)] = self.compute_q(state, reward, opponent_action)
        self.pi[state][0],self.pi[state][1] = self.compute_pi()
        self.v[state] = self.compute_v(state)

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

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

        return updated_q

    def compute_v(self, state):
        min_expected_value = sys.maxsize
        for action2 in self.actions:
            expected_value = sum([self.pi[state][action1]*self.q[state][(action1, action2)] for action1 in self.actions])
            if expected_value < min_expected_value:
                min_expected_value = expected_value

        return min_expected_value

    def compute_pi(self):
        pi = pulp.LpVariable.dicts("pi",range(2), 0, 1)
        max_min_value = pulp.LpVariable("max_min_value")
        lp_prob = pulp.LpProblem("Maxmin Problem", pulp.LpMaximize)
        lp_prob += (max_min_value, "Objective")

        lp_prob += (pi[0]+pi[1] == 1)
        for action2 in self.actions:
            label = "{}".format(action2)
            values = pulp.lpSum([pi[idx] * self.q[self.state][(action1, action2)] for idx, action1 in enumerate(self.actions)])
            conditon = max_min_value <= values
            lp_prob += conditon

        lp_prob.solve()

        return pi[0].value(), pi[1].value()

    def check_new_state(self, state):
        if state not in self.q.keys():
            self.q[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()
policy.py

方策になります。$\epsilon$-greedyが記述してあります。

import copy
import numpy as np
from abc import ABCMeta, abstractmethod

class Policy(metaclass=ABCMeta):

    @abstractmethod
    def select_action(self, **kwargs):
        pass

class EpsGreedyQPolicy(Policy):
    """
        ε-greedy選択 
    """
    def __init__(self, epsilon=.1, decay_rate=1):
        super(EpsGreedyQPolicy, self).__init__()
        self.epsilon = epsilon
        self.decay_rate = decay_rate
        self.name = "epsilon-greedy"

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

        if np.random.uniform() < self.epsilon:  # random行動
            action = np.random.random_integers(0, nb_actions-1)
        else:   # greedy 行動
            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
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

結果

両エージェントがMinimax Q Learningにより行動選択をした時の方策の推移をプロットします。

f:id:ttt242242:20190627171621j:plain

横軸がエピソード(つまり、行動選択回数)、縦軸が確率を表しています。
それぞれのグラフは各エージェントの行動Aの方策$\pi_1(A)$(選択確率)をプロットしています。
ちなみに、行動はA, Bだけなので、行動Bの選択確率は$\pi_1(B) = 1 - \pi_1(A)$となります。
このゲームでは均衡解がお互いの行動A, Bの方策(選択確率)が0.5の時です。
グラフを見ると両エージェント共に0.5にきれいに収束していることがわかります。

参考文献

Markov games as a framework for multi-agent reinforcement learning

Multiagent Reinforcement Learning for Multi-Robot Systems: A Survey

強化学習 (機械学習プロフェッショナルシリーズ)

強化学習 (機械学習プロフェッショナルシリーズ)