多智能體博弈強化學習研究綜述

王 軍，曹 雷，陳希亮，賴 俊，章樂貴

陸軍工程大學 指揮控制工程學院，南京210007

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

1 多智能體深度強化學習關鍵科學問題

強化學習主要解決的是序貫決策問題，需要智能體不斷地與環境進行交互和嘗試，當智能體通過動作與環境進行交互時，環境會給智能體一個即時回報，智能體會根據回報評估采取的動作，如果是正向的回報則加大采取該動作的概率，如果是負向的回報則減小采取該動作的概率，同時智能體的動作可能會改變環境，不斷重復，最終找到最優策略使得累積回報的期望最大。在單智能體任務中，算法只需要考慮一個智能體的動作和狀態，相比單智能體深度強化學習，多智能體深度強化學習要考慮的動作和狀態空間都更大，每個智能體的回報不僅和環境有關，與其他智能體的動作也緊密聯系，這使得多智能體學習任務的求解更加復雜。由單智能體系統向多智能體系統過渡時主要存在以下難點。

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

（2）環境非平穩性。多智能體強化學習中環境狀態轉移函數取決于聯合動作，導致環境的非平穩性，解決該問題的主要辦法有如下幾種：一是采用AC框架，通過在訓練過程中獲得其他智能體的信息和行動，智能體不會經歷環境動態的意外變化，二是采用對手建模，通過模擬其他智能體的策略，可以穩定智能體的訓練過程，三是利用元學習更快適應非平穩性環境。

（3）信度分配。當智能體的數量增加時，信度分配是無法回避的問題，解決該問題的主要方法有平均分配、差分回報分配、優勢函數分配以及Deepmind提出的基于情景記憶檢索TVT算法[4]。

隨著智能體數量的增加，最大化長期累積回報的期望作為學習目標很難得到收斂結果，某些特殊收斂點所對應的策略也不符合實際情況，所以多智能體強化學習中各智能體的學習目標還應該增加合理性和收斂性，并且可以從具體理論上解釋。同時，在很多實際博弈場景下，最優解未必存在，這些問題都阻礙多智能體強化學習進一步發展。隨著博弈理論的引入，很好地解決了多智能體直接的相互關系，博弈中的均衡解可以代替最優解以求得相對有效的策略，同時該策略具有合理性。

多智能體系統中智能體之間的關系可以用博弈論中玩家之間的關系來表示，一般分為競爭、合作和混合型。博弈論中按照博弈玩家同時決策還是先后決策分別稱為標準型博弈（Normal form Games）和擴展式博弈（Extensive form Games），囚徒困境就是常見的標準型博弈，而圍棋就是常見的擴展式博弈。另外，按照博弈中所有玩家收益的和是否為零可分為零和博弈和一般和博弈，根據玩家的目標是否一致分為共同利益博弈和不同利益博弈。擴展式博弈中根據信息是否已知可以劃分為完全信息擴展式博弈和不完全信息擴展式博弈[5]。

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

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

2 多智能體博弈強化學習基本概念

本章重點敘述多智能體強化學習和博弈論的相關概念，最簡單的強化學習數學模型是馬爾可夫決策過程，博弈論中最核心的概念是納什均衡。

2.1 馬爾可夫決策過程（MDP）

MDP是一個由五元組S,A,P,R,r構成。其中，S是包含所有狀態的有限集合，A是包含智能體所有動作的有限集合，P定義為P:S×A×S→[0,1]的轉換函數，R定義為R:S×A×S→R的回報函數，r∈[]0,1是折扣系數，用于平衡智能體的瞬時回報和長期回報對總回報的影響。

MDP的求解目標是找到期望回報值最大的最優策略σ?，一般用最優狀態動作值函數形式化表征期望回報當智能體的數量超過一個，同時環境的改變和每個智能體的回報取決于所有智能體的動作和當前狀態時則稱為多智能體馬爾可夫決策過程。

2.2 隨機博弈（Stochastic Games，SG）

隨機博弈可以看成MDP向多人博弈的推廣，由如下的六元組定義：N,S,Ai,P,Ri,γ，其中N為博弈玩家的個數，當玩家的個數為1時，即退化為MDP，Ai為第i個玩家的動作，A-i為除第i個玩家外其他玩家的動作，記A=A1×A2×…×An，Ri為第i個玩家的回報函數，當每個玩家的回報函數相同時則稱此博弈為團隊博弈（Team Games）。

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

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

2.4 納什均衡

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

2.5 元博弈（Metagame）

對于n人一般式博弈其關于智能體i的一階元博弈iG可以表示成iG=N,Ai,…,，其中Fi表示智能體i的反應函數空間。反應函數的定義為f:A-i→Ai。對于智能體i的任意反應函數f∈Fi，以及其他智能體的任意聯合動作

3 標準型博弈

在標準型博弈中，通過博弈玩家的目標是否相同，劃分為共同利益博弈和不同利益博弈，常見的共同利益博弈有團隊博弈、勢博弈和Dec-POMDP，研究共同利益博弈最大的優勢在于可以使用具有理論保證的單智能體強化學習算法。

3.1 共同利益博弈

3.1.1 團隊博弈

團隊博弈被反復研究的重要原因是其對于構建分布式AI（DAI）至關重要。團隊博弈中，每個智能體只需要維護自己的值函數，而且值函數只取決于當前的狀態和動作，從而避免了考慮聯合動作時的環境非平穩和維度爆炸問題。因此，很多單智能體算法可以運用在該問題上。如果博弈存在多個納什均衡，即使每個智能體之間的學習目標并不沖突，也會導致智能體最終不會學到最優策略的問題。

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

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

Yang等借用了平均場論（Mean Field Theory，MFT）的思想，其對多智能體系統給出了一個近似假設：對某個智能體，其他所有智能體對其產生的作用可以用一個均值替代，提出了平均場多智能體強化學習算法（Mean Field）[11]，將轉化為只包含相鄰智能體相互作用的形式：表示鄰居節點的個數。Anahtarci等[12]對智能體

其中，N(j)表示智能體j鄰居智能體的標簽集，Nj=之間的交互作用進行近似，降低智能體交互的復雜度，并且在理論上給出了收斂性證明，能夠收斂到納什均衡點。針對智能體的數量接近無限的情況，Elie等[13]在僅依賴平均場博弈的基本動力學假設的條件下，根據每個學習迭代步驟中出現的累積誤差來量化近似納什均衡的質量，首次展示了無模型學習算法向非平穩MFG均衡的收斂。

除上述方法外，分解MDPs也可以有效解決團隊博弈問題，回報函數可能只與狀態的部分特征有關，而與其他特征是獨立的，利用因子化的表達，可以避免在整個狀態-動作空間進行迭代求解。受分解MDPs思想的啟發，Vlassis等[14]將多智能體系統視為一個大型馬爾可夫決策過程（MDP），基于動態貝葉斯網絡和協調圖（coordination graphs）使用因式分解將線性值函數作為聯合值函數的近似值，值函數的這種分解允許智能體在行動時協調其動作，有效解決狀態和動作空間中的指數爆炸問題，最終可以找到全局最優聯合動作。

然而，協調圖在實際應用中可能并不總是可用的，理想的方法是讓智能體從任務中自動學習值函數分解，深度神經網絡是學習這類分解的有效方法，因此多種特殊的神經網絡結構被提出，典型的算法包括VDN、QMIX、QTRAN、Qatten和QPD等。VDN[15]在值函數可分解的假設下要求聯合值函數是每個智能體值函數的線性和，即

由于線性假設這個前提條件，VDN算法所適用的場景比較少。為此，使用神經網絡近似聯合值函數的算法QMIX[16]被提出，QMIX利用集中式訓練的優勢，使用全局狀態進行訓練但QMIX為了保證獨立全局最大化操作，假設聯合值函數對個體值函數是單調的，用公式來表示為：

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

表1 團隊博弈下的主要算法的優缺點Table 1 Advantages and disadvantages of main algorithms under team game

3.1.2 隨機勢博弈（SPG）

博弈中，如果每個玩家對于自身目標改變或策略選取，都可以映射到某個全局函數中去，這個函數就叫做勢函數（potential function），這個博弈稱為勢博弈（potential game）。一般來說，勢博弈可以被看作多智能體博弈的“單智能體成分”[20]，因為所有智能體在SPG中的利益都被描述為一個單一的勢函數。

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

3.1.3 Dec-POMDP

在Dec-POMDP中，多智能體的目標是在能觀察到的局部信息基礎上實現全部獎勵的最大化，因此在共同利益博弈中解決Dec-POMDP問題是十分困難的，目前大多數Dec-POMDP的解決算法，包括上面的VDN、QMIX和QTRAN等算法，都是基于集中式訓練和分散式執行（CTDE）的學習框架。在表示智能體的局部策略時，通常使用隨機有限狀態控制器，這樣可以將Dec-POMDP表述為非線性規劃問題，從而使用現有的優化算法，從Dec-POMDP到連續狀態MDP的轉換，稱為占領狀態MDP（occupancy-state MDP）。占用狀態本質上是關于隱藏狀態和觀測-行動對的聯合歷史分布，這兩者的區別是在標準的MDP中，智能體的學習目標是最優狀態動作值函數，而oMDP中的智能體的學習目標是占用狀態和聯合行動的最優值函數，這些最優值函數往往都是分段線性的，最重要的是這些限制會使得智能體最終會收斂至全局最優而不是局部最優。

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

3.2 不同利益博弈

不同利益博弈是指玩家的學習目標不同，根據所有玩家收益之和是否為零分為有限零和、一般和博弈。

3.2.1 有限零和博弈

有限零和博弈是指參與博弈的玩家個數有限，并且是嚴格的競爭關系，所有玩家的總體收益和支出的總和為零。在兩人零和博弈中，由于兩個玩家的學習目標完全相反，其納什均衡解本質上是一個鞍點。Adler[29]證明了兩人零和博弈和線性優化的等價性，即兩人零和博弈可以構建為一個線性優化問題，任意一個線性優化問題也可以簡化為一個零和博弈問題。在解決兩人零和博弈問題中最典型的方法是最小最大值定理（The Minimax Theorem），其可以表示為如下公式：

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

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

表2 有限零和博弈下主要算法的優缺點Table 2 Advantages and disadvantages of main algorithms under finite zero-sum game

3.2.2 有限一般和博弈

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

傳統Q-learning算法應用于多智能體系統時，每個智能體的策略都在隨著訓練的進行而變化，對每個智能體來說環境都是不穩定的，而策略梯度算法應用于多智能體系統時通常表現出很高的方差。Lowe等提出一種Actor-Critic策略梯度算法的擴展算法[43]，并利用集中訓練分散執行框架，證明該算法在競爭和合作場景下都能有效收斂。在解決多智能體協調問題中，Stackelberg均衡在帕累托優勢方面比Nash均衡具有更好的收斂性，Zhang等定義了尋找Stackelberg均衡的雙層強化學習問題，并提出了一種新的雙層AC學習方法[44]，允許智能體擁有不同的知識庫，并在矩陣博弈中證明了雙層AC可以收斂至Stackelberg均衡。

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

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

4 擴展式博弈

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

4.1 完全信息的擴展式博弈

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

4.2 不完全信息的擴展式博弈

現實中博弈往往以不完全信息的擴展式博弈存在，如即時戰略游戲和軍事對抗，不完全信息的擴展式博弈被認為是下一代人工智能的重難點之一。解決不完全信息的擴展式博弈主要有三個難點，一是子博弈之間相互關聯，二是存在狀態不可分的信息集，這使得強化學習中基于狀態的值估計方法不再適用，三是博弈的求解規模比較大，如橋牌和德州撲克的信息集數目分別為1067和10162。近幾年以德州撲克為例，不完全信息的擴展式博弈取得了不錯的進展。

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

4.2.1 反事實遺憾值最小化算法（CFR）

記Pσ i(s)為玩家i從初始狀態出發，遵循策略σ到達狀態s的概率，Pσ-i(s)為從初始狀態出發，除玩家i外，所有玩家都遵循策略σ到達狀態s的概率，Pσ i(z|s)玩家i從狀態s出發，遵循策略σ到達終止狀態z的概率，ui(z)為到達終止狀態的效用函數，反事實值的定義如下：

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

CFR算法結合了遺憾值最小化算法[51]和平均策略，通過最小化單個信息集合上的遺憾值來達到最小化全局遺憾值的目標，最終使得博弈過程中的平均策略趨近于納什均衡。由于需要遍歷整個博弈樹，時間復雜度和收斂速度慢是算法的主要缺點。

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

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

Waugh等使用回歸樹作為函數近似器，提出回歸CFR算法[57]，雖然一定程度上提升了性能，但是該算法仍有兩個缺點。首先，關于信息集的特征仍需要先驗知識。其次，回歸CFR還是需要遍歷整個博弈樹，這使得它在非簡單博弈中的時間復雜度仍然很高。隨著神經網絡的出現，可以利用神經網絡強大的擬合能力來作為函數近似器，這就是Deep-CFR算法[58]，該算法訓練一個價值網絡來估計反事實值，同時，訓練策略網絡來近似所有迭代的平均策略。但是Deep-CFR算法要求智能體記住之前所有的歷史信息，然而大多數深度強化學習中的智能體并沒有循環神經網絡。同時，該算法的目標是引導智能體獲得最大化平均回報，但是對于某些沒有終止狀態的應用場景就無法最大化平均回報，從而使得該算法失效。

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

Kash等[61]放寬智能體具有完美回憶的條件，提出局部無后悔學習（LONR），它使用類似Q學習的更新規則來允許在沒有終端狀態或完美回憶的情況下進行學習，并在NoSD游戲中實現了收斂性。CFR系列主要算法優缺點如表3所示。

表3 CFR系列主要算法優缺點分析Table 3 Analysis of advantages and disadvantages of CFR series algorithms

4.2.2 虛擬自我對弈算法（NFSP）

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

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

除上述方法以外還可以通過在強化學習中加入搜索、修改更新方式和對手建模等方法解決非完全信息博弈問題。Brown等將搜索加入強化算法中提出ReBeL算法[66]并推廣到不完全信息博弈中，在利用少量領域知識的前提下取得良好結果。

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

以德州撲克為代表的非完全信息擴展式博弈雖然在CFR和NFSP系列算法下取得了突破性的進展，但是遠沒有徹底解決非完全信息擴展式博弈，非完全信息擴展式博弈仍然是深度強化學習后續突破的重難點。要想解決這類問題可能首先需要解決兩個問題：一是如何量化非完全信息下的信息的不確定性，環境的非平穩性；二是如何科學高效解決多智能體之間的溝通、協作問題。NFSP系列主要算法優缺點如表4所示。

表4 NFSP系列主要算法優缺點分析Table 4 Analysis of advantages and disadvantages of NFSP series algorithms

5 多智能體博弈強化學習算法的重難點

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

5.1 博弈強化學習算法的優化

5.1.1 收斂性

當前大多數的博弈強化學習算法主要以實驗為基礎，由于深度神經網絡強大的擬合性，使得很多算法在大多數情況都可以較好的收斂，但是并沒有從理論上給出嚴格的收斂性證明。同時對于有收斂性證明的算法，其收斂條件往往過于苛刻，如Nash-Q Learning算法、Mean Field算法要求在博弈的每個階段都存在鞍點或者全局最優點，甚至不允許鞍點和全局最優點交替出現，這使得滿足上述收斂條件的博弈幾乎很少，所以該算法所能解決的問題有限。

5.1.2 求解法則

算法博弈論研究的著名學者Roughgarden證明了納什均衡的求解是一個NP-hard問題。一些傳統的數學分析算法，比如Lemke-Howso算法、全局牛頓算法、分布式原始對偶算法、投影梯度算法等用于求解博弈的Nash平衡時，其基本思路是在一定的假設條件下將Nash平衡的計算問題轉換為某類優化問題、變分不等式問題或互補問題等再設計相關算法求解。但這類方法大多要求博弈參與人的支付函數具有較高的光滑性，并且這些算法本身常常依賴初始點的選取，求解復雜度過高，有時因為求解時間過長導致最后無法求出正確的納什均衡值，這些都在一定程度上限制了這類算法的應用范圍。

5.2 博弈強化學習算法的模型

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

5.3 博弈強化學習算法的通用性和擴展性

現有算法研究的主要范圍局限于對稱博弈，即博弈中的每個玩家的策略集和支付函數都是相同的。無論是Nash-Q Learning算法研究的Grid World Games還是CFR系列算法研究的德撲問題都是屬于對稱博弈。然而，對稱博弈相比于非對稱博弈是個很小的集合。由于非對稱博弈中的玩家的策略集和支付函數是不相同的，所以在非對稱博弈中對于問題的建模難度會比對稱博弈大，同時遇到的不確定因素也會更多。然而從逼近和仿真現實博弈的角度來說，研究非對稱博弈意義要大于對稱博弈。

6 多智能體強化學習算法研究展望

6.1 基于智能優化算法求解納什均衡

求解納什均衡是個復雜優化問題，其優化目標函數往往具有不可導、不連續、存在多個局部最優解的特點，這些性質可能使得傳統優化算法失效。群體智能算法是受生物機制啟發的一類算法，在路徑優化、網絡優化等領域獲得廣泛應用，因此利用群體智能算法求解納什均衡理論上是可行的。當前群體智能算法主要有兩大類，一是以蟻群優化算法（Ant Colony Optimization，ACO）為代表；二是以粒子群算法（Particle Swarm Optimization，PSO）為代表。

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

PSO算法是科學家們在觀察鳥群覓食時利用計算機模擬鳥群的聚集行為總結出一種群智能算法，可以在全局隨機搜索，算法在運行之前會在自身建立的搜尋空間中設置一群隨機的粒子，粒子通過迭代的過程不斷地更新自己的速度、位置逐漸朝著最優位置逼近，最終會找到最優解。因此，這些粒子可以認為是解決優化問題的隨機解。其中，粒子會朝著最優解迭代，通過個體極值：Pbest是粒子在尋找最優解過程中遇到的最好位置，稱為自身找到的最優解；Gbest表示整個搜索過程群體的最優位置，空間中所有的粒子都會利用這兩個值得到最優解，進而不斷更新自己。因此，借鑒生物進化理論和生物行為規律的群體智能算法來仿真和模擬博弈平衡解的動態實現過程可以成為了研究博弈問題均衡解的一種新的探索和途徑，ACO和PSO算法的流程如圖3所示。

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

兩類算法本質上都是智能優化算法，而求解納什均衡本質上也是個優化問題，因此利用智能優化算法求解納什均衡是可行的，但是ACO和PSO算法的主要區別在于PSO所需設置的參數較少，主要用于連續優化問題的求解；而ACO需設置的參數相對較多，主要用于離散優化問題的求解，因此在求解納什均衡時可根據博弈具體場景確定問題類型來選擇何種智能優化算法。

6.2 基于元博弈的算法模型

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

由于元博弈是從原始博弈的基礎上推導而來，使得智能體的動作變成相應的反應函數，因此動作的數量是增加的。以三人矩陣博弈為例，||S=m為狀態集的大小為玩家動作集的大小，因此雙人矩陣博弈的空間復雜度為2mn3。擴展成元博弈321G后，玩家1的動作集大小為n2，玩家2的動作集大小為n3，玩家3的動作集大小為n5，所以元博弈321G的空間復雜度為2mn10。基于元博弈的算法模型雖然增加了空間復雜度，但是該模型在理論上可以保證純策略的存在性。

6.3 基于復因子動力學擴展非對稱博弈

非對稱博弈問題的求解困難主要在于建模的復雜性，并且不確定因素相比較對稱博弈更多。然而，如果能將復雜的非對稱博弈與對稱博弈聯系起來，建立合適的轉換關系，即將復雜的非對稱博弈轉換為多個相對簡單的對稱博弈，利用現有的解決對稱博弈的理論方法進行求解，則在一定程度上解決非對稱博弈變為可能。復制動力學本質上是一個微分方程系統，它描述了一個純策略種群（或復制因子）如何隨著時間演化。在它們最基本的形式中，它們符合生物的選擇原則，即適者生存。具體來說，選擇復制器的動態機制表達如下：

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

7 結論

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