mlsanityData to 14 Oct 2026

Learning Equilibria from Data: Provably Efficient Multi-Agent Imitation Learning

arXiv 2505.17610 ↗First posted 23 May 2025cs.LGcited by 4

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

Abstract (arXiv)

This paper provides the first expert sample complexity characterization for learning a Nash equilibrium from expert data in Markov Games. We show that a new quantity named the single policy deviation concentrability coefficient is unavoidable in the non-interactive imitation learning setting, and we provide an upper bound for behavioral cloning (BC) featuring such coefficient. BC exhibits substantial regret in games with high concentrability coefficient, leading us to utilize expert queries to develop and introduce two novel solution algorithms: MAIL-BRO and MURMAIL. The former employs a best response oracle and learns an varepsilon-Nash equilibrium with O(varepsilon-4) expert and oracle queries. The latter bypasses completely the best response oracle at the cost of a worse expert query complexity of order O(varepsilon-8). Finally, we provide numerical evidence, confirming our theoretical findings.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Placed in Imitation learning methods, one of 13 directions in Offline RL and imitation learning from data. Builds on 36 of its 58 references that are in the map. First posted on arXiv 23 May 2025.

Builds on

36 of 58 references.

Closest ancestors · 14

Same direction, newest first

  1. 2025IL-SOAR : Imitation Learning with Soft Optimistic Actor cRitic27 Feb
  2. 2024Is Behavior Cloning All You Need? Understanding Horizon in Imitation Learning20 Jul
  3. 2024Multi-Agent Imitation Learning: Value is Easy, Regret is Hard6 Jun
  4. 2024Imitation Learning in Discounted Linear MDPs without exploration assumptions3 May
  5. 2023Provably Efficient Adversarial Imitation Learning with Unknown Transitions11 Jun
  6. 2022On Efficient Online Imitation Learning via Classification26 Sep
  7. 2022Proximal Point Imitation Learning22 Sep
  8. 2022Minimax Optimal Online Imitation Learning via Replay Estimation30 May
  9. 2021Of Moments and Matching: A Game-Theoretic Framework for Closing the Imitation Gap4 Mar
  10. 2021Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally25 Feb
  11. 2021MobILE: Model-Based Imitation Learning From Observation Alone22 Feb
  12. 2020Toward the Fundamental Limits of Imitation Learning13 Sep
2 more
  1. 2019Provably Efficient Imitation Learning from Observation Alone27 May
  2. 2018Multi-Agent Generative Adversarial Imitation Learning26 Jul

Other references · 22

  1. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,885
  2. 2019The StarCraft Multi-Agent Challengecited by 597
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  4. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 311
  5. 2019A Theory of Regularized Markov Decision Processescited by 286
  6. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 158
  7. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 114
  8. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 113
  9. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 105
  10. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  11. 2017Coordinated Multi-Agent Imitation Learningcited by 72
  12. 2019Multi-Agent Adversarial Inverse Reinforcement Learningcited by 60
10 more
  1. 2020Near-optimal Regret Bounds for Stochastic Shortest Pathcited by 50
  2. 2022Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasetscited by 44
  3. 2021Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Gamescited by 40
  4. 2023Inverse Reinforcement Learning without Reinforcement Learningcited by 36
  5. 2022Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonuscited by 30
  6. 2013Computational Rationalization: The Inverse Equilibrium Problemcited by 24
  7. 2013Online Learning in Markov Decision Processes with Adversarially Chosen Transition Probability Distributionscited by 18
  8. 2025Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learningcited by 12
  9. 2023On Imitation in Mean-field Gamescited by 10
  10. 2024Independent Policy Mirror Descent for Markov Potential Games: Scaling to Large Number of Playerscited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 3.

4 papers.

  1. 2025Rate optimal learning of equilibria from datacited by 2
  2. 2026Multi-agent imitation learning with function approximation: Linear Markov games and beyondcited by 1
  3. 2026Matching Multiple Experts: On the Exploitability of Multi-Agent Imitation Learningcited by 0
  4. 2026Split the Differences, Pool the Rest: Provably Efficient Multi-Objective Imitationcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2022A Ranking Game for Imitation Learning
  2. 2023A Strong Baseline for Batch Imitation Learning
  3. 2021On the Sample Complexity of Stability Constrained Imitation Learning
  4. 2026Independent Learning of Nash Equilibria in Partially Observable Markov Potential Games with Decoupled Dynamics
  5. 2026Population-Aware Imitation Learning in Mean-field Games with Common Noise
  6. 2025Imitation Learning as Return Distribution Matching
  7. 2023Offline Learning in Markov Games with General Function Approximation
  8. 2026Imitation Learning for Combinatorial Optimisation under Uncertainty