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

arXiv: https://arxiv.org/abs/2505.17610 · HTML: https://mlsanity.com/paper/2505.17610/

## 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.

## Placed in

- Offline RL and imitation learning from data / [Imitation learning methods](https://mlsanity.com/offlinerl/imitation-learning-methods/)

## Builds on (most cited first, 30 of 36)

- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [The StarCraft Multi-Agent Challenge](https://mlsanity.com/paper/1902.04043/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving](https://mlsanity.com/paper/1610.03295/) (2016)
- [A Theory of Regularized Markov Decision Processes](https://mlsanity.com/paper/1901.11275/) (2019)
- [Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning](https://mlsanity.com/paper/2106.04895/) (2021)
- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [Provable Self-Play Algorithms for Competitive Reinforcement Learning](https://mlsanity.com/paper/2002.04017/) (2020)
- [A Sharp Analysis of Model-based Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2010.01604/) (2020)
- [Multi-Agent Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1807.09936/) (2018)
- [Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium](https://mlsanity.com/paper/2002.07066/) (2020)
- [Toward the Fundamental Limits of Imitation Learning](https://mlsanity.com/paper/2009.05990/) (2020)
- [Of Moments and Matching: A Game-Theoretic Framework for Closing the Imitation Gap](https://mlsanity.com/paper/2103.03236/) (2021)
- [Provably Efficient Imitation Learning from Observation Alone](https://mlsanity.com/paper/1905.10948/) (2019)
- [Is Behavior Cloning All You Need? Understanding Horizon in Imitation Learning](https://mlsanity.com/paper/2407.15007/) (2024)
- [Coordinated Multi-Agent Imitation Learning](https://mlsanity.com/paper/1703.03121/) (2017)
- [Multi-Agent Adversarial Inverse Reinforcement Learning](https://mlsanity.com/paper/1907.13220/) (2019)
- [Near-optimal Regret Bounds for Stochastic Shortest Path](https://mlsanity.com/paper/2002.09869/) (2020)
- [MobILE: Model-Based Imitation Learning From Observation Alone](https://mlsanity.com/paper/2102.10769/) (2021)
- [Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasets](https://mlsanity.com/paper/2202.07511/) (2022)
- [Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games](https://mlsanity.com/paper/2102.11494/) (2021)
- [Inverse Reinforcement Learning without Reinforcement Learning](https://mlsanity.com/paper/2303.14623/) (2023)
- [Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonus](https://mlsanity.com/paper/2206.00159/) (2022)
- [Proximal Point Imitation Learning](https://mlsanity.com/paper/2209.10968/) (2022)
- [Minimax Optimal Online Imitation Learning via Replay Estimation](https://mlsanity.com/paper/2205.15397/) (2022)
- [Computational Rationalization: The Inverse Equilibrium Problem](https://mlsanity.com/paper/1308.3506/) (2013)
- [Online Learning in Markov Decision Processes with Adversarially Chosen Transition Probability Distributions](https://mlsanity.com/paper/1303.3055/) (2013)
- [Provably Efficient Adversarial Imitation Learning with Unknown Transitions](https://mlsanity.com/paper/2306.06563/) (2023)
- [Imitation Learning in Discounted Linear MDPs without exploration assumptions](https://mlsanity.com/paper/2405.02181/) (2024)
- [Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally](https://mlsanity.com/paper/2102.12948/) (2021)

## Built on by (most cited first, 4 of 4)

- [Rate optimal learning of equilibria from data](https://mlsanity.com/paper/2510.09325/) (2025)
- [Multi-agent imitation learning with function approximation: Linear Markov games and beyond](https://mlsanity.com/paper/2602.22810/) (2026)
- [Matching Multiple Experts: On the Exploitability of Multi-Agent Imitation Learning](https://mlsanity.com/paper/2602.21020/) (2026)
- [Split the Differences, Pool the Rest: Provably Efficient Multi-Objective Imitation](https://mlsanity.com/paper/2605.12000/) (2026)

## 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.