# Rate optimal learning of equilibria from data

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

## Key facts

- Cited by 2 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 25 of its 34 references that are in the map.
- First posted on arXiv 10 Oct 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, 25 of 25)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1606.03476/) (2016)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning](https://mlsanity.com/paper/2106.04895/) (2021)
- [Multi-Agent Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1807.09936/) (2018)
- [Toward the Fundamental Limits of Imitation Learning](https://mlsanity.com/paper/2009.05990/) (2020)
- [Recent Advances in Imitation Learning from Observation](https://mlsanity.com/paper/1905.13566/) (2019)
- [Fast active learning for pure exploration in reinforcement learning](https://mlsanity.com/paper/2007.13442/) (2020)
- [Adaptive Reward-Free Exploration](https://mlsanity.com/paper/2006.06294/) (2020)
- [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)
- [Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes](https://mlsanity.com/paper/2201.11206/) (2022)
- [Settling the complexity of computing approximate two-player Nash equilibria](https://mlsanity.com/paper/1606.04550/) (2016)
- [Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonus](https://mlsanity.com/paper/2206.00159/) (2022)
- [A Smooth Sea Never Made a Skilled SAILOR: Robust Imitation via Learning to Search](https://mlsanity.com/paper/2506.05294/) (2025)
- [Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learning](https://mlsanity.com/paper/2304.07278/) (2023)
- [Imitation Learning in Discounted Linear MDPs without exploration assumptions](https://mlsanity.com/paper/2405.02181/) (2024)
- [Multi-Agent Imitation Learning: Value is Easy, Regret is Hard](https://mlsanity.com/paper/2406.04219/) (2024)
- [On Imitation in Mean-field Games](https://mlsanity.com/paper/2306.14799/) (2023)
- [Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs](https://mlsanity.com/paper/2303.10165/) (2023)
- [Learning Equilibria from Data: Provably Efficient Multi-Agent Imitation Learning](https://mlsanity.com/paper/2505.17610/) (2025)
- [MisoDICE: Multi-Agent Imitation from Unlabeled Mixed-Quality Demonstrations](https://mlsanity.com/paper/2505.18595/) (2025)
- [Mimicking To Dominate: Imitation Learning Strategies for Success in Multiagent Competitive Games](https://mlsanity.com/paper/2308.10188/) (2023)

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

- [Multi-agent imitation learning with function approximation: Linear Markov games and beyond](https://mlsanity.com/paper/2602.22810/) (2026)
- [Split the Differences, Pool the Rest: Provably Efficient Multi-Objective Imitation](https://mlsanity.com/paper/2605.12000/) (2026)

## Abstract (arXiv)

We close open 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. In the non-interactive setting, we prove a statistical lower bound that identifies the all-policy deviation concentrability coefficient as the fundamental complexity measure, and we show that Behavior Cloning (BC) is rate-optimal. 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. It improves the best previously known sample complexity from O(varepsilon-8) to O(varepsilon-2), matching the dependence on varepsilon implied by our lower bound. Finally, we provide numerical results that support our theory and illustrate, in environments such as grid worlds, where Behavior Cloning fails to learn.