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