Research map / Multi-agent systems and games / Games and equilibria
Learning Equilibria from Data: Provably Efficient Multi-Agent Imitation Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies sample complexity of multi-agent imitation learning for Nash equilibria in two-player zero-sum Markov games, showing behavioral cloning needs a concentrability coefficient and proposing interactive algorithms MAIL-BRO and MURMAIL with polynomial expert query complexity.
Problem
Learning a Nash equilibrium from expert demonstrations in two-player zero-sum Markov games, where non-interactive behavioral cloning can suffer large Nash gap due to out-of-distribution deviations.
Approach
Derives a sample complexity bound for multi-agent behavioral cloning featuring an all-policy deviation concentrability coefficient, proves a hardness result for non-interactive learning, and introduces interactive algorithms (one using a best response oracle, one using a maximum uncertainty response computed via an inner RL loop) that achieve epsilon-NE with polynomial expert queries.
Key results
- MAIL-BRO achieves an epsilon-Nash equilibrium with O(epsilon^-4) expert and oracle queries under a best response oracle.
- MURMAIL achieves epsilon-NE with a total of roughly O(epsilon^-8) expert queries without a best response oracle and without concentrability dependence.
- Numerical experiments show multi-agent BC fails when the concentrability coefficient is infinite while MURMAIL still minimizes the Nash gap.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use interactive expert queries and a best response oracle instead of non-interactive BC | Multi-agent imitation learning · Two-player zero-sum Markov Games | Nash-Gap: BC exhibits substantial regret in games with high concentrability coefficient; MAIL-BRO learns an \varepsilon-Nash equil | Helped |
| Use interactive expert queries without a best response oracle | Multi-agent imitation learning · Two-player zero-sum Markov Games | Nash-Gap: MURMAIL learns an \varepsilon-Nash equilibrium | Helped |
| Use interactive MURMAIL instead of BC when the concentrability coefficient is infinite | Multi-agent imitation learning · Constructed Markov Game with \mathcal{C}(\mu^{\operatorname{E}},\nu^{\operatorname{E}}) = \infty | Nash gap | Helped |
| Use MURMAIL rather than BC when concentrability is bounded | Multi-agent imitation learning · Markov Games with bounded concentrability | Expert-query efficiency: \varepsilon^{-2} compared to \varepsilon^{-8} | Mixed |
Surprising findings
- Non-interactive behavioral cloning cannot recover a Nash equilibrium even with known transitions and infinite data when the expert deviation concentrability is unbounded, with Nash gap of order (1-gamma)^-1.
Limitations
- MURMAIL's expert query complexity of O(eps^-8) is much worse than BC's eps^-2 when concentrability is bounded.
- Analysis restricted to tabular Markov games; deep imitation learning extension is conceptual only.
- Open question whether a bounded expert-deviation coefficient with unbounded all-policy coefficient yields hardness; no matching lower bound.
Experimental setup
Datasets: expert trajectories from Nash equilibrium policy pair in tabular Markov games
Benchmarks: custom tabular zero-sum Markov game (lower-bound construction)
Metrics: exploitability Nash gap
Baselines: Multi-Agent BC MALICE BLADES
Builds on: behavioral cloning UCBVI offline zero-sum Markov games lower bounds BLADES MALICE
Closest papers by meaning
- Multi-Agent Imitation Learning: Value is Easy, Regret is Hard (NeurIPS 2024 · similarity 0.89)
- Agnostic Interactive Imitation Learning: New Theory and Practical Algorithms (ICML 2024 · similarity 0.89)
- Independent Learning of Nash Equilibria in Partially Observable Markov Potential Games with Decoupled Dynamics (NeurIPS 2026 · similarity 0.88)
- Is Behavior Cloning All You Need? Understanding Horizon in Imitation Learning (NeurIPS 2024 · similarity 0.88)
- Causal Imitation for Markov Decision Processes: a Partial Identification Approach (NeurIPS 2024 · similarity 0.88)
- Mimicking To Dominate: Imitation Learning Strategies for Success in Multiagent Games (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.