FIT2021（第 20 回情報科学技術フォーラム）CF-002

見間違えのある繰り返し囚人のジレンマにおける
方策勾配法に関する研究

Policy Gradients in Prisoner’s Dilemma with Noisy Observations
坂本 充生 *

阿部 拳之 †

岩崎 敦 ∗

Mitsuki Sakamoto

Kenshi Abe

Atsushi Iwasaki

プレイヤが相手の行動について観測したシグナルと異なるシ

概要

グナルを他のプレイヤが観測しているかもしれないと仮定し本論文は見間違えのある繰り返し囚人のジレンマにおいて，ている．不完全観測付き無限回繰り返しゲームおいてどのよ

均衡戦略に相当する方策を学習する手法を提案し，従来の方

うな振る舞い (戦略) が最適なのかについては，ゲーム理論に

策勾配法などと比較，評価する．人がどのようにして協力すおける代表的なゲームである囚人のジレンマの例でさえ十分るのかは人工知能や経済学，生物学における基本的な問題でにわかっていない．例えば，部分観測可能マルコフ決定過程ある．一般には，見間違えのある繰り返し囚人のジレンマの(Partially Observable Markov Decision Process, POMDP) を用

均衡計算は非常に難しい問題であることが知られている．実

いて均衡を計算する手法 [21] が知られているが，その計算量

際，見間違えの下では，従来よく知られているしっぺ返し戦略

は一般には決定不能とされている．

でも，どちらかがいったん裏切ると，協力状態に戻るのは難し

POMDP に比べて高速に計算できる手法として，試行錯誤かくなる．そこで本研究では，試行錯誤から報酬の高い方策をら報酬の高い方策を学習する強化学習がある．しかし，マルチ学習する強化学習的な手法が厳密な均衡ソルバの代わりに機エージェント系における，その帰結は収束するか否かや収束す能するかを吟味する．そこで，本論文では突然変異付きレプるとしても均衡に到達するかどうかはよくわかっていないこ

リケータダイナミクスの仕組みを利用した Neural Replicator-とが多い．また，そのほとんどが完全観測のケースであり，常Mutator Dynamics (NeuRMD) を提案する．NeuRMD は方策に裏切るような戦略しか学習できないことが多い [17, 4]．も勾配法と似た方法で導出できるシンプルな学習アルゴリズム

う１つの手法として，レプリケータダイナミクス [16, 7] があである．計算実験の結果，シンプルだが非自明な均衡戦略でる．これは，進化ゲーム理論でよく用いられるダイナミクス

ある Win-Stay，Lose-Shift に相当する方策を安定的に学習すの１つであり，頻度依存淘汰モデルを用いて最適な戦略を探ることがわかった．

る．この手法では，利得が高くなる戦略をとるプレイヤの人

1 はじめにて代わられてやがて絶滅するといった具合に自然淘汰の過程

口は増加し，低くなる戦略をとる人口はより良い戦略へ取っ人がどう協力する／しないかの仕組みは人工知能，経済学，を表現する．このダイナミクスを計算するには，事前に戦略

生物学などにまたがった学際的な研究課題である．とくに繰を列挙する必要がある．戦略空間を有限状態機械に限定したり返しゲームは長期的関係にあるプレイヤ間の（暗黙の）協調

レプリケータダイナミクスの下では，見間違えが起きても協を説明するためのモデルであり [10]，主に経済学分野で企業間力状態を回復しやすい戦略が生き残ることが明らかになっての談合といった協調行動を分析するために発展してきた [23]．

いるが，より複雑な戦略を分析することは困難である [26]．

暗黙の協調を実現するには，プレイヤが相手の行動をある程

そこで本研究では，まず繰り返し囚人のジレンマをプレイ度観測できることが前提となる．これまで，相手の行動が完するエージェントを実装するために，エージェント自身の行

全に観測できる完全観測（perfect monitoring）のケースについ動と観測したシグナルの履歴を状態としたマルチエージェては多く論じられている [2, 12, 14]．

ント系の学習アルゴリズムを表現する枠組みを定義する．既

しかし，現実には相手の行動が完全に観測できない不完全

存の学習アルゴリズムとして，まず方策勾配法の１つである

観測（imperfect monitoring）のケース，つまり，プレイヤが相q-based Policy Gradient (QPG) [15] を取り上げる．次に，QPG

手の行動を見間違える場合がある [8, 22, 24]．これの特徴は，とよく似た方法で，突然変異のないレプリケータダイナミクス

プレイヤが相手の行動に関してノイズを含む観測（シグナル）

から各行動への重み（ロジット）の更新式を導出した Neural

を私的に受け取ると仮定する点にある．いいかえると，あるReplicator Dynamics (NeuRD) [6] を扱う．QPG は相手が振る舞いを戦略的に変えるような非定常的な状況では学習がうま* 電気通信大学大学院情報理工学研究科† 株式会社サイバーエージェント

くいかないことが知られている．NeuRD はこれを改良し，二73
第 2 分冊Copyright © 2021 by
The Institute of Electronics, Information and Communication Engineers andInformation Processing Society of Japan All rights reserved.

FIT2021（第 20 回情報科学技術フォーラム）人零和不完全情報展開型ゲームにおいてナッシュ均衡への収表 1: 囚人のジレンマ (g > 0，l > 0，および |g − l| < 1)

束を保証することに成功している．

a2 = Ca2 = D

a1 = C1, 1−l, 1 + g

a1 = D

1 + g, −l0, 0

本研究では零和ゲームから囚人のジレンマのようなゲー
ムでも均衡に近い方策を学習できるよう突然変異付きレプ
リケータダイナミクスから学習アルゴリズムである Neural

Replicator-Mutator Dynamics (NeuRMD) を提案する．見間違えのある戦略的環境下で，３つの手法のそれぞれでエージェ

表 2: (C, C) のときのシグナル分布

ントがどんな振る舞いを学習するか吟味した．その結果，

w2 = gw2 = bすることを明らかにした．この方策は経済学や生物学で Win-

w1 = gpq

Stay, Lose-Shift (WSLS) という戦略に相当する [9, 13]．実際，

w1 = bq

1 − p − 2q

NeuRMD がもっとも高い利得を実現する方策を安定的に学習

WSLS は見間違えのある環境で均衡となり最も高い利得を実現する戦略として知られている [21, 26]．

b となる. プレイヤ 2 についても同様である． よく使われる不2 モデル

完全私的観測のシグナル分布にほぼ完全観測がある． ここで

本章では文献 [21] に基づいて, 2 人私的観測付き無限回繰

は，両プレイヤが正しいシグナルを観測する確率は p, 片方のり返しゲームをモデル化する. ここでプレイヤ i ∈ {1, 2} はプレイヤが間違ったシグナルを観測する確率はそれぞれ q と成分ゲームを無限期間 t = 0, 1, 2, … に渡って繰り返す. 各期する．また，1 − p − 2q の確率で両方のプレイヤが間違ったシにおいてプレイヤ i は有限集合 A から行動 ai を選択し, そのグナルを観測する．例として，(C, C) が実現した場合のシグ

行動の組を a = (a1 , a2 ) ∈ A2 とする. 次に, プレイヤ i は a

ナル分布を表 2 に示す． ただし，両プレイヤが正しいシグナ

に関する私的なシグナル ωi ∈ Ω を観測する. w をシグナル

ルを観測する確率 p が最も高くなるように設定する．

の組 (ω1 , ω2 ) ∈ Ω2 とする. また, プレイヤが a を選択したと繰り返し囚人のジレンマの均衡戦略として，“勝ち残り，き w が生起する同時確率を o(w | a) とし, この同時確率を与負け逃げ” (Win-Stay, Lose-Shift, WSLS) [13] がある (図 1)．

える分布のことをシグナル分布と呼ぶ. 成分ゲームは無限回

WSLS は状態 R からスタートし，相手の協力を観測したとき繰り返し行われるので，プレイヤ i の割引利得和は割引因子

は同じ状態に留まり，裏切りを観測するともう一つの状態へδ ∈ (0, 1) によりと遷移する．裏切りを観測してから協力に戻るのは一見不自

∑∞

t

t

t=1 δ gi (a ) となる. ただし，gi (·) の値は然に見えるが，お互いを処罰してから協力に戻ることで，見利得表によって定められた値に従う．
このとき，有限集合 Ω に対する oi (ωi | a) を Ω の限界分

間違えのある環境で有名なしっぺ返し戦略より協力状態を維布 (marginal distribution) とする．加えて，どのプレイヤも他持しやすくなっている．本論文で提案するアルゴリズムは状のプレイヤが選択した (または選択しなかった) 行動を正確に態 P からスタートする WSLS を安定して学習することに成功は分からないと仮定する．どの行動プロファイル a に対してした．

も，それぞれのシグナルプロファイル ω が生起する確率は正数ある戦略の中から有効な戦略を発見する方法の 1 つとしとなる．プレイヤ i の行動 ai とシグナル ωi から “実現利得て，レプリケータダイナミクスがある．ゲームを行うプレイ(realized payoff)” πi (ai , ωi ) をヤの集団を考え，プレイヤはいくつかの戦略の中からランダ∑ムに戦略を選択し，他のプレイヤとゲームを行い利得を得る．

gi (a) =πi (ai , ωi )o(w | a)

その後，戦略の集団に対する利得と集団全体の平均利得との差

w∈Ω2に応じて戦略の人口比を増減させる [14]．本論文ではレプリ
ケータダイナミクスに突然変異の概念を加える．この突然変を満たすように選ぶ．
表 1 に囚人のジレンマの利得表を示す．表中の C は協力行

異付きレプリケータダイナミクスでは，適応度による人口の為を，D は裏切り行為を表す．囚人のジレンマの利得構造は変化に加えて，すべての戦略が適応度に関係なく一定の確率

g > 0，l > 0 であり，このとき D は厳密な支配戦略となる．

で突然変異し異なる戦略をとるようにする．ある戦略が突然また、囚人にジレンマでは |g − l| < 1 が要求される．もしこ

変異する確率を u とした突然変異付きレプリケータ方程式がの条件が成り立たないとすると，繰り返し囚人のジレンマに→→ẋi = xi [fi (−x ) − ϕ(−x )] + u

おいて協力と裏切りを交互に出すほうが，純粋な協力よりも利得が高くなってしまい，純粋な協力が維持できなくなる．
次にプレイヤ 2 の行動に関するプレイヤ 1 のノイズを含む観測をプレイヤ 1 の私的シグナルとし，ω ∈ {g, b} (good, bad)()
1
− xi , i = 1, ..., n (1)nと な る [20]．こ こ で ϕ(·) を 全 て の 戦 略 の 利 得 の 平 均∑−→

j xj fj ( x )，fj (·) を∑m xj ajm とする．ただし，ajm はとする．正しい観測ではプレイヤ 2 が C を選択した際のプレ戦略 j をとるプレイヤが戦略 m を取るプレイヤと無限回プレイヤ 1 の私的シグナルは g, D を選択した際の私的シグナルはイしたときの割引利得和である．

74
第 2 分冊Copyright © 2021 by
The Institute of Electronics, Information and Communication Engineers andInformation Processing Society of Japan All rights reserved.

FIT2021（第 20 回情報科学技術フォーラム）
g

g
b
b

R

利得構造とシグナル分布から

p+q
1−p−q
1+
l,
2p + 2q − 1
2p + 2q − 1
p+q
1−p−q
r(C, b) = −l−1,
2p + 2q − 1
2p + 2q − 1p+qr(D, g) =(1 + g), and
2p + 2q − 11−p−qr(D, b) = −(1 + g)
2p + 2q − 1r(C, g) =P

図 1: WSLS

3 見間違えのある環境とマルチエージェント強化
学習となる．無限回繰り返しゲームでは，割引因子 δ が定める確率で次もゲームが継続するかを定める．ここで，一度ステー

強化学習は，エージェントと呼ばれる意思決定主体が適切なジゲームをプレイすることを 1 step，１つの繰り返しゲームが振舞いを学習するアルゴリズムである．強化学習では，ある時終了するまでを 1 episode とする．マルチエージェント強化学

刻 t において，エージェントは環境から状態 st ∈ S を観測す

習はこの episode を繰り返すことで学習をする．

る．次に行動 at ∈ A を自身の方策 π : s → ∆A に従って決定

3.1

する．エージェントは行動に応じて，環境から報酬 rt ∈ R と方策勾配法

方策勾配法は，方策勾配を用いて獲得報酬を最大化するよ

新たな状態 st+1 を受け取る．強化学習の目的は，状態 s におうな方策を求める強化学習の一手法である [25]．まず，強化

rk |st = s] を最大化する学習の方策 π θ = (π(a|s; θ))s∈S,a∈A がパラメータ θ によってような方策を学習することである．よく知られている強化学

決まる関数であると考える．またこの方策 π θ に従った場合，

習手法，Q 学習 [18] は，今日の状態と行動によって報酬と次時刻 T *1 までの行動履歴∑∞

ける期待割引累積報酬 E[

k=t δ

k−t

の状態遷移が決定されるモデル，マルコフ決定過程 (Markov

τπθ = (s0 , a0 , s1 , a1 , ..., sT , aT , sT +1 )decision process; MDP) において最適な方策の学習が保証されている [19].
マルチエージェント強化学習は，複数のエージェントが同が与える期待累積報酬 R(τπθ ) =∑T

t=0 r(st , at ) が決まる．これを θ に関する関数

時に方策を学習するため，シングルエージェントの学習と比T∑J(θ) = Eπθ [R(τ )] = Eπθ [r(st , at )]較して様々な問題が存在する．マルチエージェント強化学習
では，時刻 t において複数のエージェントがそれぞれ状態 st,iを観測し，行動 at,i を決定する．そのため，エージェント i が受け取る報酬 rt,i と次の状態 st+1,i は，自分の行動 at,i だけ
でなくその他のエージェントの行動 at,−i の行動によって決定t=0として，J(θ) を最大化するような θ を求めることが方策勾配法の目的である．この θ を求めるために，方策勾配∇θ J(θ) = Eπθ [∇θ log(πθ (a|s))Qπθ (s, a)]∞∑s.t. Qπθ (s, a) = Eπθ [δ k−t rk |st = s], ∀s

される．また他のエージェントも同時に方策を学習するため，振舞いが非定常的に変化する．このような非定常性や不確実性にどう対応するかがマルチエージェント強化学習の重要なトピックである．

k=t

を用いて，

本研究では，見間違えのある繰り返し囚人のジレンマ上に，

θ t+1 = θ t + η∇θ J(θ)

マルチエージェント強化学習を定義する．繰り返しゲームで，エージェントは過去の相手の行動から自身の振る舞いを決定する．また見間違えのある環境において，エージェント i が観測できるのは，ある時刻 t の自分の行動 at,i と環境から観測するシグナル ωt,i である．そのため，エージェント i が観測する状態 st は時刻 t における任意の過去 n 期前までの履歴

st,i = (ak,i , ωk,i )t−1
k=t−n とする．ただし，本研究では状態を，
過去 1 期の履歴に限定する．つまり，エージェントに与える
状態集合を

(2)

と更新する．ここで，η は学習率を示す．このように方策勾配法では，θ を更新することで，適切な方策を学習する．
また本研究では，Mean actor critic (MAC) を用いて学習を行った．Actor-Critic 法は，方策をもつ Actor と方策評価をする Critic から構成され，Critic が現在の方策を評価し，その評価から Actor が方策を更新する．通常の Actor-Critic 法
では，∇θ J(θ) を推定するために，サンプルした状態と行動を使用してモンテカルロ近似をしていたが，MAC はサンプ
ルした状態のみを使ってモンテカルロ近似をする [1]. 具体

S = {∅, Cg, Cb, Dg, Db}

的には，従来の Actor-Critic 法は，Critic として状態価値 Vとする．ここで ∅ はゲームの始まりにおける状態を指す．ま値 V π (s) を用いて方策評価をし，サンプルした状態と行動

たエージェントには，報酬から相手の行動を推定させないた
め，報酬 r には実現利得 r(a, ω) を与える．この時 r(a, ω) は75
第 2 分冊

*1 一般的にこの T は 1 episode あたりのステップ数であり，方策はエピ

ソードごとに更新される．

Copyright © 2021 by
The Institute of Electronics, Information and Communication Engineers andInformation Processing Society of Japan All rights reserved.

FIT2021（第 20 回情報科学技術フォーラム）のみの勾配から方策を更新する．MAC では状態行動価値である Q 値を用いて方策評価し，サンプルした状態のすべてのAlgorithm 1 QPG: Tabular Case, Mean Actor-Critic
1: Initialize logits y0 and critic Q-Vaule Qπ

行動についての勾配から方策を更新する. ここで，状態価値V π (s) =∑2: for t = 0 to number of episodes doπa π(a|s)Q (s, a) と計算する．また方策の評価に

は Q 値の代わりに，アドバンテージ

Aπ (s, a) = Qπ (s, a) − V π (s)を用いる．

MAC は別名 q-based Policy Gradient (QPG) とも呼ばれ∑∇θ π(a|s; θ)Aπθ (s, a)](3)

π t = sof tmax(y t )

4:

n=0

5:

repeat6:

Perform an according to policy πt (an |sn )7:

Receive reward rn and new state sn+1
n←n+1

8:

る [15]．QPG では式 2 から θ を以下のように更新する：

θ t+1 = θ t + ηEs∼dπθ (·) [3:9:until episode is not ﬁnished10:

for i ∈ {0, ..., n − 1} do
Qπt (si , ai )←(1 − α)Qπt (si , ai )∑α {ri + δ a′ Qπt (si+1 , a′ )πt (a′ |si+1 )}

11:

a

∑∞
ここで，dπ (s) = Eπ [ t=0 δ t P (st = s|s0 , π)] は期待割引累積訪問数である．方策勾配法では様々な方策を表現すること

12:

end forができるが，本研究では行動空間が離散であるため，特にロ

13:

for s ∈ S do

ジット y = (y(s, a; θ))s∈S,a∈A から，ソフトマックス関数

14:for a ∈ A doA(s, a)πt = Qπt (s, a) −15:

exp (y(s, a; θ))′a′ exp (y(s, a ; θ))π(a|s; θ) = ∑(4)∑

yt+1 (s, a) ← yt (s, a)si ]πt (a|s)Aπt (s, a)

16:

+

πt
′
′
a′ Q (s, a )πt (a |s)∑n−1+ n1 η i=0 1[s =end forを用いて方策を導出する．これは以下の２つの手法でも同様

17:である．また本研究では，θ をニューラルネットワークなど

18:の関数パラメータではなく，ロジットが y = (θ(s, a))s∈S,a∈A

19: end forend forのように表形式 (Tabular Case) で表現される場合を考える．

Tabular Case では QPG の更新式 3 を，ロジット y を次のように更新する:

スであり，微分方程式

yt+1 (s, a) = yt (s, a) + dπ (s)ηπ(a|s)Aπ (s, a)→→ẋi = xi [fi (−x ) − ϕ(−
x )]

(5)

QPG ではロジット y の更新を式 5 にしたがって Algo-にしたがって戦略分布を更新する．NeuRD は，このレプリ

rithm 1 を構成する．まずロジット y と方策の評価値である

ケータ方程式に合わせてロジットの更新式 5 を修正する．詳Critic の Q 値 Q を初期化する．次に以下の処理を指定されしい導出は省略するが，第 4 章で示す導出とほぼ同じであたエピソードの数だけ繰り返す．まずは前の t エピソード目る．結果的に QPG と NeuRD はロジットの更新式 5 のみがに更新したロジット y t から，方策 π t をソフトマックス関数

異なるようになる．QPG はアドバンテージ関数 Aπ (s, a) にπを用いて計算する．次にエージェントはこの方策 π t に従っ

π(a|s) をかけていたのに対して，NeuRD はアドバンテージて，エピソードが終了するまで，状態 sn に対して行動 an を関数 Aπ (s, a) をそのまま使ってロジットを更新する．具体的

選択し，その結果報酬 rn と次の状態 si+n を受け取る．このには状態と行動，報酬の履歴に従って，現在の方策 π t を評価す

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

るために，Q 値 Qπt を更新する．そして，この Q 値 Qπ から，そのエピソードで到達したすべての状態 s とすべての行
π(6)となる．こうすることで，一度選択確率が低くなった行動も動 a について，アドバンテージ A (s, a) を計算し，ロジット

その他の行動と同じだけ y(s, a) を更新するようになる．このyt+1 (s, a) を更新する. ここで，dπ (s) はその状態 s を訪問し結果，マルチエージェント系のような非定常性の高い環境にた回数を履歴の長さ n で割ることで，モンテカルロ近似する．

おいて，有効な方策が大きく変化した場合に適応できるよう

次に，Neural Replicator Dynamics (NeuRD) [6] を概説す
る．これは MAC 法を用いた強化学習手法の 1 つであり，レプ
リケータダイナミクスに基づいて，マルチエージェント系のよになる．

4 Neural Replicator-Mutator Dynamics

うな非定常な環境において性能を発揮する．具体的には，二本 節 で はNeuralReplicator-Mutator

Dynamics

人零和不完全情報展開型ゲームにおいてナッシュ均衡への収(NeuRMD) を 新 し く 提 案 す る ．NeuRMD は 突 然 変 異 付束が保証される．レプリケータダイナミクスは突然変異付ききレプリケータダイナミクス [20] から，NeuRD と同じようレプリケータダイナミクスの突然変異が u = 0 の特殊なケーにロジットの更新式を導く．結果として NeuRD に突然変異

76
第 2 分冊Copyright © 2021 by
The Institute of Electronics, Information and Communication Engineers andInformation Processing Society of Japan All rights reserved.

FIT2021（第 20 回情報科学技術フォーラム）項を追加した形になる．
レプリケータダイナミクスに突然変異を導入するとそのダ

Algorithm 2 NeuRMD: Tabular Case, Mean Actor-Critic
1: Initialize logits y0 and critic Q-Vaule Qπ

イナミクスの帰結が安定しやすくなることが知られている．

2: for t = 0 to number of episodes do

突然変異がないレプリケータダイナミクスの平衡点が，同じ適応度をもつ連続した点になることが多く，１つの平衡点を

3:

π t = sof tmax(y t )選ぶのが難しい．突然変異を導入することで，このような中

4:

n=0

立的に連続している平衡点を離散化することができる [5]．ま5:

repeatた，突然変異がない場合，漸近的に安定な平衡点の存在を保証

6:

Perform an according to policy πt (an |sn )できない．一方で突然変異があれば，その確率が 0 に収束す7:

Receive reward rn and new state sn+1

るとき，漸近的に安定な平衡点の存在を保証できるようにな

8:

る [3]．加えて，数値的なダイナミクスの計算も安定する．し9:

until episode is not ﬁnished

たがって，突然変異付きレプリケータダイナミクスを用いて

10:

for i ∈ {0, ..., n − 1} do

ロジット更新を構成することで，こうした利点を NeuRD に追

11:

n←n+1

Qπt (si , ai )←(1 − α)Qπt (si , ai )∑α {ri + δ a′ Qπt (si+1 , a′ )πt (a′ |si+1 )}加できる．
具体的な導出に備えて，まずレプリケータダイナミクスと

12:

end for

方策勾配法の対応について考える．式 1 に示すレプリケータ

13:

for s ∈ S do

ダイナミクスにおけるある戦略 i の人口 xi はその戦略を取る

14:

確率に相当し，これは行動 a の選択確率 π(a) に対応する．次15:に戦略 i が得る利得 fi (⃗x) は状態行動価値 Q 値と，また全て

16:

for a ∈ A doA(s, a)πt = Qπt (s, a) −また突然変異項に着目すると，n は戦略数であるため，行動数

17:|A| と対応する．以上を用いてレプリケータ方程式を方策の変18:化量の式に書き換える：()
1π̇(a) = π(a)[Qπ (a) − V π ] + u− π(a|s)|A|()
1= π(a)Aπ (a) + u− π(a) .
|A|

(7)

∑

πt
′
′
a′ Q (s, a )πt (a |s)yt+1←y}t (s, a){ (s, a)u
1
η Aπt (s, a) + π(a|s)( |A|− πt (a|s))の戦略の利得の平均である ϕ(⃗x) は状態価値 V 値と対応する．

++

end forend for

19: end for

により，ロジット y の変化量はdu1y(a) = Aπ (a) +(− π(a))dt
π(a) |A|

次にこの方策の更新量を示す式 7 から Tabular Case における

(8)

ロジットの更新量を導出する．式 4 と同様に π(a) をロジットとなる．この式 8 から，状態を持たない RD の π(a) と状態をy に関するソフトマックス関数で表すと，持つ強化学習の π(a|s) を対応付けてオイラー離散化すること
でロジットの更新式

exp (y(a))′
a′ exp (y(a ))π(a) = ∑{yt+1 (s, a) = yt (s, a)+η A(s, a)π +となる．これを両辺を時刻 t で微分すると∑
dd′exp (y(a))
exp (y(a)) dtdπ(a)a′ exp (y(a ))
∑
= ∑dt
−
′
′
2
dt
( a′ exp (y(a )))a′ exp (y(a ))∑ddexp (y(a)) dt
y(a) exp (y(a)) a′ exp (y(a′ )) dty(a′ )
∑
= ∑
−
′
′
2
( a′ exp (y(a )))a′ exp (y(a ))∑d′ dπ(a ) y(a′ )= π(a) y(a) − π(a)
dt
dt
a′
[
]
∑
d
′ d
′
π(a ) y(a ) .
= π(a)
y(a) −dt
dt′

π̇(a) =}1u(
− π(a|s))π(a|s) |A|
(9)

を得る．

NeuRMD ではロジット y の更新を式 9 にしたがって Algorithm 2 を構成する．これは基本的に Algorlithm 1 と同じだ
が，レプリケータダイナミクスに従って方策を学習するため，

16 行目のロジット y(s, a) はすべての状態 s に関して更新していることに注意したい．

5

計算機実験

5.1

実験設定

a

また式 7 を代入して本節では QPG, NeuRD, NeuRMD の３つの手法が，見間違

∑
d
d
u
1
y(a) −
π(a′ ) y(a′ ) = Aπ (a) +(− π(a))
dt
dt
π(a)
|A|
′

えのある繰り返し囚人ジレンマで獲得する報酬と相互協力となる．ただし，この方程式はあらゆる解を許容してしまう

手法で独立して学習すると仮定する．各エージェントは行動d′a′ π(a |s) dt y(a) = 0 と仮定して解を限定する．これa ∈ {C, D} を選択し，シグナル ω ∈ {g, b} を観測し，自身の

a

ため，

∑

率を確認する．この時，2 体のエージェントがそれぞれ同じ

77
第 2 分冊Copyright © 2021 by
The Institute of Electronics, Information and Communication Engineers andInformation Processing Society of Japan All rights reserved.

FIT2021（第 20 回情報科学技術フォーラム）行動とシグナルに応じた報酬である実現利得 r(a, ω) を受け取より，NeuRMD は従来手法より安定的に，見間違えのある繰

る．囚人のジレンマの利得パラメータを g = 0.1, l = 0.1，割り返し囚人のジレンマの均衡戦略を求めることに成功した．

引因子 δ = 0.9 とする．この割引因子はエピソード内のゲー

次に，方策とロジットの推移から突然変異の効果についてムが継続する確率を表す．つまり確率 δ でゲームを継続し，確分析する．図 5 は NeuRMD のロジットの推移を表している．

率 1 − δ でそのエピソードを終了する．シグナル分布のパラ

縦軸がロジットの値，横軸がエピソード数に対応し，各状態，メータは p = 0.95, q = 0.01，Q 値の学習率 α = 0.1, 方策の行動ごとにプロットした．18000 エピソードを境に，状態 Cg

学習率 η = 0.02, 割引率 γ = 0.9 とする．また NeuRMD の突と Db における行動 C のロジットが急激に大きくなり，行動

然変異確率は µ = 0.01 とする．割引因子 δ によるゲームの終D のロジットを逆転している．これは突然変異により今まで了までを 1 エピソードとして，500,000 エピソード学習し，ラと異なる行動を選んだことで，高い報酬を獲得した結果だと

ンダムシードを変えながら行った 30 試行を評価する．

考えられる．このような逆転が起こる以前の方策やロジット

5.2 獲得報酬と相互協力率の推移の推移に見ても，一度選択確率が低くなった行動に対応する

図 2 では，各手法が獲得した 2 体の平均報酬値の推移を表

ロジットの値は定期的に増加しており，それが高い報酬を獲している．2 体の平均報酬値は，そのエピソードでエージェン

得できるような状態になることで，S-WSLS のような協力的トが獲得した 2 体の平均合計報酬値と繰り返し回数の商としな方策を学習すると考えられる．

た．縦軸は２体の平均報酬値，横軸はエピソード数に対応し，以上の実験は，ランダムシードを変えながら 30 試行の結果

区間数 10 の移動平均と信頼区間をプロットした．図 3 では，を示した．各試行で３つのアルゴリズムがどれだけ均衡に近各手法ごとの相互協力率の推移を表している．相互協力率は，

い方策を獲得したのかを分析する．どのアルゴリズムも均衡あるエピソードにおいて，お互いに行動 C をとった割合であ戦略への収束を保証できない．さらに，見間違えのある繰りる．縦軸は相互協力率，横軸はエピソード数に対応し，区間

返し囚人のジレンマでは，相手の方策を固定したときの最適数 10 の移動平均と信頼区間をプロットした．最終的な平均獲反応を計算することも非常に難しく求めた方策が均衡である

得報酬は，QPG が 0.014, NeuRD が 0.16，NeuRMD が 0.67

ことをチェックできない．そこで，求めた方策が均衡でないとなった．また最終的な相互協力率は，QPG が 0.28 × 10−3 ,ことを判定することを考える．つまり，相手が学習した方策

NeuRD が 0.14，NeuRMD が 0.66 となった．このことからわを固定して，学習させた方策（反応方策）が，元の方策よりかるように平均獲得報酬，相互協力率ともに提案手法がほか

高い報酬値を獲得すれば，元の方策は相手の方策に対する最の 2 つの手法を上回った．

適反応でない，と判定する．この判定を以下の手続きにした

平均報酬値と相互協力率を比較すると，NeuRMD は高い報がってすすめる．

酬値を獲得していても，平均報酬値と相互協力率の差が小さ

1. 学習済みの方策 (π 1 , π 2 ) の組を考える．

い．エージェントが相互協力によって得る報酬値はそれぞれ 1

R
2. それぞれの方策について反応方策 π R
1 と π 2 を求める．

である．一方，2 体のエージェントのうち片方が裏切り D を反応方策は学習済みの方策を片方のエージェントで固定

選択した場合，g = l であれば平均報酬値は 0.5 となり，両方

し，QPG で学習させることで求める．ここでエピソード

D を選択した場合，平均報酬値は 0 となる．このことから，

数は 10000 回とした．

NueRMD は，片方のエージェントによる搾取ではなく，双方

3. 次 に ，学 習 済 み の 方 策 (π 1 , π 2 ) で 獲 得 す る 各 エ ーのエージェントの協力行動によって高い報酬値を獲得していジ ェ ン ト の 報 酬 値 (r 1 , r 2 ) と ，学 習 済 み の 方 策 とることがわかる．

R
反 応 方 策 の 組 (π 1 , π R1 ), (π 2 , π 2 ) が 獲 得 し た 報 酬 値

5.3 獲得方策の評価

R(r 1,1 , r R
1,2 ), (r 2,1 , r 2,2 ) を求める．

前節では NeuRMD が協力的な方策を安定的に学習すること

4. ここでの獲得報酬は各組について 10000 エピソードをプが明らかとなったが，本説ではその獲得した方策を分析する．

レイさせた結果の報酬値の平均とした．これは見間違い

図 4 は NeuRMD の獲得した方策の推移を表している．縦軸の発生や行動選択のモンテカルロ誤差を小さくするためが行動の選択確率，横軸がエピソード数に対応し，各観測状態である．

における行動 C の選択確率をプロットした．最終的に獲得しR
5. 最後に r 1 と r R
2,1 ，r 2 と r 1,2 を比較することで最適反応

た方策は π(C|∅) が 0.01，π(C|Cg) が 0.99，π(C|Cb) が 0.01，

性を評価する．具体的には，この学習済み方策の報酬値

π(C|Dg) が 0.01，π(C|Db) が 0.99 であった．この方策では，と反応方策の報酬値の差から，学習済み方策の最適反応

シグナル g を観測した場合は昨日自分が取った行動と同じ行性を定量的に評価する．

動を，シグナル b を観測した場合は昨日自分が取った行動と異なる行動を選択する．この方策はすでに図 1 に示した WSLS

図 6 は各手法ごとの学習済み方策と反応方策の報酬値の差と初期状態だけが異なる [11]．つまり，状態 P からスタート

Rを示している．学習済み方策と反応方策の差は ri − ri,−iとする WSLS (Suspicious-WSLS, S-WSLS) が NeuRMD が獲得し，これが負になると反応方策で報酬を改善したことになり，した方策に対応する．WSLS は見間違えのある環境で最も高元の学習済み方策が均衡を構成しないと判定できる．図 6 のい利得を実現する均衡戦略として知られている [21, 26]．以上

縦軸は報酬差を示しており，すべてのランダムシードとエー

78
第 2 分冊Copyright © 2021 by
The Institute of Electronics, Information and Communication Engineers andInformation Processing Society of Japan All rights reserved.

FIT2021（第 20 回情報科学技術フォーラム）図 2: 2 体の平均獲得報酬の推移
(C| )

1.0

(C| )

図 3: 相互協力率の推移(C|Cg)

1.0(C|Cb)

1.0(C|Dg)

1.0(C|Cb)(C|Dg)

0.8

0.8

0.8

0.8

0.8

0.6

0.6

0.6

0.6

0.6

0.4

0.4

0.4

0.4

0.4

0.2

0.2

0.2

0.2

0.2

0.0

0.0

0.0

0.0

0

100000 200000 300000 400000 500000
episode(C|Cg)
0100000 200000 300000 400000 500000
episode0

100000 200000 300000 400000 500000
episode0

100000 200000 300000 400000 500000
episode(C|Db)

1.0

0.0(C|Db)
0100000 200000 300000 400000 500000
episode図 4: NeuRMD: 方策の推移

1
0
1
2
3
4
5
6
7

logits( , C)logits( , C)logits( , D)

0100000 200000 300000 400000 500000
episode

1
0
1
2
3
4
5
6
7

logits(Cg, C)

logits(Cg, C)
logits(Cg, D)
0100000 200000 300000 400000 500000
episode

1
0
1
2
3
4
5
6
7

logits(Cb, C)

1
0
1
2
3
4
5
6
7

logits(Cb, C)
logits(Cb, D)
0100000 200000 300000 400000 500000
episodelogits(Dg, C)
logits(Dg, C)
logits(Dg, D)

0100000 200000 300000 400000 500000
episode

1
0
1
2
3
4
5
6
7

logits(Db, C)
logits(Db, C)
logits(Db, D)

0100000 200000 300000 400000 500000
episode図 5: NeuRMD: ロジットの推移

ジェントに関して箱ひげ図を作成し，四分位からの外れ値をプロットした．その結果，報酬値の差の中央値はそれぞれ

6

QPG が 0.46 × 10−3 ，NeuRD が 0.40 × 10−2 ，NeuRMD が0.35 × 10−2

おわりに
本論文は，見間違えのある繰り返し囚人のジレンマの均衡となり，NeuRD, NeuRMD, QPG の順に大きかっ

戦略に相当する方策を学習する手法として，進化ゲームでよた．QPG は元々 QPG 同士で学習しているため，報酬値の差く知られている突然変異付きレプリケータダイナミクスのが 0 に近いのは自然であると考えられる．次に，NeuRD は最仕組みを行動の重み更新に導入した NeuRMD を提案した．

も報酬値の差の中央値は大きいが，大きな外れ値が 60 個中 6

NeuRMD は非自明な協力的均衡戦略である WSLS を，従来手個あるため，均衡戦略を安定的に学習しているとは言えない．

法より安定的に学習することを実験的に示した．一般に繰り最後に，NeuRMD はその報酬値がすべて 0 以上であり，大き返し囚人のジレンマで常に裏切る戦略以外を学習させることな外れ値もない．よって NeuRD より安定的に方策を獲得しは難しいが，提案手法は，同じような構造を持つゲームにおいているといえる．ここで，提案手法が従来手法である NeuRDて，プレイヤが相手を処罰する機構をもちながら協力する仕よりも平均値や中央値で劣るのは，突然変異項による探索の組みを発見できることを示唆した．今後の課題として，2 期以影響であると考えられる．それでも，NeuRMD は協力的な均上の記憶をもつケースの分析や，企業間の価格競争や企業の衡に近い戦略を安定的に獲得しているといえる．

参入／退出といった行動空間を大きくしたゲームの分析が挙
げられる．

79
第 2 分冊Copyright © 2021 by
The Institute of Electronics, Information and Communication Engineers andInformation Processing Society of Japan All rights reserved.

FIT2021（第 20 回情報科学技術フォーラム）[10] G. Mailath and L. Samuelson. Repeated Games and Reputation. Oxford University Press, 2006.
0.00[11] E. E.-S. Martin A. Nowak, Karl Sigmund. Automata, repeated games and noise. Journal of Mathematical Biology,

Reward Difference

0.02

33:703–722, 1995.

0.04[12] M. Nowak. Evolutionary Dynamics: Exploring the Equa-

0.06[13] M. Nowak and K. Sigmund. A strategy of win-stay, lose-

tions of Life. Harvard University Press, 2006.
shift that outperforms tit for tat in prisoner’s dilemma. Na-

0.08

ture, 364:56–58, 1993.
[14] K. Sigmund. The Calculus of Selﬁshness. Princeton Uni-

0.10
QPG

NeuRD

NeuRMDversity Press, 2010.
[15] S. Srinivasan, M. Lanctot, V. Zambaldi, J. Pérolat,

図 6: 反応方策との報酬差

K. Tuyls, R. Munos, and M. Bowling. Actor-critic policy optimization in partially observable multiagent environments. In Proceedings of the Thirty-second Conference
on Neural Information Processing Systems, p. 3426–3439,

参考文献

2018.

[1] C. Allen, K. Asadi, M. Roderick, A. rahman Mohamed,
G. Konidaris, and M. Littman. Mean actor critic, 2018.

[16] P. D. Taylor and L. B. Jonker. Evolutionarily stable strategies and game dynamics. Mathematical Biosciences, pp.
145–156, 1978.

[2] R. Axelrod. Genetic Algorithms and Simulated Annealing, chapter The Evolution of Strategies in the Iterated Pris-[17] K. Tuyls, Pieter Jan

T, B. Vanschoenwinkel. An evolu-

tionary dynamical analysis of multi-agent learning in iter-

oner’s Dilemma, pp. 32–41. 1987.
equilibria in evolutionary game dynamics through muta-

ated games. Autonomous Agents and Multi-Agent Systems,
12(1):115–153, 2006.

tion: mutation limits in evolutionary games. Proceedings[18] C. Watkins. Learning from delayed rewards. PhD thesis,[3] J. Bauer, M. Broom, and E. Alonso. The stabilization of1989.

of the Royal Society A: Mathematical, Physical and Engi-[19] C. Watkins and P. Dayan. Q-learning. In Machine Learn-

neering Sciences, 475(2231):20190355, 2019.

ing, pp. 279–292, 1992.

[4] D. Bloembergen, K. Tuyls, D. Hennes, and M. Kaisers.
Evolutionary dynamics of multi-agent learning: A survey.

[20] B. M. Zagorsky, J. G. Reiter, K. Chatterjee, and M. A.
Nowak.

J. Artif. Int. Res., 53(1):659–697, May 2015.
tionary games. Games and Economic Behavior, 11(2):146–

Forgiver triumphs in alternating prisoner’s

dilemma. PLOS ONE, pp. 1–8, 2013.

[5] I. M. Bomze and R. Burger. Stability by mutation in evolu-[21] ヨンジュン, 岩崎, 神取, 小原, 横尾. 部分観測可能マル
コフ決定過程を用いた私的観測付き繰り返しゲームに

172, 1995.

おける均衡分析プログラム. 情報処理学会論文誌, pp.

[6] D. Hennes, D. Morrill, S. Omidshaﬁei, R. Munos, J. Per-

1234–1246, 2012.

olat, M. Lanctot, A. Gruslys, J.-B. Lespiau, P. Parmas,
E. Duéñez-Guzmán, et al. Neural replicator dynamics:
Multiagent learning via hedging policy gradients.

[22] 関口. 経済セミナー増刊:ゲーム理論プラス, 「協調達成のための正しいお仕置きの仕方」. 日本評論社, 2007.

In

Proceedings of the 19th International Conference on Au-[23] 岡田. ゲーム理論 新版. 有斐閣, 2011.

tonomous Agents and MultiAgent Systems, pp. 492–501,[24] 松島. ゲーム理論の新展開. 勁草書房, 2002. 第 4 章:「繰り返しゲームの新展開:私的モニタリングによる暗黙の協2020.

調」, pp.89-114.

[7] J. Hofbauer and K. Sigmund. Evolutionary Games andPopulation Dynamics. Cambridge University Press, Cambridge, 1998.
[8] M. Kandori. Repeated games. In S. N. Durlauf and L. E.

[25] 森村. 強化学習. 講談社, 2019.
[26] 西野上, 五十嵐, 岩崎. 私的観測下の繰り返し囚人のジレ

Blume eds., Game theory, pp. 286–299. Palgrave Macmil-

ンマにおける協力のダイナミクス. 第 19 回情報科学技術フォーラム, 2020.

lan, 2010.
[9] D. Kraines and V. Kraines.

Pavlov and the prisoner’s

dilemma. Theory and Decision, 26:47–79, 1989.

80
第 2 分冊Copyright © 2021 by
The Institute of Electronics, Information and Communication Engineers andInformation Processing Society of Japan All rights reserved.