德扑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 的议程会更加精彩，明天雷锋网将继续在现场为大家报道精彩盛况。

雷峰网原创文章，未经授权禁止转载。详情见转载须知。