兩方零和馬爾科夫博弈下的策略梯度算法

李永強(qiáng) 周 鍵 馮 宇 馮遠(yuǎn)靜

LI Yongqiang1，ZHOU Jian1，F(xiàn)ENG Yu1，F(xiàn)ENG Yuanjing1

博弈問(wèn)題是實(shí)際應(yīng)用中的常見(jiàn)問(wèn)題，如圍棋、象棋、撲克游戲、對(duì)抗類(lèi)電子游戲等.近年來(lái)，在模型未知的情況下，利用多智能體強(qiáng)化學(xué)習(xí)求解博弈問(wèn)題受到廣泛關(guān)注[1-6].在現(xiàn)有文獻(xiàn)中，通常利用如下兩類(lèi)框架描述多步博弈問(wèn)題：擴(kuò)展形式博弈(Extensive-Form Games)和馬爾科夫博弈(Markov Games).

擴(kuò)展形式博弈適用于描述不完全信息、回合制博弈問(wèn)題，如撲克游戲.回合制是指參與博弈的玩家在每步?jīng)Q策時(shí)，知道已行動(dòng)玩家采取的動(dòng)作.例如，在撲克游戲中，參與的玩家輪流出牌或下注，當(dāng)前行動(dòng)的玩家可看到已行動(dòng)玩家出的牌或下的注.為了解決生活中流行的擴(kuò)展形式博弈問(wèn)題，學(xué)者們提出大量基于策略梯度的多智能體強(qiáng)化學(xué)習(xí)算法，如基于虛擬自博弈(Fictitious Self-Play)的方法[7-10]和基于反事實(shí)遺憾(Counter factual Regret)的方法[11-14].

馬爾科夫博弈適用于描述完全信息、同時(shí)移動(dòng)博弈問(wèn)題.同時(shí)移動(dòng)博弈問(wèn)題是指在每步?jīng)Q策時(shí)，所有參與的玩家同時(shí)選擇動(dòng)作，玩家在決策時(shí)并不知道另一玩家會(huì)采取的動(dòng)作，如軍事對(duì)抗博弈問(wèn)題.

馬爾科夫博弈拓寬?cǎi)R爾科夫決策過(guò)程(Markov Decision Process, MDP)只能有一個(gè)智能體的限制，馬爾科夫博弈可包含多個(gè)智能體.在使用多智能體強(qiáng)化學(xué)習(xí)方法求解博弈問(wèn)題時(shí)，強(qiáng)化學(xué)習(xí)中的術(shù)語(yǔ)“智能體”一般稱(chēng)為“玩家”，本文也保持這個(gè)習(xí)慣.這些玩家可以有各自的利益目標(biāo).兩方零和馬爾科夫博弈(Two-Player Zero-Sum Markov Games, TZMG)為馬爾科夫博弈的一種特殊情況，特殊之處是參與博弈的兩個(gè)玩家的利益完全相反.

針對(duì)TZMG的多智能體強(qiáng)化學(xué)習(xí)算法可分為兩類(lèi)：值函數(shù)方法和策略梯度方法.現(xiàn)有文獻(xiàn)中大部分方法都是值函數(shù)方法.Littman[15]提出Minimax-Q，可找到納什均衡策略，但是由于每次更新Q函數(shù)需要構(gòu)建線(xiàn)性規(guī)劃以求解每個(gè)狀態(tài)階段博弈的納什均衡策略，計(jì)算量巨大.為了解決Minimax-Q的計(jì)算效率問(wèn)題，Gran-Moya等[16]提出Soft Q-Learning,計(jì)算熵正則化條件下閉合形式的軟最優(yōu)策略，從而避免使用線(xiàn)性規(guī)劃更新Q函數(shù).然而，由于固定的正則化條件，策略可能無(wú)法達(dá)到納什均衡.為了在保持計(jì)算效率的同時(shí)保證策略收斂到納什均衡，Guan等[17]提出SNQ2L(Soft Nash Q2-Learning).值函數(shù)方法由于算法本身的限制并不適合動(dòng)作空間大的環(huán)境.對(duì)于MDP，策略梯度方法比值函數(shù)方法更容易擴(kuò)展到大動(dòng)作空間，通常收斂速度更快.

策略梯度方法在許多領(lǐng)域具有較優(yōu)性能[18-19].但是，對(duì)于TZMG，策略梯度方法的研究結(jié)果依然很少.Daskalakis等[20]提出雙時(shí)間尺度的策略梯度算法，解決TZMG問(wèn)題，主要思想是兩個(gè)玩家采用快慢學(xué)習(xí)率交替進(jìn)行訓(xùn)練，本質(zhì)上還是單智能體強(qiáng)化學(xué)習(xí)，并且訓(xùn)練過(guò)程比同時(shí)訓(xùn)練玩家的策略更繁瑣.

本文致力于實(shí)現(xiàn)同時(shí)訓(xùn)練并更新玩家的策略，圍繞這個(gè)目標(biāo)，首先將策略梯度定理擴(kuò)展到TZMG，給出針對(duì)TZMG的策略梯度定理的嚴(yán)格證明.該定理是利用采樣數(shù)據(jù)估計(jì)TZMG的玩家策略梯度的理論基礎(chǔ).本文采用類(lèi)似于單智能體REINFORCE[21]的思路估計(jì)TZMG下的玩家策略梯度，即利用完整采樣軌跡的回報(bào)均值估計(jì)期望回報(bào).得到玩家策略梯度的估計(jì)之后，可利用基于梯度的方法求解TZMG的等價(jià)問(wèn)題，即最大最小化問(wèn)題.由此，本文提出基于額外梯度的REINFORCE算法(Extra-Gradient Based REINFORCE, EG-R),求解最大最小化問(wèn)題，解決直接使用梯度上升下降算法時(shí)，玩家的聯(lián)合策略無(wú)法達(dá)到近似納什均衡的問(wèn)題.

1 問(wèn)題描述及背景知識(shí)

1.1 馬爾科夫決策過(guò)程問(wèn)題

馬爾科夫決策過(guò)程(MDP)可用一個(gè)五元組(S,A,P,ρ,γ)描述.其中：S表示有限狀態(tài)空間，狀態(tài)個(gè)數(shù)為|S|；A表示智能體的有限動(dòng)作空間，動(dòng)作個(gè)數(shù)為|A|；

P(s′,r|s,a)∶S×A→Δ(S×R)

表示在任意動(dòng)作a∈A下，從任意狀態(tài)s∈S轉(zhuǎn)移到狀態(tài)s′∈S，且智能體獲得獎(jiǎng)勵(lì)r的概率；ρ∶S→Δ(S)表示初始狀態(tài)的概率分布；γ∈(0,1]表示折扣因子.

MDP下的智能體與環(huán)境的交互如圖1所示，環(huán)境根據(jù)初始狀態(tài)的概率分布ρ生成初始狀態(tài)S0.在每個(gè)時(shí)刻t，智能體按照隨機(jī)策略

圖1 MDP下的智能體與環(huán)境的交互

π(·|St)∶S→Δ(A)

在當(dāng)前狀態(tài)St下選擇動(dòng)作，得到的動(dòng)作記為At.環(huán)境對(duì)動(dòng)作At做出相應(yīng)響應(yīng)，然后根據(jù)狀態(tài)轉(zhuǎn)移及獎(jiǎng)勵(lì)生成的概率分布P將狀態(tài)從St轉(zhuǎn)移到St+1，并給出獎(jiǎng)勵(lì)Rt，即

St+1,Rt～P(·,·|St,At).

智能體和環(huán)境如此交互直至終止時(shí)刻T.每局交互產(chǎn)生一條軌跡:

τ∶=(S0,A0,R0,S1,…,ST-1,AT-1,RT-1,ST).

獲得的回報(bào)大小體現(xiàn)智能體在這局交互中的表現(xiàn)，回報(bào)定義為累計(jì)折扣獎(jiǎng)勵(lì)：

對(duì)于MDP，只有一個(gè)智能體與環(huán)境交互，訓(xùn)練智能體的目的就是找到一個(gè)最優(yōu)策略，使智能體在與環(huán)境交互的過(guò)程中獲得最大的期望回報(bào).初始狀態(tài)為s時(shí)的期望回報(bào)定義為

Vs(π)∶=Eπ[G(τ)|S0=s].

(1)

由于初始狀態(tài)s服從概率分布ρ，期望回報(bào)也可定義為

Vρ(π)∶=Es～ρ[Vs(π)]=Eπ[G(τ)]，

(2)

則最優(yōu)策略滿(mǎn)足

1.2 兩方零和馬爾科夫博弈問(wèn)題

兩方零和馬爾科夫博弈(TZMG)可用一個(gè)六元組(S,A,B,P,ρ,γ)描述.其中：S表示有限狀態(tài)空間，狀態(tài)個(gè)數(shù)為|S|；A和B分別表示玩家1和玩家2的有限動(dòng)作空間，動(dòng)作個(gè)數(shù)分別為|A|和|B|；

P(s′,r|s,a,b)∶S×A×B→Δ(S×R)

表示在任意聯(lián)合動(dòng)作(a,b)∈A×B下，從任意狀態(tài)s∈S轉(zhuǎn)移到狀態(tài)s′∈S，且玩家1獲得獎(jiǎng)勵(lì)r，玩家2獲得獎(jiǎng)勵(lì)-r的概率；ρ∶S→Δ(S)表示初始狀態(tài)的概率分布；γ∈(0,1]表示折扣因子.

TZMG下的玩家與環(huán)境的交互如圖2所示，一輪博弈開(kāi)始時(shí)，環(huán)境根據(jù)初始狀態(tài)的概率分布ρ生成初始狀態(tài)S0.在每個(gè)時(shí)刻t，玩家1按照隨機(jī)策略

圖2 TZMG下的玩家與環(huán)境的交互

π(·|St)∶S→Δ(A)

在當(dāng)前狀態(tài)St下選擇動(dòng)作，得到的動(dòng)作記為At.同時(shí)，玩家2按照隨機(jī)策略

μ(·|St)∶S→Δ(B)

在當(dāng)前狀態(tài)St下選擇動(dòng)作，得到的動(dòng)作記為Bt.聯(lián)合動(dòng)作(At,Bt)送入環(huán)境中執(zhí)行，環(huán)境根據(jù)狀態(tài)轉(zhuǎn)移及獎(jiǎng)勵(lì)生成的概率分布P將環(huán)境狀態(tài)從St轉(zhuǎn)移到St+1，并給出獎(jiǎng)勵(lì)Rt，即

St+1,Rt～P(·,·|St,At,Bt).

如此直至本輪博弈的終止時(shí)刻T.每輪博弈都會(huì)產(chǎn)生一條軌跡

τ∶=(S0,A0,B0,R0,S1,…,ST-1,AT-1,BT-1,RT-1,ST).

玩家1的回報(bào)定義為累積折扣獎(jiǎng)勵(lì):

由于是零和博弈，玩家2的回報(bào)為-G(τ).

對(duì)于TZMG，有兩個(gè)玩家同時(shí)與環(huán)境交互，相比式(1)和式(2),期望回報(bào)發(fā)生改變，初始狀態(tài)為s時(shí)的期望回報(bào)定義為

Vs(π,μ)∶=Eπ,μ[G(τ)|S0=s]

，

由于初始狀態(tài)s服從概率分布ρ，期望回報(bào)可定義為

Vρ(π,μ)∶=Es～ρ[Vs(π,μ)]=Eπ,μ[G(τ)].

(3)

由式(3)可知，期望回報(bào)Vρ(π,μ)不僅與己方策略有關(guān)，也與對(duì)方策略有關(guān)，即雙方的聯(lián)合策略(π,μ)共同確定Vρ(π,μ)的值.因此，TZMG的最優(yōu)策略為達(dá)到納什均衡時(shí)的聯(lián)合策略，此時(shí)的期望回報(bào)正好處于圖3中的鞍點(diǎn)處.所以，對(duì)于TZMG，訓(xùn)練玩家的目的就是找到一個(gè)納什均衡的聯(lián)合策略.由于兩個(gè)玩家的策略對(duì)期望回報(bào)的影響不同，為了找到納什均衡的聯(lián)合策略，兩個(gè)玩家的目標(biāo)也不同.玩家1的目標(biāo)是：對(duì)任意玩家2的策略μ，尋找最優(yōu)策略π*最大化期望回報(bào)Vρ(π,μ).如圖3所示，玩家1的策略參數(shù)更新方向應(yīng)為期望回報(bào)增大的方向.玩家2的目標(biāo)是：對(duì)任意玩家1的策略π，尋找最優(yōu)策略μ*最小化期望回報(bào)Vρ(π,μ).如圖3所示，玩家2的策略參數(shù)更新方向應(yīng)為期望回報(bào)減小的方向.

圖3 雙曲拋物面

文獻(xiàn)[22]證明TZMG滿(mǎn)足最大最小化定理，即對(duì)任意的TZMG，一定存在一個(gè)納什均衡的聯(lián)合策略(π*,μ*)，使

Vρ(π,μ*)≤Vρ(π*,μ*)≤Vρ(π*,μ),

?π,μ.

(4)

式(4)也稱(chēng)為鞍點(diǎn)不等式，由式(4)可知，納什均衡的聯(lián)合策略(π*,μ*)滿(mǎn)足

(5)

TZMG可能存在多個(gè)納什均衡的聯(lián)合策略，但是所有納什均衡的聯(lián)合策略的期望回報(bào)Vρ(π*,μ*)是相等的[20].

1.3 求解兩方零和馬爾科夫博弈問(wèn)題的難點(diǎn)

一方面，如圖1和圖2所示，根據(jù)MDP和TZMG的定義，MDP的狀態(tài)轉(zhuǎn)移和獎(jiǎng)勵(lì)生成只跟環(huán)境狀態(tài)和一個(gè)智能體選擇的動(dòng)作有關(guān)，而TZMG的狀態(tài)轉(zhuǎn)移和獎(jiǎng)勵(lì)生成跟環(huán)境狀態(tài)，及玩家1和玩家2各自選擇的動(dòng)作有關(guān).由于兩個(gè)玩家同時(shí)選擇動(dòng)作，每個(gè)玩家并不知道對(duì)方選擇的動(dòng)作，因此，有必要研究MDP下的策略梯度定理對(duì)于TZMG是否適用.

另一方面，TZMG求解的是一個(gè)最大最小化問(wèn)題

最優(yōu)策略為期望回報(bào)處于鞍點(diǎn)時(shí)的聯(lián)合策略.而MDP求解的是一個(gè)最大化問(wèn)題

最優(yōu)策略為期望回報(bào)最大時(shí)的策略.最大化問(wèn)題只要使用梯度上升算法，一定可找到一個(gè)局部極大值，而最大最小化問(wèn)題更復(fù)雜，直接使用梯度上升下降算法不一定能收斂到鞍點(diǎn).為了解決這個(gè)問(wèn)題，本文使用額外梯度算法求解鞍點(diǎn).

2 兩方零和馬爾科夫博弈下的策略梯度定理

考慮參數(shù)化的策略πθ和μφ，其中θ∈Rd和φ∈Rd為可調(diào)參數(shù).將聯(lián)合策略(πθ,μφ)代入期望回報(bào)Vρ(π,μ)，結(jié)合式(3)，得到關(guān)于參數(shù)θ和φ的性能指標(biāo)函數(shù)：

J(θ,φ)=Vρ(πθ,μφ)=Eπθ,μφ[G(τ)].

(6)

由式(5)可知，TZMG問(wèn)題可轉(zhuǎn)化為最大最小化問(wèn)題:

(7)

采用基于梯度的方法(如梯度上升下降算法、額外梯度算法等)求解最大最小化問(wèn)題(7)的前提是：在狀態(tài)轉(zhuǎn)移及獎(jiǎng)勵(lì)生成的概率分布和初始狀態(tài)的概率分布未知時(shí)，實(shí)現(xiàn)用玩家與環(huán)境交互的采樣數(shù)據(jù)估計(jì)指標(biāo)函數(shù)J(θ,φ)關(guān)于參數(shù)θ和φ的梯度?θJ(θ,φ)∈Rd和?φJ(rèn)(θ,φ)∈Rd.

文獻(xiàn)[20]將對(duì)方策略看作環(huán)境不確定性的一部分，進(jìn)而給出關(guān)于己方策略參數(shù)的策略梯度估計(jì)方法，這本質(zhì)上還是基于MDP的策略梯度定理.本文給出針對(duì)TZMG的策略梯度定理的理論證明，該定理是利用采樣數(shù)據(jù)估計(jì)策略梯度的理論基礎(chǔ).

定理1對(duì)于兩方零和馬爾科夫博弈問(wèn)題和參數(shù)化的聯(lián)合隨機(jī)策略(πθ,μφ)，式(6)定義的指標(biāo)函數(shù)J(θ,φ)關(guān)于參數(shù)θ和φ的梯度分別為

(8)

證明由式(6)可得

?θJ(θ,φ)=

?θEπθ,μφ[G(τ)]=

Eπθ,μφ[?θlnPr(τ|πθ,μφ)G(τ)].

(9)

給定玩家的聯(lián)合策略(πθ,μφ)，產(chǎn)生軌跡τ的概率為

Pr(τ|πθ,μφ)=

(10)

由式(10)可得

lnPr(τ|πθ,μφ)=

在上式中，ρ(S0)、P(St+1,Rt|St,At,Bt)、μφ(Bt|St)都與參數(shù)θ無(wú)關(guān)，因此

將上式代入式(9)，可得

同理可得

證畢.

3 基于額外梯度的REINFORCE算法

注意到式(8)求期望的部分并不包含狀態(tài)轉(zhuǎn)移及獎(jiǎng)勵(lì)生成的概率分布P和初始狀態(tài)的概率分布ρ，因此可使用采樣數(shù)據(jù)的均值估計(jì)期望.假設(shè)收集到一個(gè)軌跡集合

D∶={τi}i=1,2,…,N，

其中每條軌跡都是在當(dāng)前參數(shù)(θ,φ)確定的策略(πθ,μφ)下采樣得到，那么指標(biāo)函數(shù)J(θ,φ)關(guān)于參數(shù)θ和φ的梯度?θJ(θ,φ)和?φJ(rèn)(θ,φ)可估計(jì)如下：

?θJ(θ,φ)≈

?φJ(rèn)(θ,φ)≈

得到J(θ,φ)關(guān)于參數(shù)θ和φ的梯度估計(jì)后，就可利用基于梯度的方法求解最大最小化問(wèn)題.簡(jiǎn)單的方法為梯度上升下降算法，即每次更新參數(shù)時(shí)，沿著梯度?θJ(θ,φ)上升的方向更新參數(shù)θ的值，而沿著梯度?φJ(rèn)(θ,φ)下降的方向更新參數(shù)φ的值.

然而，即使對(duì)于簡(jiǎn)單的最大最小化問(wèn)題——凸凹最大最小化問(wèn)題(指標(biāo)函數(shù)是關(guān)于最大化參數(shù)的凸函數(shù)，關(guān)于最小化參數(shù)的凹函數(shù))，梯度上升下降算法也無(wú)法保證能收斂到指標(biāo)函數(shù)的鞍點(diǎn).例如，考慮最大最小化問(wèn)題

其中x∈Rd,y∈Rd，顯然中心處的原點(diǎn)是該問(wèn)題的鞍點(diǎn).利用梯度上升下降算法，(x,y)的軌跡是發(fā)散的，如圖4(a)所示，圖中的“五角星”為軌跡的起點(diǎn).而利用額外梯度算法，能收斂到該問(wèn)題的鞍點(diǎn)，如圖4(b)所示.相比梯度上升下降算法，每次迭代，額外梯度算法增加一步外推(Extrapolation)點(diǎn)的計(jì)算，使用外推點(diǎn)的梯度完成當(dāng)前參數(shù)的更新.

(a)梯度上升下降算法 (b)額外梯度算法

額外梯度算法求解最大最小化問(wèn)題(7)的參數(shù)更新為

(11)

其中α為更新步長(zhǎng).

如果J(θ,φ)是關(guān)于θ的凸函數(shù)且關(guān)于φ的凹函數(shù)，額外梯度算法(式(11))可收斂到J(θ,φ)的鞍點(diǎn)[23].如果J(θ,φ)是非凸非凹的，且滿(mǎn)足Minty變分不等式，那么額外梯度算法(式(11))也可收斂到J(θ,φ)的鞍點(diǎn)[24].但是最大最小化問(wèn)題(7)的解在什么條件下滿(mǎn)足Minty變分不等式目前依然是一個(gè)未解決的問(wèn)題.

基于額外梯度的REINFORCE算法的偽代碼見(jiàn)算法1.盡管該算法的收斂性目前沒(méi)有理論上的嚴(yán)格證明，但是第5節(jié)的仿真實(shí)驗(yàn)表明該算法可求解得到近似納什均衡的聯(lián)合策略.

算法1EG-R

輸入初始策略參數(shù)θ，φ

fori=1,2,…Ido

在策略(πθ,μφ)下,收集博弈軌跡集合

D∶={τi}i=1,2,…,N

計(jì)算策略梯度?θJ(θ,φ)和?φJ(rèn)(θ,φ)的估計(jì)值

D∶={τi}i=1,2,…,N

更新策略參數(shù)θ和φ

end for

4 實(shí)驗(yàn)及結(jié)果分析

4.1 實(shí)驗(yàn)設(shè)置和評(píng)估指標(biāo)

本文采用DeepMind開(kāi)發(fā)的open_spiel平臺(tái)上的兩玩家同時(shí)移動(dòng)博弈游戲Oshi_Zumo驗(yàn)證EG-R算法.這款游戲是完全信息同時(shí)移動(dòng)的零和博弈游戲，一輪博弈往往需要經(jīng)過(guò)多步博弈才能分出勝負(fù).游戲規(guī)則如下：有2K+1個(gè)格子一維排列，編號(hào)1，2，…，2K+1，在第K+1個(gè)格子上有一面旗幟，一輪博弈中玩家1和玩家2的每步博弈結(jié)果會(huì)控制旗幟的移動(dòng).玩家1和玩家2初始時(shí)各有N枚硬幣，每一步玩家1和玩家2同時(shí)出硬幣，記為M1和M2，然后對(duì)比M1和M2的大小.若M1>M2，旗幟向右移動(dòng)一個(gè)格子；若M1

Oshi-Zumo游戲的狀態(tài)由3部分組成：玩家1的剩余硬幣數(shù)、玩家2的剩余硬幣數(shù)、旗幟的位置.旗幟的位置由格子的編號(hào)表示，當(dāng)從左移出第1個(gè)格子后，旗幟位置為0，當(dāng)從右移出第2K+1個(gè)格子后，旗幟位置為2K+2.玩家的動(dòng)作就是出幣數(shù).Oshi-

Zumo游戲在參數(shù)確定情況下，初始狀態(tài)是確定的.在本文的仿真研究中，Oshi-Zumo游戲的參數(shù)設(shè)置如下：初始幣數(shù)N=6,格子規(guī)模K=1,最小出幣數(shù)為0.

本文選擇2個(gè)對(duì)比算法：基于值函數(shù)的算法(Minimax-Q)和基于策略梯度的算法(梯度上升下降算法).這兩個(gè)對(duì)比算法和本文的EG-R超參數(shù)設(shè)置保持一致，更新次數(shù)設(shè)為50 000，每次更新的采樣局?jǐn)?shù)設(shè)為300，學(xué)習(xí)率α設(shè)為0.9.折扣因子λ設(shè)為1.

梯度上升下降算法和EG-R都是基于策略梯度的算法，玩家的策略采用直接參數(shù)化的方式.玩家在狀態(tài)s下的策略參數(shù)θs∈R|As|和φs∈R|Bs|可構(gòu)成一個(gè)參數(shù)向量，其中，|As|和|Bs|分別表示玩家1和玩家2在狀態(tài)s下的合法動(dòng)作個(gè)數(shù).玩家1和玩家2在狀態(tài)s上的策略為:

(12)

其中，[·]a表示在狀態(tài)s下的所有合法動(dòng)作依次按照方括號(hào)內(nèi)的公式計(jì)算得到的向量,θ和φ的初始值全為0，即初始策略服從均勻分布.

Minimax-Q是基于值函數(shù)的算法，Q值函數(shù)采用直接參數(shù)化的方式.Q值函數(shù)在狀態(tài)s下的參數(shù)q(s,·,·)∈R|As|×|Bs|可構(gòu)成一個(gè)參數(shù)矩陣.value[q(s,·,·)]表示以q(s,·,·)為收益矩陣的矩陣博弈的最優(yōu)值，定義如下:

(13)

式(13)可采用線(xiàn)性規(guī)劃方法求解.求解式(13)可得到策略參數(shù)θs、φs、value[q(s,·,·)]，再通過(guò)式(12)得到玩家在狀態(tài)s下的策略.Q值函數(shù)的更新公式如下：

q(St,At,Bt)=(1-α)q(St,At,Bt)+

α(Rt+λ·value[q(St+1,·,·)]).

本文采用常用的納什收斂指標(biāo)評(píng)價(jià)聯(lián)合策略的性能.給定聯(lián)合策略(π,μ)，納什收斂指標(biāo)為[25]：

NashConv(π,μ)=Vρ(πb,μ)+Vρ(π,μb).

其中，πb表示玩家1在給定玩家2策略μ情況下的最佳響應(yīng)策略，μb同理.本文求解的是近似最佳響應(yīng)策略，固定對(duì)手的策略，對(duì)玩家進(jìn)行訓(xùn)練，直到玩家的勝率達(dá)到95%或策略參數(shù)的更新次數(shù)達(dá)到5 000次.給定對(duì)手玩家策略下，最佳響應(yīng)策略保證玩家的回報(bào)最大，需要注意的是,最佳響應(yīng)策略并不是唯一的.當(dāng)

NashConv(π,μ)=0

時(shí)，聯(lián)合策略(π,μ)達(dá)到納什均衡；當(dāng)

NashConv(π,μ)<ε, ?ε>0

時(shí)，聯(lián)合策略為近似納什均衡.

4.2 實(shí)驗(yàn)結(jié)果對(duì)比

3種算法均收集10組實(shí)驗(yàn)的評(píng)估數(shù)據(jù)，10組實(shí)驗(yàn)的納什收斂指標(biāo)均值如圖5所示，圖中陰影部分表示10組實(shí)驗(yàn)納什收斂指標(biāo)的離散程度，陰影的上下界分別由均值加減標(biāo)準(zhǔn)差得到.這3種算法納什收斂指標(biāo)的方差如圖6所示.

(a)EG-R

由圖5(a)可看出，隨著更新次數(shù)的增加，EG-R納什收斂指標(biāo)的均值整體呈下降趨勢(shì)，當(dāng)更新次數(shù)達(dá)到50 000次左右時(shí)，納什收斂指標(biāo)的均值接近于0，此時(shí)聯(lián)合策略達(dá)到近似納什均衡.由于使用REINFORCE，所以不同實(shí)驗(yàn)組的方差較大，由圖6可知，EG-R的最大方差為0.403，在40 000次更新之前，方差的波動(dòng)較大，但在40 000次更新之后，方差開(kāi)始明顯減小，并最終趨向于0.

由圖5(b)可看出，梯度上升下降算法的納什收斂指標(biāo)的均值在1.0～1.7之間，無(wú)明顯的下降趨勢(shì)，由此可見(jiàn)，梯度上升下降算法無(wú)法得到近似納什均衡的聯(lián)合策略.梯度上升下降算法使用的也是REINFORCE，由圖6可知，不同實(shí)驗(yàn)組的方差很大，呈現(xiàn)增大的趨勢(shì)，最大方差為0.56.

圖6 3種算法的納什收斂指標(biāo)方差曲線(xiàn)

從圖6可看出Minimax-Q的方差很小，波動(dòng)也很小，最大方差為0.002，同時(shí)從圖5(c)可看出，Minimax-Q的納什收斂指標(biāo)有輕微的下降趨勢(shì)，但在50 000次更新下，距離下降到0還很遙遠(yuǎn).由此可見(jiàn)，在限定更新次數(shù)的條件下，Minimax-Q無(wú)法得到近似納什均衡的聯(lián)合策略.

分析3種算法的納什收斂指標(biāo)的均值和方差的變化趨勢(shì)可看出，EG-R具有顯著的優(yōu)越性，具體體現(xiàn)在EG-R可在更少的更新次數(shù)下得到近似納什均衡的聯(lián)合策略，方差在后期明顯趨向于0.

EG-R在訓(xùn)練過(guò)程中的方差較大，是因?yàn)槭褂肦EINFORCE.對(duì)于MDP，REINFORCE的方差也較大，廣泛認(rèn)可的一種解決方案是使用帶基線(xiàn)的RE-INFORCE.沿著這個(gè)思路，本文認(rèn)為對(duì)于TZMG，帶基線(xiàn)的EG-R的方差也會(huì)小于EG-R.為此進(jìn)行如下預(yù)實(shí)驗(yàn)：使用帶基線(xiàn)的EG-R和EG-R分別進(jìn)行10組實(shí)驗(yàn)，游戲參數(shù)和算法超參數(shù)的設(shè)置見(jiàn)4.1節(jié).然后，選取其中5個(gè)檢查點(diǎn)(檢查點(diǎn)的更新次數(shù)為10 000次更新的整數(shù)倍)的聯(lián)合策略進(jìn)行評(píng)估，得到這兩種算法的納什收斂指標(biāo)的均值和方差，如圖7所示.需要注意的是，EG-R的基線(xiàn)可以是任意函數(shù)，但不能和玩家的策略相關(guān)，本文選取的基線(xiàn)是歷史軌跡回報(bào)的滑動(dòng)平均.

由圖7可看出，帶基線(xiàn)的EG-R在前4個(gè)檢查點(diǎn)處的方差小于EG-R，而在第5個(gè)檢查點(diǎn)處略大于EG-R.由圖5(a)可知，EG-R的納什收斂指標(biāo)越接近0，方差也越接近0.在第5個(gè)檢查點(diǎn)處，帶基線(xiàn)的EG-R的納什收斂指標(biāo)均值在0.2左右，而EG-R的納什收斂指標(biāo)均值在0左右，所以在第5個(gè)檢查點(diǎn)處帶基線(xiàn)的EG-R的方差略大于EG-R.總之，帶基線(xiàn)的EG-R確實(shí)可減小方差.

(a)方差 (b)均值

4.3 近似納什均衡解分析

EG-R的10組實(shí)驗(yàn)得到的聯(lián)合策略都達(dá)到近似納什均衡，但會(huì)收斂到兩個(gè)不同的近似納什均衡解(記為NE解1和NE解2).限于篇幅，本文僅給出NE解1和NE解2的聯(lián)合策略在10個(gè)狀態(tài)上的表現(xiàn)，展示這兩種不同聯(lián)合策略的差異，具體如表1和表2所示.表中第2行的數(shù)字0～6表示玩家的動(dòng)作，即玩家投出的硬幣數(shù)，第1列表示狀態(tài)，計(jì)算玩家在該狀態(tài)下選擇對(duì)應(yīng)動(dòng)作的概率，-表示在該狀態(tài)下該玩家的合法動(dòng)作不包括該動(dòng)作.在一個(gè)狀態(tài)下，玩家選擇合法動(dòng)作的概率之和為1，這些概率就是玩家在該狀態(tài)下的策略.

表1 部分狀態(tài)下NE解1的聯(lián)合策略

表2 部分狀態(tài)下NE解2的聯(lián)合策略

使用NE解1和NE解2的聯(lián)合策略各自進(jìn)行多次博弈，發(fā)現(xiàn)NE解1的聯(lián)合策略的博弈結(jié)果幾乎全是平局，輸局和贏局很少.而NE解2的聯(lián)合策略的博弈結(jié)果幾乎全是輸局和贏局，平局很少，且輸贏局?jǐn)?shù)幾乎相等.

雖然NE解1和NE解2的聯(lián)合策略的博弈結(jié)果不同，但是期望回報(bào)幾乎相等.NE解1和NE解2的玩家策略都是混合策略，即玩家在某個(gè)狀態(tài)下以某個(gè)概率分布選擇動(dòng)作，若在某個(gè)狀態(tài)下確定性地選擇某個(gè)動(dòng)作，為純策略.混合策略的近似納什均衡相對(duì)不穩(wěn)定，因?yàn)樗赊D(zhuǎn)換為它的混合均衡策略中任意正概率的策略，即純策略，也可轉(zhuǎn)換為這些純策略的任意概率組合[26].因此，相對(duì)純策略，混合策略的求解更困難.

為了進(jìn)一步驗(yàn)證EG-R訓(xùn)練得到的聯(lián)合策略是近似納什均衡策略，設(shè)計(jì)12組實(shí)驗(yàn)，游戲參數(shù)和算法超參數(shù)的設(shè)置見(jiàn)4.1節(jié).

在每組實(shí)驗(yàn)中，玩家1和玩家2以選定的策略進(jìn)行1 000局博弈，記錄每局的回報(bào)，然后使用1 000局回報(bào)的均值作為期望回報(bào)的估計(jì)值.玩家可選擇的策略有4種：EG-R訓(xùn)練得到的NE解1和NE解2的聯(lián)合策略、兩種隨機(jī)策略(高斯分布策略和均勻分布策略).高斯分布策略表示在每個(gè)狀態(tài)下玩家選取合法動(dòng)作的概率服從標(biāo)準(zhǔn)正態(tài)分布.均勻分布策略表示在每個(gè)狀態(tài)下玩家選取動(dòng)作的概率服從均勻分布，即在每個(gè)狀態(tài)下，玩家等概率選擇合法動(dòng)作.

4種策略交叉博弈的回報(bào)均值如表3所示.由表可看出，當(dāng)玩家1和玩家2都使用NE解1的策略時(shí)，回報(bào)均值為0.當(dāng)玩家1使用NE解1的策略，玩家2使用均勻分布策略或高斯分布策略時(shí)，回報(bào)均值大于0.當(dāng)玩家1使用均勻分布策略或高斯分布策略，玩家2使用NE解1的策略時(shí)，回報(bào)均值小于0.根據(jù)鞍點(diǎn)不等式(4)可知，NE解1的聯(lián)合策略達(dá)到近似納什均衡.同理可知，NE解2的聯(lián)合策略也達(dá)到近似納什均衡.當(dāng)玩家1和玩家2分別選擇NE解1或NE解2的策略進(jìn)行博弈時(shí)，回報(bào)均值都在0附近，這說(shuō)明雖然NE解1和NE解2的聯(lián)合策略不同，但是期望回報(bào)幾乎相等.

表3 4種策略交叉博弈的回報(bào)均值

4.4 不同難度等級(jí)實(shí)驗(yàn)結(jié)果對(duì)比

為了驗(yàn)證EG-R的魯棒性，本文選擇3種不同難度等級(jí)的Oshi-Zumo游戲進(jìn)行實(shí)驗(yàn).不同難度等級(jí)的區(qū)別體現(xiàn)在：難度等級(jí)越高，游戲的狀態(tài)空間和玩家的動(dòng)作空間越大，玩家的聯(lián)合策略越難收斂.不同難度等級(jí)的Oshi-Zumo游戲參數(shù)如表4所示，EG-R的超參數(shù)設(shè)置見(jiàn)4.1節(jié).

表4 3種難度等級(jí)的Oshi-Zumo游戲參數(shù)

EG-R在3種游戲難度等級(jí)上的納什收斂指標(biāo)如圖8所示.由圖可看出，在難度等級(jí)1上，納什收斂指標(biāo)的均值接近于0，聯(lián)合策略達(dá)到近似納什均衡.在難度等級(jí)2和難度等級(jí)3上，納什收斂指標(biāo)的均值都呈現(xiàn)明顯的下降趨勢(shì)，但是限于更新次數(shù)還未下降到0.綜上所述，EG-R在更大的狀態(tài)空間和動(dòng)作空間下，也可取得較好的效果.

圖8 EG-R在3種游戲難度等級(jí)上的納什收斂指標(biāo)均值曲線(xiàn)

5 結(jié)束語(yǔ)

為了在TZMG下實(shí)現(xiàn)同時(shí)訓(xùn)練并更新玩家的策略，本文首先將策略梯度定理推廣到TZMG，然后提出基于額外梯度的REINFORCE算法(EG-R).在Oshi-Zumo游戲中，對(duì)比分析EG-R的優(yōu)越性，并進(jìn)一步在不同難度等級(jí)的Oshi-Zumo游戲中驗(yàn)證EG-R的魯棒性.但是，由于REINFORCE本身的缺點(diǎn)，不同實(shí)驗(yàn)組的方差較大，如何改進(jìn)算法以減小方差是今后的一個(gè)研究方向.借鑒在MDP下的經(jīng)驗(yàn)，優(yōu)化基線(xiàn)函數(shù)或引入行動(dòng)家-評(píng)論家框架會(huì)是優(yōu)先考慮的解決方案.另外將著重于EG-R收斂性的理論證明.