Multi-agent imitation learning with function approximation: Linear Markov games and beyond

📄 arXiv: 2602.22810v1 📥 PDF

作者: Luca Viano, Till Freihaut, Emanuele Nevali, Volkan Cevher, Matthieu Geist, Giorgia Ramponi

分类: cs.LG

发布日期: 2026-02-26

💡 一句话要点

针对线性马尔可夫博弈，提出基于函数逼近的多智能体模仿学习方法

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 多智能体模仿学习 线性马尔可夫博弈 函数逼近 交互式学习 特征集中系数

📋 核心要点

  1. 现有MAIL方法依赖于难以满足的“全策略偏差集中系数”，限制了其在复杂环境中的应用。
  2. 利用线性马尔可夫博弈的结构特性，将集中系数定义在特征层面，降低了对集中系数的要求，并提出了交互式MAIL算法。
  3. 实验结果表明，提出的深度MAIL交互式算法在井字棋和Connect4等游戏中显著优于行为克隆方法。

📝 摘要（中文）

本文针对线性马尔可夫博弈中的多智能体模仿学习（MAIL）问题，提出了首个理论分析框架。在该框架下，转移动态和每个智能体的奖励函数都与给定的特征呈线性关系。研究表明，利用这种线性结构，可以将状态-动作层面的“全策略偏差集中系数”替换为特征层面的集中系数，当特征能够有效描述状态相似性时，后者通常远小于前者。此外，为了避免对集中系数的依赖，本文转向交互式设置，提出了首个针对线性马尔可夫博弈的计算高效的交互式MAIL算法，并证明其样本复杂度仅取决于特征映射的维度d。基于这些理论发现，本文提出了一种深度MAIL交互式算法，在井字棋和Connect4等游戏中明显优于行为克隆（BC）方法。

🔬 方法详解

问题定义：论文旨在解决多智能体模仿学习（MAIL）在线性马尔可夫博弈中的效率问题。现有的MAIL方法，特别是那些依赖于集中系数的方法，在复杂环境中往往表现不佳，因为“全策略偏差集中系数”可能非常大，导致样本复杂度过高。此外，计算集中系数本身也是一个难题。

核心思路：论文的核心思路是利用线性马尔可夫博弈的结构特性，即转移动态和奖励函数都与给定的特征呈线性关系。通过将集中系数定义在特征层面，而不是状态-动作层面，可以显著降低集中系数的值，从而降低样本复杂度。此外，通过引入交互式学习框架，可以完全避免对集中系数的依赖。

技术框架：论文提出了两种主要的MAIL方法。第一种方法是基于特征层面集中系数的MAIL算法，该算法利用线性马尔可夫博弈的结构特性，降低了对集中系数的要求。第二种方法是交互式MAIL算法，该算法通过与环境进行交互，主动探索策略空间，从而避免了对集中系数的依赖。此外，论文还提出了一种深度MAIL交互式算法，该算法将深度学习与交互式MAIL相结合，以提高算法的性能。

关键创新：论文的关键创新点在于：1) 提出了基于特征层面集中系数的MAIL算法，降低了对集中系数的要求；2) 提出了交互式MAIL算法，避免了对集中系数的依赖；3) 提出了深度MAIL交互式算法，将深度学习与交互式MAIL相结合。与现有方法相比，该方法在复杂环境中具有更高的效率和更好的性能。

关键设计：论文中的关键设计包括：1) 特征映射的选择：选择合适的特征映射对于降低集中系数至关重要；2) 交互式学习策略的设计：设计有效的交互式学习策略可以提高算法的探索效率；3) 深度神经网络结构的设计：设计合适的深度神经网络结构可以提高算法的性能。

🖼️ 关键图片

fig_0
fig_1

📊 实验亮点

论文提出的深度MAIL交互式算法在井字棋和Connect4等游戏中明显优于行为克隆（BC）方法，验证了该方法的有效性。具体的性能提升数据未在摘要中给出，需要在论文正文中查找。

🎯 应用场景

该研究成果可应用于多智能体协作与博弈场景，例如自动驾驶、机器人协同、资源分配、网络安全等。通过模仿专家策略，智能体能够学习到高效的协作方式，提升整体性能和效率。该方法在游戏AI领域也有着广泛的应用前景，可以训练出更强大的游戏AI。

📄 摘要（原文）

In this work, we present the first theoretical analysis of multi-agent imitation learning (MAIL) in linear Markov games where both the transition dynamics and each agent's reward function are linear in some given features. We demonstrate that by leveraging this structure, it is possible to replace the state-action level "all policy deviation concentrability coefficient" (Freihaut et al., arXiv:2510.09325) with a concentrability coefficient defined at the feature level which can be much smaller than the state-action analog when the features are informative about states' similarity. Furthermore, to circumvent the need for any concentrability coefficient, we turn to the interactive setting. We provide the first, computationally efficient, interactive MAIL algorithm for linear Markov games and show that its sample complexity depends only on the dimension of the feature map $d$. Building on these theoretical findings, we propose a deep MAIL interactive algorithm which clearly outperforms BC on games such as Tic-Tac-Toe and Connect4.