德撲AI之父請來了最棒的博弈論學者們，他們能與 AI 擦出怎樣的火花？｜ AAAI 2018

美國當地時間 2 月 3 日，AAAI 2018 在第一天的預熱之后逐漸熱鬧了起來。雷鋒網 AI 科技評論在前瞻報道中提到過，本次大會將會有 15 個 Workshop 陸續進行，其中《非對稱信息博弈的 AI（ AI for Imperfect-Information Games）》就是其中一個。這一 workshop 的組織者包括 CMU 的 Noam Brown, DeepMind 的 Marc Lanctot 還有南加州大學博士生、曾獲谷歌 PhD 獎研金的徐海峰。

就像 AlphaGo 讓大家更加熟知深度學習，大家對非對稱信息博弈開始了解并熟悉，很大程度也是因為 2017 年初，CMU 計算機系在讀博士生 Noam Brown 和計算機系教授 Tuomas Sandholm 聯合研發的 Libratus 在單挑無限注德州撲克（ heads-up no-limit hold’em）人機對戰中完勝人類選手。在去年的 NIPS 2017 上，最佳論文正是由他倆的合作論文《Safe and Nested Subgame Solving for Imperfect-Information Games》所摘得。雷鋒字幕組也曾對這一論文解讀視頻進行獨家編譯。

正像 Noam Brown 和 Tuomas Sandholm 在 Reddit 上所表達的那樣：深度學習遠非人工智能的全部，非對稱信息博弈也與 AI 聯系得越發緊密。「非對稱信息博弈」常被用來模擬涉及隱藏信息的各種戰略交互（例如談判，拍賣等）和安全交互中。由于隱藏信息的存在，解決這些事件需要的方法與傳統的對稱信息（比如國際象棋或棋類游戲）完全不同。盡管在一些研究「非對稱信息模擬」的領域取得了相當大的進展，但是每個領域所使用的技術盡管具有普遍性，卻仍然相對孤立。它們之間存在充分的跨學科交流的機會，讓研究人員們會通過已經在一個領域中流行的方法的新應用、或使用建立在不同領域中已有方法來創建新的技術。

本場 Workshop 的主要話題幾乎包含了「非對稱信息博弈的 AI」相關的大部分內容，包括新近用于 AAAI 年度計算機撲克比賽（ACPC），用于解決大型不完美信息游戲的可伸縮算法，游戲中的對手建模和開發，一般和多于兩個的算法建模和分析信息非對稱在游戲中的作用，戰略信號（又名說服），在不完整信息的戰略環境中進行探索與開發，以及一些與非對稱信息博弈有關的其他主題的研究。

?研究者們將分享他們在研究 AI 在非對稱信息博弈中的理論和實踐方面當前的研究成果，也提出有關如何改善相關領域算法的構想，推動該領域的 AI 研究。

這場 Workshop 持續了一整天，原計劃是早上 9:30 開場，下午 5:00 結束，有 8 個演講者對他們的研究成果進行分享，每人限時半小時，以下是原定議程：

但由于第一位演講者未到現場，所以第一個主題《Dynamic Adaptation and Opponent Exploitation in Computer Poker》取消，活動推遲到 10 點，并將第二個主題作為開場，并且其中一些主題也做了相應的調整。

1

開場的論文是由 CMU 的 Christian Kroer 帶來的，題目為《廣泛形式博弈中 Stackelberg 均衡的魯棒性及有限前瞻的擴展（Robust Stackelberg Equilibria in Extensive-Form Games and Extension to Limited Lookahead）》 ，而作者也包括了 Gabriele Farina 和 Tuomas Sandholm。后者與本次議程的主持人 Noam Brown 所研發的 Libratus 在 2017 年初打敗了人類選手，他也被譽為德州AI之父。

作為計算博弈論中的一個解決方案概念，Stackelberg 均衡已經變得越來越重要，這在很大程度上受到諸如安全設置等實際問題的啟發。然而在實踐中，關于對手的模型通常具有不確定型。據作者介紹，這篇論文是首個在廣泛形式博弈中進行不確定條件下的 Stackelberg 均衡的研究。

Christian Kroer 的團隊引入了魯棒性較高的 Stackelberg 均衡，其中不確定性是關于對手的收益，以及對手有有限前瞻性和關于對手的節點評價函數的不確定。他們為確定性限制前瞻設置開發了一個新的混合整數程序。然后，系統把這個程序擴展到無限制下的 Stackelberg 均衡的魯棒設置，并且仍然位于對手有限的前瞻范圍內。

該論文證明了對于對手的收益區間不確定性的具體情況（或者在有限的前瞻的情況下關于對手的節點評估），可以用一個混合整數程序來計算 Stackelberg 平衡的魯棒性，該程序的漸近大小與確定性設置相同。

2

第二篇論文是由哈佛大學的劉洋帶來的《建立高質量信息的強化學習框架（A Reinforcement Learning Framework for Eliciting High Quality Information）》。

對等預測是一類機制，當沒有驗證貢獻的基礎事實時，它有助于從 strategic human agents 中獲得高質量的信息。盡管它的設計看似完善，但是在實踐中經常失敗，主要是由于兩個缺點：(1) agents 對提供高質量信息的努力的動機被認為是已知的； (2) agents 被建模為完全理性的。

在這篇論文中，作者們提出了第一個強化學習（RL）框架，在這個領域，加強對等預測，來解決這兩個限制。在論文中提到的框架中，研究人員為數據請求者開發了一個RL算法，用于數據請求者動態調整縮放級別以最大化其收入，并使用對等預測評分函數調配工作人員。實驗顯示，在不同的模式下，數據請求者的收入顯著提高。

3

第三篇論文是由密歇根大學的 Mason Wright 帶來的《在連續雙標拍賣中評估非自適應交易的穩定性:一種強化學習方法（ Evaluating the Stability of Non-Adaptive Trading in Continuous Double Auctions: A Reinforcement Learning Approach）》。

該論文是在本次 AAAI 2018 大會上首次公開， 此前 Mason 和他的團隊曾在 2017 年發表過關于非對稱性信息博弈在連續雙標拍賣中的研究成果，在本次的論文中，主要針對新的強化學習方法進行闡述，由于本篇論文還未正式放出，雷鋒網 AI 科技評論將在后續的報道中對該篇論文的演講 PPT 進行詳細報道。

4

第四篇是由 Facebook AI Research 的研究工程師 Adam Lerer 主講的《在社會困境中結果主義的條件合作的非對稱博弈（Consequentialist Conditional Cooperation in Social Dilemmas with Imperfect Information）》

在社會困境中，合作可以帶來高回報，但參與者面臨欺騙的動機，且這一情況在多主體的互動中無處不在。我們希望與純粹的合作伙伴進行合作，并避免背叛者的剝削；此外，我們還需要鼓勵其他的合作。然而，通常合作伙伴采取的行動(部分)未能被觀察到，或者個人行為的后果很難預測。這篇論文中證明，在一個大型的活動中，好的策略可以通過調整一個人的行為來建立一個獎勵機制，這被稱之為結果主義的條件合作。在論文中，Adam Lerer 展示了如何使用深度強化學習技術來構建這樣的策略，并通過分析和實驗證明，它們在簡單的矩陣游戲之外的社會困境中是有效的，此外，論文還說明了單純依賴后果的局限性，并討論了對行動的后果意圖的理解的必要性。

5

第五個演講內容是圣路易斯華盛頓大學 Samuel Ang等人的課題《應用于安全領域的博弈論目標識別模型Game-theoretic Goal-Recognition Models with Applications to Security Domains》。

在人工智能規劃領域的目標識別 (GR) 和目標識別設計 (GRD) 問題的驅動下，論文分別介紹和研究了戰略代理的 GR 和 GRD 問題的兩種自然變體。更具體地說，就是考慮了游戲理論 (GT) 的場景，其中一個惡意對手的目標是在一個 (物理或虛擬) 環境中對一個防御者監視的目標進行破壞。敵人必須采取一系列行動以攻擊預定目標。在 GTGR 和 GTGRD 設置中，防御者試圖識別對手的預定目標，同時觀察對手的可用動作，這樣他/她就可以加強目標防御攻擊。此外，在 GTGRD 設置中，防御者可以改變環境 (例如，增加路障)，以便更好地區分對手的目標/目標。

在論文中，研究人員建議將 GTGR 和 GTGRD 設置為零和隨機游戲，其信息不對稱與對手的預定目標有關。游戲是在圖形上播放的，頂點代表狀態，邊緣是對手的動作。對于 GTGR 設置，如果防御者只局限于只玩固定的策略，那么計算最優策略的問題 (對于防御者和對手) 都可以被制定并以一個線性程序來表示。對于 GTGRD 設置，在游戲開始時，防御者可以選擇 K 條邊來阻止，研究人員將計算最優策略的問題作為混合整數規劃，并提出一種基于 LP 二元性和貪婪算法的啟發式算法。實驗表明，這一研究的啟發式算法具有良好的性能。與混合整數規劃方法相比，它具有更好的可擴展性。

目前研究中，現有的工作，尤其是 GRD 問題，幾乎完全集中在決策理論范式上，即對手在沒有考慮到他們可能被觀察的情況下選擇自己的行為。由于這種假設在 GT 場景中是不現實的，所以該篇論文提出的模型和算法填補了文獻中的一個空白。

6

第六篇論文是來自南加州大學的 Sara McCarthy 帶來的《在游戲中保持領先：用于威脅篩選的資源動態分配的自適應魯棒性優化（Staying Ahead of the Game: Adaptive Robust Optimization for Dynamic Allocation of Threat Screening Resources）》

Sara McCarthy 的研究考慮在安檢地點(例如，在機場或港口)動態分配不同效率的篩選資源(例如X光機等)，以成功地避免一名被篩查者的攻擊。在此之前，研究人員引入了威脅篩選博弈模型來解決這個問題，雖然理論上能假設屏幕到達時間是完全已知的，但實際上，到達時間是不確定的，這嚴重阻礙了該方法的實現和性能。

因此，研究者們提出了一種新的威脅篩選資源動態分配框架，明確說明了篩選到達時間的不確定性。研究者將問題建模為一個多階段魯棒優化問題，并提出了一個使用緊湊線性決策規則和魯棒重構和約束隨機化相結合的解決方案。在進行了大量的數值實驗后，這些實驗表明，這種方法在處理性方面勝過(a)精確的解決方法，同時在最優性方面只產生很小的損失，(b)方法忽略了可行性和最優性方面的不確定性。

7

最后一篇論文來自卡內基梅隆大學的于瀾濤，主題為《基于網絡信息綠色安全游戲的深度強化學習（Deep Reinforcement Learning for Green Security Game with Online Information）》。

出于保護瀕危野生動物免受偷獵和防止非法采伐等綠色安全領域的迫切需要，研究人員提出了博弈論模型，以優化執法機構的巡邏。盡管有了這些努力，在線信息和在線互動(例如，巡邏者追蹤偷獵者的足跡)在之前的游戲模型和解決方案中被忽略了。這篇論文的研究旨在通過將安全游戲與深度強化學習相結合，為復雜的現實世界綠色安全問題提供更切實可行的解決方案。具體來說，研究者提出了一種新穎的游戲模型，它融合了在線信息的重要元素，并對可能的解決方案進行了討論，并提出了基于深度強化學習的未來研究方向。

小結

以上就是 AAAI 第二天「人工智能非對稱信息博弈」專場 workshop 的全部內容摘要，接下來，雷鋒網 AI 科技評論會對全部 7 篇論文的 PPT 和演講內容進行精編整理，逐步放出。

接下來 AAAI 的議程會更加精彩，明天雷鋒網將繼續在現場為大家報道精彩盛況。

雷峰網原創文章，未經授權禁止轉載。詳情見轉載須知。