多智能體博弈強(qiáng)化學(xué)習(xí)研究綜述

王 軍，曹 雷，陳希亮，賴 俊，章樂(lè)貴

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

自20世紀(jì)50年代著名的達(dá)特茅斯會(huì)議首次提出人工智能的概念以來(lái)，人工智能就在不斷的發(fā)展，人工智能的發(fā)展大致可分為運(yùn)算智能、感知智能和認(rèn)知智能幾個(gè)階段。運(yùn)算智能，即快速計(jì)算和記憶存儲(chǔ)能力。感知智能，即視覺(jué)、聽(tīng)覺(jué)、觸覺(jué)等感知能力，如采用神經(jīng)元網(wǎng)絡(luò)方法識(shí)別圖像和斯坦福大學(xué)研制的診斷和治療感染性疾病的專家系統(tǒng)MYCIN，所依賴的技術(shù)主要是監(jiān)督學(xué)習(xí)，監(jiān)督學(xué)習(xí)解決問(wèn)題的方法就是靠輸入大量的標(biāo)簽數(shù)據(jù)學(xué)到抽象特征并分類。隨著感知智能技術(shù)的不斷提高和完善，人工智能也逐漸從感知智能向決策智能邁進(jìn)[1]，如AlphaGo、AlphaZero和DQN在Atari游戲中的重大突破，而AlphaGo的核心算法是強(qiáng)化學(xué)習(xí)，相比監(jiān)督學(xué)習(xí)的標(biāo)簽數(shù)據(jù)，強(qiáng)化學(xué)習(xí)只需要帶有回報(bào)的交互數(shù)據(jù)[2]。然而現(xiàn)實(shí)世界復(fù)雜多變，物聯(lián)網(wǎng)時(shí)代使得物物相連，單個(gè)智能體的智能決策已無(wú)法滿足需求，群體智能決策逐漸成為主流，很多過(guò)去被認(rèn)為是不可能解決的群體決策問(wèn)題都能通過(guò)多智能體深度強(qiáng)化學(xué)習(xí)算法得以解決[3]，最具代表性的就是StarCraftⅡ、Dota2和德州撲克。

1 多智能體深度強(qiáng)化學(xué)習(xí)關(guān)鍵科學(xué)問(wèn)題

強(qiáng)化學(xué)習(xí)主要解決的是序貫決策問(wèn)題，需要智能體不斷地與環(huán)境進(jìn)行交互和嘗試，當(dāng)智能體通過(guò)動(dòng)作與環(huán)境進(jìn)行交互時(shí)，環(huán)境會(huì)給智能體一個(gè)即時(shí)回報(bào)，智能體會(huì)根據(jù)回報(bào)評(píng)估采取的動(dòng)作，如果是正向的回報(bào)則加大采取該動(dòng)作的概率，如果是負(fù)向的回報(bào)則減小采取該動(dòng)作的概率，同時(shí)智能體的動(dòng)作可能會(huì)改變環(huán)境，不斷重復(fù)，最終找到最優(yōu)策略使得累積回報(bào)的期望最大。在單智能體任務(wù)中，算法只需要考慮一個(gè)智能體的動(dòng)作和狀態(tài)，相比單智能體深度強(qiáng)化學(xué)習(xí)，多智能體深度強(qiáng)化學(xué)習(xí)要考慮的動(dòng)作和狀態(tài)空間都更大，每個(gè)智能體的回報(bào)不僅和環(huán)境有關(guān)，與其他智能體的動(dòng)作也緊密聯(lián)系，這使得多智能體學(xué)習(xí)任務(wù)的求解更加復(fù)雜。由單智能體系統(tǒng)向多智能體系統(tǒng)過(guò)渡時(shí)主要存在以下難點(diǎn)。

（1）維度爆炸。多智能體系統(tǒng)中動(dòng)作空間、狀態(tài)空間和參數(shù)數(shù)量大幅度增加，迫使計(jì)算量呈指數(shù)遞增導(dǎo)致維度爆炸，該問(wèn)題的主要解決辦法有如下幾種：一是采用混合型訓(xùn)練機(jī)制，即集中式訓(xùn)練分布式執(zhí)行（CTDE），二是基于偽計(jì)數(shù)的探索算法，算法通過(guò)設(shè)計(jì)滿足一定性質(zhì)的密度模型來(lái)評(píng)估頻次，計(jì)算在連續(xù)空間下具有泛化性的偽計(jì)數(shù)提高探索效率，緩解維數(shù)爆炸問(wèn)題。

（2）環(huán)境非平穩(wěn)性。多智能體強(qiáng)化學(xué)習(xí)中環(huán)境狀態(tài)轉(zhuǎn)移函數(shù)取決于聯(lián)合動(dòng)作，導(dǎo)致環(huán)境的非平穩(wěn)性，解決該問(wèn)題的主要辦法有如下幾種：一是采用AC框架，通過(guò)在訓(xùn)練過(guò)程中獲得其他智能體的信息和行動(dòng)，智能體不會(huì)經(jīng)歷環(huán)境動(dòng)態(tài)的意外變化，二是采用對(duì)手建模，通過(guò)模擬其他智能體的策略，可以穩(wěn)定智能體的訓(xùn)練過(guò)程，三是利用元學(xué)習(xí)更快適應(yīng)非平穩(wěn)性環(huán)境。

（3）信度分配。當(dāng)智能體的數(shù)量增加時(shí)，信度分配是無(wú)法回避的問(wèn)題，解決該問(wèn)題的主要方法有平均分配、差分回報(bào)分配、優(yōu)勢(shì)函數(shù)分配以及Deepmind提出的基于情景記憶檢索TVT算法[4]。

隨著智能體數(shù)量的增加，最大化長(zhǎng)期累積回報(bào)的期望作為學(xué)習(xí)目標(biāo)很難得到收斂結(jié)果，某些特殊收斂點(diǎn)所對(duì)應(yīng)的策略也不符合實(shí)際情況，所以多智能體強(qiáng)化學(xué)習(xí)中各智能體的學(xué)習(xí)目標(biāo)還應(yīng)該增加合理性和收斂性，并且可以從具體理論上解釋。同時(shí)，在很多實(shí)際博弈場(chǎng)景下，最優(yōu)解未必存在，這些問(wèn)題都阻礙多智能體強(qiáng)化學(xué)習(xí)進(jìn)一步發(fā)展。隨著博弈理論的引入，很好地解決了多智能體直接的相互關(guān)系，博弈中的均衡解可以代替最優(yōu)解以求得相對(duì)有效的策略，同時(shí)該策略具有合理性。

多智能體系統(tǒng)中智能體之間的關(guān)系可以用博弈論中玩家之間的關(guān)系來(lái)表示，一般分為競(jìng)爭(zhēng)、合作和混合型。博弈論中按照博弈玩家同時(shí)決策還是先后決策分別稱為標(biāo)準(zhǔn)型博弈（Normal form Games）和擴(kuò)展式博弈（Extensive form Games），囚徒困境就是常見(jiàn)的標(biāo)準(zhǔn)型博弈，而圍棋就是常見(jiàn)的擴(kuò)展式博弈。另外，按照博弈中所有玩家收益的和是否為零可分為零和博弈和一般和博弈，根據(jù)玩家的目標(biāo)是否一致分為共同利益博弈和不同利益博弈。擴(kuò)展式博弈中根據(jù)信息是否已知可以劃分為完全信息擴(kuò)展式博弈和不完全信息擴(kuò)展式博弈[5]。

多智能體中均衡、協(xié)同和合作等學(xué)習(xí)目標(biāo)都會(huì)涉及到智能體之間的決策問(wèn)題，博弈論的中心思想是為博弈建立一個(gè)策略交互模型，博弈論中均衡解是讓博弈玩家都滿意的策略組合，通過(guò)展示玩家最終會(huì)采用哪些策略來(lái)描述博弈的結(jié)果，這與多智能體深度強(qiáng)化學(xué)習(xí)的學(xué)習(xí)目標(biāo)完美契合，利用博弈論中納什均衡、Stacklberg均衡和元均衡等概念來(lái)指導(dǎo)智能體每次迭代，以使結(jié)果收斂到納什均衡點(diǎn)，同時(shí)使得每個(gè)智能體的收益相對(duì)較大，收斂速度比較快。將博弈理論引入多智能體深度強(qiáng)化學(xué)習(xí)算法中取得了很多成果，具體的算法如圖1所示。

圖1 主要算法分類圖Fig.1 Classification of main algorithms

2 多智能體博弈強(qiáng)化學(xué)習(xí)基本概念

本章重點(diǎn)敘述多智能體強(qiáng)化學(xué)習(xí)和博弈論的相關(guān)概念，最簡(jiǎn)單的強(qiáng)化學(xué)習(xí)數(shù)學(xué)模型是馬爾可夫決策過(guò)程，博弈論中最核心的概念是納什均衡。

2.1 馬爾可夫決策過(guò)程（MDP）

MDP是一個(gè)由五元組S,A,P,R,r構(gòu)成。其中，S是包含所有狀態(tài)的有限集合，A是包含智能體所有動(dòng)作的有限集合，P定義為P:S×A×S→[0,1]的轉(zhuǎn)換函數(shù)，R定義為R:S×A×S→R的回報(bào)函數(shù)，r∈[]0,1是折扣系數(shù)，用于平衡智能體的瞬時(shí)回報(bào)和長(zhǎng)期回報(bào)對(duì)總回報(bào)的影響。

MDP的求解目標(biāo)是找到期望回報(bào)值最大的最優(yōu)策略σ?，一般用最優(yōu)狀態(tài)動(dòng)作值函數(shù)形式化表征期望回報(bào)當(dāng)智能體的數(shù)量超過(guò)一個(gè)，同時(shí)環(huán)境的改變和每個(gè)智能體的回報(bào)取決于所有智能體的動(dòng)作和當(dāng)前狀態(tài)時(shí)則稱為多智能體馬爾可夫決策過(guò)程。

2.2 隨機(jī)博弈（Stochastic Games，SG）

隨機(jī)博弈可以看成MDP向多人博弈的推廣，由如下的六元組定義：N,S,Ai,P,Ri,γ，其中N為博弈玩家的個(gè)數(shù)，當(dāng)玩家的個(gè)數(shù)為1時(shí)，即退化為MDP，Ai為第i個(gè)玩家的動(dòng)作，A-i為除第i個(gè)玩家外其他玩家的動(dòng)作，記A=A1×A2×…×An，Ri為第i個(gè)玩家的回報(bào)函數(shù)，當(dāng)每個(gè)玩家的回報(bào)函數(shù)相同時(shí)則稱此博弈為團(tuán)隊(duì)博弈（Team Games）。

2.3 部分可觀察的隨機(jī)博弈（Partially Observable SG，POSG）

部分可觀察的隨機(jī)博弈（POSG）是在隨機(jī)博弈的基礎(chǔ)上對(duì)玩家所能觀察到的信息進(jìn)行了一定的約束，具體表示為N,S,Ai,P,Ri,γ,OBi,O，其中OBi為第i個(gè)玩家的觀測(cè)集，聯(lián)合觀測(cè)集為OB=OB1×OB2×…×OBn，O為S×A→[]0,1的觀測(cè)函數(shù)。去中心化的部分可觀察馬爾可夫決策過(guò)程（Dec-POMDP）是特殊情況下的POMDP，即所有智能體的回報(bào)函數(shù)都相同：R1=R2=…=Rn。

2.4 納什均衡

其中，σi∈Πi，Πi是玩家i所有可能的策略集合。

2.5 元博弈（Metagame）

對(duì)于n人一般式博弈其關(guān)于智能體i的一階元博弈iG可以表示成iG=N,Ai,…,，其中Fi表示智能體i的反應(yīng)函數(shù)空間。反應(yīng)函數(shù)的定義為f:A-i→Ai。對(duì)于智能體i的任意反應(yīng)函數(shù)f∈Fi，以及其他智能體的任意聯(lián)合動(dòng)作

3 標(biāo)準(zhǔn)型博弈

在標(biāo)準(zhǔn)型博弈中，通過(guò)博弈玩家的目標(biāo)是否相同，劃分為共同利益博弈和不同利益博弈，常見(jiàn)的共同利益博弈有團(tuán)隊(duì)博弈、勢(shì)博弈和Dec-POMDP，研究共同利益博弈最大的優(yōu)勢(shì)在于可以使用具有理論保證的單智能體強(qiáng)化學(xué)習(xí)算法。

3.1 共同利益博弈

3.1.1 團(tuán)隊(duì)博弈

團(tuán)隊(duì)博弈被反復(fù)研究的重要原因是其對(duì)于構(gòu)建分布式AI（DAI）至關(guān)重要。團(tuán)隊(duì)博弈中，每個(gè)智能體只需要維護(hù)自己的值函數(shù)，而且值函數(shù)只取決于當(dāng)前的狀態(tài)和動(dòng)作，從而避免了考慮聯(lián)合動(dòng)作時(shí)的環(huán)境非平穩(wěn)和維度爆炸問(wèn)題。因此，很多單智能體算法可以運(yùn)用在該問(wèn)題上。如果博弈存在多個(gè)納什均衡，即使每個(gè)智能體之間的學(xué)習(xí)目標(biāo)并不沖突，也會(huì)導(dǎo)致智能體最終不會(huì)學(xué)到最優(yōu)策略的問(wèn)題。

Sandholm等[6]利用有偏好的動(dòng)作選擇和不完整的歷史采樣提出了最優(yōu)自適應(yīng)學(xué)習(xí)算法（Optimal Adaptive Learning，OAL），并證明該方法對(duì)于存在多個(gè)納什均衡的團(tuán)隊(duì)博弈中都會(huì)收斂至最優(yōu)納什均衡，但是該方法在一般的隨機(jī)博弈中收斂性并不能得到保證。所以，在OAL算法基礎(chǔ)上，Arslan等[7]提出了隨機(jī)博弈的去中心化Q-learning算法，并借助雙時(shí)間尺度分析以團(tuán)隊(duì)博弈問(wèn)題為例，證明了算法在大量的隨機(jī)博弈中都會(huì)穩(wěn)定收斂到最優(yōu)納什均衡。

團(tuán)隊(duì)博弈中，獲得最優(yōu)解的關(guān)鍵是如何解決智能體之間的合作關(guān)系。Mao等提出ATT-MADDPG算法[8]，算法通過(guò)一個(gè)集中的ctitic來(lái)收集其他玩家的信息和策略，并在集中critic中嵌入注意力機(jī)制以自適應(yīng)的方式對(duì)其他玩家的動(dòng)態(tài)聯(lián)合策略建模，當(dāng)玩家的策略發(fā)生改變時(shí)，相關(guān)的注意權(quán)重就會(huì)自適應(yīng)地改變，智能體就會(huì)快速地調(diào)整自己的策略。在多智能體系統(tǒng)中，智能體的交互并不是一直存在，某個(gè)特定的智能體也不是一直處于和其他智能體交互的狀態(tài)，Liu等利用完全圖對(duì)智能體的關(guān)系進(jìn)行建模，提出基于兩階段注意力網(wǎng)絡(luò)的博弈抽象機(jī)制（G2ANet）[9]，并在Traffic Junction和Predator-Prey場(chǎng)景下證明該方法可以簡(jiǎn)化學(xué)習(xí)過(guò)程。Zhu等為解決智能體之間通信問(wèn)題，提出Partaker-Sharer框架[10]，通過(guò)在每個(gè)時(shí)間步彼此共享智能體的最大Q值來(lái)加速學(xué)習(xí)過(guò)程，并在Predator-Prey場(chǎng)景下驗(yàn)證了算法的有效性。

Yang等借用了平均場(chǎng)論（Mean Field Theory，MFT）的思想，其對(duì)多智能體系統(tǒng)給出了一個(gè)近似假設(shè)：對(duì)某個(gè)智能體，其他所有智能體對(duì)其產(chǎn)生的作用可以用一個(gè)均值替代，提出了平均場(chǎng)多智能體強(qiáng)化學(xué)習(xí)算法（Mean Field）[11]，將轉(zhuǎn)化為只包含相鄰智能體相互作用的形式：表示鄰居節(jié)點(diǎn)的個(gè)數(shù)。Anahtarci等[12]對(duì)智能體

其中，N(j)表示智能體j鄰居智能體的標(biāo)簽集，Nj=之間的交互作用進(jìn)行近似，降低智能體交互的復(fù)雜度，并且在理論上給出了收斂性證明，能夠收斂到納什均衡點(diǎn)。針對(duì)智能體的數(shù)量接近無(wú)限的情況，Elie等[13]在僅依賴平均場(chǎng)博弈的基本動(dòng)力學(xué)假設(shè)的條件下，根據(jù)每個(gè)學(xué)習(xí)迭代步驟中出現(xiàn)的累積誤差來(lái)量化近似納什均衡的質(zhì)量，首次展示了無(wú)模型學(xué)習(xí)算法向非平穩(wěn)MFG均衡的收斂。

除上述方法外，分解MDPs也可以有效解決團(tuán)隊(duì)博弈問(wèn)題，回報(bào)函數(shù)可能只與狀態(tài)的部分特征有關(guān)，而與其他特征是獨(dú)立的，利用因子化的表達(dá)，可以避免在整個(gè)狀態(tài)-動(dòng)作空間進(jìn)行迭代求解。受分解MDPs思想的啟發(fā)，Vlassis等[14]將多智能體系統(tǒng)視為一個(gè)大型馬爾可夫決策過(guò)程（MDP），基于動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)和協(xié)調(diào)圖（coordination graphs）使用因式分解將線性值函數(shù)作為聯(lián)合值函數(shù)的近似值，值函數(shù)的這種分解允許智能體在行動(dòng)時(shí)協(xié)調(diào)其動(dòng)作，有效解決狀態(tài)和動(dòng)作空間中的指數(shù)爆炸問(wèn)題，最終可以找到全局最優(yōu)聯(lián)合動(dòng)作。

然而，協(xié)調(diào)圖在實(shí)際應(yīng)用中可能并不總是可用的，理想的方法是讓智能體從任務(wù)中自動(dòng)學(xué)習(xí)值函數(shù)分解，深度神經(jīng)網(wǎng)絡(luò)是學(xué)習(xí)這類分解的有效方法，因此多種特殊的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)被提出，典型的算法包括VDN、QMIX、QTRAN、Qatten和QPD等。VDN[15]在值函數(shù)可分解的假設(shè)下要求聯(lián)合值函數(shù)是每個(gè)智能體值函數(shù)的線性和，即

由于線性假設(shè)這個(gè)前提條件，VDN算法所適用的場(chǎng)景比較少。為此，使用神經(jīng)網(wǎng)絡(luò)近似聯(lián)合值函數(shù)的算法QMIX[16]被提出，QMIX利用集中式訓(xùn)練的優(yōu)勢(shì)，使用全局狀態(tài)進(jìn)行訓(xùn)練但QMIX為了保證獨(dú)立全局最大化操作，假設(shè)聯(lián)合值函數(shù)對(duì)個(gè)體值函數(shù)是單調(diào)的，用公式來(lái)表示為：

QTRAN[17]算法結(jié)合了上述VDN和QMIX的優(yōu)點(diǎn)，認(rèn)為直接用神經(jīng)網(wǎng)絡(luò)去逼近聯(lián)合Q函數(shù)相對(duì)困難，因而將整個(gè)逼近過(guò)程分為兩步：首先采用VDN的方式得到加和的聯(lián)合值函數(shù)，作為聯(lián)合值函數(shù)的近似，接著去擬合加和的聯(lián)合值函數(shù)與聯(lián)合值函數(shù)的差值。然而，不管是VDN算法的累加性還是QMIX算法的單調(diào)性，都從一定程度上限制了聯(lián)合值函數(shù)和每個(gè)智能體的值函數(shù)之間的關(guān)系，假設(shè)過(guò)于嚴(yán)格。Qatten[18]算法在不引入附加假設(shè)和約束條件的情況下，首次從理論上推導(dǎo)出任意數(shù)量的智能體的聯(lián)合值函數(shù)和各智能體的值函數(shù)的廣義形式，提出基于多頭注意力機(jī)制的值函數(shù)混合網(wǎng)絡(luò)來(lái)近似聯(lián)合值函數(shù)和分解單個(gè)值函數(shù)，算法在星際爭(zhēng)霸SMAC環(huán)境中進(jìn)行實(shí)驗(yàn)，取得良好效果。QPD[19]是另外一種值函數(shù)的分解方法，使用積分梯度的方法，沿軌跡路徑直接分解聯(lián)合值函數(shù)，為智能體分配信度。團(tuán)隊(duì)博弈下的主要算法優(yōu)缺點(diǎn)如表1所示。

表1 團(tuán)隊(duì)博弈下的主要算法的優(yōu)缺點(diǎn)Table 1 Advantages and disadvantages of main algorithms under team game

3.1.2 隨機(jī)勢(shì)博弈（SPG）

博弈中，如果每個(gè)玩家對(duì)于自身目標(biāo)改變或策略選取，都可以映射到某個(gè)全局函數(shù)中去，這個(gè)函數(shù)就叫做勢(shì)函數(shù)（potential function），這個(gè)博弈稱為勢(shì)博弈（potential game）。一般來(lái)說(shuō)，勢(shì)博弈可以被看作多智能體博弈的“單智能體成分”[20]，因?yàn)樗兄悄荏w在SPG中的利益都被描述為一個(gè)單一的勢(shì)函數(shù)。

將勢(shì)博弈推廣至隨機(jī)勢(shì)博弈后，問(wèn)題的復(fù)雜度會(huì)提高。隨機(jī)博弈下，玩家的策略不僅要考慮自己的狀態(tài)還要考慮其他玩家的行動(dòng)，Macua等[21]研究了一般形式的勢(shì)博弈，即策略與狀態(tài)及行動(dòng)時(shí)間都有關(guān)，并證明了在此前提下存在納什均衡，同時(shí)理論證明了純策略的勢(shì)博弈中的納什均衡可以通過(guò)求解MDP來(lái)找到[22]。Mazumdar等[23]針對(duì)勢(shì)博弈提出了基于策略的動(dòng)態(tài)更新算法，并應(yīng)用在Morse-Smale游戲中，證明了該算法可以收斂到局部納什均衡。在復(fù)雜的多智能體系統(tǒng)中，有效的學(xué)習(xí)需要所有參與的智能體之間高度協(xié)調(diào)，但是智能體之間的協(xié)調(diào)和通信往往是低效的，Chen[24]提出了集中訓(xùn)練和探索，并通過(guò)policy distillation來(lái)分散執(zhí)行來(lái)促進(jìn)智能體之間的協(xié)調(diào)和有效的學(xué)習(xí)。

3.1.3 Dec-POMDP

在Dec-POMDP中，多智能體的目標(biāo)是在能觀察到的局部信息基礎(chǔ)上實(shí)現(xiàn)全部獎(jiǎng)勵(lì)的最大化，因此在共同利益博弈中解決Dec-POMDP問(wèn)題是十分困難的，目前大多數(shù)Dec-POMDP的解決算法，包括上面的VDN、QMIX和QTRAN等算法，都是基于集中式訓(xùn)練和分散式執(zhí)行（CTDE）的學(xué)習(xí)框架。在表示智能體的局部策略時(shí)，通常使用隨機(jī)有限狀態(tài)控制器，這樣可以將Dec-POMDP表述為非線性規(guī)劃問(wèn)題，從而使用現(xiàn)有的優(yōu)化算法，從Dec-POMDP到連續(xù)狀態(tài)MDP的轉(zhuǎn)換，稱為占領(lǐng)狀態(tài)MDP（occupancy-state MDP）。占用狀態(tài)本質(zhì)上是關(guān)于隱藏狀態(tài)和觀測(cè)-行動(dòng)對(duì)的聯(lián)合歷史分布，這兩者的區(qū)別是在標(biāo)準(zhǔn)的MDP中，智能體的學(xué)習(xí)目標(biāo)是最優(yōu)狀態(tài)動(dòng)作值函數(shù)，而oMDP中的智能體的學(xué)習(xí)目標(biāo)是占用狀態(tài)和聯(lián)合行動(dòng)的最優(yōu)值函數(shù)，這些最優(yōu)值函數(shù)往往都是分段線性的，最重要的是這些限制會(huì)使得智能體最終會(huì)收斂至全局最優(yōu)而不是局部最優(yōu)。

Li在系統(tǒng)僅部分觀測(cè)時(shí)，提出生成式注意多智能體網(wǎng)絡(luò)[25]直接對(duì)底層的生成行為的分布進(jìn)行逼近，同時(shí)模型還通過(guò)在生成過(guò)程中采用混合密度來(lái)支持具有多模態(tài)分布的多智能體行為，并對(duì)缺失行為進(jìn)行推斷（Generative Attention），實(shí)驗(yàn)證明該模型可以捕獲具有線性復(fù)雜度的智能體交互，處理不斷演化的交互結(jié)構(gòu)。在多智能體強(qiáng)化學(xué)習(xí)的研究很少考慮訓(xùn)練后的策略對(duì)新任務(wù)的遷移能力，這使得訓(xùn)練好的策略很難應(yīng)用至更復(fù)雜的多智能體任務(wù)，為解決上述問(wèn)題Ryu等提出基于多層圖注意網(wǎng)絡(luò)和多智能體AC算法[26]的模型，并證明了所提出的模型在多個(gè)混合協(xié)同和競(jìng)爭(zhēng)任務(wù)下的性能優(yōu)于現(xiàn)有方法。除了上述方法外，解決Dec-POMDP問(wèn)題的方法還包括蒙特卡羅策略迭代法[27]，以及一種通過(guò)維護(hù)智能體之間的共享內(nèi)存來(lái)分散POMDP的方法[28]。

3.2 不同利益博弈

不同利益博弈是指玩家的學(xué)習(xí)目標(biāo)不同，根據(jù)所有玩家收益之和是否為零分為有限零和、一般和博弈。

3.2.1 有限零和博弈

有限零和博弈是指參與博弈的玩家個(gè)數(shù)有限，并且是嚴(yán)格的競(jìng)爭(zhēng)關(guān)系，所有玩家的總體收益和支出的總和為零。在兩人零和博弈中，由于兩個(gè)玩家的學(xué)習(xí)目標(biāo)完全相反，其納什均衡解本質(zhì)上是一個(gè)鞍點(diǎn)。Adler[29]證明了兩人零和博弈和線性優(yōu)化的等價(jià)性，即兩人零和博弈可以構(gòu)建為一個(gè)線性優(yōu)化問(wèn)題，任意一個(gè)線性優(yōu)化問(wèn)題也可以簡(jiǎn)化為一個(gè)零和博弈問(wèn)題。在解決兩人零和博弈問(wèn)題中最典型的方法是最小最大值定理（The Minimax Theorem），其可以表示為如下公式：

然而，該定理并不適用于回報(bào)函數(shù)為非凸非凹的博弈。對(duì)于離散動(dòng)作空間下的零和博弈，Shapley給出了第一個(gè)值迭代的方法[30]，證明了HShapley在兩人零和博弈中是壓縮映射，且可以收斂至納什均衡。與Shapley基于模型的值迭代方法不同，Littman針對(duì)兩人零和博弈提出了無(wú)模型的Minimax-Q算法[31]，Minimax-Q中的Minimax指的是使用最小最大值定理構(gòu)建線性規(guī)劃來(lái)求解每個(gè)特定狀態(tài)的納什均衡策略，Q指的是借用Q-learning中的TD方法來(lái)迭代狀態(tài)值函數(shù)或動(dòng)作-狀態(tài)值函數(shù)。隨后，Littman證明了與Q-learning相似的假設(shè)下，Minimax-Q算法的Bellman算子也是壓縮映射，并且會(huì)收斂到唯一的不動(dòng)點(diǎn)[32]，但是上述算法還是基于Q表的，因此無(wú)法應(yīng)用到動(dòng)作和狀態(tài)空間很大的場(chǎng)景中。Fan等[33]結(jié)合DQN和最小最大定理提出解決兩人零和博弈問(wèn)題的Minimax-DQN算法，并量化了該方法求出的策略和納什均衡之間的差異。Goodfellow等在2014年提出了生成對(duì)抗網(wǎng)絡(luò)（GANs）利用神經(jīng)網(wǎng)絡(luò)使得求解這類問(wèn)題變?yōu)榭赡躘34]，在GANs中，兩個(gè)神經(jīng)網(wǎng)絡(luò)參數(shù)化模型（生成器G和鑒別器D）進(jìn)行零和博弈。生成器接收隨機(jī)變量并生成“假”樣本，鑒別器則用于判斷輸入的樣本是真實(shí)的還是虛假的。兩者通過(guò)相互對(duì)抗來(lái)獲得彼此性能的提升。上述方法依然無(wú)法解決多智能體算法訓(xùn)練不穩(wěn)定、智能體對(duì)環(huán)境的變化很敏感和容易陷入局部最優(yōu)等問(wèn)題。Li等提出M3DDPG算法[35]，核心是在訓(xùn)練過(guò)程中使得每個(gè)智能體都表現(xiàn)良好，即使對(duì)手以最壞的方式反應(yīng)。

在尋找納什均衡時(shí)，以相同的步長(zhǎng)實(shí)現(xiàn)梯度-下降-上升（Gradient-Descent-Ascent，GDA），相當(dāng)于在一個(gè)算法中對(duì)兩個(gè)智能體應(yīng)用了策略梯度方法。通過(guò)對(duì)步長(zhǎng)的微調(diào)，GDA方法可以有效地解決部分兩人零和博弈問(wèn)題。Zhang等證明了當(dāng)兩人零和博弈中的回報(bào)函數(shù)都是線性時(shí)，交替更新比同步更新收斂的速度更快[36]。但是在雙線性模型中，收斂性并不能得到保證。Mertikopoulos等[37]提出樂(lè)觀鏡像下降法（optimistic mirror descent）解決了雙線性模型中的收斂問(wèn)題，并在CelebA和CIFAR-10數(shù)據(jù)集中進(jìn)行了驗(yàn)證。當(dāng)回報(bào)函數(shù)為非凸非凹時(shí)，GDA方法也有不足，一是GDA算法可能不再收斂，二是算法收斂的點(diǎn)可能連局部最優(yōu)都不是。為解決此問(wèn)題，Jin等引入局部Stackelberg均衡，并在此基礎(chǔ)上建立了與GDA算法的聯(lián)系，證明了GDA的所有穩(wěn)定極限點(diǎn)都是局部Stackelberg均衡點(diǎn)[38]。Fiez等[39]通過(guò)證明GDA算法中的收斂點(diǎn)為零和博弈中Stackelberg均衡的充分條件，建立了納什均衡和Stackelberg均衡之間的聯(lián)系。Zhang等[40]對(duì)GDA算法使用了“光滑化”的技巧，使得算法可以在非凸-凹的極小-極大問(wèn)題的兩類常見(jiàn)形式上收斂至最優(yōu)結(jié)果。有限零和博弈下主要算法的優(yōu)缺點(diǎn)如表2所示。

表2 有限零和博弈下主要算法的優(yōu)缺點(diǎn)Table 2 Advantages and disadvantages of main algorithms under finite zero-sum game

3.2.2 有限一般和博弈

求解一般和隨機(jī)博弈的計(jì)算復(fù)雜度是PPAD，而求解零和博弈的計(jì)算復(fù)雜度是P-complete[41]，所以解決一般和的隨機(jī)博弈問(wèn)題的難度比零和的隨機(jī)博弈要困難很多。Herings等[42]引用拓?fù)鋵W(xué)中同倫思想，提出一種可以找到求解多個(gè)獨(dú)立MDPs和多人隨機(jī)博弈的均衡解之間的同倫路徑算法，從而使得多人隨機(jī)博弈問(wèn)題轉(zhuǎn)化為求解多個(gè)獨(dú)立MDPs問(wèn)題，但是這種方法只能應(yīng)用在狀態(tài)集很小的兩人博弈中。隨后，一系列基于值的算法被提出來(lái)解決一般和隨機(jī)博弈。這些方法大多采用經(jīng)典Q-learning作為中心控制器，不同之處在于中心控制器運(yùn)用何種均衡來(lái)引導(dǎo)智能體在迭代中逐漸收斂。例如，Nash-Q算法采用的就是納什均衡，而correlated-Q算法采用的則是相關(guān)均衡（correlated equilibrium）。

傳統(tǒng)Q-learning算法應(yīng)用于多智能體系統(tǒng)時(shí)，每個(gè)智能體的策略都在隨著訓(xùn)練的進(jìn)行而變化，對(duì)每個(gè)智能體來(lái)說(shuō)環(huán)境都是不穩(wěn)定的，而策略梯度算法應(yīng)用于多智能體系統(tǒng)時(shí)通常表現(xiàn)出很高的方差。Lowe等提出一種Actor-Critic策略梯度算法的擴(kuò)展算法[43]，并利用集中訓(xùn)練分散執(zhí)行框架，證明該算法在競(jìng)爭(zhēng)和合作場(chǎng)景下都能有效收斂。在解決多智能體協(xié)調(diào)問(wèn)題中，Stackelberg均衡在帕累托優(yōu)勢(shì)方面比Nash均衡具有更好的收斂性，Zhang等定義了尋找Stackelberg均衡的雙層強(qiáng)化學(xué)習(xí)問(wèn)題，并提出了一種新的雙層AC學(xué)習(xí)方法[44]，允許智能體擁有不同的知識(shí)庫(kù)，并在矩陣博弈中證明了雙層AC可以收斂至Stackelberg均衡。

對(duì)于Stackelberg均衡，Blum等[45]研究了在大型一般和游戲中計(jì)算Stackelberg均衡的復(fù)雜性。證明了有效地計(jì)算零和博弈的納什均衡是有效計(jì)算的大型一般和博弈的Stackelberg均衡的充分條件。Friend-or-Foe Q-Learning算法[46]（FFQ）也是從Minimax-Q算法拓展而來(lái)，對(duì)于某個(gè)智能體運(yùn)用FFQ算法，是將除該智能體以外的所有智能體分為兩組，一組稱為friend的智能體幫助其一起最大化其獎(jiǎng)勵(lì)回報(bào)，另一組稱為foe的智能體對(duì)抗它并降低它的獎(jiǎng)勵(lì)回報(bào)，這樣多智能體的一般和博弈就轉(zhuǎn)化為了兩個(gè)智能體的零和博弈。但是此類算法所共有的缺陷是算法的假設(shè)條件過(guò)于苛刻，運(yùn)用至現(xiàn)實(shí)場(chǎng)景中，收斂性往往無(wú)法保證。

除了集中式Q-Learning算法，分散式Q-Learning算法也因其可擴(kuò)展性而被廣泛的關(guān)注，并且分散式QLearning算法結(jié)合two-timescale隨機(jī)分析在強(qiáng)化學(xué)習(xí)中取得了很多不錯(cuò)的結(jié)果[47]。two-timescale隨機(jī)分析證明了兩個(gè)耦合且變化速度不同的隨機(jī)過(guò)程，如果固定慢過(guò)程，則快過(guò)程一定會(huì)收斂至某個(gè)極限點(diǎn)。Prasad等[48]將two-timescale隨機(jī)分析運(yùn)用到critic網(wǎng)絡(luò)和actor網(wǎng)絡(luò)，證明了如果critic網(wǎng)絡(luò)比actor網(wǎng)絡(luò)更新得更快，它可以確保訓(xùn)練在一般和隨機(jī)博弈中達(dá)到一個(gè)平穩(wěn)的局部納什均衡。Heusel等[49]提出two-timescale更新規(guī)則（TTUR），在任意GAN損失函數(shù)上使用隨機(jī)梯度下降訓(xùn)練GAN，并證明了在一般和博弈中可以收斂于局部納什均衡。通過(guò)直接策略搜索收斂到納什均衡的方法在早期只能適用于兩人兩動(dòng)作的博弈，應(yīng)用范圍極其有限，雖然隨著GANs的出現(xiàn)，解決了特定場(chǎng)景下的局部納什均衡問(wèn)題，但并未取得重大突破，主要原因是損失函數(shù)的可導(dǎo)性一般不成立。

4 擴(kuò)展式博弈

如果效用函數(shù)是共有知識(shí)，則稱這樣的博弈為完全信息博弈，如圍棋、象棋，否則為非完全信息博弈，如德州撲克。

4.1 完全信息的擴(kuò)展式博弈

納什在博弈論中主要的貢獻(xiàn)是證明了在有限玩家有限次標(biāo)準(zhǔn)型博弈下，一定存在混合策略的納什均衡。但是這個(gè)納什均衡是假設(shè)玩家在決策時(shí)，其他玩家的策略不會(huì)改變，但在擴(kuò)展式博弈中先決策玩家無(wú)法知道后決策玩家的策略，所以會(huì)導(dǎo)致不可置信的納什均衡存在，因此擴(kuò)展式博弈中均衡解應(yīng)該在每個(gè)子博弈中都是納什均衡解，這時(shí)的解稱為子博弈精煉納什均衡。求解子博弈精煉納什均衡最典型的算法是alpha-beta修剪算法，該算法通過(guò)逆向歸納從最底部的子博弈中求出納什均衡，然后通過(guò)深度優(yōu)先搜索算法不斷將上層信息節(jié)點(diǎn)加入其中，形成新的子博弈并求出新的納什均衡，最終在搜索完整個(gè)博弈樹(shù)時(shí)求出的納什均衡即為子博弈精煉納什均衡。近年來(lái)，完全信息的擴(kuò)展式博弈最大的突破是AlphaGo系列，AlphaGo系列使用蒙特卡洛樹(shù)搜索的框架進(jìn)行模擬，并在學(xué)習(xí)策略時(shí)中使用監(jiān)督學(xué)習(xí)，有效地利用人類棋手的棋譜，通過(guò)強(qiáng)化學(xué)習(xí)，從左右互搏中提高自己，超越人類棋手水平。

4.2 不完全信息的擴(kuò)展式博弈

現(xiàn)實(shí)中博弈往往以不完全信息的擴(kuò)展式博弈存在，如即時(shí)戰(zhàn)略游戲和軍事對(duì)抗，不完全信息的擴(kuò)展式博弈被認(rèn)為是下一代人工智能的重難點(diǎn)之一。解決不完全信息的擴(kuò)展式博弈主要有三個(gè)難點(diǎn)，一是子博弈之間相互關(guān)聯(lián)，二是存在狀態(tài)不可分的信息集，這使得強(qiáng)化學(xué)習(xí)中基于狀態(tài)的值估計(jì)方法不再適用，三是博弈的求解規(guī)模比較大，如橋牌和德州撲克的信息集數(shù)目分別為1067和10162。近幾年以德州撲克為例，不完全信息的擴(kuò)展式博弈取得了不錯(cuò)的進(jìn)展。

在不完全信息擴(kuò)展式博弈中，由于策略之間的相互影響，直接對(duì)聯(lián)合策略進(jìn)行建模很難實(shí)現(xiàn)，Tian等基于策略變化密度提出了聯(lián)合策略搜索（JPS）方法[50]，該方法可以在不重新評(píng)估整個(gè)博弈的情況下，迭代地改進(jìn)不完全信息博弈中協(xié)作智能體的聯(lián)合策略，并在網(wǎng)格世界中對(duì)算法性能進(jìn)行了驗(yàn)證。解決不完全信息博弈主要有CFR系列和NFSP系列算法，兩個(gè)系列算法的驗(yàn)證環(huán)境主要為德州撲克。

4.2.1 反事實(shí)遺憾值最小化算法（CFR）

記Pσ i(s)為玩家i從初始狀態(tài)出發(fā)，遵循策略σ到達(dá)狀態(tài)s的概率，Pσ-i(s)為從初始狀態(tài)出發(fā)，除玩家i外，所有玩家都遵循策略σ到達(dá)狀態(tài)s的概率，Pσ i(z|s)玩家i從狀態(tài)s出發(fā)，遵循策略σ到達(dá)終止?fàn)顟B(tài)z的概率，ui(z)為到達(dá)終止?fàn)顟B(tài)的效用函數(shù)，反事實(shí)值的定義如下：

圖2 CFR算法迭代步驟Fig.2 Iteration steps of CFR

CFR算法結(jié)合了遺憾值最小化算法[51]和平均策略，通過(guò)最小化單個(gè)信息集合上的遺憾值來(lái)達(dá)到最小化全局遺憾值的目標(biāo)，最終使得博弈過(guò)程中的平均策略趨近于納什均衡。由于需要遍歷整個(gè)博弈樹(shù)，時(shí)間復(fù)雜度和收斂速度慢是算法的主要缺點(diǎn)。

為了減少CFR算法的時(shí)間復(fù)雜度，Zhou等提出的Lazy-CFR[52]針對(duì)原始CFR必須在每一輪中遍歷整個(gè)游戲樹(shù)的缺點(diǎn)，采用惰性更新策略，在只需要訪問(wèn)部分博弈節(jié)點(diǎn)條件下，取得和CFR同等效率。對(duì)于CFR算法的改進(jìn)還有最佳響應(yīng)剪枝算法（Best-Response Pruning，BRP）[53]，Brown等證明了在使用CFR算法時(shí)加入BRP會(huì)減少對(duì)于收斂到納什均衡沒(méi)有幫助的動(dòng)作，從而加速收斂和節(jié)約空間。

Lanctot等提出了一類基于蒙特卡洛抽樣的在線算法（MCCFR）[54]，包括基于結(jié)果抽樣的CFR算法和基于外部抽樣的CFR算法，兩者都可以計(jì)算一個(gè)近似納什均衡。雖然MCCFR算法減少了CFR算法的時(shí)間復(fù)雜度，但是由于蒙特卡洛搜索本身會(huì)帶來(lái)高方差，所以Schmid等以沒(méi)有訪問(wèn)到的節(jié)點(diǎn)的平均效用值作為baseline提出了減小方差MCCFR算法[55]（Variance Reduction MCCFR，VR-MCCFR），有效緩解了高方差的問(wèn)題，并且從理論上證明了該方法的無(wú)偏性。MCCFR算法和VR-MCCFR算法都是基于表格的CFR，這就要求大量的領(lǐng)域知識(shí)來(lái)對(duì)狀態(tài)節(jié)點(diǎn)進(jìn)行抽象處理，所以上述算法的性能和擴(kuò)展性都不理想。Li等提出一種不完全信息博弈的雙神經(jīng)網(wǎng)絡(luò)表示方法（Double Neural Counterfactual Regret Minimization，DNCRM）[56]，其中一個(gè)網(wǎng)絡(luò)表示累積遺憾，另一個(gè)網(wǎng)絡(luò)表示平均策略，并在One-Card-Poker游戲中證明了該方法的收斂速度優(yōu)于其他算法。

Waugh等使用回歸樹(shù)作為函數(shù)近似器，提出回歸CFR算法[57]，雖然一定程度上提升了性能，但是該算法仍有兩個(gè)缺點(diǎn)。首先，關(guān)于信息集的特征仍需要先驗(yàn)知識(shí)。其次，回歸CFR還是需要遍歷整個(gè)博弈樹(shù)，這使得它在非簡(jiǎn)單博弈中的時(shí)間復(fù)雜度仍然很高。隨著神經(jīng)網(wǎng)絡(luò)的出現(xiàn)，可以利用神經(jīng)網(wǎng)絡(luò)強(qiáng)大的擬合能力來(lái)作為函數(shù)近似器，這就是Deep-CFR算法[58]，該算法訓(xùn)練一個(gè)價(jià)值網(wǎng)絡(luò)來(lái)估計(jì)反事實(shí)值，同時(shí)，訓(xùn)練策略網(wǎng)絡(luò)來(lái)近似所有迭代的平均策略。但是Deep-CFR算法要求智能體記住之前所有的歷史信息，然而大多數(shù)深度強(qiáng)化學(xué)習(xí)中的智能體并沒(méi)有循環(huán)神經(jīng)網(wǎng)絡(luò)。同時(shí)，該算法的目標(biāo)是引導(dǎo)智能體獲得最大化平均回報(bào)，但是對(duì)于某些沒(méi)有終止?fàn)顟B(tài)的應(yīng)用場(chǎng)景就無(wú)法最大化平均回報(bào)，從而使得該算法失效。

Steinberger使用函數(shù)近似和部分樹(shù)遍歷來(lái)泛化博弈的狀態(tài)空間，提出Single Deep CFR（SD-CFR）算法[59]，該算法直接從過(guò)去迭代的Q值網(wǎng)絡(luò)緩沖區(qū)中提取平均策略，從而避免訓(xùn)練平均策略網(wǎng)絡(luò)，具有較低的總體近似誤差，提高了Deep-CFR的收斂速度。但是SD-CFR算法無(wú)法解決不完全信息博弈，Steinberger等改進(jìn)上述算法提出基于遺憾的深度強(qiáng)化學(xué)習(xí)方法[60]（DREAM），一種CFR的神經(jīng)網(wǎng)絡(luò)形式，在保持低方差的前提下在不完全信息中收斂至納什均衡。

Kash等[61]放寬智能體具有完美回憶的條件，提出局部無(wú)后悔學(xué)習(xí)（LONR），它使用類似Q學(xué)習(xí)的更新規(guī)則來(lái)允許在沒(méi)有終端狀態(tài)或完美回憶的情況下進(jìn)行學(xué)習(xí)，并在NoSD游戲中實(shí)現(xiàn)了收斂性。CFR系列主要算法優(yōu)缺點(diǎn)如表3所示。

表3 CFR系列主要算法優(yōu)缺點(diǎn)分析Table 3 Analysis of advantages and disadvantages of CFR series algorithms

4.2.2 虛擬自我對(duì)弈算法（NFSP）

虛擬對(duì)弈（Fictitious Play）是根據(jù)對(duì)手的平均策略做出最佳反應(yīng)來(lái)求解納什均衡的一種算法，重復(fù)迭代后該算法在兩人零和博弈、勢(shì)博弈中的平均策略將會(huì)收斂到納什均衡。但是FP算法對(duì)于對(duì)手的平均策略很敏感，很難運(yùn)用至高維度大型問(wèn)題中。Heinrich等提出廣泛的虛擬對(duì)弈（Extensive Fictitious Play），將虛擬對(duì)弈的概念擴(kuò)展到擴(kuò)展式博弈。然而，狀態(tài)在每個(gè)樹(shù)節(jié)點(diǎn)中都以表的形式表示，因此泛化訓(xùn)練是不切實(shí)際的，而且平均策略的更新需要遍歷整個(gè)游戲樹(shù)，這就給大型游戲帶來(lái)了維數(shù)災(zāi)難。Fudenberg等通過(guò)加入噪聲引入隨機(jī)虛擬對(duì)弈（Stochastic Fictitious Play，SFP）[62]，證明了該算法在零和博弈和勢(shì)博弈上的收斂性，然而，當(dāng)信息集的數(shù)目較大時(shí)，算法的性能較低。Heinrich等將FSP與神經(jīng)網(wǎng)絡(luò)函數(shù)近似結(jié)合，提出神經(jīng)虛擬自我對(duì)弈（NFSP）算法[63]，玩家由Q-學(xué)習(xí)網(wǎng)絡(luò)和監(jiān)督式學(xué)習(xí)網(wǎng)絡(luò)組成。算法通過(guò)貪婪深度Q學(xué)習(xí)（greedy deep Q-learning）計(jì)算最佳反應(yīng)，通過(guò)對(duì)智能體歷史行為的監(jiān)督學(xué)習(xí)計(jì)算平均策略。隨后，Heinrich又將NFSP推廣至部分可觀測(cè)的場(chǎng)景中，并在德州撲克上取得了不錯(cuò)的效果。作為NFSP算法的直接應(yīng)用是OpenAI和牛津大學(xué)合作提出的LOLA算法（Learning with Opponent-Learning Awareness）[64]，讓智能體在更新自己策略的同時(shí)，考慮到其他智能體的學(xué)習(xí)過(guò)程，每個(gè)LOLA智能體都調(diào)整自己的策略，用有利的方式塑造其他智能體的學(xué)習(xí)過(guò)程，該算法在重復(fù)囚徒困境博弈中收斂到了互惠策略。

但是NFSP在搜索空間和搜索深度規(guī)模較大的游戲中表現(xiàn)較差，同時(shí)，最佳反應(yīng)依賴于深度Q-Learning的計(jì)算，這需要很長(zhǎng)時(shí)間的計(jì)算才能收斂。為解決上述兩個(gè)問(wèn)題，蒙特卡洛神經(jīng)虛擬自我對(duì)弈（Monte Carlo Neural Fictitious Self Play，MC-NFSP）和異步神經(jīng)虛擬自我對(duì)弈（ANFSP）方法[65]被提出，MC-NFSP算法結(jié)合了NFSP與蒙特卡洛樹(shù)搜索的優(yōu)點(diǎn)在雙方零和的棋牌游戲中評(píng)估了該方法。實(shí)驗(yàn)表明，在奧賽羅棋中，MC-NFSP將收斂到近似納什均衡，但NFSP無(wú)法做到。ANFSP使用并行的actor來(lái)穩(wěn)定和加速訓(xùn)練，多個(gè)玩家并行進(jìn)行決策，并在監(jiān)督學(xué)習(xí)中計(jì)算小批量的梯度。與NFSP相比，這減少了數(shù)據(jù)存儲(chǔ)所需的內(nèi)存，并在雙人零和撲克游戲中進(jìn)行了實(shí)驗(yàn)驗(yàn)證，與NFSP相比，ANFSP可以更加穩(wěn)定和快速地接近近似納什均衡。

除上述方法以外還可以通過(guò)在強(qiáng)化學(xué)習(xí)中加入搜索、修改更新方式和對(duì)手建模等方法解決非完全信息博弈問(wèn)題。Brown等將搜索加入強(qiáng)化算法中提出ReBeL算法[66]并推廣到不完全信息博弈中，在利用少量領(lǐng)域知識(shí)的前提下取得良好結(jié)果。

利用強(qiáng)化學(xué)習(xí)AC算法中的優(yōu)勢(shì)值的定義（A=Q?V），即優(yōu)勢(shì)值量化了選擇某個(gè)行為的優(yōu)勢(shì)，同時(shí)也是沒(méi)有選擇某個(gè)行為的劣勢(shì)，而這正好符合非完全信息博弈中遺憾值的定義，Srinivasan等[67]基于這個(gè)思想提出三種不同的更新策略，并與AC算法和CFR算法在簡(jiǎn)化版的德州撲克環(huán)境進(jìn)行了驗(yàn)證?；诓淮_定性的量化理論，從效用的不確定性進(jìn)行獎(jiǎng)勵(lì)重塑和模型的不確定性增加探索，對(duì)非完全信息博弈條件的不確定性進(jìn)行量化，提出自適應(yīng)的切換方法（Uncertainty Fueled opponent），并與經(jīng)典的CFR和NFSP算法在德州撲克環(huán)境下進(jìn)行了比較，該方法都能穩(wěn)定地超越CFR和NFSP。

以德州撲克為代表的非完全信息擴(kuò)展式博弈雖然在CFR和NFSP系列算法下取得了突破性的進(jìn)展，但是遠(yuǎn)沒(méi)有徹底解決非完全信息擴(kuò)展式博弈，非完全信息擴(kuò)展式博弈仍然是深度強(qiáng)化學(xué)習(xí)后續(xù)突破的重難點(diǎn)。要想解決這類問(wèn)題可能首先需要解決兩個(gè)問(wèn)題：一是如何量化非完全信息下的信息的不確定性，環(huán)境的非平穩(wěn)性；二是如何科學(xué)高效解決多智能體之間的溝通、協(xié)作問(wèn)題。NFSP系列主要算法優(yōu)缺點(diǎn)如表4所示。

表4 NFSP系列主要算法優(yōu)缺點(diǎn)分析Table 4 Analysis of advantages and disadvantages of NFSP series algorithms

5 多智能體博弈強(qiáng)化學(xué)習(xí)算法的重難點(diǎn)

博弈論主要是沖突環(huán)境下的決策理論，將完善的博弈理論加入到強(qiáng)化學(xué)習(xí)獲得很多了令人驚喜的結(jié)果，特別是對(duì)于一些無(wú)法解決的不完全信息博弈問(wèn)題，解決上述問(wèn)題最主要的算法有CFR系列算法和NFSP系列算法，CFR系列算法存在的主要難點(diǎn)：一是要求智能體具有完美回憶，這在很多實(shí)際博弈場(chǎng)景中很難滿足；二是算法的收斂性很難保證；三是由于要遍歷很多博弈節(jié)點(diǎn)，因此需要大量?jī)?nèi)存空間。NFSP系列算法存在的主要難點(diǎn)有：一是NFSP系列算法依賴于off-policy的深度Q值網(wǎng)絡(luò)，因此在搜索規(guī)模大、即時(shí)策略場(chǎng)景下很難收斂；二是在訓(xùn)練時(shí)智能體都是獨(dú)立更新，沒(méi)有利用對(duì)手的信息；三是NFSP的最佳響應(yīng)計(jì)算依賴于Deep Q-learning，收斂時(shí)間長(zhǎng)且計(jì)算量大。除以上難點(diǎn)外，當(dāng)前博弈強(qiáng)化學(xué)習(xí)算法還需要在以下幾個(gè)方面重點(diǎn)突破。

5.1 博弈強(qiáng)化學(xué)習(xí)算法的優(yōu)化

5.1.1 收斂性

當(dāng)前大多數(shù)的博弈強(qiáng)化學(xué)習(xí)算法主要以實(shí)驗(yàn)為基礎(chǔ)，由于深度神經(jīng)網(wǎng)絡(luò)強(qiáng)大的擬合性，使得很多算法在大多數(shù)情況都可以較好的收斂，但是并沒(méi)有從理論上給出嚴(yán)格的收斂性證明。同時(shí)對(duì)于有收斂性證明的算法，其收斂條件往往過(guò)于苛刻，如Nash-Q Learning算法、Mean Field算法要求在博弈的每個(gè)階段都存在鞍點(diǎn)或者全局最優(yōu)點(diǎn)，甚至不允許鞍點(diǎn)和全局最優(yōu)點(diǎn)交替出現(xiàn)，這使得滿足上述收斂條件的博弈幾乎很少，所以該算法所能解決的問(wèn)題有限。

5.1.2 求解法則

算法博弈論研究的著名學(xué)者Roughgarden證明了納什均衡的求解是一個(gè)NP-hard問(wèn)題。一些傳統(tǒng)的數(shù)學(xué)分析算法，比如Lemke-Howso算法、全局牛頓算法、分布式原始對(duì)偶算法、投影梯度算法等用于求解博弈的Nash平衡時(shí)，其基本思路是在一定的假設(shè)條件下將Nash平衡的計(jì)算問(wèn)題轉(zhuǎn)換為某類優(yōu)化問(wèn)題、變分不等式問(wèn)題或互補(bǔ)問(wèn)題等再設(shè)計(jì)相關(guān)算法求解。但這類方法大多要求博弈參與人的支付函數(shù)具有較高的光滑性，并且這些算法本身常常依賴初始點(diǎn)的選取，求解復(fù)雜度過(guò)高，有時(shí)因?yàn)榍蠼鈺r(shí)間過(guò)長(zhǎng)導(dǎo)致最后無(wú)法求出正確的納什均衡值，這些都在一定程度上限制了這類算法的應(yīng)用范圍。

5.2 博弈強(qiáng)化學(xué)習(xí)算法的模型

將博弈理論融入到強(qiáng)化學(xué)習(xí)中，用博弈論的知識(shí)來(lái)引導(dǎo)智能體的學(xué)習(xí)過(guò)程，但是在具體的建模過(guò)程中考慮的因素較少，導(dǎo)致模型過(guò)度簡(jiǎn)化。例如，Nash-Q算法采用的就是納什均衡、correlated-Q算法采用的是相關(guān)均衡而Friend-or-Foe Q-Learning算法將多個(gè)智能體簡(jiǎn)化為Friend和Foe兩組，都沒(méi)有考慮在實(shí)際博弈過(guò)程中可能會(huì)出現(xiàn)的其他情況，如不可置信的威脅和有限理性等，這些因素都會(huì)影響博弈強(qiáng)化學(xué)習(xí)算法模型的科學(xué)性和合理性。同時(shí)，算法的最終目標(biāo)是想要獲得最科學(xué)合理的純策略，因此混合策略的納什均衡一定程度上不滿足實(shí)際要求，然而純策略的納什均衡并非所有博弈場(chǎng)景都存在。

5.3 博弈強(qiáng)化學(xué)習(xí)算法的通用性和擴(kuò)展性

現(xiàn)有算法研究的主要范圍局限于對(duì)稱博弈，即博弈中的每個(gè)玩家的策略集和支付函數(shù)都是相同的。無(wú)論是Nash-Q Learning算法研究的Grid World Games還是CFR系列算法研究的德?lián)鋯?wèn)題都是屬于對(duì)稱博弈。然而，對(duì)稱博弈相比于非對(duì)稱博弈是個(gè)很小的集合。由于非對(duì)稱博弈中的玩家的策略集和支付函數(shù)是不相同的，所以在非對(duì)稱博弈中對(duì)于問(wèn)題的建模難度會(huì)比對(duì)稱博弈大，同時(shí)遇到的不確定因素也會(huì)更多。然而從逼近和仿真現(xiàn)實(shí)博弈的角度來(lái)說(shuō)，研究非對(duì)稱博弈意義要大于對(duì)稱博弈。

6 多智能體強(qiáng)化學(xué)習(xí)算法研究展望

6.1 基于智能優(yōu)化算法求解納什均衡

求解納什均衡是個(gè)復(fù)雜優(yōu)化問(wèn)題，其優(yōu)化目標(biāo)函數(shù)往往具有不可導(dǎo)、不連續(xù)、存在多個(gè)局部最優(yōu)解的特點(diǎn)，這些性質(zhì)可能使得傳統(tǒng)優(yōu)化算法失效。群體智能算法是受生物機(jī)制啟發(fā)的一類算法，在路徑優(yōu)化、網(wǎng)絡(luò)優(yōu)化等領(lǐng)域獲得廣泛應(yīng)用，因此利用群體智能算法求解納什均衡理論上是可行的。當(dāng)前群體智能算法主要有兩大類，一是以蟻群優(yōu)化算法（Ant Colony Optimization，ACO）為代表；二是以粒子群算法（Particle Swarm Optimization，PSO）為代表。

ACO算法思想來(lái)源于螞蟻尋食中的通信機(jī)制，螞蟻在尋找食物過(guò)程中通過(guò)分泌信息素，通過(guò)信息素的濃度來(lái)選取最佳路徑。對(duì)于ACO算法的改進(jìn)有Max-Min Ant System（MMAS）和Ant Colony System（ACS）算法，MMAS算法的主要特征是在每一次迭代結(jié)束后，僅最優(yōu)螞蟻對(duì)其所經(jīng)過(guò)的最優(yōu)路徑進(jìn)行信息素更新，其他螞蟻不參與更新，ACS加入偽隨機(jī)比例規(guī)則和離線信息素更新規(guī)則，并且只對(duì)全局最優(yōu)路徑的信息素進(jìn)行更新。

PSO算法是科學(xué)家們?cè)谟^察鳥(niǎo)群覓食時(shí)利用計(jì)算機(jī)模擬鳥(niǎo)群的聚集行為總結(jié)出一種群智能算法，可以在全局隨機(jī)搜索，算法在運(yùn)行之前會(huì)在自身建立的搜尋空間中設(shè)置一群隨機(jī)的粒子，粒子通過(guò)迭代的過(guò)程不斷地更新自己的速度、位置逐漸朝著最優(yōu)位置逼近，最終會(huì)找到最優(yōu)解。因此，這些粒子可以認(rèn)為是解決優(yōu)化問(wèn)題的隨機(jī)解。其中，粒子會(huì)朝著最優(yōu)解迭代，通過(guò)個(gè)體極值：Pbest是粒子在尋找最優(yōu)解過(guò)程中遇到的最好位置，稱為自身找到的最優(yōu)解；Gbest表示整個(gè)搜索過(guò)程群體的最優(yōu)位置，空間中所有的粒子都會(huì)利用這兩個(gè)值得到最優(yōu)解，進(jìn)而不斷更新自己。因此，借鑒生物進(jìn)化理論和生物行為規(guī)律的群體智能算法來(lái)仿真和模擬博弈平衡解的動(dòng)態(tài)實(shí)現(xiàn)過(guò)程可以成為了研究博弈問(wèn)題均衡解的一種新的探索和途徑，ACO和PSO算法的流程如圖3所示。

圖3 ACO和PSO算法的流圖Fig.3 Flow chart of ACO and PSO

兩類算法本質(zhì)上都是智能優(yōu)化算法，而求解納什均衡本質(zhì)上也是個(gè)優(yōu)化問(wèn)題，因此利用智能優(yōu)化算法求解納什均衡是可行的，但是ACO和PSO算法的主要區(qū)別在于PSO所需設(shè)置的參數(shù)較少，主要用于連續(xù)優(yōu)化問(wèn)題的求解；而ACO需設(shè)置的參數(shù)相對(duì)較多，主要用于離散優(yōu)化問(wèn)題的求解，因此在求解納什均衡時(shí)可根據(jù)博弈具體場(chǎng)景確定問(wèn)題類型來(lái)選擇何種智能優(yōu)化算法。

6.2 基于元博弈的算法模型

元博弈理論由Howard在1971年首次提出，其核心思想是在原有博弈的基礎(chǔ)上構(gòu)建一種假想的博弈。而在該博弈中，某個(gè)智能體的動(dòng)作將是其他所有智能體聯(lián)合動(dòng)作的反應(yīng)函數(shù)（Reaction Function）。對(duì)于一個(gè)n人一般式博弈以及該博弈中的某個(gè)聯(lián)合動(dòng)作a，如果存在一個(gè)元博弈ηG和這個(gè)元博弈的一個(gè)純策略納什均衡π，滿足φ(π)=a，則稱聯(lián)合動(dòng)作a為博弈G的一個(gè)元均衡。具體的，可以稱a為元博弈ηG導(dǎo)出的一個(gè)元均衡。φ定義為元博弈中任意動(dòng)作到基本博弈中的動(dòng)作的映射。元均衡和純策略的納什均衡最主要的區(qū)別在于，不存在純策略納什均衡的博弈也存在元均衡，因?yàn)樵谌我庖粋€(gè)一般式博弈中，至少存在一個(gè)元均衡，從該博弈的完全元博弈中推導(dǎo)出的元均衡一定存在。因此基于元均衡的算法模型更有利于求解最終的純策略。

由于元博弈是從原始博弈的基礎(chǔ)上推導(dǎo)而來(lái)，使得智能體的動(dòng)作變成相應(yīng)的反應(yīng)函數(shù)，因此動(dòng)作的數(shù)量是增加的。以三人矩陣博弈為例，||S=m為狀態(tài)集的大小為玩家動(dòng)作集的大小，因此雙人矩陣博弈的空間復(fù)雜度為2mn3。擴(kuò)展成元博弈321G后，玩家1的動(dòng)作集大小為n2，玩家2的動(dòng)作集大小為n3，玩家3的動(dòng)作集大小為n5，所以元博弈321G的空間復(fù)雜度為2mn10?；谠┺牡乃惴Ｐ碗m然增加了空間復(fù)雜度，但是該模型在理論上可以保證純策略的存在性。

6.3 基于復(fù)因子動(dòng)力學(xué)擴(kuò)展非對(duì)稱博弈

非對(duì)稱博弈問(wèn)題的求解困難主要在于建模的復(fù)雜性，并且不確定因素相比較對(duì)稱博弈更多。然而，如果能將復(fù)雜的非對(duì)稱博弈與對(duì)稱博弈聯(lián)系起來(lái)，建立合適的轉(zhuǎn)換關(guān)系，即將復(fù)雜的非對(duì)稱博弈轉(zhuǎn)換為多個(gè)相對(duì)簡(jiǎn)單的對(duì)稱博弈，利用現(xiàn)有的解決對(duì)稱博弈的理論方法進(jìn)行求解，則在一定程度上解決非對(duì)稱博弈變?yōu)榭赡?。?fù)制動(dòng)力學(xué)本質(zhì)上是一個(gè)微分方程系統(tǒng)，它描述了一個(gè)純策略種群（或復(fù)制因子）如何隨著時(shí)間演化。在它們最基本的形式中，它們符合生物的選擇原則，即適者生存。具體來(lái)說(shuō)，選擇復(fù)制器的動(dòng)態(tài)機(jī)制表達(dá)如下：

這個(gè)等式本質(zhì)上比較了一個(gè)策略的收益和整個(gè)總體的平均收益。如果這種策略的得分高于平均水平，它將能夠復(fù)制后代，如果得分低于平均水平，它在種群中的存在將減少，甚至有可能走向滅絕。同時(shí)，如果策略組合(x,y)是非對(duì)稱博弈G=(S1,S2,A,B)的納什均衡，并且對(duì)于所有的i,j，都有則x是單人博弈BT的納什均衡，y是單人博弈A的納什均衡，反之也正確。因此可以通過(guò)上述的定理結(jié)論將非對(duì)稱博弈轉(zhuǎn)換成為對(duì)稱博弈，從而使用現(xiàn)有的對(duì)稱博弈算法進(jìn)行求解。

7 結(jié)論

本文從博弈論的角度出發(fā)，梳理了近年來(lái)出現(xiàn)的多智能體強(qiáng)化學(xué)習(xí)算法。首先簡(jiǎn)要介紹了多智能體系統(tǒng)的背景知識(shí)、主要難點(diǎn)和解決技術(shù)路線。為解決多智能體系統(tǒng)中智能體之間的相互關(guān)系和一些不存在最優(yōu)解的實(shí)際問(wèn)題，同時(shí)為了增加求解結(jié)果的合理性，博弈理論被引入強(qiáng)化學(xué)習(xí)算法中。文中以標(biāo)準(zhǔn)型博弈和擴(kuò)展式博弈為分類方法，從共同利益博弈、不同利益博弈、完全信息博弈和不完全信息博弈等角度對(duì)多智能體深度強(qiáng)化學(xué)習(xí)算法進(jìn)行了分類，對(duì)各類算法進(jìn)行了橫向的對(duì)比，指出了各類算法的優(yōu)缺點(diǎn)，并從算法的收斂性、均衡解的求解方式和博弈問(wèn)題的建模三個(gè)方面總結(jié)了當(dāng)前博弈強(qiáng)化學(xué)習(xí)算法的重難點(diǎn)。針對(duì)上述存在的問(wèn)題，結(jié)合智能優(yōu)化算法、元博弈理論和復(fù)因子動(dòng)力學(xué)給出了可能解決上述問(wèn)題的具體研究方向。實(shí)現(xiàn)博弈強(qiáng)化學(xué)習(xí)在復(fù)雜、不確定系統(tǒng)中的優(yōu)化控制問(wèn)題，對(duì)于推動(dòng)機(jī)器人控制和軍事決策等各領(lǐng)域的發(fā)展有重要意義，特別是在未來(lái)智能化戰(zhàn)爭(zhēng)中，基于規(guī)則的智能體體現(xiàn)的往往是指揮科學(xué)，而基于強(qiáng)化學(xué)習(xí)的智能體可能會(huì)體現(xiàn)指揮藝術(shù)，而指揮藝術(shù)在未來(lái)戰(zhàn)爭(zhēng)中仍然發(fā)揮著不會(huì)替代的作用。所以，博弈強(qiáng)化學(xué)習(xí)可能在更加科學(xué)、合理的智能輔助決策系統(tǒng)越來(lái)越關(guān)鍵。