首届国际理论计算机联合大会（International Joint Conference on Theoretical Computer Science，IJTCS）于2020年8月17日-22日在线上举行，主题为“理论计算机科学领域的最新进展与焦点问题”，由北京大学与中国工业与应用数学学会（CSIAM）、中国计算机学会（CCF）、国际计算机学会中国委员会（ACM China Council）联合主办，北京大学前沿计算研究中心承办。  

 

　　8月18日，大会“多智能体强化学习”分论坛如期举行，北京大学李文新教授和中国科学院自动化研究所张海峰副研究员共同主持。小编为大家带来论坛精彩回顾。

 

Online Search and Pursuit-Evasion in Robotics
张国川，浙江大学

 

　　在机器人领域，会进行比赛让两个队伍对战。每个智能体都面临以下的一些问题：1、环境探索：如何高效地探索比赛场地，找到障碍物、充电处、装弹处等关键位置；2、追与逃：如果比赛规则是一方逃一方追，追逐者如何找到敌方、逃亡者如何隐藏自己？讲者用一个一维空间上的简化问题暖场，向听众指出，在缺乏全局知识、只知道局部环境的前提下，为了找到目标点，数倍于最短距离的探索耗费是必不可少的。

 

　　然后，讲者将环境拓展到了二维的无向图上：每个时刻，智能体处于图中的一个节点，并可以沿着边进行移动。演讲者对于智能体可能了解到的局部信息做了具体说明，例如所在节点的标签、所在节点连接的各条边的相对编号等；也说明了可以最小化的优化目标，例如遍历所有节点所需要走过的边数、智能体记录信息所需的内存大小、智能体在途经各个节点时需要留下的信息占外存的空间大小，然后介绍了 DFS、RWH、UXS、RR 等一系列优化改进的算法，以及它们侧重于优化的指标。

 

　　最后，讲者还做了一些拓展，例如从单智能体拓展到多智能体同时探索、彼此交流的情况；从无向图到有向图；从无限制探索到有限制探索；从单独探索环境到追与逃的双方对抗；给出了一些理论证明的结果，并在最后给出了展望：除了利用当前的局部信息外，还可以让智能体从预训练中获得知识、提前预测未来信息。

 

A Distance Function to Nash Equilibrium
王冬鸽，北京大学

 

　　纳什均衡计算是非合作博弈论、机制设计和机器学习领域的重要话题，特别是在近年来兴起的多智能体学习中，均衡学习一直是这一领域研究的中心问题之一。然而，纳什均衡计算是一个已经被证明了的计算复杂度很高的问题，即便是求近似解也面临很大的困难。过去的工作中，一部分算法不断优化个体的利益，每个智能体相互独立，虽然也有良好的近似效果，但只能在二人零和博弈下保证收敛；另一部分算法采用了全局视角，得到了理论保证，但也只适用于部分博弈场景。

 

　　讲者本次介绍的工作提出了一个可以衡量任意多玩家策略组合到某个不确定纳什均衡点的距离函数。论文证明了这一距离函数对所有点均非负，并且，当且仅当为纳什均衡点时距离归零。距离函数的出现将纳什均衡求解转化为了最优化问题，这一工作进一步提出了基于梯度的近似纳什均衡计算算法，并证明了在所有玩家收益函数为凸时，该算法可以保证在多人博弈上收敛。为了验证算法的实际效果，论文展示了该算法与基准算法在通用博弈数据集 GAMUT 上的性能，并测试了算法在博弈矩阵大小成指数型增长时的鲁棒性。

 

Model-based Multi-Agent Reinforcement Learning
张伟楠，上海交通大学

 

　　AlphaGo、AlphaStar 等 AI 的出色表现都依赖于强化学习。强化学习分为基于模型（model-based）与无模型（model-free）两大方向。无模型方向是目前主流的研究方向，但它的本质是试错，面临数据利用效率低的问题。而基于模型的方法则通过另外学习一个环境模型，来估计环境的状态转移和奖励函数，然后就可以产生大量的模拟数据供模型学习，而不需要与真实环境不断交互；同时可以一直保持在线学习，来避免学习不稳定的问题。讲者介绍了基于模型方法中的 Q-planning 和 Dyna-Q 方法，并通过实验说明了它们相对于无模型的 Q-learning 方法能明显更快速地收敛。

 

　　但同时，基于模型的方法学习到的环境模型与真实环境之间的偏差会给学习带来另外的误差。演讲者提出了三个关键问题：环境模型真的对提升数据效率有益吗？什么时候起可以相信环境模型与真实环境之间的偏差足够小？怎么利用好环境模型来帮助模型训练？第一个问题的回答是肯定的；关于第二个问题，演讲者引用了 When to Trust Your Model: Model-Based Policy Optimization 一文，介绍它做的理论误差分析；第三个问题涉及到它提出的 branched rollout 的概念：连续用环境模型进行不止一步、而是 k 步的交互和数据采集；还有它提出的 MBPO 算法，核心是寻找一个合适的 k 值来最小化误差。

 

　　接着，讲者将单智能体拓展到多智能体。以往的多智能体基于模型的方法仅考虑去中心化的独立环境建模或者对于对手建模，讲者的工作首次将两者结合起来，除 MBPO 提到的采样的泛化误差、状态的分布偏移之外，还考虑了对于对手建模导致的偏差，对三者做了误差分析，然后对每个智能体分别计算不同的合适大小的k值。最后介绍了实验部分和算法收敛性证明。

 

Solution Concepts in Multi-agent Reinforcement Learning
张海峰，中国科学院自动化研究所

 

　　讲者首先讨论了博弈论中的纳什均衡（Nash equilibrium）面临的协调问题（coordination problem）。演讲者举了囚徒困境等四个矩阵博弈的实例，这些博弈可能同时存在多个纳什均衡。已有的 Nash-Q、MADDPG、Mean-field AC 等方法都可以让多智能体收敛到纳什均衡，但并不能保证收敛到多个纳什均衡中更有利于社会总利益的那一个。为此，有些情况应该考虑博弈论中其他的均衡模型。演讲者举了两种均衡。

 

　　第一种是 Stackelberg 均衡，它不再让所有智能体同时行动，而是将它们分为领导者和跟随者，按预先约定好的顺序先后确定自己的动作、并且在考虑彼此的前提下优化自身利益。讲者介绍了自己提出的基于双重优化、 actor-critic 算法的模型，以及理论上的收敛性证明。实验部分中，占据先机的领导者将先获得更高的奖励，而追随者也能在其后跟上，取得高于纳什均衡时的收益。在合作博弈、非合作博弈、视频游戏下的实验，相较其他算法均取得最好的结果。

 

　　第二种是 correlated 均衡，它允许多智能体在行动之前通过公共信号彼此交流，而在所有人都服从调度的情况下，都能达到最优。讲者介绍了团队中 Chen 等主导的工作，其核心思想是设计一个可以与大多数现有 MARL 框架集成的 SIC 模块，它将协作策略编码进公共信号中，来协调各个智能体的策略。具体来说，SIC 预定义一个关于公共信号 z 的分布，然后通过互信息损失函数，让信号 z 与全局联合策略的相关性尽量的大，从而指导各个智能体的学习，然后去中心化地服从调度、执行策略。演讲者介绍了拓展版剪刀石头布、捕食者-猎物两个实验。

 

　　最后，演讲者做了未来工作的展望，例如将二人游戏推广到多人游戏。

 

Learning Multi-Agent Cooperation
卢宗青，北京大学

 

　　合作是一种在自然界中普遍存在的现象，从底层的病毒、细菌群体中，到昆虫社会、动物社会和人类社会中都有存在。在很多的实际应用中，学习合作也是至关重要的，比如无人驾驶，多机器人控制，交通灯控制。本次的报告中，讲者分别向我们介绍了他们在与合作相关的四篇多智能体研究工作。

 

　　第一个工作是关于奖励稀缺问题（Sparse Rewards）。讲者考虑如何克服在奖励稀缺的情况下学习一个强化学习算法，并提出了一个框架 GENE。其基本思想在于自动生成初始状态，从而鼓励智能体探索环境，并利用获得的信号。GENE 可以自适应地根据之前经历的不断变化的状态来权衡探索与利用之间的比重。GENE 不依赖任何关于环境的先验知识，并可以与任何强化学习算法相结合。

 

　　第二个工作关于个体性（Individuality）。个体性在人类社会是非常重要的，个体性使得社会可以进行劳动分工，从而提高效率和生产率。因此，个体性也应该是多智能体领域的研究重点。由此启发，讲者提出了 EOI 多智能体强化学习方法。EOI 通过学习一个概率分类器，输出在给定观察状态的情况下，一个关于多智能体身份的识别概率。同时，EOI 也鼓励智能体做出更好的被识别的动作。当识别概率较高时，也就可以达到比较好的合作效果。

 

　　第三个工作关于通信（Communication）。合作的关键在于理解智能体之间的相互作用。但是，多智能体环境通常是高度变化的，这让学习智能体之间关系的抽象表示变得困难。因此讲者提出了图卷积强化学习方法，利用图卷积神经网络来适应于变化的多智能体环境，提高感知域，使得协作不再局限于局部。在非完全信息情况下尽可能向完全信息靠近，从而达到合作的目的。

 

　　第四个工作关于公平（Fairness）。将公平性考虑到多智能体系统中可以提高系统的效率和稳定性。但是，同时提高效率和公平性是一个复杂的、多目标的联合策略优化问题。为解决该难点，讲者提出了 FEN —— 一种层次强化学习模型。其主要思想是将公平性按照每个智能体进行分解并提出公平-效率奖励，从而可以使每个智能体独立学习。为了避免多目标冲突，他们设计了层级结构，用一个控制器最大化公平-效率奖励，几个子策略来提供与环境交互的多样化行为。

 

An Overview of Game-Based AI Competitions — From a Perspective of AI Evaluation
李文新，北京大学

 

　　游戏 AI 评测是 AI 发展中的重要组成部分，评测使得 AI 不断发展进步。讲者指出，AI 的竞赛有利于 AI 的评测、比较和交流，因为它保证了清晰统一的问题定义和平台环境、公平的机制、公开的数据集等。竞赛也有利于学术研究，因为它可以吸引更多的研究者、促进开源、促进学术界和工业界的联系、保证研究随着比赛周期性地推进、形成良性循环等。

 

　　演讲者列举出了很多涉及 AI 竞赛的会议和比赛，其中有不少都是北大主导的；并讲解了它们之间的差别：游戏的人数、对抗性质是竞争还是也包含合作、各方是回合制还是同时行动、智能体掌握的信息是否完全等。评测 AI 就涉及到 AI 之间排名的问题：是给予每个 AI 一个排名，还是只给出最后的胜者？对于前者，如何安排赛制、设计积分的累加制度？各个 AI 对于所需的软硬件条件的不同，会给评测平台带来哪些挑战？演讲者介绍了北大的 BOTZONE 平台作为例子。

 

　　接下来，讲者介绍了一篇利用蒙特卡罗树搜索（MCTS）方法来评测 AI 的工作，Lanzi. P.L. 定义了 MCTS 复杂度这一概念，用 MCTS 与指定玩家表现相当时所需的最小迭代次数来定性地评估玩家的实力， Zhengfei 的后续工作则将方法拓展到了斗地主的纸牌游戏上，以解决初始手牌的不公平性带来的评测问题，并且应用了 MCTS 的更多性质，例如子树深度、子节点的价值估计的最大值、平均值等。此外，这篇工作还考虑了对人类表现的评价问题，其方法是考虑 AI 使用人类行为和不使用人类行为之间的差异。最后讲者对论文的未来工作进行了展望。