第三届国际理论计算机联合大会：算法智慧的前沿探索

第三届国际理论计算机联合大会：算法智慧的前沿探索

编者注

第三届国际理论计算机联合会议（IJTCS-FAW）由北京大学邓小铁教授于2020年发起，将于2022年8月15日至19日以线上线下相结合的方式举办。会议由中国计算机学会（CCF）、国际计算机协会中国委员会（ACM China）、中国工业与应用数学学会（CSIAM）联合主办，香港城市大学（CityU）主办，北京大学前沿计算研究中心和人工智能研究所协办。

8月17日“多智能体机器学习”分论坛由北京大学李文新教授和中科院自动化研究所张海峰副研究员主持。8月18日“计算经济学”分论坛由上海交通大学陶标帅助理教授主持。下面小编为大家带来两场分论坛报告的精彩回顾。

多智能体机器学习论坛的亮点

多代理

杨耀东，北京大学

无论在自然环境还是人工环境中，我们都经常能看到智能体的合作行为，比如鱼群、动物群、无人机群、机器人的群体行动等。在多智能体学习问题中，学习合作行为非常重要，这引起了合作式多智能体强化学习的关注。在完全合作的博弈中，所有智能体的目标都是最大化同一个奖励函数。通过集中式学习方法，可以将所有智能体的行为视为单独的智能体，应用单智能体强化学习方法。然而，这会导致策略空间大小的指数级膨胀。在多智能体强化学习中，可以通过分散式方法避免这一问题。一个常见的假设是个体全局最大值（--max，IGM）条件，该条件假设每个个体最大化奖励函数的一部分时，整体奖励函数也能最大化。在此条件下，可以使用基于价值的方法来学习每个个体。然而，即使在许多简单的合作博弈中，IGM条件也经常不成立。基于策略梯度的方法会遇到估计方差大等问题。

主讲人提出了一种合作式多智能体强化学习框架，可以避免上述方法存在的问题。主讲人首先引入了信赖域方法（Trust），可以保证支付函数的单调改进性。主讲人设计了一系列多智能体强化学习算法，并通过将TRPO方法扩展到多智能体强化学习中，从理论上保证了单调改进性。他提出的算法在多种强化学习任务中取得了良好的效果。

主讲嘉宾与主席互动交流

简要介绍

陈兴国 南京邮电大学

主讲人介绍了几种强化学习模型的收敛性分析。主讲人首先介绍了马尔可夫决策过程和贝尔曼方程。应用不动点定理，可以证明值函数是压缩映射的唯一不动点，可以用迭代法求解。当状态数较少时，可以记录每个状态的值，称为表格值函数（value）。很多学习算法都可以用不动点法证明表格值函数的收敛性。但包括国际象棋在内的很多问题都会遇到“维数灾难”，导致状态数达到指数级，表格值函数无法使用。线性值函数将状态的值函数表示为若干特征函数的线性加权和，权重参数可以用最小二乘法求解。但线性拟合存在误差，时间序列查询的不动点和贝尔曼残差不动点都是真实值函数的近似。

主讲人还介绍了线性值函数学习算法的稳定性和矩阵的正定性之间的联系。目前很多算法无法兼顾效率和收敛性，为了更好地拟合值函数，需要用非线性函数进行拟合，比如很多深度强化学习模型。这时候收敛性的分析就比较困难。当有多个agent的时候，强化学习的收敛性分析更加复杂。主讲人介绍了一些工作，并指出了一些开放的问题。

在多智能体中

杜雅丽，伦敦国王学院

多智能体系统无处不在，多智能体强化学习有着重要的研究价值。主讲人首先介绍了多智能体马尔可夫决策过程，常规的马尔可夫决策过程学习方法不太适合多智能体场景，因为策略空间的大小会呈指数增长。分布式学习方法具有更好的可扩展性，主讲人提出了一种完全分布式的学习算法DMPO。主讲人指出在很多现实任务中，智能体不会受到远处智能体的影响。利用图来建模智能体之间的相邻关系，形成网络结构。每个智能体都有局部状态，每个智能体的动作只需要考虑所有相邻节点的局部状态。当环境为独立系统（ ）和非独立系统（ \xi- sytem ）时，主讲人分别分析了学习过程的性质。对于独立系统，转移概率可以分解为局部转移概率的乘积，因此每个局部转移概率可以独立估计。 对于非独立系统，考虑其转移概率以及到独立系统的距离 \xi-，当 \xi- 较小时，可以近似地进行学习。报告人证明了分布式算法得到的局部策略梯度与全局策略梯度之间的误差不会太大。报告人还提出了一个基于模型的学习框架，并对优化过程进行了理论分析。所提模型在车队控制和交通信号控制任务中都取得了良好的效果。

人类和

Joel Z Leibo，

社会行为是人类智能的重要组成部分，研究表明，人类社会行为相关脑区发育程度在发育早期远远超过其他灵长类动物，因此模仿人类的合作行为应是人工智能研究的重要内容。

主讲人介绍说，他的工作重点是人类合作行为中的SCCRM领域（社会认知能力、表征和动机）：该领域涵盖了几乎所有复杂的社会行为，如互惠、声誉、社会分工、知识积累等。他的研究目标是总结人工智能模仿人类的各种原则，以促进合作型人工智能的创建。

为了构建、评估和改进各种合作博弈的策略，主讲人及其团队建立了一个开源游戏库[1]，其中包含不同类型和内容的合作博弈。他随后用两个例子介绍了自己的工作：

1. 如何避免公地悲剧：

主讲人通过一款资源收集游戏对AI的行为进行了训练，发现设置资源阈值可以有效地将AI的策略从掠夺性行为转变为可持续行为。

2. 如何避免搭便车：

在简单情况下，博弈论研究已经给出了合适的策略，即著名的“以牙还牙”策略。在复杂情况下，目前尚无简单的原则。演讲者列举了自己以往的研究，并给出了许多不同的答案，例如建立声誉系统、树立榜样等。在实验中，这些方法可以有效减少AI的搭便车行为。

[1]

计算经济学论坛精彩看点

：从基于代理到

余芳宜

主讲人研究了一类随机过程的收敛问题，定义为X_{k+1}-X_{k}=\frac{1}{n}\left(F\left(X_{k}\right)+U_{k}\right)。具体来说，他们想知道当起点在鞍点或非吸引的不动点时，序列是否会逃离鞍点，以及以什么样的速率逃离鞍点并收敛到吸引的不动点。他们证明了当F和U满足一定条件时，序列会以\Theta(n \log n)的速度逃离鞍点。在证明上界的过程中，他们将序列点分解为稳定（收敛到鞍点）和不稳定（逃离鞍点）两个方向，并通过分析不同阶段在两个方向上分解的强度得到结果。 他们还证明了在一定条件下，该序列会以\Theta(n \log n)的速度收敛到一个吸引点。最后，主讲者介绍了该理论在社交网络中共识形成中的应用。

主讲嘉宾与主席互动交流

蛋糕

新南威尔士大学 陆新航

主讲人介绍了一种新颖的公平分配（fair）场景：蛋糕，并研究了蛋糕场景下当玩家具有短而均匀的（-）支付函数（ ）时的机制设计问题。具体来说，每个人的支付可以由蛋糕上的一个子集W_{i}决定；机制需要在蛋糕上选取一块A给所有人分享，每个人的效用可以用W_{i} \cap A计算，其中W_{i}通常是玩家自己的私人信息。主讲人与合作者希望设计一种机制，让玩家能够诚实报告自己的效用信息，即反策略（ ），同时又能满足一定的公平性（fair）。他们考虑了两种机制，并纳什（MNW），证明了 的反策略性，并证明了它是所有反策略和机制中，使社会福利（ ）最大化的机制。 在两人参与的场景中，通过证明和MNW的等价性，证明了MNW的反策略性，但该性质在一般场景中并不成立。在分析上述两种机制时，演讲者首先假设可以防止参与者获得他们生成的不需要的部分（）。当机制无法保证这一点时，他们证明了不存在任何机制可以同时实现反策略性、帕累托最优（-）和正的社会福利近似率。

零和博弈中的纳什

文英，上海交通大学

主讲人介绍了一种近似解决零信息与不完全信息博弈的新算法。零信息空间（PSRO）算法是求解元博弈的-方法的扩展，它通过不断对现有元博弈中的对手均衡策略做出最优应对来扩展策略空间，并通过使用基于的方法有效提升算法的性能和鲁棒性。然而在经典的PSRO算法中，大量的模拟和最佳应对策略的学习使得算法运行效率极低。主讲人针对-（URR）博弈提出了一种新的无解算法，避免了元博弈中的模拟问题，并设计了一种新的并行PSRO（EPSRO）算法。主讲人及其合作者证明了EPSRO在上的单调改进性质，这是其他现有算法所不具备的，并通过实验证明了EPSRO在速度方面的优越性能。

多方参与

沈一恒，杜克大学

在联邦学习等设定中，想要构建机器学习模型的玩家（代理）可以共享自己的数据，共同构建模型以提高机器学习的性能。然而，这种场景下可能出现的问题，例如不同公司之间的利益冲突，他们不一定愿意提交自己的所有数据。基于这一动机，本报告研究了这种设定下的机制设计问题。

具体来说，每个参与共享数据的玩家都有一个私有类型，也就是他拥有的数据（多少）。每个玩家在参与共享数据时向平台上报自己的数据。然后平台计算这些数据，并运行机制为每个玩家分配一个模型，并要求每个玩家支付相应的费用。每个玩家的模型都有一个“质量”，以衡量获得的模型的质量。玩家可以将该模型与用自己的私有数据训练的模型进行比较，并选择最佳的一个。他们的估值函数是他们获得的模型质量、他们的真实数据量以及所有其他玩家获得的模型质量的函数。这种形式的估值函数是本报告不同于以往研究的重要亮点。平台的收益是所有玩家支付的总和。 在此设定下，报告研究了激励相容（参与者的最优策略是报告自己的数据（多少））、个体理性（参与者提供数据获得的效用总是高于不提供数据的效用）、最大化社会福利、满足预算约束（平台收益非负）等性质。证明了当参与者的估值函数可以分解为分配的模型质量的单调函数和模型质量的其他函数之和时，让每个参与者支付参与数据共享和不参与数据共享的估值差额是最大化所有个体理性机制收益的机制，也是激励相容的。报告还给出了一般估值函数下个体理性和激励相容机制的充分条件和必要条件。最后，报告还证明了平凡机制在非竞争市场中的有效性，并给出了一种算法，判断当每个参与者的类型为离散时，是否存在满足激励相容、个体理性、最大化社会福利并满足预算约束的机制。

- Sybil 防护

刘翔 东南大学

智能手机与便携设备的普及使得人们能够参与到大规模的数据收集任务中，促进了系统的发展。为了使得自私的参与者能够诚实地报告自己的隐私信息，需要设计一种满足特定性质的机制。记者与合作者围绕买家有预算、参与者可以自行竞标完成特定任务的损失情形设计了机制。他们进一步考虑到玩家的Sybil攻击，即同时注册多个小账户参与机制的策略行为，提出了一种满足反策略性（）、个体理性（）、在预算之内且能够抵御Sybil攻击的机制。同时，记者通过实验表明该机制在实际应用中非常高效。

并遵守规则

李培华 山东大学

本报告介绍了一种新的迭代选举方法（ ）。假设有一个集合R，其元素是筛选参加下一轮选举的候选人的各种规则。在每一轮选举中，选举党可以选择R中的一条规则来筛选本轮选举的候选人。报告人关注的问题是，是否存在一种规则组合，使得候选人p在给定集合R的情况下成为唯一的赢家（ ，PWP）；或者候选人p在所有规则组合下是否都是唯一的赢家（ ）。报告人及其合作者考虑了Hart、 和四条筛选规则，通过3-SAT归约，证明了当R是{Hart、 ， ， }中除{、 }之外的任意子集且至少包含2个元素时，上述两个问题都是NP难的。此外，报告人还讨论了PWP关于候选人和选民数量的参数复杂度，并证明了它是固定的。

编辑 | 李宁远、李东晨、陈昱荣、王昌

@PKU