第三届国际理论计算机联合大会（International Joint Conference on Theoretical Computer Science-Frontier of Algorithmic Wisdom，IJTCS-FAW）由北京大学讲席教授邓小铁于2020年牵头发起，第三届于2022年8月15日-19日线上线下交互举行。大会由中国计算机学会（CCF）、国际计算机学会中国委员会（ACM China Council）、中国工业与应用数学学会（CSIAM）联合主办，香港城市大学（CityU）承办，北京大学前沿计算研究中心、北京大学人工智能研究院协办。

　　

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

 

 

多智能体机器学习分论坛精彩回顾

　　

A Continuum of Solutions to Cooperative Multi-Agent Reinforcement Learning

杨耀东，北京大学

 

 

　　我们在自然环境和人工环境中都常常见到智能体的合作行为，例如鱼群、兽群和无人机集群和机器人的群体行动。在多智能体学习问题中，合作行为的学习是十分重要的，这使得合作性的多智能体强化学习受到关注。在完全合作博弈（fully-cooperative game）中，所有智能体的目标都是最大化同一个收益函数。通过中心化的学习方法，可以将所有智能体的行动视为单独的智能体，并应用单智能体强化学习方法。但这将造成策略空间大小的指数膨胀问题。在多智能体强化学习中可以通过去中心化的方法避免这一问题。一个常见的假设是个体全局最大（individual-global-max, IGM）条件，它假设当每个个体各自最大化收益函数的一部分时，总体的收益函数也能得到最大化。在此条件下，可以使用基于价值的方法对每个个体进行学习。但即使在很多简单的合作博弈中，IGM 条件也常常不成立。基于策略梯度的方法会遇到估计方差较大等问题。

　　

　　报告人提出了一种合作性多智能体强化学习框架，能避免以上几种方法的问题。报告人首先介绍了信赖域方法（Trust Region Method），能够保证收益函数单调提升。报告人设计了 HATRPO 等一系列多智能体强化学习算法，通过将 TRPO 方法拓展到多智能体强化学习中，从理论上保证了单调提升性质。他所提出的算法在多种强化学习任务中都取得了良好效果。

 

报告人与主席互动交流

　　

A Brief Introduction to Convergence Analysis of Reinforcement Learning

陈兴国，南京邮电大学

 

 

　　报告人介绍了几种强化学习模型的收敛性分析。报告人首先介绍了马尔科夫决策过程与贝尔曼等式。应用巴拿赫不动点定理，可以证明价值函数是一个压缩映射的唯一不动点，可以使用迭代方法求解。当状态数量较少时，可以记录每个状态的价值，称为表格价值函数（tabular value functions）。许多学习算法对于表格价值函数都可以用不动点方法证明收敛性。但包括棋类在内的许多问题都会遇到“维度诅咒”，导致状态的数量达到指数级别，无法使用表格价值函数。线性价值函数将状态的价值函数表示为若干个特征函数的线性加权和，可以通过最小二乘法求解权重参数。但线性拟合存在误差，时序查分不动点和贝尔曼残差不动点都是真实价值函数的近似。

　　

　　报告人还介绍了对于线性价值函数的学习算法的稳定性与矩阵正定性的联系，目前许多算法还无法兼顾效率与收敛性。为了更好地拟合价值函数，需要使用非线性函数进行拟合，例如许多深度强化学习模型，此时对于收敛性的分析更为困难。而当存在多个智能体时，强化学习的收敛性分析更为复杂。报告人介绍了一些工作，并指出了一些开放问题。

　　

Decision Structure in Decentralized Multi-Agent Learning

杜雅丽，伦敦国王学院

 

 

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

　　

Reverse Engineering Human Cooperation and Cultural Evolution

Joel Z Leibo, DeepMind

 

 

　　社会行为是人类智能的重要环节。研究表明，人类在发育初期社会行为相关的脑区的发展便已经远超其他灵长类动物。因此，模仿人类的合作行为应当是人工智能研究的重要内容。

　　

　　报告人介绍到，他的工作专注于人类合作行为中的 SCCRM 领域（社会认知的能力、代表和动机）：这个领域涵盖了几乎所有复杂的社会行为，例如互惠、声誉、社会分工、知识积累等等，他的研究目标是总结AI模仿人类的各种原则，以为制造合作型AI提供便利。

　　

　　为了构建、评估和提升各种合作博弈的策略，报告人和团队建立了一个开源游戏库[1]，包含了不同种类和内容的合作游戏。随后，他通过两个例子介绍了他的工作：

　　

　　1. 如何避免公地悲剧：

　　报告人在一个资源收集游戏上训练了 AI 的行为。他发现，为资源设置门槛可以有效地让 AI 的策略从竭泽而渔性的掠夺行为迁移为可持续发展的行为。

　　

　　2. 如何避免搭便车：

　　在简单情况下，博弈论研究已经给出了合适的策略，即著名的“以牙还牙”策略。而在复杂情况下，目前还没有简单的原则。报告人列举了他过往的研究，给出了许多不同的答案，如建立声誉系统、树立模范等。在实验中，这些方法均可以有效地减少 AI 的搭便车行为。

　　

　　[1] https://github.com/deepmind/meltingpot

　　

 

计算经济学分论坛精彩回顾

　　

Escaping Saddle Points: from Agent-based Models to Stochastic Gradient Descent

Fang-Yi Yu, George Mason University

 

 

　　报告人研究了一类定义如 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) 的速度收敛至一个吸引点。最后，报告人介绍了该理论在社交网络中共同观点的形成相关的应用。

 

报告人与主席互动交流

　　

Truthful Cake Sharing

陆馨杭，新南威尔士大学

 

 

　　报告人介绍了一种新颖的公平分配（fair division）场景：cake sharing，并研究了 cake sharing 场景下，玩家拥有按短均匀（piecewise-uniform）的收益函数（utility function）时的机制设计问题。具体而言，每个人的收益可用 cake 上的一个子集 W_{i} 来决定；机制需要选择 cake 上的一片 A，让所有人分享，每个人的效用可用 W_{i} \cap A 来计算，而  W_{i} 通常是玩家自己的私有信息。报告人及其合作者希望设计的机制既能让玩家诚实地报出自己的效用信息，即防策略性（truthful），又能满足一定的公平性（fair）。他们一共考虑了 leximin 和 maximum Nash welfare (MNW) 两种机制，证明了 leximin 的防策略性，并且证明了其为所有防策略性和 position oblivious 的机制中最大化社会福利（egalitarian welfare）的机制。在两个玩家的场景下，通过证明 leximin 和 MNW 的等价性，证明了 MNW 的防策略性，然而这一性质在一般场景下是不成立的。在分析上述两个机制的时候，报告人首先假设可以阻止玩家获取他们生成不想要的部分（blocking），当机制不能保证 blocking 的时候，他们证明了不同时存在达到防策略性、帕累托最优（Pareto-optimal）和 position oblivious 的机制，可以达到一个正的社会福利近似比。

　　

An Efficient Algorithm for Approximating Nash Equilibrium in Zero-sum Imperfect-information Games

温颖，上海交通大学

 

 

　　报告人介绍了一种新型的近似求解零和非完美信息博弈的算法。Policy Space Response Oracles (PSRO) 算法作为求解元博弈（meta games）的 double-oracle 方法的扩展，通过不断对现有的元博弈下对手的均衡策略做最优反应来扩充策略空间，利用基于 population 的方式来有效的提升算法的表现和鲁棒性。然而，经典的 PSRO 算法中，海量的仿真和学习最优反应策略使算法运行非常低效。报告人通过引入一个新的对 unrestricted-restrictd (URR) 博弈的 no-regret 求解算法来避免元博弈上的仿真问题，设计了可并行的新型的 Efficient PSRO (EPSRO) 算法。报告人及其合作者证明了 EPSRO 相对于其他现有算法所没有的，在 exploitability 上的单调提升性质，并通过实验证明了 EPSRO 在速度上优越的表现。

　　

Mechanism Design for Multi-party Machine Learning

沈毅恒，杜克大学

 

 

　　在联邦学习等设定下，希望建立机器学习模型的玩家（agent）可以分享自己拥有的数据，共同建模以提高机器学习的性能。不过，在这种情境下可能出现 incentive 的问题，例如不同的公司之间存在利益冲突，因此它们不一定愿意提交自己的全部数据。基于这样的动机，本报告研究了此种设定下机制设计问题。

　　

　　具体而言，参与共享数据的每个玩家都有一个私有的类型（type），即所拥有的数据（多寡）。每个玩家在参与分享数据时向平台汇报自己的数据，随后平台通过计算这些数据和运行机制，为每个玩家分配一个模型，并要求每个玩家相应付款。每位玩家得到的模型都存在一个“质量”来衡量所得模型的好坏，玩家可以比较该模型和自己使用私有数据训练得到的模型而选择最好者。他们的估值函数是自己获得的模型质量、自己真实的数据多寡和所有其他玩家获得的模型质量的函数——估值函数的这种形式是本报告不同于前人研究的一个重要亮点。而平台的收益是所有玩家的支付之和。在这样的设定下，报告研究了激励相容（玩家的最好策略是真实报出自己的数据（多寡））、个体理性（玩家提供数据所得的效用总是高于不提供数据的效用）、最大化社会福利、满足预算限制（平台的收益非负）等性质。他们证明：当玩家的估值函数可分离为分配得到模型质量的单调函数和其它模型质量的函数的加和时，让每个玩家支付其参与分享数据和不参与分享数据之间估值的差是所有满足个体理性机制中最大化收益的，同时它也是激励相容的。报告还给出了一般估值函数下个体理性和激励相容机制的充分条件和必要条件各一。最后，报告还证明了非竞争性市场下平凡机制的高效性，同时还给出了一个当每个玩家的类型是离散的情形下，判定是否存在一个满足激励相容、个体理性、最大化社会福利和满足预算限制的机制的算法。

　　

Budget-Feasible Sybil-Proof Mechanisms for Crowdsensing

刘翔，东南大学

 

 

　　智能手机和便携式设备的普及，使得人们可以参与到大规模的数据收集任务中来，促进了 crowdsensing 系统的发展。为了使自私的参与者能够诚实地报出自己的私有信息，需要设计满足特定性质的机制。报告人及其合作者围绕买家拥有预算、参与者可以竞价自己完成特定任务的损失情形下的机制设计，更进一步将玩家的女巫攻击—即通过注册多个小号同时参与机制的这一策略性行为考虑在内，提出了满足防策略性（truthfulness）、个体理性（individual rationality）、在预算范围内且能抵御女巫攻击的 crowdsensing 机制。同时，报告人通过实验表明该机制是在实际应用上是非常高效的。

　　

Possible and Necessary Winner Problems in Iterative Elections with Multiple Rules

黎佩华，山东大学

 

 

　　该报告介绍了一种新型的迭代选举法（iterative election），假设存在一个集合 R，其中的元素是用于筛选候选者参加下一轮选举的各种规则，每一轮，选举方可以选择R中的一种规则来对当前轮的候选者进行筛选。报告人关心的问题是给定集合 R，是否存在一种规则的组合，使得某个候选人 p 是唯一的获胜者（possible winner problem, PWP）；或者决定是否在所有规则组合下，某个候选人 p 都是唯一的获胜者（necessary winner problem）。报告人及其合作者考虑了 Hart, Coombs, Baldwin 和 Nanson 四种筛选规则，通过3-SAT 规约，证明了在 R 是 {Hart, Coombs, Baldwin, Nanson} 的除了 {Baldwin, Nanson} 以外的任意包含至少2个元素的子集时，上述两个问题都是 NP-hard problem。另外，报告人也讨论了 PWP 的关于候选者和投票者人数的参数复杂性，证明了其为 fixed-parameter tractable 的。