Research map / Multi-agent systems and games / Games and equilibria
Multi-Agent Imitation Learning: Value is Easy, Regret is Hard
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 multi-agent imitation learning in Markov games with a regret-gap objective, showing value equivalence does not imply regret equivalence, and proposes MALICE (coverage-based) and BLADES (queryable-expert) reductions to no-regret online convex optimization achieving O(H) regret-gap bounds.
Problem
Multi-agent imitation learning for coordinating strategic agents via mediator recommendations: standard value-gap objectives ignore agents' incentives to deviate, so learned policies may not be robust to deviations.
Approach
Introduces the regret gap (difference in maximal deviation incentive between learner and expert mediator) as the MAIL objective, proves value equivalence can yield an Omega(H) regret gap, and gives two multi-agent DAgger/ALICE-style reductions (MALICE, BLADES) that minimize the regret gap via no-regret online convex optimization.
Key results
- Value equivalence can yield a regret gap of Omega(H) in a constructed Markov game, showing value equivalence does not imply regret equivalence.
- MALICE achieves a regret gap upper bound of O(epsilon u H) under beta-coverage, matched by a lower bound Omega(epsilon u H).
- BLADES achieves a regret gap upper bound of O(epsilon u H) with access to a queryable expert, matched by a lower bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use J-BC or J-IRL under β-coverage instead of MALICE | MALICE regret-gap minimization · Markov Games, β-coverage | regret gap upper bound: O(\epsilon u H) -> O\left(\frac{1}{\beta}\epsilon u H\right) | Hurt |
| Use MALICE's importance-weighted loss over deviations | J-BC under β-coverage · Markov Games, β-coverage | regret gap upper bound: O\left(\frac{1}{\beta}\epsilon u H\right) -> O(\epsilon uH) | Helped |
| Use BLADES with expert queries on states reached under deviations | MAIL regret-gap minimization · Markov Games, queryable expert | regret gap upper bound: O(\epsilon uH) | Helped |
| Optimize value gap by extending behavioral cloning to joint policies | J-BC · Markov Games | value gap upper bound: O(\epsilon H^2) | Mixed |
| Optimize value gap with joint inverse reinforcement learning | J-IRL · Markov Games | value gap upper bound: O(\epsilon H) | Helped |
| Match the expert's occupancy measure without matching recommendations at states reached after deviations | MAIL learner · Markov Games | regret gap: \Omega(H) | Hurt |
| Satisfy regret equivalence with complete reward and deviation classes | MAIL learner · Markov Games | value gap: 0 | Helped |
| Use interactive J-IRL without counterfactual expert recommendations | J-IRL · Markov Games, β-coverage | regret gap upper bound: O\left(\frac{1}{\beta}\epsilon uH\right) | Hurt |
Surprising findings
- Value equivalence provides essentially no guarantee on the regret gap in Markov games, even though it suffices for single-agent IL.
- J-IRL's regret gap bound is O(H/beta) like J-BC, unlike the linear-in-H value gap in single-agent IRL; interactive training alone does not suffice for regret gap minimization.
Limitations
- Algorithms are idealized theoretical reductions; practical approximations are left to future work.
- MALICE and J-BC/J-IRL bounds depend on beta-coverage, whose constant can grow exponentially with horizon.
- No empirical experiments are reported.
Experimental setup
Metrics: regret gap value gap
Baselines: J-BC J-IRL
Builds on: ALICE DAgger behavioral cloning inverse reinforcement learning
Closest papers by meaning
- Learning Equilibria from Data: Provably Efficient Multi-Agent Imitation Learning (NeurIPS 2025 · similarity 0.89)
- Mimicking To Dominate: Imitation Learning Strategies for Success in Multiagent Games (NeurIPS 2024 · similarity 0.87)
- Learning to Recommend in Unknown Games (NeurIPS 2026 · similarity 0.87)
- Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithms (NeurIPS 2024 · similarity 0.87)
- Causal Imitation for Markov Decision Processes: a Partial Identification Approach (NeurIPS 2024 · similarity 0.87)
- Impact of Decentralized Learning on Player Utilities in Stackelberg Games (ICML 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.