AAAI/ACM SIGAI博士论文奖《大型对抗性不完美信息博弈的均衡发现》附230页pdf与slides

2022 年 3 月 1 日 专知

德扑 AI 作者 Noam Brown 获 AAAI/ACM SIGAI 博士论文奖

AAAI/ACM SIGAI 博士论文奖由 AAAI 和 ACM SIGAI 共同设立，旨在发现和鼓励人工智能领域的优秀博士研究和论文。这是一个年度奖项，将出现在一年一度的 AAAI 会议上，获奖者将在会议上做演讲。第一届奖项由吴佳俊获得。

第二届的 2020 年 AAAI/ACM SIGAI 博士学位论文奖由 Meta AI（原 FAIR）科学家 Noam Brown 摘得，获奖理由是「在大型对抗性不完全信息博弈均衡求解方面的工作」。

2020 年 9 月，Noam Brown 宣布完成 CMU 博士论文答辩，并公开了长达 230 页的超硬核博士论文《大型对抗性不完美信息博弈的均衡发现》。

在博士学位论文中，Noam Brown 详述了大型对抗性不完美信息博弈中均衡计算的一系列进展。这些新技术使得 AI 智能体首次有可能在无限注扑克游戏中击败顶级职业玩家，而这正是几十年来 AI 和博弈论领域一直存在的重大挑战性难题。

Noam Brown 致力于结合计算博弈论和机器学习来开发能够在不完美信息多智能体环境中进行策略推理的 AI 系统，其研究成果应用到了首个分别在在双人无限扑克和多人无限扑克中战胜人类顶级玩家的 Libratus 和 Pluribus。这两个游戏 AI 系统为 Noam Brown 带来了巨大的关注度。

2017 年，Noam Brown 与其导师 Tuomas Sandholm 开发的 AI 系统 Libratus 在宾夕法尼亚州匹兹堡 Rivers 赌场持续 20 天 1 对 1 无限制德扑比赛中成功战胜了 4 名全球顶级职业玩家。该研究登上了《Science》杂志，与研究相关的另一篇论文《Safe and Nested Subgame Solving for Imperfect-Information Games》也获得了 NIPS 2017 最佳论文奖。Noam 团队还因此获得了 IJCAI 颁发的第二枚马文 · 明斯基奖章（Marvin Minsky Medal）。

此外，Noam 还曾获得 2017 年度 Allen Newell「卓越研究奖」，也曾被 MIT 科技评论评选为 2019 年度「35 岁以下科技精英」（MIT TR35）。2019 年，Noam Brown 与其导师 Tuomas Sandholm 合著的论文《Solving Imperfect-Information Games via Discounted Regret Minimization》获得了 AAAI 杰出论文荣誉提名奖。2021 年，他的博士论文还获得 2020 IFAAMAS Victor Lesser Distinguished Dissertation Award。

在 CMU 获得博士学位之后，Noam Brown 现在是 Facebook 人工智能研究中心的研究科学家，致力于多智能体人工智能的研究。

不完全信息博弈模型是指具有私有信息的多个主体之间的交互作用。在这种情况下，一个典型的目标是接近一个均衡，在这个均衡中，所有主体的策略都是最优的。本文描述了大型对抗不完全信息博弈均衡计算方面的若干进展。这些新技术使人工智能智能体首次有可能在全规模扑克游戏中击败顶级人类专业人员。几十年来，扑克一直是人工智能和博弈论领域的一大挑战。

我们首先介绍了反事实后悔最小化(CFR)的改进，这是一种收敛于双方零和博弈纳什均衡的迭代算法。我们描述了CFR的新变种，使用折现来显著加快收敛速度。这些新的CFR变体现在是大型对抗非完全信息博弈的最先进的均衡发现算法。我们还介绍了第一种热启动CFR的通用技术。最后，我们介绍理论健全的剪枝技术，可以在大型博弈中数量级地加速收敛。

接下来，我们将描述通过自动抽象和函数近似将CFR扩展到大型游戏的新方法。特别地，我们介绍了第一个在不完全信息博弈中离散连续动作空间的算法。我们将其扩展到求解具有连续动作空间博弈的算法中。

之后，我们介绍了Deep CFR，一种使用神经网络函数近似而不是基于bucketing的抽象形式。Deep CFR是第一个可扩展到大型游戏的non-tabular形式的CFR，它使CFR能够在几乎没有领域知识的情况下成功部署。最后，我们提出了一种新的不完全信息博弈搜索技术，以确保智能体的搜索策略不会被对手利用。方法，它在计算上比以前的方法要代价要少得多。最最后，我们提出了一种在训练和测试时结合强化学习和搜索的算法ReBeL。它朝着弥合完全信息游戏和不完全信息游戏研究之间的差距迈出了重要的一步。

论文目录：