GNN+多智能体？剑桥大学最新《图神经网络多智能体学习》博士论文

随着时间的推移，机器学习研究越来越重视利用关系归纳偏差[1]。通过关注图结构数据中的潜在关系，已经能够创建性能和泛化能力优越的模型。对于不同的图拓扑结构，这些模型可以表现为CNN（在网格图上）、RNN（在线图上）和Transformer（在全连接图上）。然而，所有这些架构都可以被归为图神经网络（GNNs）的一种特例，这是一种可以在任意图结构数据上操作的框架。利用关系归纳偏差，GNNs使用局部滤波器学习在高维数据上泛化的函数。它们在多智能体学习中尤其有用，因为大多数数据都被结构化为图（例如，多机器人团队中的通信链接生成图连接）。在本论文中，我们研究了多智能体学习领域。该领域的最新进展令人鼓舞，但还需要进一步创新以解决诸如部分可观测性下的学习和促进协作行为等问题。GNNs提供了一个有用的框架来解决这些问题，因为其去中心化架构使其能够利用全局信息，同时保持泛化能力和样本效率。尽管有这些好处，现有基于GNN的多智能体问题解决方法的应用范围仍然有限。在本论文中，我们研究了当前GNN架构的弱点，并提出了改进其能力的扩展方法。此外，我们还拓展到新的学习范式，使基于GNN的方法能够应对新的应用。我们首先通过开发一个模块化框架来分析现有的基于GNN的多机器人任务方法[2]。通过对框架内的子模块进行消融研究，我们可以得出关于GNN架构中表征复杂性最佳分配的结论。我们的分析强调了在聚合之前映射到学习的潜在空间的必要性，使网络能够保留最重要的信息。为了避免通过简单聚合造成的信息损失，我们随后的工作努力寻找一种使聚合器本身可以被学习的架构[3]。我们引入了一种新的方法来参数化所有标准聚合器的空间，并验证其在图学习问题中的性能。接下来，我们将重点扩展到集合学习的相关问题[4]。我们引入了一种新的集合自编码器，使得可以以无监督方式学习从集合到固定大小嵌入的双射映射。为了展示这种架构的有用性，我们使用它创建了一种任务无关的多智能体通信策略。在我们的最后一项工作中，我们使用GNNs来解决多智能体强化学习中的信用分配问题[5]。利用GNNs以去中心化方式结合局部和聚合的邻域信息，我们采用基于GNN的架构进行价值分解。该方法保持了表示不可分解价值函数的能力，但在可能时进行分解。我们在本论文结尾处反思了我们的贡献，这些贡献涵盖了监督学习、无监督学习和强化学习领域。我们开发的新架构为研究开辟了新的途径，不仅在应用上，还在方法扩展上。对于论文中的每个研究主题，我们提出了可以进一步影响该领域的未来工作。

跨越宇宙，从亚原子粒子的舞蹈到天体的旋转，宇宙按照基本定律展开。这些定律在其简洁中体现出优雅，支配着所有物质的行为。然而，当实体通过成对交互编织联系的网络时，一种显著的现象出现了——涌现现象产生了超越其支配定律的意外行为。

在计算机科学领域，我们在“多智能体系统”的框架下描述这些现象，其中“智能体”代表任何类型的实体，系统的行为由实体之间的交互模型描述。根据不同的规则，系统可以产生截然不同的行为。例如，在受Navier-Stokes方程支配的粒子系统中，复杂性可以从湍流的混沌中产生。类似的情况在细胞自动机中也有体现，其中简单的邻域规则可以生成计算上不可约的信息[6]。然而，复杂性并不总是导致混沌——通过稍微不同的规则，实体之间的交互也可以导致组织化。人类大脑就是一个例子，其中细胞网络产生了高度组织化的行为。大脑中的每个神经元在功能上极其简单，但通过它们之间的交互，意识这一不可思议的现象得以产生。作为交互的研究，多智能体系统包含了宇宙中待解的最大谜题之一。在本论文中，我们的目标是双重的：开发稳健的机制来建模多智能体系统，并利用这一理解来设计新的多智能体系统，找到产生某种期望涌现行为的具体局部规则。尽管我们对多智能体系统的理解仍然初步，它们目前在计算机科学的许多领域中都有应用。这些系统可以是具体的或虚拟的，并且它们可以有个体目标或共同目标。例如，分布式问题解决指的是一个网络中的通信设备为一个共享目标而工作[7]。该领域包括基于网络的问题（网络访问、电力控制、计算卸载、内容缓存、数据包路由等）[8]，车辆路由问题（包括许多变体，引入了如边容量、车辆容量、实时需求等约束）[9]，以及传感器网络问题（涵盖定位、路由、信息处理和主动感知）[10]。机器人技术是另一个多智能体系统的大子领域。多智能体系统可以在自主车辆中找到（无论是否有共享目标和通信）[11]，群体机器人技术（包括自组装结构、映射、搜索等）[12]，以及模块化机器人（其中一个机器人内的执行器被视为独立的智能体）[13]。另一个多智能体系统的用途是多人游戏，如《星际争霸》[14]。最后，多智能体系统可以用于建模现实世界的数据（如知识图谱、动物群体行为、行星运动、点云、分子结构、推荐系统等）[15]。 这些应用仍然是开放的研究领域，因为它们在计算上是困难的——大多数没有基于第一原理的可行的最优解。在追求NP难问题的可行解时，一种流行的方法是使用基于学习的方法来提供近似解[16]。在这一范式下，计算“努力”转移到训练阶段，使得在执行时间能够近乎瞬时地产生解决方案。而算法方法可能使用搜索技术来解决任何NP难题，基于学习的方法可以利用特定领域的信息来识别模式，并且在某些问题中可以发现解空间中的潜在组织。简而言之，通过绕过算法方法的计算难度，转而采用基于学习的方法，可以为多智能体问题提供近似解，否则这些问题是不可解的。

在以这种方式解决多智能体问题之前，必须先形式化这些问题。也许最好的方式是将多智能体系统表示为图。图的节点表示系统中的智能体，边表示它们之间的关系（图1.1）。这种表示具有显著的灵活性——通过定义自定义的节点和边特征，可以在同一抽象下捕捉上述所有应用。例如，边可以表示机器人问题中可用的通信链接，知识图谱中概念之间的语义链接，社交数据集中如友谊/合作者关系的个人链接，以及物理模拟中相互作用的对象（如在模拟电力时，质子和电子之间会有一条边，但质子和中子之间则不会）。

一种自然的学习图结构数据的方法是使用图神经网络（GNNs）[17]。GNNs是图卷积的扩展，通过对图中每个节点（及其关联边）应用局部变换来实现[18]。这种结构的模型有几个好处。首先，由于模型定义在与底层数据相同的图结构上，它可以充分利用数据中存在的任何归纳偏差[1]。其次，由于它由局部操作定义，可学习组件的状态空间的维度显著小于集中式网络。重复使用局部操作也使GNNs具有置换等变性，从而显著提高了样本效率。此外，由于在整个图中使用相同的局部操作，它从图中的每个节点接收训练信号。这些特性绕过了维度灾难，这通常是朴素多智能体学习方法面临的挑战。最后，由于不同的图可能在局部参考框架中具有相似性，GNNs在可迁移性方面表现出色[18]。也就是说，GNNs不仅可以对新的联合状态进行泛化，还可以外推到训练时未曾经历的不同大小的图。

研究问题

本论文探讨了GNNs在多智能体学习中的应用。为了指导我们的研究，我们提出以下研究问题： * 当前GNN架构在多机器人应用中的弱点是什么，如何改进？在为该领域提供贡献之前，重要的是要更好地理解GNNs的工作原理。当两个GNNs在性能上表现出差异时，我们能解释原因吗？或者更简单地说，我们能描述架构本身的差异吗？此外，如果我们能识别出一个弱点，那么我们如何解决它？由于答案在不同领域之间可能不同，我们专注于一个特定应用：基于GNN的多机器人系统策略。

**在不同的学习范式下，如何利用GNNs的特性？**大多数文献在监督学习领域使用GNNs——有大量研究将GNNs应用于图结构数据集的建模。也有一些现有工作使用GNNs进行多智能体强化学习，作为学习数据驱动的策略通信策略的工具。然而，在无监督上下文中使用GNNs的工作极其稀少。是否存在一个缺失的环节，或是GNNs在无监督学习领域存在根本性的障碍？

**基于GNN的架构可以解决哪些新应用？**作为前一个研究问题的自然延伸，我们问：是否有任何新问题可以通过GNNs与无监督学习的结合来解决？例如，通过使用重建损失训练GNN（即不使用标签），有可能学习一种独立于下游任务的通信策略。这样的策略将有许多潜在的应用。另一个可能有用的无监督概念是因子化，即某些期望的值不是通过标记数据学习的，而是通过架构本身隐含产生的因子化。