mlsanityData to 7 Oct 2026

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

arXiv 2602.22810 ↗First posted 26 Feb 2026cs.LGcited by 1

On the map: Offline RL and imitation learning from data → Imitation learning methods

Abstract (arXiv)

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.

Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Placed in Imitation learning methods, one of 13 directions in Offline RL and imitation learning from data. Builds on 41 of its 53 references that are in the map. First posted on arXiv 26 Feb 2026.

Builds on

41 of 53 references.

Closest ancestors · 15

Same direction, newest first

  1. 2025Rate optimal learning of equilibria from data10 Oct
  2. 2025Inverse Q-Learning Done Right: Offline Imitation Learning in Qπ-Realizable MDPs26 May
  3. 2025MisoDICE: Multi-Agent Imitation from Unlabeled Mixed-Quality Demonstrations24 May
  4. 2025Learning Equilibria from Data: Provably Efficient Multi-Agent Imitation Learning23 May
  5. 2025IL-SOAR : Imitation Learning with Soft Optimistic Actor cRitic27 Feb
  6. 2024Is Behavior Cloning All You Need? Understanding Horizon in Imitation Learning20 Jul
  7. 2024Multi-Agent Imitation Learning: Value is Easy, Regret is Hard6 Jun
  8. 2024Imitation Learning in Discounted Linear MDPs without exploration assumptions3 May
  9. 2022On Efficient Online Imitation Learning via Classification26 Sep
  10. 2022Proximal Point Imitation Learning22 Sep
  11. 2021IQ-Learn: Inverse soft-Q Learning for Imitation23 Jun
  12. 2021Of Moments and Matching: A Game-Theoretic Framework for Closing the Imitation Gap4 Mar
3 more
  1. 2021MobILE: Model-Based Imitation Learning From Observation Alone22 Feb
  2. 2019Provably Efficient Imitation Learning from Observation Alone27 May
  3. 2018Multi-Agent Generative Adversarial Imitation Learning26 Jul

Other references · 26

  1. 2017Squeeze-and-Excitation Networkscited by 4,763
  2. 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
  3. 2016Generative Adversarial Imitation Learningcited by 1,576
  4. 2017Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithmcited by 723
  5. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  6. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  7. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  8. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  9. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  10. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  11. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
  12. 2020Adaptive Reward-Free Explorationcited by 77
14 more
  1. 2019Learning Linear-Quadratic Regulators Efficiently with only √T Regretcited by 67
  2. 2019Multi-Agent Adversarial Inverse Reinforcement Learningcited by 60
  3. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
  4. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  5. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
  6. 2022Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasetscited by 42
  7. 2020Task-agnostic Exploration in Reinforcement Learningcited by 37
  8. 2023Inverse Reinforcement Learning without Reinforcement Learningcited by 35
  9. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 29
  10. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 26
  11. 2025Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecificationcited by 12
  12. 2025Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learningcited by 12
  13. 2023On Imitation in Mean-field Gamescited by 10
  14. 2022Generalised agent for solving higher board states of tic tac toe using Reinforcement Learningcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Split the Differences, Pool the Rest: Provably Efficient Multi-Objective Imitationcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Matching Multiple Experts: On the Exploitability of Multi-Agent Imitation Learning
  2. 2023Inverse Factorized Q-Learning for Cooperative Multi-agent Imitation Learning
  3. 2023Mimicking To Dominate: Imitation Learning Strategies for Success in Multiagent Competitive Games
  4. 2025Structured Imitation Learning of Interactive Policies through Inverse Games
  5. 2021SS-MAIL: Self-Supervised Multi-Agent Imitation Learning
  6. 2026Coordinated Diffusion: Generating Multi-Agent Behavior Without Multi-Agent Demonstrations
  7. 2022A Ranking Game for Imitation Learning
  8. 2022Conditional Imitation Learning for Multi-Agent Games