張人文,賴 俊,陳希亮

(陸軍工程大學(xué) 指揮控制工程學(xué)院,江蘇 南京 210007)

0 引 言

近年來,強(qiáng)化學(xué)習(xí)(Reinforcement Learning)[1]逐漸成為人工智能的熱門研究領(lǐng)域。智能體(Agent)通過采取不同的動(dòng)作(Action)與環(huán)境進(jìn)行交互[2],改變自身狀態(tài)(State),并獲得獎(jiǎng)勵(lì)(Reward)。通過引導(dǎo)智能體獲得更大收益的方式驅(qū)使智能體進(jìn)行學(xué)習(xí),完成任務(wù)。2017年,以強(qiáng)化學(xué)習(xí)算法為核心的AlphaGo戰(zhàn)勝圍棋世界冠軍李世石,引發(fā)人們的廣泛關(guān)注。隨著研究深入,更符合現(xiàn)實(shí)需求的多智能體強(qiáng)化學(xué)習(xí)(Multi-agent Reinforcement Learning)獲得人們重視,已在決策支持、智能推薦、即時(shí)戰(zhàn)略游戲等領(lǐng)域取得進(jìn)展。

博弈訓(xùn)練方式的運(yùn)用為強(qiáng)化學(xué)習(xí)技術(shù)進(jìn)一步賦能。采用種群訓(xùn)練的“FTW agent”[3]在《雷神之錘III競(jìng)技場(chǎng)》中達(dá)到人類玩家水平;采用聯(lián)盟訓(xùn)練的AlphaStar[4]在《星際2》中戰(zhàn)勝人類頂尖玩家;采用自我博弈訓(xùn)練的OpenAI Five[5]在《Dota 2》中戰(zhàn)勝世界冠軍,在即時(shí)戰(zhàn)略游戲中擊敗世界冠軍。

該文對(duì)多智能體強(qiáng)化學(xué)習(xí)基本理論、博弈基本理論、多智能體強(qiáng)化學(xué)習(xí)博弈訓(xùn)練方式分類、關(guān)鍵問題和前景展望進(jìn)行綜述。其中第二節(jié)對(duì)強(qiáng)化學(xué)習(xí)基本理論、博弈基本理論進(jìn)行簡(jiǎn)要闡述;第三節(jié)結(jié)合多智能體博弈訓(xùn)練研究成果應(yīng)用對(duì)典型博弈訓(xùn)練算法進(jìn)行分類及介紹;第四節(jié)分析博弈訓(xùn)練的關(guān)鍵問題及挑戰(zhàn);第五節(jié)簡(jiǎn)要介紹現(xiàn)有部分多智能體強(qiáng)化學(xué)習(xí)博弈訓(xùn)練平臺(tái);最后對(duì)多智能體強(qiáng)化學(xué)習(xí)博弈訓(xùn)練的發(fā)展前景及展望進(jìn)行討論。

1 基本理論

本節(jié)對(duì)強(qiáng)化學(xué)習(xí)及博弈論的概念進(jìn)行闡述,介紹博弈求解方式發(fā)展歷程及博弈訓(xùn)練的基本含義。

1.1 強(qiáng)化學(xué)習(xí)基本理論

1.1.1 馬爾可夫決策過程(MDP)

MDP由多元組構(gòu)成,一般包括S,A,P,R,γ等,S表示智能體狀態(tài)空間,A表示智能體動(dòng)作空間,P為智能體狀態(tài)轉(zhuǎn)移函數(shù), 其定義為[6]:

P:S×A×S→[0,1]

(1)

P代表智能體在狀態(tài)s∈S的情況下,采用給定動(dòng)作a∈A時(shí),狀態(tài)轉(zhuǎn)移至下一狀態(tài)s'∈S的概率分布。智能體的瞬時(shí)回報(bào)函數(shù)R為:

R:S×A×S→R

(2)

R表示智能體在狀態(tài)s的情況下,采用動(dòng)作a時(shí),狀態(tài)轉(zhuǎn)移至下一狀態(tài)s'所獲得的即時(shí)回報(bào)。將所有即時(shí)回報(bào)累加,可得到智能體的總收益Rt:

(3)

式中,γ∈[0,1]是折扣系數(shù),用于平衡智能體的瞬時(shí)回報(bào)和長(zhǎng)期回報(bào)對(duì)總回報(bào)的影響[7]。

馬爾可夫決策過程中,當(dāng)智能體從一個(gè)狀態(tài)轉(zhuǎn)移到另一狀態(tài)時(shí),只需要考慮當(dāng)前的狀態(tài)與行為,不需要考慮以往所采取的行為以及所處的環(huán)境[8]。

1.1.2 強(qiáng)化學(xué)習(xí)

強(qiáng)化學(xué)習(xí)是智能體通過與環(huán)境交互以期獲得最大收益而采取的學(xué)習(xí)方式。智能體通過采取最優(yōu)的動(dòng)作與環(huán)境進(jìn)行交互,獲得回報(bào),進(jìn)而學(xué)習(xí)到指導(dǎo)問題解決的最佳策略。通俗而言,強(qiáng)化學(xué)習(xí)即智能體在環(huán)境中不斷“試錯(cuò)”,以最大化回報(bào)為驅(qū)動(dòng)力,在試錯(cuò)過程中逐漸適應(yīng)環(huán)境,達(dá)成學(xué)習(xí)的目的。

智能體與環(huán)境的交互過程可以由三個(gè)要素來描述:狀態(tài)s、動(dòng)作a、獎(jiǎng)勵(lì)r。智能體根據(jù)初始狀態(tài)s,執(zhí)行動(dòng)作a并與環(huán)境進(jìn)行交互,獲得獎(jiǎng)勵(lì)r,轉(zhuǎn)移至下一狀態(tài)s'[9]。強(qiáng)化學(xué)習(xí)基本過程如圖1所示。

圖1 強(qiáng)化學(xué)習(xí)基本過程

智能體學(xué)習(xí)成果是獲得一個(gè)適合環(huán)境的策略π,π是智能體可能會(huì)選擇某種行為的概率[8],表示為:

π:S×A→[0,1]

(4)

策略可分為確定性策略和隨機(jī)性策略。確定性策略即智能體在不同時(shí)刻(t)或回合(episode)時(shí),遇到相同狀態(tài)均選擇某一確定的動(dòng)作。隨機(jī)性策略為一個(gè)概率分布,即為智能體輸入一個(gè)狀態(tài),輸出選擇某個(gè)動(dòng)作的概率。隨機(jī)性策略可表示為:

π(a|s)=p(at=a|st=s)

(5)

在智能體與環(huán)境交互的過程中,不斷優(yōu)化其目前使用的策略,使策略越來越好,這個(gè)過程即策略更新。策略更新在強(qiáng)化學(xué)習(xí)中迭代執(zhí)行,以期智能體能得到一個(gè)最佳策略。為了判斷智能體在某一狀態(tài)s時(shí)策略的優(yōu)劣,定義狀態(tài)值函數(shù)Vπ(s):

Vπ(s)=E[Gt|st=s,π]

(6)

同樣,為了判斷智能體在某一狀態(tài)s時(shí)執(zhí)行動(dòng)作a的優(yōu)劣,定義狀態(tài)動(dòng)作值函數(shù)Qπ(s,a):

Qπ(s,a)=E[Gt|st=s,at=a,π]

(7)

其中,Gt是智能體從當(dāng)前狀態(tài)一直到交互過程結(jié)束所獲得的總收益R,即累計(jì)回報(bào)。

在強(qiáng)化學(xué)習(xí)過程中,智能體通過對(duì)值函數(shù)進(jìn)行評(píng)價(jià),進(jìn)而判定自身策略優(yōu)劣并加以改進(jìn)。

1.2 多智能體強(qiáng)化學(xué)習(xí)

現(xiàn)實(shí)場(chǎng)景往往有多個(gè)主體交互,多智能體系統(tǒng)(Multi-Agent System,MAS)[10]是對(duì)現(xiàn)實(shí)世界多主體交互場(chǎng)景進(jìn)行的一種建模方式。多智能體強(qiáng)化學(xué)習(xí)(Multi-Agent Reinforcement Learning,MARL)[11]是采用強(qiáng)化學(xué)習(xí)方法對(duì)多智能體系統(tǒng)進(jìn)行訓(xùn)練的人工智能方法,遵循隨機(jī)博弈(Stochastic Game,SG)[12]過程。

在多智能體強(qiáng)化學(xué)習(xí)中,智能體的動(dòng)作空間Ai(i=1,2,…,n)交互形成聯(lián)合動(dòng)作空間A:

A=A1×A2×…×An

(8)

策略、狀態(tài)轉(zhuǎn)移函數(shù)等也相應(yīng)改變。如聯(lián)合狀態(tài)轉(zhuǎn)移函數(shù),即全部智能體在執(zhí)行聯(lián)合狀態(tài)動(dòng)作a時(shí),由狀態(tài)s轉(zhuǎn)移至下一狀態(tài)s'的概率分布。智能體的聯(lián)合策略決定智能體的總回報(bào)。

多智能體強(qiáng)化學(xué)習(xí)算法可分為完全合作型、完全競(jìng)爭(zhēng)型和混合型[13],采用多智能體強(qiáng)化學(xué)習(xí)能完成復(fù)雜任務(wù),提升算法效率[6]。

1.3 博弈論

博弈論(Game Theory)[14]是對(duì)存在利益關(guān)系的理性行為實(shí)體之間的沖突或合作模型進(jìn)行形式化研究的一門學(xué)科[15]。博弈論的形式化表述一般由玩家(Player)、策略(Strategy)、收益(Payoff)、理性(Rationality)等要素構(gòu)成。

博弈論有多種分類。根據(jù)博弈過程玩家是否同時(shí)決策,可分為標(biāo)準(zhǔn)式博弈(靜態(tài)博弈)、拓展式博弈(動(dòng)態(tài)博弈);根據(jù)玩家對(duì)博弈過程信息是否了解,可分為完美信息博弈和不完美信息博弈等。

對(duì)于一般標(biāo)準(zhǔn)式博弈,進(jìn)行如下形式化定義:

(9)

a-i=(a1,…,ai-1,ai+1,…,an)

(10)

根據(jù)理性假設(shè),每名玩家在博弈中都試圖通過尋求針對(duì)其他玩家的最優(yōu)響應(yīng)(Best Response)來獲得更高收益。若當(dāng)每名玩家均采用最優(yōu)響應(yīng)時(shí),任何一方單獨(dú)改變策略都不能使自己獲得更高的收益,此時(shí)博弈達(dá)到一種穩(wěn)定的局面,即納什均衡(Nash Equilibrium)。

納什均衡是博弈論的重要理論基礎(chǔ),納什證明了標(biāo)準(zhǔn)式博弈中均衡點(diǎn)的存在[16],為博弈論的應(yīng)用開創(chuàng)了理論基礎(chǔ)。其形式化定義如下:

(11)

1.4 博弈求解方式的發(fā)展歷程

納什均衡提出后,求解納什均衡成為研究的熱點(diǎn)。自我博弈的使用在精神上類似于虛擬博弈[5]。

1951年,Brown[17]提出虛擬博弈(Fictitious Play,FP)的概念。Genugten[18]提出弱化形式的虛擬游戲(Weakened Fictitious Play,WFP),獲得近似最優(yōu)響應(yīng),加快收斂速度。Heinrich[19]提出Full-width extensive-form fictitious play(XSP)和Fictitious Self-Play(FSP),將虛擬博弈由標(biāo)準(zhǔn)式博弈推廣到擴(kuò)展式博弈。Heinrich等人[20]提出Neural Fictitious Self-Play (NFSP),是第一個(gè)在自我博弈中收斂到近似納什均衡的深度強(qiáng)化學(xué)習(xí)方法。另一方面,McMahan等人[21]提出基于博弈論的Double Oracle(DO)算法,在此基礎(chǔ)上,Lanctot等人[22]提出Policy Space Response Oracles (PSRO)算法,提升了博弈求解水平。Balduzzi 等人[23]提出PSRO-rectified Nash response(PSRO-rN),進(jìn)一步提升了納什均衡下策略的改進(jìn)機(jī)率。Muller等人[24]提出α-PSRO算法,使用α-Rank[25]擴(kuò)展PSRO的理論基礎(chǔ),避免求解納什均衡面臨的均衡選擇問題[26]。McAleer等人[27]提出Pipeline PSRO(P2SRO),通過維護(hù)分層管道來并行化 PSRO。

1.5 博弈訓(xùn)練

博弈訓(xùn)練,是在對(duì)抗性環(huán)境中,智能體通過和當(dāng)前的自己及自身歷史版本進(jìn)行博弈對(duì)抗的訓(xùn)練方式。一方面,如何在數(shù)據(jù)不足或有限的情況下,訓(xùn)練出符合要求的智能體,需要尋找一種能夠平衡訓(xùn)練數(shù)據(jù)規(guī)模與智能體訓(xùn)練效果的方法。另一方面,如何在復(fù)雜場(chǎng)景中訓(xùn)練智能體獲得更優(yōu)的策略,突破策略循環(huán),博弈訓(xùn)練開辟了一個(gè)新的途徑。

2 博弈訓(xùn)練方式分類

根據(jù)基礎(chǔ)原理的不同,可將博弈訓(xùn)練分為基于自我博弈的訓(xùn)練和基于博弈論的訓(xùn)練;根據(jù)從對(duì)手策略池中不同“挑選和應(yīng)對(duì)對(duì)手”方法,基于自我博弈的訓(xùn)練又可劃分為自我博弈、種群訓(xùn)練和聯(lián)盟訓(xùn)練。

2.1 自我博弈訓(xùn)練

自我博弈(Self-Play,SP)是在多智能體訓(xùn)練的背景下出現(xiàn)的一種訓(xùn)練方案[28]。自我博弈訓(xùn)練的本質(zhì)是通過自身行為模擬產(chǎn)生數(shù)據(jù),并利用數(shù)據(jù)進(jìn)行學(xué)習(xí)和提升[29]。自我博弈的實(shí)證成功挑戰(zhàn)了經(jīng)典觀點(diǎn),即專家對(duì)手是獲得良好表現(xiàn)所必需的[30]。

Samuel[31]在跳棋程序中設(shè)計(jì)了自我對(duì)戰(zhàn),發(fā)現(xiàn)這種模式早期特別好。Epstein[32]指出,自我博弈訓(xùn)練的程序有條不紊地確定和探索自己在搜索空間中的路徑。Tesauro等人[33]設(shè)計(jì)了TD-Gammon,在玩西洋雙陸棋的能力上達(dá)到專家水平。在訓(xùn)練AlphaGo[34]的策略網(wǎng)絡(luò)時(shí),將當(dāng)前正在訓(xùn)練的策略網(wǎng)絡(luò)Pρ和從對(duì)手池中隨機(jī)抽樣的對(duì)手Pρ-進(jìn)行對(duì)弈。AlphaGo Zero[35]的訓(xùn)練數(shù)據(jù)全部來自于自我博弈訓(xùn)練。Kaplanis等人[36]指出,每個(gè)智能體的經(jīng)驗(yàn)分布會(huì)受到對(duì)手不斷變化的策略影響。Balduzzi等人[23]描述了自我博弈訓(xùn)練算法,指出自我博弈適合由傳遞博弈建模的游戲。Hernandez 等人[28]使用形式符號(hào)定義了SP的通用框架,在該框架下統(tǒng)一了流行的SP算法的定義,進(jìn)一步指出自我博弈表現(xiàn)出周期性的策略演變[37]。

2.1.1 自我博弈訓(xùn)練算法基本框架

Balduzzi等人[23]描述了一種自我博弈訓(xùn)練算法。其中oracle表示,從上帝視角,oracle能夠找到一個(gè)智能體Vt',其能力比Vt更好。該定義描述,通過自我博弈訓(xùn)練,Vt+1的能力均比Vt要好,如算法1描述:

算法1 Self-Play算法。

輸入:智能體V1

對(duì)t=1,2,…,T執(zhí)行以下循環(huán):

智能體Vt+1←oracle(智能體Vt',φvt(·))

結(jié)束循環(huán)

輸出:智能體VT+1

Hernandez等人[37]定義了通用的自我博弈訓(xùn)練框架,描述了所有自我博弈訓(xùn)練方案的最小結(jié)構(gòu),同時(shí)未對(duì)策略交互的環(huán)境做出任何假設(shè)。

πο:πο∈ai;表示策略集(menagerie),智能體的行為從策略集中進(jìn)行采樣,集合包括當(dāng)前的訓(xùn)練策略π,并隨著訓(xùn)練的進(jìn)行而不斷改變。

Ω:Ω∈[0,1];表示策略抽樣分布(policy sampling distribution),即策略集πο上的概率分布。

G:G∈[0,1];表示門控函數(shù)(gating function),決定是否將當(dāng)前策略π引入策略集,及哪些策略π∈πο將丟棄,如算法2描述:

算法 2:強(qiáng)化學(xué)習(xí)Self-Play算法。

輸入:環(huán)境等要素(S,A,O,P,R等);

輸入:Self-Play要素(Ω,G);

輸入:需要訓(xùn)練的策略π。

1 初始化策略集πο={π};

2 對(duì)e=0,1,2…執(zhí)行以下循環(huán):

3 根據(jù)策略抽樣分布Ω從πο中抽取π';

4 將π'加入π中;

5 采樣S0和O0;

6 對(duì)t=0,1,2…,直至終止,執(zhí)行以下循環(huán):

7 根據(jù)策略π及觀察Ot選擇動(dòng)作并執(zhí)行;

8 結(jié)合狀態(tài)St和動(dòng)作at,根據(jù)P得到St+1和Ot+1;

9 獲得獎(jiǎng)勵(lì)rt;

10t=t+1;

11 結(jié)束循環(huán);

12 更新π;

13 根據(jù)G決定是否將當(dāng)前策略π加入策略集πο

14 結(jié)束循環(huán)

15 輸出策略π

2.1.2 經(jīng)典自我博弈訓(xùn)練算法

經(jīng)典自我博弈訓(xùn)練算法(Naive Self-Play,NSP)是最典型的自我博弈訓(xùn)練算法,1959年Samuel在其論文中已經(jīng)使用[31],智能體每次都與最新版本的自己進(jìn)行對(duì)戰(zhàn),即智能體均在相同的最新策略的指導(dǎo)下進(jìn)行交互[37]。形式化表述如下:

(12)

此時(shí),門控函數(shù)G總是將最新版本的策略放入策略集πο中,且策略集中僅保持最新策略[37]。

G(π°,π)={π}

(13)

Samuel[31]使用經(jīng)典自我博弈方法訓(xùn)練跳棋游戲,發(fā)現(xiàn)這種模式在訓(xùn)練早期階段效果較好。Kaplanis等人[36]通過僅針對(duì)自身最新版本的自我博弈訓(xùn)練,來評(píng)估智能體的持續(xù)學(xué)習(xí)能力。通過將最終智能體與在訓(xùn)練的各個(gè)階段的模型進(jìn)行對(duì)比,發(fā)現(xiàn)智能體的能力得到了平穩(wěn)的提高。但也發(fā)現(xiàn)存在少數(shù)被擊敗的情況。

2.1.3 成長(zhǎng)式自我博弈訓(xùn)練算法

成長(zhǎng)式自我博弈訓(xùn)練(Mature Self-Play,MSP)的核心是與過去的自我對(duì)戰(zhàn)。即訓(xùn)練時(shí)將訓(xùn)練過程中產(chǎn)生的模型收集起來,加入到模型池(對(duì)手池)中,正在訓(xùn)練的智能體不僅與最新版本的自我對(duì)戰(zhàn),還采用多種抽樣方式與過去版本的模型進(jìn)行博弈對(duì)戰(zhàn)。

Bansal等人[38]發(fā)現(xiàn),智能體針對(duì)最新版本的自我進(jìn)行博弈訓(xùn)練會(huì)導(dǎo)致訓(xùn)練不平衡。相反,針對(duì)隨機(jī)舊版本對(duì)手的訓(xùn)練效果要好,可以獲得更強(qiáng)大的策略。

根據(jù)博弈訓(xùn)練時(shí)新舊模型不同采樣比例及不同采樣方式,可分為多種算法:

(1)歷史均勻訓(xùn)練法。

History Uniform Self-Play(HUSP)。即智能體在進(jìn)行博弈訓(xùn)練時(shí),以在整個(gè)歷史版本上進(jìn)行均勻隨機(jī)采樣選擇對(duì)手,使用Uniform(0,v)方法,其中v是抽樣時(shí)的模型版本總數(shù)。參考Hernandez等人[37]描述的自我博弈訓(xùn)練框架,將HUSP方法形式化描述如下:

Ω(π'|π°,π)=Uniform(0,M)

(14)

門控函數(shù)G采用確定性策略吸收新的策略。每次訓(xùn)練后,將當(dāng)前策略加入到策略集中。

G(π°,π)=π°∪{π}

(15)

Al-Shedivat等人[39]在進(jìn)行模型的預(yù)訓(xùn)練時(shí),將模型自我博弈過程中的歷史版本進(jìn)行保存,用于后期的對(duì)抗訓(xùn)練。Silver等人[34]在訓(xùn)練AlphoGO的策略網(wǎng)絡(luò)時(shí),使用當(dāng)前策略網(wǎng)絡(luò)和隨機(jī)選擇的先前策略網(wǎng)絡(luò)進(jìn)行博弈對(duì)戰(zhàn),不斷增強(qiáng)對(duì)手池的多樣性。

(2)區(qū)間均勻訓(xùn)練法。

區(qū)間均勻法是Bansal等人[38]提出的考慮對(duì)手抽樣時(shí)新舊版本占比的方法,目的是訓(xùn)練出能夠擊敗自身隨機(jī)舊版本的策略。即選取對(duì)手時(shí),不是在整個(gè)歷史版本上進(jìn)行均勻隨機(jī)采樣,而是使用Uniform(δM,M)方法,其中M是抽樣時(shí)對(duì)手池內(nèi)所含模型版本數(shù)量。δ∈[0,1]是抽樣比例的閾值。Hernandez等人[37]將該方法命名為δ-Uniform Self-Play(δ-USP),形式化描述為:

Ω(π'|π°,π)=Uniform(δM,M)

(16)

與歷史均勻訓(xùn)練法相同,門控函數(shù)G為:

G(π°,π)=π°∪{π}

(17)

Bansal等人[38]發(fā)現(xiàn),針對(duì)最新版本的對(duì)手進(jìn)行自我博弈訓(xùn)練會(huì)導(dǎo)致最差的表現(xiàn)。δ的取值對(duì)不同的場(chǎng)景較為敏感,將直接影響博弈訓(xùn)練效果。

(3)區(qū)間限制訓(xùn)練法。

受到RL方法順序數(shù)據(jù)收集方式影響,較早的對(duì)手比最近添加的對(duì)手被更加頻繁地采樣。Van Der Ree[40]發(fā)現(xiàn),訓(xùn)練期間對(duì)手策略質(zhì)量與智能體策略的潛在質(zhì)量呈現(xiàn)相關(guān)性。相對(duì)而言,早期智能體版本的性能較差,可能影響智能體最終訓(xùn)練效果。

Hernandez等人[37]提出了一種新的博弈訓(xùn)練方法,命名為δ-Limit Uniform Self-Play(δ-LUSP)。通過改進(jìn)對(duì)手抽樣分布,定義了新的采樣概率公式和歸一化算法,增加后續(xù)策略被抽樣的概率。

(18)

(19)

Hernandez等人[37]發(fā)現(xiàn)這種方法能夠降低早期版本的抽樣頻率,但仍然存在策略循環(huán)的情況。

(4)回溯比例訓(xùn)練法。

回溯比例訓(xùn)練法是前述方法的結(jié)合,博弈訓(xùn)練時(shí),以一定訓(xùn)練比例與最新的自我對(duì)戰(zhàn),其余訓(xùn)練比例與過去的版本對(duì)戰(zhàn)。回溯比例訓(xùn)練法未舍棄任何過去的對(duì)手,所有歷史對(duì)手均保存在對(duì)手池中。

該文給出回溯比例訓(xùn)練法的形式化描述:

(20)

lastestself表示與最新版本模型進(jìn)行對(duì)戰(zhàn),即經(jīng)典自我博弈;historyself表示與過去版本對(duì)手模型進(jìn)行對(duì)戰(zhàn),可根據(jù)需求選擇多種對(duì)手抽樣算法;η∈[0,1]表示lastestself在總體訓(xùn)練中所占比例。

表1 典型自我博弈訓(xùn)練方法分類

OpenAI Five進(jìn)行自我博弈訓(xùn)練時(shí),80%的訓(xùn)練場(chǎng)次采用經(jīng)典自我博弈法,20%的訓(xùn)練場(chǎng)次與過去的對(duì)手進(jìn)行對(duì)戰(zhàn),即η=0.8。Berner等人[5]指出,保持與過去的版本進(jìn)行對(duì)抗,獲得更強(qiáng)大策略的同時(shí),減小智能體忘記如何打敗過去對(duì)手的可能性。

Inseok等人[41]使用了類似方式,但以概率p選擇最近的k個(gè)版本對(duì)手,以1-p的概率選擇其余版本,p以一定的方式下降,前期較大的p有助于快速適應(yīng)對(duì)手,后期使用較小的p減輕災(zāi)難性遺忘的影響,穩(wěn)定學(xué)習(xí)過程[41]。

2.2 種群訓(xùn)練

PBT(Population Based Training)算法[42]具有高效和易并行的特點(diǎn),進(jìn)化策略類似于遺傳算法[43]。

圖2 常見的參數(shù)調(diào)優(yōu)方式

For The Win(FTW)[3]采用基于種群的自我博弈訓(xùn)練算法(Population Based Training Self-Play,PBTSF),將PBT算法與多智能體強(qiáng)化學(xué)習(xí)方法結(jié)合。智能體之間的關(guān)系是多樣的,根據(jù)訓(xùn)練效果“優(yōu)勝劣汰”,獲得水平較高的智能體并保持魯棒性。

種群內(nèi)的每個(gè)智能體使用Elo分?jǐn)?shù)[44]作為標(biāo)準(zhǔn),抽樣與其水平相近的對(duì)手,使對(duì)戰(zhàn)結(jié)果具有不確定性,當(dāng)智能體勝率低于70%時(shí),將較好智能體的參數(shù)復(fù)制至較差智能體,同時(shí)對(duì)參數(shù)進(jìn)行探索[3],這種方式思想上類似遺傳算法的選擇、交叉和變異階段。

PBTSF使整個(gè)種群內(nèi)的智能體相互對(duì)戰(zhàn),每個(gè)智能體都要進(jìn)行學(xué)習(xí),通過挑選高水平智能體并不斷進(jìn)行探索,使整個(gè)種群都變得更加智能。

2.3 聯(lián)盟訓(xùn)練

由于策略循環(huán)非傳遞性問題的限制,自我博弈訓(xùn)練常常會(huì)陷入局部最優(yōu)中,無法獲得更好的表現(xiàn)。

Vinyals等人[4]為名為AlphaStar的星際爭(zhēng)霸AI設(shè)計(jì)了一種新的博弈訓(xùn)練算法——聯(lián)盟訓(xùn)練(League Training),旨在解決自我博弈訓(xùn)練中常見的循環(huán)問題,并整合各種策略[4]。對(duì)手抽樣方面,Vinyals等人[4]設(shè)計(jì)了優(yōu)先虛擬自我博弈算法(Prioritized Fictitious Self-Play,PFSP),PFSP使用了新的抽樣匹配機(jī)制:

(21)

上式含義為:給定一個(gè)正在訓(xùn)練的智能體A,從對(duì)手池C中采樣對(duì)手B的概率為p。式中,f:[0,1]→[0,∞)是權(quán)重函數(shù),Vinyals等人[4]設(shè)計(jì)了fhard(x)和fvar(x)兩種具體的函數(shù):

fhard(x)=(1-x)2

(22)

fvar(x)=x(1-x)

(23)

fhard(x)是PFSP的默認(rèn)式,智能體專注于較難戰(zhàn)勝的對(duì)手。為了避免陷入只與最難對(duì)手對(duì)戰(zhàn)的循環(huán),PFSP還提出另外一種形式fvar(x),使智能體關(guān)注與自己水平相近的對(duì)手。

聯(lián)盟由三種不同類型的智能體組成,包括主智能體(Main agents)、主利用者(Main exploiters)和聯(lián)盟利用者(League exploiters)[4]。主智能體是最終需要的智能體,采用混合策略進(jìn)行對(duì)手采樣,且不會(huì)被重置。主利用者的目標(biāo)是發(fā)現(xiàn)主智能體的缺陷。打敗智能體了解的對(duì)手是不夠的,培養(yǎng)更好的對(duì)手也很重要,他們表現(xiàn)出智能體不知道的行為[23]。聯(lián)盟利用者的目標(biāo)是發(fā)現(xiàn)整個(gè)聯(lián)盟的弱點(diǎn),使用PFSP在聯(lián)盟中抽樣對(duì)手進(jìn)行訓(xùn)練,采用一定的規(guī)則被重置。

星際爭(zhēng)霸指揮官(StarCraft Commander,SCC)[45]也采用了聯(lián)盟訓(xùn)練方法。Wang等人[45]設(shè)計(jì)了智能體分支(Agent branching),使用當(dāng)前主智能體初始化新的主利用者,而不使用監(jiān)督學(xué)習(xí)的參數(shù)。Han等人[46]設(shè)計(jì)了TStarBot-X,采用多元化聯(lián)盟訓(xùn)練(Diversified League Training ,DLT),豐富了聯(lián)盟的多樣性。

2.4 策略空間響應(yīng)預(yù)言機(jī)

基于博弈論的博弈訓(xùn)練方面,Lanctot等人[22]定義了策略空間響應(yīng)預(yù)言機(jī)(Policy Space Response Oracle,PSRO)算法,統(tǒng)一了多智能體訓(xùn)練的博弈論算法。

PSRO算法是雙預(yù)言機(jī)(Double Oracle,DO)算法[21]的延伸,是基于博弈論的博弈訓(xùn)練方式,通過迭代生成相對(duì)于現(xiàn)有策略單調(diào)更強(qiáng)的策略解決博弈訓(xùn)練問題。DO算法根據(jù)對(duì)手歷史策略求出納什均衡,采取最優(yōu)響應(yīng),若當(dāng)前最優(yōu)響應(yīng)已在策略空間中,則算法終止,否則將此最優(yōu)響應(yīng)作為新的策略加入策略空間,繼續(xù)迭代至終止[47]。

圖3 Double Oracle算法示意圖

PSRO算法迭代進(jìn)行以下循環(huán):在當(dāng)前策略集上定義元博弈(meta-game),通過使用元求解器獲得元博弈最優(yōu)響應(yīng),每個(gè)博弈訓(xùn)練輪次加入新的策略(通過“Oracle”獲得),近似最優(yōu)響應(yīng)不斷提升。開始時(shí)僅有單個(gè)策略[22],最終得到近似最優(yōu)響應(yīng)。

與DO算法操作的“動(dòng)作”不同,PSRO算法的操作對(duì)象是“策略”,不同的元求解器以及從元求解器生成新策略的過程是PSRO算法之間的區(qū)別所在。

PSRO具有泛化性明顯的特點(diǎn),但強(qiáng)化學(xué)習(xí)訓(xùn)練可能需要很長(zhǎng)時(shí)間才能收斂到近似最優(yōu)反應(yīng)。Lanctot等人[22]提出深層認(rèn)知層次(Deep Cognitive Hierarchies,DCH)算法,提升訓(xùn)練速度,但犧牲了部分準(zhǔn)確性。Balduzzi等人[23]提出改進(jìn)版本PSROrN(Response to the rectified Nash),鼓勵(lì)智能體“放大自的優(yōu)勢(shì)并忽略自身的弱點(diǎn)”。Muller等人[24]提出α-PSRO算法,使用α-Rank[25]擴(kuò)展PSRO的理論基礎(chǔ),避免求解納什均衡的均衡選擇問題[26],在撲克中得到更快收斂的實(shí)例[24]McAleer等人[27]提出Pipeline PSRO (P2SRO),通過維護(hù)分層管道來并行化PSRO,同時(shí)具有收斂保證。Smith等人[48]提出兩種PSRO變體,減少應(yīng)用深度強(qiáng)化學(xué)習(xí)所需的訓(xùn)練量。

3 博弈訓(xùn)練的關(guān)鍵問題與挑戰(zhàn)

3.1 策略循環(huán)

在具備博弈對(duì)抗性質(zhì)的現(xiàn)實(shí)場(chǎng)景中,多智能體強(qiáng)化學(xué)習(xí)可能會(huì)遇到傳遞性場(chǎng)景和非傳遞性場(chǎng)景。以游戲場(chǎng)景為例,傳遞性游戲[23]可以通過等級(jí)或積分的高低判斷勝率;而諸如石頭剪刀布等非傳遞性游戲[23]則極有可能表現(xiàn)出策略循環(huán),為博弈訓(xùn)練帶來挑戰(zhàn)。

自我博弈對(duì)于傳遞性游戲有較好策略提升效果。Balduzzi等人[23]指出,自我博弈是一種開放式學(xué)習(xí)算法,具有傳遞性。然而,對(duì)于非傳遞性游戲,智能體的一個(gè)策略改進(jìn)并不能保證針對(duì)其他策略均改進(jìn)。

為了跳出非傳遞性場(chǎng)景中的策略循環(huán),許多研究者利用游戲環(huán)境進(jìn)行了嘗試。OpenAI Five采用并行自我博弈生成訓(xùn)練數(shù)據(jù),確保智能體對(duì)廣泛的對(duì)手具有魯棒性。聯(lián)盟訓(xùn)練[4]采用不同類型的智能體組合,在解決策略循環(huán)問題上取得了一定進(jìn)展。SCC[45]和TStarBot-X[46]對(duì)聯(lián)盟訓(xùn)練進(jìn)行了豐富和探索。Balduzzi等人[23]提出PSROrN算法,為應(yīng)對(duì)策略循環(huán)挑戰(zhàn)提供了新的思路。

3.2 策略遺忘

在多智能體強(qiáng)化學(xué)習(xí)博弈訓(xùn)練過程中,訓(xùn)練后期的模型對(duì)戰(zhàn)前期版本的模型時(shí)勝率下降,甚至被前期版本擊敗,這種策略遺忘的情況廣泛存在。

由于利用神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)新任務(wù)時(shí),需要更新相關(guān)參數(shù),但前期任務(wù)提取出來的知識(shí)也儲(chǔ)存在這些參數(shù)上,因此學(xué)習(xí)新任務(wù)時(shí),智能體會(huì)遺忘舊知識(shí)。Fedus等人[49]建立了災(zāi)難性遺忘與強(qiáng)化學(xué)習(xí)中樣本效率低下等核心問題的經(jīng)驗(yàn)聯(lián)系。Reed等人[50]構(gòu)建了多任務(wù)智能體 Gato,在更高層次解決策略遺忘問題。

3.3 策略探索

探索(Exploration)是強(qiáng)化學(xué)習(xí)的一個(gè)關(guān)鍵挑戰(zhàn),其目的是確保智能體的行為不會(huì)過早收斂到局部最優(yōu)[51]。通過博弈訓(xùn)練得到的模型,是否可以在真實(shí)的博弈環(huán)境中發(fā)揮很好的效果,取決于當(dāng)前智能體所在的環(huán)境分布與真實(shí)分布之間的差距情況。

Epstein[32]指出,在自我博弈訓(xùn)練中,不能保證智能體探索的空間是最重要的部分,并且探索的區(qū)域可能與所需要的幾乎無關(guān)。Tesauro等人[33]指出,在確定性博弈環(huán)境中,通過自我博弈訓(xùn)練的系統(tǒng)最終可能只探索狀態(tài)空間非常狹窄的部分。Inseok等人[41]指出,自我博弈得到的策略空間并不能保證對(duì)具有較大問題空間的場(chǎng)景具有足夠覆蓋率。

為了應(yīng)對(duì)探索難題,許多研究者進(jìn)行了深入的探討。Pathak等人[52]提出好奇心探索(Curiosity-driven Exploration)算法,使智能體能夠進(jìn)一步探索環(huán)境并學(xué)習(xí)有用的策略。Fortunato等人[53]提出NoisyNet算法,幫助智能體進(jìn)行有效探索。Ecoffet等人[54]提出Go-Explore 算法,記錄訪問狀態(tài),提升了探索效率。

3.4 策略突破

如何在策略提升的過程中突破策略循環(huán),是一個(gè)重要挑戰(zhàn)。首先,對(duì)于剪刀石頭布這樣完全循環(huán)的博弈場(chǎng)景而言,哪個(gè)策略更好是沒有實(shí)際意義的。其次,策略的探索和遺忘在一定程度上制約高質(zhì)量策略的獲得,同時(shí)受算法、硬件條件限制,存在現(xiàn)實(shí)困難。Czarnecki等人[55]分析了現(xiàn)實(shí)世界游戲的幾何特性,指出現(xiàn)實(shí)世界的游戲是由傳遞部分和非傳遞部分混合而成,幾何結(jié)構(gòu)類似于旋轉(zhuǎn)陀螺。

目前,研究者從設(shè)置規(guī)則、添加人類經(jīng)驗(yàn)、利用人類玩家數(shù)據(jù)等方面進(jìn)行了有益嘗試。AlphaGO使用人類專家數(shù)據(jù)進(jìn)行監(jiān)督學(xué)習(xí),而后通過自我博弈訓(xùn)練進(jìn)行改進(jìn)提升。AlphaStar[4]和SCC[45]在監(jiān)督學(xué)習(xí)中利用高質(zhì)量人類數(shù)據(jù)集進(jìn)行初始化,在強(qiáng)化學(xué)習(xí)中利用聯(lián)盟訓(xùn)練方式提升和改進(jìn)智能體。JueWu[56]雖沒有使用人類數(shù)據(jù)用于智能體初始化,但其將人類高質(zhì)量數(shù)據(jù)用于分析英雄陣容。OpenAI Five[5]未直接使用人類數(shù)據(jù),但在神經(jīng)網(wǎng)絡(luò)和獎(jiǎng)勵(lì)函數(shù)等設(shè)計(jì)中一定程度上融入了人類先驗(yàn)知識(shí)。

4 博弈訓(xùn)練測(cè)試框架及平臺(tái)

4.1 MALib

MALib[57]是首個(gè)專門面向基于種群的多智能體強(qiáng)化學(xué)習(xí)的開源大規(guī)模并行訓(xùn)練框架(官網(wǎng)鏈接:https://malib.io/)。支持自我博弈、聯(lián)盟訓(xùn)練及PSRO等多種博弈訓(xùn)練方式,已對(duì)接多種多智能體環(huán)境。

4.2 POAC

部分可觀測(cè)異步智能體協(xié)同(POAC)平臺(tái)[58]是多智能體強(qiáng)化學(xué)習(xí)算法的標(biāo)準(zhǔn)測(cè)試環(huán)境(官網(wǎng)鏈接:http://turingai.ia.ac.cn/app/detail/30),可用于兵棋AI人機(jī)對(duì)抗挑戰(zhàn),支持自我博弈、人機(jī)對(duì)抗等模式。

4.3 Go-Bigger

Go-Bigger是OpenDILab推出的多智能體強(qiáng)化學(xué)習(xí)博弈訓(xùn)練環(huán)境(文檔鏈接:https://gobigger.readthedocs.io/en/latest/index.html),涵蓋自我博弈、聯(lián)盟訓(xùn)練等多種博弈訓(xùn)練方式,提供了直觀、高效的平臺(tái)。

4.4 RoboSumo

RoboSumo[39]是多智能體競(jìng)爭(zhēng)環(huán)境,具有模擬物理特征,使用相撲規(guī)則,智能體觀察敵我位置、速度等參數(shù),在連續(xù)動(dòng)作空間進(jìn)行自我博弈訓(xùn)練。

5 博弈訓(xùn)練的前景展望

博弈訓(xùn)練方法為多智能體強(qiáng)化學(xué)習(xí)開拓了思路,解決現(xiàn)實(shí)場(chǎng)景的能力有了顯著提升,必將成為未來博弈訓(xùn)練的重點(diǎn)研究方向。同時(shí),博弈訓(xùn)練方法還存在一些亟待解決的問題。

一方面,目前的博弈訓(xùn)練方法大多是啟發(fā)式的[59],具體的理論解釋還不完善,如新舊版本的比例設(shè)定、抽樣方式的設(shè)計(jì),可解釋性不強(qiáng),泛化性較弱。

另一方面,正如通過博弈訓(xùn)練能否獲得最強(qiáng)玩家一樣,智能體的決策水平能否通過自身博弈無限地提升下去?智能體自我博弈學(xué)習(xí)是否存在極限[29]?從這兩個(gè)方面來看,博弈訓(xùn)練方法的研究還處于起步階段,需要進(jìn)行更加深入細(xì)致的研究。

6 結(jié)束語

從智能體訓(xùn)練的角度出發(fā),對(duì)多智能體強(qiáng)化學(xué)習(xí)博弈訓(xùn)練方法進(jìn)行了梳理,介紹了博弈訓(xùn)練的基本概念、方式分類、關(guān)鍵問題、測(cè)試平臺(tái)及前景展望等。通過該文可以看出,多智能體強(qiáng)化學(xué)習(xí)博弈訓(xùn)練是一種新興的智能體訓(xùn)練方式,能夠在許多現(xiàn)實(shí)復(fù)雜場(chǎng)景中獲得較好表現(xiàn),具有極大的發(fā)展?jié)摿蛻?yīng)用價(jià)值。相信隨著研究的深入,博弈訓(xùn)練必將不斷在可解釋性、解決策略循環(huán)、探索、突破等問題上取得進(jìn)展,成為多智能體強(qiáng)化學(xué)習(xí)領(lǐng)域一顆閃亮的新星。