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

📄 arXiv: 2602.22810 📥 PDF

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

分类: cs.LG

发布日期: 2026-02-28

💡 一句话要点

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

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

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

📋 核心要点

  1. 传统多智能体模仿学习方法在复杂环境中面临高样本复杂度和难以泛化的问题，尤其是在状态空间庞大时。
  2. 本文利用线性马尔可夫博弈的结构特性，通过特征层面的集中系数降低样本复杂度，并提出交互式学习框架避免对集中系数的依赖。
  3. 实验结果表明，所提出的深度MAIL交互式算法在井字棋和四子棋等游戏中显著优于行为克隆算法，验证了方法的有效性。

📝 摘要（中文）

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

🔬 方法详解

问题定义：论文旨在解决多智能体模仿学习（MAIL）在线性马尔可夫博弈中的样本复杂度问题。现有的MAIL方法，例如基于行为克隆（BC）的方法，通常需要大量的专家数据才能学习到有效的策略，尤其是在状态空间很大的情况下。此外，一些理论分析依赖于难以满足的“全策略偏差集中系数”，限制了算法的实际应用。

核心思路：论文的核心思路是利用线性马尔可夫博弈的结构特性，即转移动态和奖励函数都与给定的特征呈线性关系。通过将集中系数从状态-动作层面转移到特征层面，可以显著降低样本复杂度。此外，通过引入交互式学习框架，算法不再需要预先收集大量的专家数据，而是通过与环境的交互来逐步学习。

技术框架：整体框架包含两个主要部分：理论分析和算法设计。理论分析部分证明了在线性马尔可夫博弈中，可以使用特征层面的集中系数来降低样本复杂度。算法设计部分提出了一个计算高效的交互式MAIL算法，该算法通过与环境的交互来学习策略。此外，还提出了一个基于深度学习的MAIL交互式算法，用于处理更复杂的环境。

关键创新：论文的关键创新在于：1) 首次对线性马尔可夫博弈中的MAIL进行了理论分析，并证明了可以使用特征层面的集中系数来降低样本复杂度；2) 提出了一个计算高效的交互式MAIL算法，该算法不需要预先收集大量的专家数据；3) 提出了一个基于深度学习的MAIL交互式算法，该算法可以在更复杂的环境中应用。

关键设计：论文的关键设计包括：1) 使用线性函数逼近来表示转移动态和奖励函数；2) 定义了特征层面的集中系数，并证明其可以显著小于状态-动作层面的集中系数；3) 设计了一个交互式学习框架，该框架允许智能体通过与环境的交互来学习策略；4) 使用深度神经网络来表示策略，并使用模仿学习损失函数来训练网络。

🖼️ 关键图片

fig_0
fig_1

📊 实验亮点

实验结果表明，所提出的深度MAIL交互式算法在井字棋和四子棋等游戏中明显优于行为克隆（BC）算法。具体来说，该算法能够更快地学习到有效的策略，并且在面对不同的对手时具有更好的泛化能力。这些结果验证了该方法在线性马尔可夫博弈中的有效性。

🎯 应用场景

该研究成果可应用于多智能体协作控制、博弈游戏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.