日本オペレーションズ・リサーチ学会
2021年 秋季研究発表会

2-C-11

見間違えのある繰り返しゲームのための Actor-Critic 型強化学習

050004931.

電気通信大学*坂本 充生SAKAMOTO Mitsuki

株式会社サイバーエージェント

阿部 拳之

ABE Kenshi

電気通信大学岩崎 敦

IWASAKI Atsushi

はじめに

表 1: 囚人のジレンマ (g > 0，l > 0，および |g − l| < 1)

人がどう協力するかの仕組みは人工知能，経済学，生物学等における学際的な研究課題である．見間違えの

a2 = Ca2 = Dある（不完全観測下の）無限回繰り返しゲームおいて

a1 = C1, 1−l, 1 + g

どのような振る舞い (戦略) が均衡になるかは十分にわ

a1 = D

1 + g, −l0, 0

かっていない．戦略空間を有限状態機械に限定すると，見間違えが起きても協力状態を回復しやすいシンプル

レイヤも他のプレイヤが選択した (または選択しなかっな戦略が生き残ることが知られているが，複雑な戦略た) 行動を正確には分からないと仮定する．これに合を含めた分析はまだまだ困難である [5]．そこで，個々わせて各期の “実現利得 (realized payoff)” をプレイヤのエージェントが強化学習にしたがうダイナミクスが， i の行動 ai とシグナル ωi から決定する．具体的には∑
gi (a) = w∈Ω2 ri (ai , ωi )o(w | a) を満たす ri (ai , ωi )どんな振る舞いを学習するか吟味する．
本研究では，見間違えのある繰り返し囚人のジレンマとする．というマルチエージェント系の上に，学習アルゴリズム

次にシグナル分布 o(w | a) で規定する，プレイヤ 2を表現する枠組みを定義する．既存手法として，Actor-の行動に関するプレイヤ 1 のノイズを含む観測をプレCritic 型強化学習の１つである q-based Policy Gradientイヤ 1 の私的シグナルとし，ω ∈ {g, b} (good, bad) と(QPG) [2] と Neural Replicator Dynamics (NeuRD) [1] をする．正しい観測ではプレイヤ 2 が C を選択した際の扱う．これらに対して突然変異付きレプリケータダイナ

プレイヤ 1 の私的シグナルは g, D を選択した際は b とミクスに着想したアルゴリズムである Neural Replicator-なる. これはプレイヤ 2 についても同様である．

Mutator Dynamics (NeuRMD) を提案する．３つの手法

3. マルチエージェント強化学習

それぞれでエージェントがどんな振る舞いを学習するか吟味した結果，NeuRMD がもっとも高い利得を実現する方策を学習しやすいことがわかった．さらにその方策は Win-Stay, Lose-Shift (WSLS, 図 2) という均衡戦略に相当することもわかった．

2.

強化学習は，エージェントが試行錯誤により適切な振る舞い (方策) を学習する．エージェントはある時刻t において状態 st ∈ S を観測する．次に行動 at ∈ A を方策 π : s → ∆A に従い決定する．行動に応じて，報酬 rt ∈ R と新たな状態 st+1 を受け取る．

モデル

エージェントが観測する状態は，過去 1 期の履歴に

本章では文献 [4] にもとづいて, 2 人私的観測付き無限定し，S = {∅, Cg, Cb, Dg, Db} とする．ここで ∅ は限回繰り返しゲームをモデル化する. ここでプレイヤゲームの始まりにおける状態を指す．また報酬から相手i ∈ {1, 2} は成分ゲームを無限期間 t = 0, 1, 2, … に渡っの行動を推定させないため，報酬 r には実現利得 r(a, ω)て繰り返す. 各期においてプレイヤ i は有限集合 A かを与える．無限回繰り返しゲームでは，割引因子 δ がら行動 ai を選択し, その行動の組を a = (a1 , a2 ) ∈ A

定める確率で次もゲームが継続するかを定める．

2とする. 次に, プレイヤ i は a に関する私的なシグナル

ωi ∈ Ω を観測する. w をシグナルの組 (ω1 , ω2 ) ∈ Ω2 とする. また, プレイヤが a を選択したとき w が生起する
同時確率を o(w | a) とし, この同時確率を与える分布

表形式で方策関数を表現する Actor-Critic 法では，Critic が各 (s, a) に対するアドバンテージ
Aπ (s, a) = Qπ (s, a) −∑′π′a′ π(a |s)Q (s, a )のことをシグナル分布と呼ぶ. プレイヤ i の利得は gi (·)

を 用 い て 現 在 の 方 策 を 評 価 し ，そ こ か ら Ac-の値は表 1 によって定められた値に従う．
このとき，有限集合 Ω に対する oi (ωi | a) を Ω の限

tor が 方 策 を 更 新 す る ．た だ し ，Qπ (s, a)=][∑∞ k−tEπδr|s=sとする．また表形式
でk tk=t

界分布 (marginal distribution) とする．加えて，どのプは ロ ジット y を 方 策 の パ ラ メ ー タ θ に よって ，gPgbbR

図 2: 状態 P からスタートする WSLS
ゲームの終了までを 1 エピソードとして，500,000 エピソード学習し，ランダムシードを変えながら行った 30試行を評価する．
図 1 に各手法の平均報酬値の推移を示す．平均報酬値は，そのエピソードの 2 体の 1 ゲームあたりの平均

図 1: 2 体の平均獲得報酬の推移報酬値とした．縦軸は平均報酬値，横軸はエピソード数

y = (θ(s, a))s∈S,a∈A のように表現し，ロジット y かに対応し，区間数 10 の移動平均と信頼区間をプロット

らソフトマックス関数で各状態でどの行動をとるかをした．最終的な平均獲得報酬は，QPG が 0.014, NeuRD規定する:が 0.16，NeuRMD が 0.67 となり，NeuRMD が従来手法よりかなり高い報酬を与える方策を学習した．

exp (y(s, a))π(a|s) = ∑′ .
a′ ∈A exp (y(s, a ))こ の 実 験 で NeuRMD が 獲 得 し た 方 策 の 多 く はπ(C|∅)，π(C|Cb) と π(C|Dg) が 0.01，π(C|Cg) とそれぞれの手法でロジット y をどのように更新するかを概説する．まず，QPG ではπ(C|Db) が 0.99 でとなっていた．興味深いことにこれは状態 P からスタートする WSLS とほぼ一致する

yt+1 (s, a) = yt (s, a) + dπ (s)ηπ(a|s)Aπ (s, a)(1)πにしたがって更新する．ここで，η は学習率，d (s) =∑∞Eπ [ t=0 δ t P (st = s|s0 , π)] は期待割引累積訪問数とす(図 2)．WSLS は見間違えのある環境で最も高い利得を実現する均衡戦略として知られている [5]．このことから NeuRMD が非自明な協力的均衡戦略を従来手法より安定的に学習することを実験的に示せた．

る．次に NeuRD [1] では

yt+1 (s, a) = yt (s, a) + dπ (s)ηAπ (s, a)

(2)

参考文献
[1] D. Hennes, D. Morrill, S. Omidshaﬁei, R. Munos,にしたがって更新する．これは QPG とは独立にレプリ

J. Perolat, et al. Neural replicator dynamics: Multia-ケータダイナミクスからロジットの更新式 1 を導いて

gent learning via hedging policy gradients. In AAMAS,いる．最後に提案手法である NeuRMD では

pp. 492–501, 2020.

}
1u[2] S. Srinivasan, M. Lanctot, V. Zambaldi, J. Pérolat,(− π(a|s))
yt+1 (s, a) = yt (s, a) + η Aπ (s, a) +π(a|s) |A|
K. Tuyls, R. Munos, and M. Bowling. Actor-critic{にしたがって更新する．ここで，u は突然変異率とする．これは突然変異付きレプリケータダイナミクス [3]policy optimization in partially observable multiagent
environments. In NIPS, pp. 3426–3439, 2018.

から，NeuRD と同じようにロジットの更新式 2 を導い[3] B. Zagorsky, J. Reiter, K. Chatterjee, and M. Nowak.ている．また，突然変異項を追加するだけでなく，期Forgiver triumphs in alternating prisoner’s dilemma.

待割引累積訪問数を取り除くことで相互協力状態を学

PLOS ONE, pp. 1–8, 2013.

習しやすいようにしている．

4.

計算機実験
本節では，囚人のジレンマの利得パラメータを g =0.1, l = 0.1，割引因子 δ = 0.9，シグナル分布のパラ[4] ヨンジュン, 岩崎, 神取, 小原, 横尾. 部分観測可能マ
ルコフ決定過程を用いた私的観測付き繰り返しゲー
ムにおける均衡分析プログラム. 情報処理学会論文誌, pp. 1234–1246, 2012.

[5] 西野上, 五十嵐, 岩崎. 私的観測下の繰り返し囚人のジレンマにおける協力のダイナミクス. 第 19 回情率 α = 0.1, 方策の学習率 η = 0.02, 割引率 γ = 0.9，
報科学技術フォーラム, 2020.
NeuRMD の突然変異確率は µ = 0.01 とする．δ によるメータは p = 0.95, q = 0.01，アドバンテージの学習