Skip to content

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

🕒 Published (v1): 2025-01-01 · Source: NeurIPS · Venue: NeurIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

This paper provides the first sample complexity characterization for learning Nash equilibria from expert demonstrations in Markov Games (Multi-Agent Imitation Learning, MAIL). It proves that behavioral cloning (BC) is fundamentally limited by a new quantity called the all policy deviation concentrability coefficient (Cmax), and introduces two interactive algorithms—MAIL-BRO and MURMAIL—that circumvent this limitation with polynomial sample and computational complexity.

Problem

Prior MAIL work (Tang et al. 2024) offered only error propagation analyses without characterizing how many expert samples are needed to reach an ε-Nash equilibrium; their algorithms (BLADES, MALICE) also incur computational cost exponential in |S|. More critically, no prior work formally established whether non-interactive imitation learning (e.g., BC) is fundamentally insufficient for multi-agent settings. The paper fills these gaps by: (1) giving sample complexity upper and lower bounds for BC, and (2) showing that interactive expert access is necessary when the concentrability coefficient is unbounded.

Method

Non-interactive setting (BC analysis): BC solves maximum likelihood estimation over trajectory data to recover policies (μ̂, ν̂). The analysis bounds Nash-Gap(μ̂, ν̂) using a novel all policy deviation concentrability coefficient Cmax = max over all policies μ,ν of the ∞-norm ratio between best-response-induced state occupancies and the expert occupancy. A matching impossibility result (Theorem 3.2) constructs a zero-sum MG where even with known transitions and infinite data, any non-interactive algorithm incurs Ω((1−γ)⁻¹) Nash-Gap when C(μE, νE) = ∞.

Interactive setting—MAIL-BRO (Algorithm 1): Queries a Best Response Oracle to obtain μk ∈ br(ν̂k) and νk ∈ br(μ̂k), then runs exponential weights updates using stochastic unbiased gradients computed from rollouts under (μk, νk) and (μk, νk). Avoids concentrability by directly sampling from best-response occupancy distributions.

Interactive setting—MURMAIL (Algorithm 2): Replaces the BR oracle with a maximum uncertainty response: at each outer iteration, solves a single-agent MDP (via UCBVI) where the reward is ‖μE(·|s) − μk(·|s)‖² — i.e., the opponent seeks states maximally uncertain about the current policy. Each agent solves its own induced MDP independently (decentralized), avoiding the curse of multi-agents. Outer loop then applies exponential weights updates using samples from the maximum-uncertainty rollouts.

Key Contributions

  • First sample complexity upper bound for BC in Markov Games: Nash-Gap ≤ Cmax · Õ(√(|S||Amax|/(1−γ)² · N⁻¹))
  • Formal impossibility theorem: non-interactive MAIL cannot learn an ε-NE even with known transitions when C(μE, νE) = ∞, formally separating MAIL from SAIL
  • MAIL-BRO: achieves ε-NE with Õ(|S||Amax|²/(1−γ)⁴ · ε⁻⁴) expert and oracle queries; polynomial compute
  • MURMAIL: achieves ε-NE with Õ(|S|⁴|Amax|⁵/(1−γ)¹² · ε⁻⁸) expert queries; no BR oracle; polynomial compute; fully decentralized

Results

  • BC upper bound (Theorem 3.1): Nash-Gap ≤ Cmax · Õ(√(|S||Amax|/((1−γ)² N))); requires Cmax < ∞
  • BC lower bound (Theorem 3.2): ∃ MG with C(μE, νE) = ∞ where any non-interactive algorithm achieves Nash-Gap ≥ (1−γ)⁻¹ with infinite data and known transitions
  • MAIL-BRO (Theorem 4.1): Õ(|S||Amax|²/(1−γ)⁴ · ε⁻⁴) queries for ε-NE; no concentrability requirement
  • MURMAIL (Theorem 4.2): Õ(|S|⁴|Amax|⁵/(1−γ)¹² · ε⁻⁸) expert queries for ε-NE; no BR oracle or concentrability requirement
  • Empirical: MURMAIL succeeds for all values of C(μE, νE) including ∞; BC outperforms MURMAIL when C is small (ε⁻² vs ε⁻⁸ efficiency); MURMAIL is strictly necessary at C = ∞ (BC Nash-Gap stays at maximum)
  • Both new algorithms improve over BLADES/MALICE by replacing exponential-in-|S| computation with poly(|S|, |Amax|, (1−γ)⁻¹, ε⁻¹)

Limitations

  • Analysis restricted to tabular (finite state/action) Markov Games; extension to deep RL or function approximation is left to future work
  • The gap between Cmax (upper bound) and C(μE, νE) (lower bound) is not closed; it is unknown whether a game can have bounded C(μE, νE) but unbounded Cmax
  • No statistical lower bound in ε is provided; it remains open whether BC is rate-optimal or whether ε⁻⁴/ε⁻⁸ complexities are tight
  • MURMAIL's ε⁻⁸ dependence is substantially weaker than MAIL-BRO's ε⁻⁴; improving the inner UCBVI loop may be possible only in structured game graphs (e.g., tree-structured/extensive-form)
  • Results hold in expectation (not high probability) for the interactive algorithms

Relevance to Agentic AI / LLM Agents

Multi-agent imitation learning is foundational to deploying LLM agents in interactive environments where reward specification is hard—autonomous driving, negotiation, multi-robot coordination, and AI-human collaboration all fit this template. This work establishes the first rigorous sample complexity theory for the regime, showing that naive behavioral cloning is provably insufficient when agents can deviate to out-of-distribution states, motivating interactive/online data collection paradigms similar to RLHF and DAgger. The MURMAIL algorithm's decentralized maximum-uncertainty exploration principle offers a theoretically grounded approach for multi-agent settings where centralized oracles are unavailable, which maps directly to practical multi-LLM-agent pipelines. The formal separation of MAIL from single-agent IL also underscores why single-agent alignment techniques cannot be naively transplanted to multi-agent LLM systems.