作者 | Mr Bear
編輯 | 青暮
AAAI 2021設立了學術新星獎（New Faculty Highlight）， 其中來自 Facebook 人工智慧研究院的 Noam Brown上榜，並 帶來了題為「用於不完美信息多智能體場景下的人工智慧」的演講。
其他上榜者包括楊笛一、馬航、杜少雷、Noam Brown、孫舉、李俊東、牟力立、許晶晶等人。
圖 1：用於不完美信息多智能體場景下的人工智慧
圖 2：不完美信息多智能體
Noam Brown，卡耐基梅隆大學（CMU）博士，Facebook 人工智慧實驗室研究科學家、AI德州撲克作者，致力於使AI在大型不完全信息多智能體交互中進行戰略推理。
Noam Brown已經將自己的研究成果應用到了第一款在無限注德州撲克中擊敗頂級人類的 AI 上。
他和他的CMU導師一起創建了AI系統Libratus和Pluribus，並在人機對抗比賽中果斷擊敗了頂尖的人類撲克職業玩家，AI撲克Pluribus也因此曾登頂了Science封面。
他還曾獲得NIPS 2017最佳論文獎、AAAI 2019傑出論文獎、馬文·明斯基獎，入選MIT TR35。
以下是報告全文，AI科技評論進行了不改變原意的整理。
1
引言
首先，本文提及的「多智能體環境」也被稱為「博弈」，它指的是涉及多個參與者可以完成的行為，以及根據選定的行為得到的收益的任意形式的策略交互。
早在人工智慧領域興起之初，多智能體環境就成為了一種極具挑戰的問題，並且成為了人工智慧研究的一類對比基準。舉例而言，西洋棋在很長一段時間以來都是一種很困難的人工智慧問題，該領域的大多數研究工作都重點關注「完美信息博弈」，此時博弈參與者知道所處世界的確切狀態。
另一方面，我的研究傾向於關注不完美信息博弈。在這種博弈中，玩家可以獲得其他玩家無法獲得的私人信息。如果我們想要在現實世界中部署人工智慧系統，我們必須能夠解決這類隱藏信息的問題，因為大多數現實世界的策略交互都涉及到一些隱藏信息。例如，金融市場、安全交互、業務談判，甚至車輛導航場景下都涉及隱藏信息。
圖 3：無限制德州撲克
長期以來，撲克都是博弈論領域中的一項極具挑戰性的問題。具體而言，「無限制德州撲克」是其中的一種變體。實際上，早在上世紀 40、50 年代，博弈論領域就有人撰寫論文來研究撲克。而撲克也是一種大規模博弈，在「無限制德州撲克」中，博弈雙方擁有 10^161 個決策點。到目前為止，「無限制德州撲克」是世界上最流行的一種撲克遊戲。在各種有關撲克的電影（如圖 3 所示的電影《007 大戰皇家賭場》）中都有「無限制德州撲克」的身影。每年的撲克世界巡迴錦標賽也都會舉辦有關「無限制德州撲克」的比賽。
圖 4：2017 年的人機撲克大戰——Libratus
在很長一段時間內，人工智慧系統都無法擊敗世界上頂尖的撲克選手。直到 2017 年，我和我的導師研製出了 Libratus，它與世界上 4 位最頂尖的「無限制德州撲克」對戰，並成功擊敗了他們。在 2017 年 1 月的 20 天內，Libratus 打了 120,000 手撲克。最終超過 20 萬美元的獎金池根據選手的表現分給了撲克高手們。Libratus 以極大的統計顯著性（大約正態分布周圍 4 個標準差）獲得了勝利，每一位選手都敗給了 Libratus。
Libratus 系統有一些有趣的地方。首先，它完全通過自己和自己博弈來訓練，並沒有使用任何的人類數據。另一個值得注意的地方是，該系統在 20 天內打了超過 12 萬手德州撲克，而在這個過程中人類專家隊伍試圖尋找他們可以利用的系統的漏洞和弱點。但直到最後，他們也未能如願以償。這也證明了我們在 Libratus 匯總使用的博弈論方法是有效的。如果我們想要在現實世界中具有數以億計的用戶的場景下部署人工智慧系統，這種對於對抗性的調整和利用的魯棒性是十分重要的。如果這些系統中存在一些漏洞，那麼用戶們終究是會發現它們的。
圖 4：2019 年的 Pluribus 實驗
繼 Libratus 之後，我們在 2019 年推出了 Pluribus 人工智慧系統，它與 15 名世界頂尖的撲克專家進行 6 人無限制德州撲克遊戲。Pluribus 在 12 天中打了一萬手德州撲克，它使用了方差縮減技術來降低運氣成分。同樣，Pluribus 也以極大的統計顯著性獲勝。值得一提的是，儘管我們將 Libratus 的雙人博弈擴展到了 Pluribus 中的六人博弈，指數級地擴大了博弈的規模，但是 Pluribus 的訓練開銷卻比 Librabus 小得多，我們只需要花費不到 150 美元，在 28 個 CPU 核上就可以訓練 Pluribus（無需 GPU）。
圖 5：納什均衡與可利用性——石頭、剪刀、布
2
Librabus和Pluribus的博弈論方法
接下來，我們將簡要介紹 Librabus 和 Pluribus 中用到的博弈論方法。
首先，納什均衡指的是在某組策略下形成的一種局面：沒有人能夠通過改變自己的策略改善自己的收益。在二元零和博弈中，形成納什均衡可以保證無論我們的對手如何行動，從期望上說，我們都不會輸掉。此外，可利用性（exploitability）指的是：我們的結局比最佳對策差多少（即如果對手完美地反擊了我們，從期望上說，我們將會輸多少）。
假設我們在玩「石頭、剪刀、布」遊戲，我們的策略是始終出「石頭」。而此時，對手的最佳對策是始終出「布」。這種情況下，我們的可利用性為 1。而如果我們的策略稍微機智一些：我們在前兩輪出「石頭」，如果對手在這兩輪都出「布」，那麼我們將在第三輪出「剪刀」。這種情況下，對手的最佳對策是在第三輪出「石頭」，此時我們的可利用性仍然為 1。你可能會認為這並不公平，因為我們假設對手知道我們的策略，並且能夠相應地反擊我們。
圖 6：關鍵假設
如果我們真的想要部署一個數以億級的用戶都會使用的人工智慧系統，我們需要保證他們無法「利用」我們。為此，我們假設對手知道我們的策略，而並不知道隨機過程的結果。因此，我們希望即使他們知道我們的策略，我們的策略仍然應該魯棒（這是博弈論中的一個普遍的假設）。我認為這個研究動機是成立的，因為如果用戶有充足的時間與我們的系統進行交互，他們最終會想到我們的策略是什麼，並想出相應的對策。這樣一來，我們首先應該試圖最小化系統的可利用性。
圖 7：通過隨機化方法改進「石頭、剪刀、布」中的策略。
在「石頭、剪刀、布」遊戲中，我們可以通過隨機化方法實現上述目標。如果我們在出石頭、布和剪刀之間隨機分配相同的機率。那麼不管對手怎麼做，他們都無法做出最佳的對策。也就是說，他們無法「利用」我們，此時便達到了納什均衡。
在這種情況下，你可能會認為，從期望上說我們並不會輸，不會被「利用」。但是，在形成納什均衡的局面後，我們也不會贏。在「石頭、剪刀、布」遊戲中，這種想法是成立的。
但是當問題擴展到越來越大的博弈場景下，想到如何做出最好地應對以達到納什均衡會越來越困難。在對手試圖做出最佳對策時，他們很有可能會出錯。如果我們達到了納什均衡，從期望上說，我們不會輸掉。但是實際上，我們需要最終勝出。
有人說：打撲克其實很簡單，只要對手犯錯，我們就可以從中獲利。這也正是我們在撲克遊戲中採用的方法，許多專業撲克選手也向我們推薦了這種方法。
接下來，我們將討論非二元零和博弈中的均衡。此時，我們無法在多項式時間內計算出納什均衡。即使我們可以高效地計算出納什均衡，這麼做也沒有意義。這是因為在非二元零和博弈中，一些納什均衡的優秀性質（例如，從期望上說，我們不會輸掉）就不復存在了。然而，本次演講中提到的算法在這種情況下效果仍然很好。這些算法在實際情況下通用性如何仍然是個有待研究的問題。
圖 8：非二元零和博弈中的均衡
3
反事實遺憾最小化
接下來，我們將介紹在大型博弈中計算上述均衡的一種方法：反事實遺憾最小化。在本次演講中，我們將介紹該算法的蒙特卡洛版本。
CRF 是一種疊代式的算法，它會逐漸收斂到納什均衡。同時，CRF 是一種自我博弈（self-play）算法，智能體會與自己進行對局。在起始狀態下，該智能體會完全隨機地進行博弈。隨著時間的推移，智能體會學習到效果好的動作和效果不佳的動作。它會更多地採用在過去的所有疊代過程中效果良好的動作。最終，CRF 算法會收斂到一種納什均衡狀態。
如圖 9 所示，我們將遍歷玩家 1（P1）的博弈樹，在下一輪疊代中我們將轉而考慮玩家 2，接著再考慮玩家 1......如此循環往復。玩家會一直在每個決策點上為博弈中的每個動作維護一個被稱為遺憾值（regret value）的指標。在每次需要做出動作時，玩家會選擇動作的機率與正向遺憾值成正比。遺憾（regret）值對應於玩家有多麼後悔在之前的情況下沒有採取某個動作。在第一輪中，所有的遺憾值都為 0。
圖 9：第一輪 MCCFR 博弈樹
第一輪疊代過程如下：
Step 1：在博弈開始時，我們考慮的是玩家 1。請注意，玩家 1 選擇動作的機率正比於正向遺憾值。此時所有的遺憾值為 0，這意味著他們會均勻、隨機地選取動作。假設他們隨機地選取了左側的分支，我們會來到玩家 2 的決策點。
Step 2：同樣地，玩家 2 選擇各種動作的機率也與其正向遺憾值成正比。假設玩家 2 隨機選擇了左側分支。接著，我們又回來到另一個玩家 1 的決策點。
Step 3：假設此時玩家 1 又隨機選擇了左側的分支，我們最終得到了 50 美元的獎勵。
圖 10：計算右側動作的遺憾值
現在，玩家 1 將會審視他們本來可以採取（但沒有採取）的所有其它動作。例如，他們在 Step 3 中本可以採取右側分支的行動，並且得到 100 美金的獎勵。此時，該動作的遺憾值就上升了。通過他們在反事實情況下選取右側動作本可以得到的獎勵減去他們實際選取左側動作得到的獎勵，我們計算出此處的遺憾值上升了 50。在未來的情況下，由於右側動作的遺憾值更高，所以玩家選取該動作的機率就會更高，。
實際上，這與人類學習玩遊戲的方式非常相似。舉例而言，在打撲克時，我們往往會問「假如我當時採取了其它的動作，對手會作何反應呢」？這種假設推理與 CRF 算法中的智能體的思考方式是類似的。由於智能體此時與自己對弈，因此能夠計算出某種假設的獎勵是多少。在如圖 10 所示的過程中，他們可以看到在怎樣的情況下會獲得 100 美元的獎勵。
在更新了遺憾值後，算法會向上傳遞他們實際獲得的 50 美元的獎勵。由於我們只更新本輪疊代中玩家 1 的遺憾值，所以我們會跳過所有玩家 2 的決策點。同樣地，玩家 1 會探索所有他本來可以才去的行動。玩家 1 本來可以在根節點選擇右側的動作。然後他們會達到另一個玩家 1 節點，假設此時它們選擇左側分支並且獲得了 -500 美元的獎勵。此時，他們繼續探索他們本可以採取的行動（選擇右側的分支）。如果他們選擇了右側的分支，他們將得到 100 美元的獎勵。此時右側動作的遺憾值上升為 600 ，而根節點對右側動作的遺憾值變為了 -550。
在本輪疊代完成後，我們會以同樣的方式更新玩家 2 的遺憾值，接著再重新更新玩家 1，玩家 1 會以更高的機率選取遺憾值更高的動作......如此循環往復。
圖 11：反事實遺憾最小化
至此，我們介紹了 CFR 算法的蒙特卡洛版本。而 CFR 算法的非蒙特卡洛版本工作原理與前者相類似，只不過我們需要對所有的動作取期望值，而不是對它們進行採樣。在所有疊代後得到的平均值將會收斂到納什均衡。
4
CFR的變體
圖 12：線性 CFR 和折扣化 CFR
如今，CFR 算法已經成為了計算大規模不完美信息博弈中的均衡的常用方法。但是，CFR 真正的強大之處在於近年來出現了許多對其進行改進的變體。原始的 CFR 方法在計算納什均衡時效率很低。我們接下來將介紹的兩種 CFR 變體則十分高效，它們是目前許多大規模不完美信息博弈場景下性能最佳的方法。
線性 CFR 和折扣化 CFR 背後的思想是降低較早的疊代的影響，這樣可以維持 CFR理論上的收斂界（儘管實際上收斂的要快一些）。以圖 12 左側為例，我們給出了「石頭、剪刀、布」遊戲中的收斂情況。可以看出，CFR 策略給出石頭、剪刀、布的機率會逐漸收斂到 1/3。在圖 12 的右側，我們可以通過線性 CFR 算法實現相同的效果，但是其收斂速度則要快得多。
圖 13：CFR 的剪枝策略
另一方面，我們關注 CFR 的剪枝策略。剪枝背後的思想是，我們沒有必要在每一輪疊代中探索那些遺憾值為負且其絕對值很大的動作。我們至少可以暫時將它們剪枝掉。從理論上說，我們是可以實現這種剪枝策略的，並且不會損害模型的性能。在多種博弈場景下，我們的剪枝策略最終很可能加速模型收斂。實驗結果表明，我們在中型規模的博弈中取得了 10 倍的加速。
如圖 13 所示，在中型撲克遊戲 Leduc-5 中，y 軸代表可利用性（我們距離納什均衡有多遠），我們希望可利用性的值下降。另一方面，x 軸代表我們已經考慮過的決策點。紅色的虛線代表原始版本的 CFR，綠色虛線代表 CFR 的一個改進版（CFR +），黑色的實線代表使用了基於遺憾值的剪枝策略的 CFR。可以看到，我們改進後的算法將收斂速度提升了一個數量級。
基於深度學習的CFR/DREAM算法
圖 14：基於深度學習的 CFR/DREAM
基於深度學習的 CFR（Deep CFR）/DREAM 算法是另一個令人激動的領域。它們是 CFR 的非扁平版本。為了將原始的 CFR 算法擴展到超大規模的博弈（如「無限制德州撲克」）中，我們需要使用一種名為「抽象」的技術。「抽象」背後的思想是，在博弈中將多個相似決策點合併起來同等地處理，而不是在每個決策點上考慮每個動作的遺憾值。例如，撲克中的兩種同花順「queen high flush」和「king high flush」將會擁有各自而定遺憾值，而在使用「抽象」技術後，我們會將二者放在一起同等地處理。因此，在使用了「抽象」技術之後，我們可以將合併起來的決策點一同更新，而不需要分別更新這些不同情況下的決策點。「抽象」技術對於撲克遊戲十分有效。而想要將該技術拓展到其它領域也很困難。實際上，已經有許多研究者撰文討論如何在撲克領域進行「抽象」。
基於深度學習的 CFR/DREAM 算法真正的強大之處在於，它使我們可以在需要的知識少得多的情況下，達到相似的性能。實際上，基於深度學習的 CFR 是首個將 CFR 應用到大型博弈中的非扁平 CFR 形式。而 DREAM 是一項後繼的工作，它實現了與「Deep CFR」相近的性能，並且它是模型無關的，即我們無需知道交互的規則。這意味著，Deep CFR 和 DREAM 算法提供了將 CFR 拓展到極為複雜的多智能體環境（甚至是三維環境）下的途徑。目前，將這一算法拓展到連續動作空間中的三維環境下仍然是極具挑戰的問題。但是我堅信我們目前的研究思路是正確的，未來對該算法的改進會使其更加強大。
5
實時搜索更好的策略
圖 15：實時搜索更好的策略
「搜索」指的是，我們並不是立刻就採取動作，而是在底層花費大約 30 秒左右的時間基於某種算法決定出最佳的動作。
圖 16：實時搜索是非常重要的
首先，搜索不僅僅對於非完美信息博弈十分重要，對於完美信息博弈也是如此。在圖 16 中，y 軸代表了 Elo 等級分，它衡量了人類棋手和機器的表現。在圍棋中，表現為「superhuman」的閾值被設定為 3,600 Elo。如圖 16 所示，淺藍色的豎線代表 AlphaGo Zero 的性能，顯然其性能達到了「superhuman」水平。但是，如果我們去除掉測試時（甚至不用取出訓練時）使用的實時搜索技術（本例中為蒙特卡洛樹搜索），該系統的性能將會下降至灰色豎線所示的情況（大約 3000 Elo 等級分），而這並沒有達到「superhuman」水平。這說明搜索對於圍棋遊戲是十分重要的。實際上，搜索的重要性不僅僅局限於圍棋，它幾乎對所有的遊戲（例如，西洋棋、撲克）都很重要。
圖 17：完美信息博弈中的搜索
不完美信息博弈中的搜索比完美信息博弈中的搜索要困難得多。為了解釋這一點，我們首先將介紹搜索在完美信息博弈中的工作原理，其中「值函數」是核心的概念。在完美信息博弈中，某個狀態的值是反向歸納得到的唯一值。而值網絡則以某個狀態作為輸入，並且輸出對於狀態值的估計。如圖 17 所示，在西洋棋棋盤中，如果白方用其皇后吃掉黑方的象，然後就會「將軍」，此時白方該狀態的值為「1」。因此，如果我們將此時棋盤的狀態賦到值函數中作為輸入，值函數會返回白方的值為「1」。
圖 18：為什麼非完全信息博弈中的搜索更加困難？
非完全信息博弈中的搜索更加困難，這是因為在非完美信息博弈中，並沒有像在完美信息博弈中那樣為傳統的「狀態」很好地定義「值」，這會導致現有的搜索技術失效。
石頭、剪刀、布+
圖 19：升級版的「石頭、剪刀、布」
我們將以一個升級版的「石頭、剪刀、布」（石頭、剪刀、布+）為例說明非完全信息博弈中的搜索有多困難。除了「如果有選手出剪刀，那麼獲勝者會得到兩分，敗者則減兩分」這一修改之外，該遊戲的規則與「石頭、剪刀、布」相同。而這一修改打破了原本遊戲的對稱性。
如圖 19 所示，我們將給出該遊戲中可能出現的序列化的情況。其中玩家 1 首先出招，接著玩家 2 在不看玩家 1 的出招情況的條件下也出招。在該遊戲中，最佳的策略（納什均衡）是以 40% 的機率出石頭和布，而以 20% 的機率出剪刀。如果博弈雙方都採取這種策略，那麼值的期望就是 0。假設你是玩家 1，並且進行深度受限搜索，你會在某一步停下來，替換納什均衡雙方的值，然後再往下進行遊戲。
在深度受限搜索情況下，玩家 1 會在石頭、剪刀、布之間做出選擇。接著，我們停留在這一步，將納什均衡情況的值（0）輸入給函數。接下來，我們需要對這個博弈進行求解。然而，此時我們並沒有足夠的信息讓玩家 1 達到納什均衡（以 40% 的機率出石頭和布，而以 20% 的機率出剪刀）。最終可能會以 1/3 的機率均勻選取三種動作。
此時，問題在於我們假設無論玩家 1 做了什麼，玩家 2 都達到納什均衡。在完美信息博弈中，這種假設是成立的，但是在非完美信息博弈中並非如此。在非完美信息博弈中，動作的值依賴於該動作被選取的機率。例如，如果玩家 1 以 80% 的機率出石頭，那麼石頭的值就會變化，因為玩家 2 會在玩家 1 出石頭之後停下來，而這會打破納什均衡。相反，他會常常出布。那麼石頭的值就會從 0 降為 -1。這就是非完美信息博弈和完美信息博弈之間的主要差別之一。
圖 20：非完美信息博弈中的搜索
那麼，我們如何處理這種差異呢？Nayyar 等人於 2013 年提出了其中一種解決方案。我們可以根據可能的情況的機率分布定義一種「狀態」。其中，石頭的值並沒有被很好地定義。然而，「玩家 1 以 80% 的機率出石頭、10% 的機率出剪刀、10% 的機率出布」這種情況的值被定義為 -0.6。這與「信念狀態」和「部分可觀測馬爾科夫決策過程」的想法相似，只不過它被擴展到了多智能體環境下。這種思路被稱為「公開信念狀態」，其中我們可以將狀態定義為所有玩家的不同可能性的機率分布。這一思路最早是為完全協作環境開發的。
然而，在非完全協作環境下（例如，對抗性環境、混合協作環境、競爭環境下），我們不再能夠確定其它玩家的策略，這是因為他們可能會欺騙我們。如果我們不知道他們的策略，也就不知道我們所處的狀態。對於玩家 2 來說，他應該設想玩家 1 的策略是怎樣的，從而弄清他們所處的公開信念狀態。那麼，為了決定狀態的機率分布，我們應該怎樣假設對手們的策略呢？直觀地想，我們可能會認為只需直接假設其他玩家處於納什均衡狀態，但是這樣做並不可行。
圖 21：不保險的搜索
如圖 21 所示，假設你是遊戲中的玩家 2，現在輪到你做出動作。此時，你希望進行搜索。現在的問題是，你應該怎樣假設玩家 1 之前的行為？一種看似合理的假設是：假設玩家 1 達到了納什均衡。然而，這樣做並不可行。
為了更簡單地說明該問題，我們假設逼近了納什均衡，但是並沒有完美地達到納什均衡。我們實現了玩家 1 的近似納什均衡，他有 40.1% 的機率出石頭，有 19.9% 的機率出剪刀，40% 的機率出布。現在輪到我們（玩家 2）出招。此時，我們的最優策略為以 100% 的機率出布。但是問題是，如果我們這麼做，我們的對手在知曉了我們的算法後，可以通過從納什均衡狀態轉變為總是出剪刀來對抗我們。這會使我們得到 -2 的值。因此，假設對手處於納什均衡是一種「不保險」的搜索策略，因為對手可以利用我們這種假設。
圖 22：保險的搜索
為了解決上述問題，研究人員撰寫了許多論文探究解決方案。但是我們最近於 NeurIPS 2020 上發表的方法是目前最有效的技術，它對我們所處狀態的信念進行了隨機化處理。其中，我們通過 CFR 算法判斷對手的策略，而不是假設對手處於納什均衡。此外，我們經過隨機輪次的疊代後會終止算法，而不是將算法疊代固定數量的輪次。我們假設玩家的策略來源於這種隨機疊代的過程，由於我們從一個隨機的疊代過程中採樣，對手就無法知道我們怎樣對它們的策略進行假設，他們就無法利用我們的信念。根據納什均衡，我們證明了這種有關信念的假設在理論上是合理的。
6
比純粹的對抗和純粹的合作更複雜的情況
圖 23：比純粹的對抗和合作更複雜的情況
最後，我們將討論比純粹的對抗和純粹的合作更複雜的情況。在現實生活中，往往並不存在這種零和博弈的情況。人工智慧系統在協作、談判、聯盟等場景下仍然表現不佳。在這些博弈問題中，人工智慧與自己進行對弈是遠遠不夠的。假設我們擁有無限的時間和資源，通過自我博弈訓練處的西洋棋智能體最終會學習到西西里防禦。但是即使擁有無限的時間和資源，通過自我博弈訓練的談判智能體也無法學會說英語。如果我們想要在這些場景下取得成功，我們需要智能體能與人類交互，或收集人類的數據。
圖 24：無媒介「外交」遊戲中的基於 CFR 的搜索
多年來，「外交」遊戲已經成為了多智能體研究領域的常用對比基準，它是一種 7 人博弈遊戲，玩家之間同時需要進行合作和競爭，涉及同時行動的博弈。近年來，人工智慧領域有多篇論文涉及「外交」遊戲。在我們 ICLR 2021 上發表的研究「外交」遊戲的論文中，我們使用與前文所述的方法相類似的技術，通過基於 CFR 的搜索和使用人類數據的監督學習首次實現了與人類相當的性能。這說明，我們在本次演講中介紹的相關思想不僅僅局限於二元博弈或對抗博弈，它可以被擴展當更廣闊的場景下。
7
結語
圖 25：要點回顧
綜上所述，Noam Brown 的研究工作主要關注對大規模環境下的均衡的高效計算，將搜索和學習技術泛化到單智能體環境和完美信息博弈中，最終開發適用於真實場景（混合協作、競爭、多智能體環境）下的人工智慧技術。
點擊閱讀原文，進入CVPR2021專區！