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

• URL: http://arxiv.org/abs/2602.22810v1
• Date: Thu, 26 Feb 2026 09:50:15 GMT
• Title: Multi-agent imitation learning with function approximation: Linear Markov games and beyond
• Authors: Luca Viano, Till Freihaut, Emanuele Nevali, Volkan Cevher, Matthieu Geist, Giorgia Ramponi,
• Abstract summary: We present the first theoretical analysis of multi-agent imitation learning (MAIL) in linear Markov games.<n>We show that it is possible to replace the state-action level "all policy deviation concentrability coefficient" with a concentrability coefficient defined at the feature level.<n>We propose a deep MAIL interactive algorithm which clearly outperforms BC on games such as Tic-Tac-Toe and Connect4.
• Score: 63.14746189846806
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Dimension-Free Minimax Rates for Learning Pairwise Interactions in Attention-Style Models [9.144120605998138]
  We study the convergence rate of learning pairwise interactions in single-layer attention-style models.<n>We prove that the minimax rate is $M-frac2beta2beta+1$ with $M$ being the sample size.
  arXiv  Detail & Related papers  (2025-10-13T18:00:04Z)
• Rate optimal learning of equilibria from data [63.14746189846806]
  We close theoretical gaps in Multi-Agent Imitation Learning (MAIL) by characterizing the limits of non-interactive MAIL and presenting the first interactive algorithm with near-optimal sample complexity.<n>For the interactive setting, we introduce a framework that combines reward-free reinforcement learning with interactive MAIL and instantiate it with an algorithm, MAIL-WARM.<n>We provide numerical results that support our theory and illustrate, in environments such as grid worlds, where Behavior Cloning fails to learn.
  arXiv  Detail & Related papers  (2025-10-10T12:28:35Z)
• Unveiling Induction Heads: Provable Training Dynamics and Feature Learning in Transformers [54.20763128054692]
  We study how a two-attention-layer transformer is trained to perform ICL on $n$-gram Markov chain data. We prove that the gradient flow with respect to a cross-entropy ICL loss converges to a limiting model.
  arXiv  Detail & Related papers  (2024-09-09T18:10:26Z)
• Convergence of Decentralized Actor-Critic Algorithm in General-sum Markov Games [3.8779763612314633]
  We study the properties of learning algorithms in general-sum Markov games.<n>In particular, we focus on a decentralized algorithm where each agent adopts an actor-critic learning dynamic.
  arXiv  Detail & Related papers  (2024-09-06T20:49:11Z)
• Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximation [56.715186432566576]
  We propose a new model, independent linear Markov game, for reinforcement learning with a large state space and a large number of agents. We design new algorithms for learning correlated equilibria (CCE) and Markov correlated equilibria (CE) with sample bounds complexity that only scalely with each agent's own function class complexity. Our algorithms rely on two key technical innovations: (1) utilizing policy replay to tackle non-stationarity incurred by multiple agents and the use of function approximation; and (2) separating learning Markov equilibria and exploration in the Markov games.
  arXiv  Detail & Related papers  (2023-02-07T18:47:48Z)
• Representation Learning for General-sum Low-rank Markov Games [63.119870889883224]
  We study multi-agent general-sum Markov games with nonlinear function approximation. We focus on low-rank Markov games whose transition matrix admits a hidden low-rank structure on top of an unknown non-linear representation.
  arXiv  Detail & Related papers  (2022-10-30T22:58:22Z)
• Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning [53.17258888552998]
  This work proposes an exploration variant of the basic $Q$-learning protocol with linear function approximation. We show that the performance of the algorithm degrades very gracefully under a novel and more permissive notion of approximation error.
  arXiv  Detail & Related papers  (2022-06-01T23:26:51Z)
• SPINE: Soft Piecewise Interpretable Neural Equations [0.0]
  Fully connected networks are ubiquitous but uninterpretable. This paper takes a novel approach to piecewise fits by using set operations on individual pieces(parts) It can find a variety of applications where fully connected layers must be replaced by interpretable layers.
  arXiv  Detail & Related papers  (2021-11-20T16:18:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.