今回はMinimax Q Learning というマルチエージェント強化学習のアルゴリズムについて紹介しようと思います。
Minimax Q Learningは一言で言ってしまえば、Q Learning とゲーム理論のMinimax戦略を組み合わせた手法になります。
前提知識として、Q Learningについては知っているとしています。
Q Learningについて知らない方は以下の記事を参考にしてもらえればと思います。
Minimax Q Learning
Minimax Q LearningはQ Learning とゲーム理論のMinimax戦略を組み合わせた手法であり、
ゼロサムゲームでは最適なQ値に収束することが証明されている手法です。
Minimax Q Learningを2体のエージェント(1, 2)の時で説明します。
Minimax Q LearningではJALsと同様に、自分以外エージェントの直近の行動を観測でき、 エージェント1の\(Q_1\)を以下のように更新します。
\begin{aligned}
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{aligned}
$$
\(a_1\)はエージェント1、\(a_2\)はエージェント2の行動を表してします。
Minimax Q Learningでは\(V_1(s’)\)にMixmax値を用いることが大きな特徴となります。 つまりエージェント1の\(V_1(s’)\)は以下のような式となり、線形計画法を用いて計算します。
\begin{aligned}
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{aligned}
$$
PD(A)は行動の集合Aに対する確率分布となります。
そして、エージェント1の戦略\(\pi_1\)も\(V(s)\)と同様にはMinimaxとなるように戦略を計算します。
\begin{aligned}
\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{aligned}
$$
Minimax Q Learningはゼロサムゲームにおいて最適Q値に収束することが証明されています。
さらに探索率を０に近づけていけば最適方策に収束することが知られています。
アルゴリズム
アルゴリズムを以下に示します。
出典: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にあげました。
以下ディレクトリ構成
├── 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により行動選択をした時の方策の推移をプロットします。
横軸がエピソード（つまり、行動選択回数）、縦軸が確率を表しています。
それぞれのグラフは各エージェントの行動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
コメント