Multi-agent imitation learning (MA-IL) aims to learn optimal policies from expert demonstrations of interactions in multi-agent interactive domains. Despite existing guarantees on the performance of the resulting learned policies, characterizations of how far the learned polices are from a Nash equilibrium are missing for offline MA-IL. In this paper, we demonstrate impossibility and hardness results of learning low-exploitable policies in general n-player Markov Games. We do so by providing examples where even exact measure matching fails, and demonstrating a new hardness result on characterizing the Nash gap given a fixed measure matching error. We then show how these challenges can be overcome using strategic dominance assumptions on the expert equilibrium. Specifically, for the case of dominant strategy expert equilibria, assuming Behavioral Cloning error εBC, this provides a Nash imitation gap of O(nεBC/(1−γ)2) for a discount factor γ. We generalize this result with a new notion of best-response continuity, and argue that this is implicitly encouraged by standard regularization techniques.
Figures & tables
Figure 1: Cooperative two-player game G : the transitions and rewards are described by the left and right sub-figures, respectively. In this game, there exists a Nash equilibrium πE with full-state support and a policy π such that μπE=μπ with a Nash gap linear in the effective horizon 1/(1−γ) .
Figure 2: Transitions of a two-player Markov Game. The unique initial state is s1 . The rest of the chain ( ⋯ ) and reward functions can be designed to induce linear Nash gap for state-action matching.
Figure 3: Deterministic transition dynamics of a two-player game G , with states s0 , sexp and sub-Markov chain Mk . Player 1 has action space A1={a1r,a2r} and player 2 has action space A2={a1c,a2c} .
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: Transition dynamics for the two-player game. s0 is the initial state. The top branch contains all odd states while the bottom branch together with s0 comprises all even states.
Figure 5: Evolution of the tight Nash gap upper bound and the tight δ function with the behavior cloning error. This shows how the delta function and Nash gap tend to increase together in the simple Tag-Game environment.
Figure 6: Evolution of the tight δ for different entropy temperature parameters. This shows that a greater temperature leads to a better control on δ . This behavior is consistent on the full range of ϵBC values.
Mean Field Games (MFGs) provide a powerful framework for modeling the collective behavior of large populations of interacting agents. In this paper, we address the problem of Imitation Learning (IL) in MFGs subject to common noise, where the population distribution evolves stochastically. This stochasticity compels agents to adopt population-aware policies to respond to aggregate shocks. We formulate two distinct learning objectives: recovering a Nash equilibrium and maximizing performance against an expert population. We investigate two imitation proxies: Behavioral Cloning (BC) and Adversarial (ADV) divergence. We then establish finite-sample error bounds showing that minimizing these proxies effectively controls both the policy's exploitability and its performance gap relative to the expert. Furthermore, we propose a numerical framework using generalized Fictitious Play and Deep Learning to compute expert population-aware policies. Through experiments on three environments we demonstrate that standard population-unaware policies fail to capture the equilibrium dynamics. Our results highlight that learning population-aware policies is crucial to avoid being misled by the randomness inherent in common noise.
Grégoire Lambrecht, Mathieu Laurière
Center for Data Science, New York University and NYU Shanghai, New York, United States of America · Shanghai Center for Data Science; NYU-ECNU Institute of Mathematical Sciences at NYU Shanghai; NYU Shanghai, Shanghai, People’s Republic of China.
In this work, we present the first theoretical analysis of multi-agent imitation learning (MAIL) in linear Markov games where both the transition dynamics and each agent's reward function are linear in some given features. We demonstrate that by leveraging this structure, it is possible to replace the state-action level "all policy deviation concentrability coefficient" (Freihaut et al., arXiv:2510.09325) with a concentrability coefficient defined at the feature level which can be much smaller than the state-action analog when the features are informative about states' similarity. Furthermore, to circumvent the need for any concentrability coefficient, we turn to the interactive setting. We provide the first, computationally efficient, interactive MAIL algorithm for linear Markov games and show that its sample complexity depends only on the dimension of the feature map d. Building on these theoretical findings, we propose a deep MAIL interactive algorithm which clearly outperforms BC on games such as Tic-Tac-Toe and Connect4.
Luca Viano, Till Freihaut, Emanuele Nevali +3
1EPFL · University of Zurich · 3Earth Species Project
This work investigates multi-objective imitation learning: the problem of recovering policies that lie on the Pareto front given demonstrations from multiple Pareto-optimal experts in a Multi-Objective Markov Decision Process (MOMDP). Standard imitation approaches are ill-equipped for this regime, as naively aggregating conflicting expert trajectories can result in dominated policies. To address this, we introduce Multi-Output Augmented Behavioral Cloning (MA-BC), an algorithm that systematically partitions divergent expert data while pooling state-action pairs where no behavior conflict is observed. Theoretically, we prove that MA-BC converges to Pareto-optimal policies at a faster statistical rate than any learner that considers each expert dataset independently. Furthermore, we establish a novel lower bound for multi-objective imitation learning, demonstrating that MA-BC is minimax optimal. Finally, we empirically validate our algorithm across diverse discrete environments and, guided by our theoretical insights, extend and evaluate MA-BC on a continuous Linear Quadratic Regulator (LQR) control task.
Ziyad Sheebaelhamd, Luca Viano, Volkan Cevher +1
University of Tübingen · EPFL · University of Technology Nuremberg