美國當(dāng)?shù)貢r(shí)間 2 月 3 日，AAAI 2018 在第一天的預(yù)熱之后逐漸熱鬧了起來。雷鋒網(wǎng) AI 科技評論在前瞻報(bào)道中提到過，本次大會將會有 15 個(gè) Workshop 陸續(xù)進(jìn)行，其中《非對稱信息博弈的 AI（ AI for Imperfect-Information Games）》就是其中一個(gè)。這一 workshop 的組織者包括 CMU 的 Noam Brown, DeepMind 的 Marc Lanctot 還有南加州大學(xué)博士生、曾獲谷歌 PhD 獎(jiǎng)研金的徐海峰。

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

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

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

?研究者們將分享他們在研究 AI 在非對稱信息博弈中的理論和實(shí)踐方面當(dāng)前的研究成果，也提出有關(guān)如何改善相關(guān)領(lǐng)域算法的構(gòu)想，推動該領(lǐng)域的 AI 研究。

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

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

1

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

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

Christian Kroer 的團(tuán)隊(duì)引入了魯棒性較高的 Stackelberg 均衡，其中不確定性是關(guān)于對手的收益，以及對手有有限前瞻性和關(guān)于對手的節(jié)點(diǎn)評價(jià)函數(shù)的不確定。他們?yōu)榇_定性限制前瞻設(shè)置開發(fā)了一個(gè)新的混合整數(shù)程序。然后，系統(tǒng)把這個(gè)程序擴(kuò)展到無限制下的 Stackelberg 均衡的魯棒設(shè)置，并且仍然位于對手有限的前瞻范圍內(nèi)。

該論文證明了對于對手的收益區(qū)間不確定性的具體情況（或者在有限的前瞻的情況下關(guān)于對手的節(jié)點(diǎn)評估），可以用一個(gè)混合整數(shù)程序來計(jì)算 Stackelberg 平衡的魯棒性，該程序的漸近大小與確定性設(shè)置相同。

2

第二篇論文是由哈佛大學(xué)的劉洋帶來的《建立高質(zhì)量信息的強(qiáng)化學(xué)習(xí)框架（A Reinforcement Learning Framework for Eliciting High Quality Information）》。

對等預(yù)測是一類機(jī)制，當(dāng)沒有驗(yàn)證貢獻(xiàn)的基礎(chǔ)事實(shí)時(shí)，它有助于從 strategic human agents 中獲得高質(zhì)量的信息。盡管它的設(shè)計(jì)看似完善，但是在實(shí)踐中經(jīng)常失敗，主要是由于兩個(gè)缺點(diǎn)：(1) agents 對提供高質(zhì)量信息的努力的動機(jī)被認(rèn)為是已知的； (2) agents 被建模為完全理性的。

在這篇論文中，作者們提出了第一個(gè)強(qiáng)化學(xué)習(xí)（RL）框架，在這個(gè)領(lǐng)域，加強(qiáng)對等預(yù)測，來解決這兩個(gè)限制。在論文中提到的框架中，研究人員為數(shù)據(jù)請求者開發(fā)了一個(gè)RL算法，用于數(shù)據(jù)請求者動態(tài)調(diào)整縮放級別以最大化其收入，并使用對等預(yù)測評分函數(shù)調(diào)配工作人員。實(shí)驗(yàn)顯示，在不同的模式下，數(shù)據(jù)請求者的收入顯著提高。

3

第三篇論文是由密歇根大學(xué)的 Mason Wright 帶來的《在連續(xù)雙標(biāo)拍賣中評估非自適應(yīng)交易的穩(wěn)定性:一種強(qiáng)化學(xué)習(xí)方法（ Evaluating the Stability of Non-Adaptive Trading in Continuous Double Auctions: A Reinforcement Learning Approach）》。

該論文是在本次 AAAI 2018 大會上首次公開， 此前 Mason 和他的團(tuán)隊(duì)曾在 2017 年發(fā)表過關(guān)于非對稱性信息博弈在連續(xù)雙標(biāo)拍賣中的研究成果，在本次的論文中，主要針對新的強(qiáng)化學(xué)習(xí)方法進(jìn)行闡述，由于本篇論文還未正式放出，雷鋒網(wǎng) AI 科技評論將在后續(xù)的報(bào)道中對該篇論文的演講 PPT 進(jìn)行詳細(xì)報(bào)道。

4

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

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

5

第五個(gè)演講內(nèi)容是圣路易斯華盛頓大學(xué) Samuel Ang等人的課題《應(yīng)用于安全領(lǐng)域的博弈論目標(biāo)識別模型Game-theoretic Goal-Recognition Models with Applications to Security Domains》。

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

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

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

6

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

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

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

7

最后一篇論文來自卡內(nèi)基梅隆大學(xué)的于瀾濤，主題為《基于網(wǎng)絡(luò)信息綠色安全游戲的深度強(qiáng)化學(xué)習(xí)（Deep Reinforcement Learning for Green Security Game with Online Information）》。

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

小結(jié)

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

接下來 AAAI 的議程會更加精彩，明天雷鋒網(wǎng)將繼續(xù)在現(xiàn)場為大家報(bào)道精彩盛況。

雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。