【ZiDongHua 之自動(dòng)化學(xué)院派收錄關(guān)鍵詞：同濟(jì)大學(xué) 人工智能 】
 
　　同濟(jì)大學(xué)陳杰院士團(tuán)隊(duì) | 對(duì)抗博弈的決策方法綜述研究團(tuán)隊(duì)
 
　　李修賢,孟敏,洪奕光,陳杰：同濟(jì)大學(xué)電子與信息工程學(xué)院，上海自主智能無(wú)人系統(tǒng)科學(xué)中心研究意義
 
　　與人工智能關(guān)系密切的博弈論在眾多領(lǐng)域具有廣泛應(yīng)用。而在許多實(shí)際應(yīng)用中，如撲克游戲、追逃問(wèn)題、海岸防衛(wèi)、網(wǎng)絡(luò)安全等，玩家之間往往具有敵對(duì)立場(chǎng)，即每個(gè)玩家明顯具有自私行為并對(duì)其他玩家造成利益損失。在這些場(chǎng)景中，對(duì)抗博弈的高效智能決策方法對(duì)于玩家至關(guān)重要，其在國(guó)計(jì)民生、科技發(fā)展及國(guó)防安全等多方面扮演著重要角色。
 
 
　　本文工作
 
　　基于此，本文就對(duì)抗博弈的三種主要模型進(jìn)行了系統(tǒng)性的綜述，包括零和正規(guī)式與擴(kuò)展式博弈、Stackelberg博弈以及零和微分博弈，旨在從博弈模型、研究分類(lèi)、流行算法及未來(lái)展望等多維度對(duì)對(duì)抗博弈進(jìn)行概述。值得注意的是，這三種博弈模型并不相互獨(dú)立，從不同角度來(lái)看有可能具有一定的重疊性。例如，Stackelberg博弈和微分博弈也可以是零和博弈。
 
　　(1) 研究分類(lèi)
 
　　正規(guī)式博弈用于描述玩家同時(shí)決策的情形，而擴(kuò)展式博弈應(yīng)用于玩家序貫決策的情況，特別對(duì)于不完美信息博弈尤其重要。而零和博弈意味著所有玩家的效用函數(shù)之和始終為零。已有文獻(xiàn)中，零和正規(guī)式和擴(kuò)展式博弈的研究大致可分為：雙線性博弈、鞍點(diǎn)問(wèn)題、多玩家零和博弈、團(tuán)隊(duì)博弈和不完美信息零和博弈。
 
　　Stackelberg博弈用于處理玩家具有不對(duì)稱信息的情形，其中領(lǐng)導(dǎo)者具有信息與決策的主導(dǎo)權(quán)，并知道跟隨者們的效用函數(shù)，而跟隨者們通常在領(lǐng)導(dǎo)者做出決策后執(zhí)行最佳響應(yīng)動(dòng)作。此類(lèi)博弈主要包括一般性Stackelberg博弈 (GSGs) 與Stackelberg安全博弈 (SSGs)，其中后者是前者的一類(lèi)特殊情況。在SSGs中，領(lǐng)導(dǎo)者和跟隨者通常被叫做防衛(wèi)者和攻擊者。已有文獻(xiàn)研究主要包括一般性的GSGs和SSGs、連續(xù)Stackelberg博弈 (玩家具有連續(xù)的決策空間)、不完全信息Stackelberg博弈等。
 
　　微分博弈是用于描述連續(xù)時(shí)間演化的博弈模型，即描述此類(lèi)博弈的模型為連續(xù)時(shí)間微分方程?，F(xiàn)有文獻(xiàn)中大多研究的是二人的零和微分博弈，此類(lèi)模型在追逃等多種問(wèn)題中具有廣泛應(yīng)用?，F(xiàn)有研究大體分為：線性二次微分博弈、非線性微分博弈、Stackelberg微分博弈、隨機(jī)微分博弈等，另外，基于不同的終端時(shí)間與狀態(tài)約束，研究也包括有限和無(wú)限終端時(shí)間、狀態(tài)無(wú)約束和狀態(tài)有約束情形。
 
　　(2) 主流算法
 
　　對(duì)于零和正規(guī)式博弈，至今已有大量算法，例如，后悔匹配 (RM)、RM+、fictitious play、 (online) double oracle等。其中，最流行的算法是基于后悔學(xué)習(xí)的，通常稱為no-regret (或次線性) 學(xué)習(xí)算法，依賴于外部遺憾、內(nèi)在遺憾、交換遺憾及基于納什均衡的遺憾等概念?；诖?，兩個(gè)主流算法是optimistic FTRL和optimistic mirror descent。
 
　　針對(duì)零和不完美信息擴(kuò)展式博弈，流行方法均基于反事實(shí)遺憾最小化 (CFR)。至今，許多更優(yōu)性能的CFR變體被相繼提出，包括CFR+、DCFR、LCFR、ECFR、AutoCFR等。同時(shí)涌現(xiàn)大量AI算法，例如，PSRO、deep CFR、single deep CFR、UDEF、PoG、NAC等。
 
　　針對(duì)Stackelberg博弈，普遍的解決辦法是把問(wèn)題轉(zhuǎn)化成雙層線性規(guī)劃或者混合整數(shù)線性規(guī)劃問(wèn)題，然后流行的解決算法包括multiple LP方法、benders decomposition、cut and branch等。對(duì)于連續(xù)Stackelberg博弈，常用算法是梯度上升下降法，許多算法都可以看作這個(gè)算法的變體。
 
　　對(duì)于零和微分博弈，最流行的方法是粘性解方法，其關(guān)鍵是Hamilton-Jacobi-Isaacs方程，值函數(shù)是此方程的解。
 
　　(3) 未來(lái)展望
 
　　最后，針對(duì)對(duì)抗博弈中的諸多挑戰(zhàn)，提出了潛在的熱點(diǎn)研究方向，包括高效算法設(shè)計(jì)、最后迭代收斂、不完美信息、大型模型、不完全信息、有限理性、動(dòng)態(tài)環(huán)境、混合博弈、博弈中的人工智能方法等。
 
　　文章信息