多智能體強化學習博弈訓練方式研究綜述

張人文,賴 俊,陳希亮

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

0 引 言

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

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

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

1 基本理論

本節(jié)對強化學習及博弈論的概念進行闡述,介紹博弈求解方式發(fā)展歷程及博弈訓練的基本含義。

1.1 強化學習基本理論

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

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

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

(1)

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

R:S×A×S→R

(2)

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

(3)

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

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

1.1.2 強化學習

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

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

圖1 強化學習基本過程

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

π:S×A→[0,1]

(4)

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

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

(5)

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

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

(6)

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

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

(7)

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

在強化學習過程中,智能體通過對值函數(shù)進行評價,進而判定自身策略優(yōu)劣并加以改進。

1.2 多智能體強化學習

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

在多智能體強化學習中,智能體的動作空間Ai(i=1,2,…,n)交互形成聯(lián)合動作空間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)動作a時,由狀態(tài)s轉(zhuǎn)移至下一狀態(tài)s'的概率分布。智能體的聯(lián)合策略決定智能體的總回報。

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

1.3 博弈論

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

博弈論有多種分類。根據(jù)博弈過程玩家是否同時決策,可分為標準式博弈(靜態(tài)博弈)、拓展式博弈(動態(tài)博弈);根據(jù)玩家對博弈過程信息是否了解,可分為完美信息博弈和不完美信息博弈等。

對于一般標準式博弈,進行如下形式化定義:

(9)

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

(10)

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

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

(11)

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

納什均衡提出后,求解納什均衡成為研究的熱點。自我博弈的使用在精神上類似于虛擬博弈[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),將虛擬博弈由標準式博弈推廣到擴展式博弈。Heinrich等人[20]提出Neural Fictitious Self-Play (NFSP),是第一個在自我博弈中收斂到近似納什均衡的深度強化學習方法。另一方面,McMahan等人[21]提出基于博弈論的Double Oracle(DO)算法,在此基礎(chǔ)上,Lanctot等人[22]提出Policy Space Response Oracles (PSRO)算法,提升了博弈求解水平。Balduzzi 等人[23]提出PSRO-rectified Nash response(PSRO-rN),進一步提升了納什均衡下策略的改進機率。Muller等人[24]提出α-PSRO算法,使用α-Rank[25]擴展PSRO的理論基礎(chǔ),避免求解納什均衡面臨的均衡選擇問題[26]。McAleer等人[27]提出Pipeline PSRO(P2SRO),通過維護分層管道來并行化 PSRO。

1.5 博弈訓練

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

2 博弈訓練方式分類

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

2.1 自我博弈訓練

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

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

2.1.1 自我博弈訓練算法基本框架

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

算法1 Self-Play算法。

輸入:智能體V1

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

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

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

輸出:智能體VT+1

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

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

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

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

算法 2:強化學習Self-Play算法。

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

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

輸入:需要訓練的策略π。

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

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

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

4 將π'加入π中;

5 采樣S0和O0;

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

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

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

9 獲得獎勵rt;

10t=t+1;

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

12 更新π;

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

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

15 輸出策略π

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

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

(12)

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

G(π°,π)={π}

(13)

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

2.1.3 成長式自我博弈訓練算法

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

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

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

(1)歷史均勻訓練法。

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

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

(14)

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

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

(15)

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

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

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

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

(16)

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

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

(17)

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

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

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

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

(18)

(19)

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

(4)回溯比例訓練法。

回溯比例訓練法是前述方法的結(jié)合,博弈訓練時,以一定訓練比例與最新的自我對戰(zhàn),其余訓練比例與過去的版本對戰(zhàn)?；厮荼壤柧毞ㄎ瓷釛壢魏芜^去的對手,所有歷史對手均保存在對手池中。

該文給出回溯比例訓練法的形式化描述:

(20)

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

表1 典型自我博弈訓練方法分類

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

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

2.2 種群訓練

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

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

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

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

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

2.3 聯(lián)盟訓練

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

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

(21)

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

fhard(x)=(1-x)2

(22)

fvar(x)=x(1-x)

(23)

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

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

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

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

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

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

圖3 Double Oracle算法示意圖

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

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

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

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

3.1 策略循環(huán)

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

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

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

3.2 策略遺忘

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

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

3.3 策略探索

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

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

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

3.4 策略突破

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

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

4 博弈訓練測試框架及平臺

4.1 MALib

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

4.2 POAC

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

4.3 Go-Bigger

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

4.4 RoboSumo

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

5 博弈訓練的前景展望

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

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

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

6 結(jié)束語

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