今回はNash Q Learning(Nash Q学習)について紹介します。
背景
マルチエージェント強化学習では、ナッシュ均衡戦略が１つの目標となります。
各エージェントが単純に強化学習を行う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{aligned}
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{aligned}
$$
Nash Q Valueは以下のように計算します。
\begin{aligned}
NashQ_i(s’) = \pi_0(s’) \cdots \pi_n(s’) Q_i(s’)
\end{aligned}
$$
\(\pi_i\)はナッシュ均衡戦略となります。
各エージェントはこのナッシュ均衡戦略群\(\pi_0, \cdots, \pi_n\)を計算するために、
自分以外のエージェントのQ値も計算しなければなりません。
つまり、各エージェントは全エージェントの行動群\(a_0, \cdots, a_n\)と報酬群\(r_0, \cdots, r_n\)を観測して、
\(Q_0, \cdots, Q_n\)を計算する必要があります。
なので、エージェント数が増加すればするほど、メモリ量、計算量ともに増大していまいます。
また、ナッシュ均衡解は複数存在することがあるので、
どのナッシュ均衡解を選択するかも自分で決めなければなりません。
しかしながら、
この手法はナッシュ均衡解に収束することが証明されています。
(かなり厳しい条件の元でですが)
マルチエージェント強化学習アルゴリズムでナッシュ均衡戦略に収束することが証明されていることは、
非常に重要なので、この手法は広く研究されています。
証明に関しては参考文献の論文を参照していただければと思います。
アルゴリズム
アルゴリズムを以下に示します。
出典:http://www.jmlr.org/papers/volume4/hu03a/hu03a.pdf
実装と実験
ソースコード
実装したソースコードはgithubにあげました。
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によって学習した結果を以下に示します。
正しく学習できているようです。
今後の課題
今回はゼロサムゲームでのみNash Q Learningの性能を確認しました。
次はマルチなstateでの実験も行っていきます。
ゼロサムゲームでしか確認していないので、
もしバグや間違っている点があれば教えていただければと思います。
参考文献
Nash Q-Learning for General-Sum Stochastic Games
コメント