mlsanityData to 14 Oct 2026

Rate optimal learning of equilibria from data

arXiv 2510.09325 ↗First posted 10 Oct 2025cs.LG cs.AIcited by 2

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

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.

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.

Builds on

25 of 34 references.

Closest ancestors · 10

Same direction, newest first

  1. 2025A Smooth Sea Never Made a Skilled SAILOR: Robust Imitation via Learning to Search5 Jun
  2. 2025MisoDICE: Multi-Agent Imitation from Unlabeled Mixed-Quality Demonstrations24 May
  3. 2025Learning Equilibria from Data: Provably Efficient Multi-Agent Imitation Learning23 May
  4. 2024Is Behavior Cloning All You Need? Understanding Horizon in Imitation Learning20 Jul
  5. 2024Multi-Agent Imitation Learning: Value is Easy, Regret is Hard6 Jun
  6. 2024Imitation Learning in Discounted Linear MDPs without exploration assumptions3 May
  7. 2023Mimicking To Dominate: Imitation Learning Strategies for Success in Multiagent Competitive Games20 Aug
  8. 2020Toward the Fundamental Limits of Imitation Learning13 Sep
  9. 2019Recent Advances in Imitation Learning from Observation30 May
  10. 2018Multi-Agent Generative Adversarial Imitation Learning26 Jul

Other references · 15

  1. 2021Convex optimizationcited by 2,515
  2. 2016Generative Adversarial Imitation Learningcited by 1,597
  3. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  4. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  5. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 158
  6. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  7. 2020Adaptive Reward-Free Explorationcited by 77
  8. 2017Coordinated Multi-Agent Imitation Learningcited by 72
  9. 2019Multi-Agent Adversarial Inverse Reinforcement Learningcited by 60
  10. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  11. 2016Settling the complexity of computing approximate two-player Nash equilibriacited by 31
  12. 2022Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonuscited by 30
3 more
  1. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 15
  2. 2023On Imitation in Mean-field Gamescited by 10
  3. 2023Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPscited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Multi-agent imitation learning with function approximation: Linear Markov games and beyondcited by 1
  2. 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. 2024Interactive and Hybrid Imitation Learning: Provably Beating Behavior Cloning
  3. 2021Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally
  4. 2021SS-MAIL: Self-Supervised Multi-Agent Imitation Learning
  5. 2021On the Sample Complexity of Stability Constrained Imitation Learning
  6. 2022On Efficient Online Imitation Learning via Classification
  7. 2026Learning When to Stop: Selective Imitation Learning Under Arbitrary Dynamics Shift
  8. 2020Explaining Fast Improvement in Online Imitation Learning