Paper deep dive
Matching Multiple Experts: On the Exploitability of Multi-Agent Imitation Learning
Antoine Bergerault, Volkan Cevher, Negar Mehr
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 7/20/2026, 1:31:55 PM
Summary
This paper investigates the theoretical limitations of Multi-Agent Imitation Learning (MA-IL) in Markov Games, specifically focusing on the exploitability of learned policies relative to Nash equilibria. It demonstrates that in general n-player Markov Games, learning low-exploitable policies is impossible or hard, even with exact measure matching, due to issues with state support and the distinction between state-only and state-action occupancy measures. The authors prove that state-only matching is insufficient to guarantee a Nash equilibrium, while state-action matching under full-state support is sufficient. They further introduce a notion of best-response continuity and show that assuming dominant strategy expert equilibria allows for tractable bounds on the Nash imitation gap, specifically O(n*epsilon_BC / (1-gamma)^2).
Entities (8)
Relation Signals (5)
Multi-Agent Imitation Learning → appliedto → Markov Games
confidence 95% · MA-IL aims to learn optimal policies from expert demonstrations of interactions in multi-agent interactive domains... general n-player Markov Games.
State-Only Matching → failstoguarantee → Nash Equilibrium
confidence 92% · We show that only assuming state-only matching... can only guarantee the trivial bound... Nash gap linear in the effective horizon.
State-Action Matching → sufficientfor → Nash Equilibrium
confidence 90% · State-action matching under full-state support is therefore a sufficient condition for learning the expert Nash equilibrium.
Behavioral Cloning Error → bounds → Nash Gap
confidence 88% · Assuming Behavioral Cloning error epsilon_BC, this provides a Nash imitation gap of O(n*epsilon_BC/(1-gamma)^2).
Dominant Strategy → enables → Tractable Nash Gap Bounds
confidence 85% · We then show how these challenges can be overcome using strategic dominance assumptions... specifically for the case of dominant strategy expert equilibria.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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 $\epsilon_{\text{BC}}$, this provides a Nash imitation gap of $\mathcal{O}\left(n\epsilon_{\text{BC}}/(1-\gamma)^2\right)$ for a discount factor $\gamma$. We generalize this result with a new notion of best-response continuity, and argue that this is implicitly encouraged by standard regularization techniques.
Tags
Links
- Source: https://arxiv.org/abs/2602.21020v1
- Canonical: https://arxiv.org/abs/2602.21020v1
Trouble viewing inline? Open PDF directly →
Full Text
96,576 characters extracted from source content.
Expand or collapse full text
Matching Multiple Experts: On the Exploitability of Multi-Agent Imitation Learning Antoine Bergerault EPFL, UC Berkeley &Volkan Cevher EPFL &Negar Mehr UC Berkeley The work was done when the first author was an EPFL master’s student visiting UC Berkeley. Now at the University of Zurich. Correspondence to antoine.bergerault@uzh.ch. Abstract 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 _BC, this provides a Nash imitation gap of (nϵBC/(1−γ)2)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. 1 Introduction Learning from expert demonstrations via imitation learning (IL) has recently seen growing adoption in the Machine Learning and Robotics communities (Finn et al., 2016b; Shih et al., 2022; Pearce et al., 2023; Yang et al., 2023). Given a demonstration dataset, IL is traditionally done by either regressing a policy (Behavioral Cloning (Pomerleau, 1991)), fitting a plausible reward function and extracting a policy via Reinforcement Learning (Inverse Reinforcement Learning (Ng et al., 2000; Abbeel & Ng, 2004)), or implicitly matching expert occupancy measures (Finn et al., 2016a; Ho & Ermon, 2016). Crucially, imitation learning bypasses the need of designing a reward function, a common limitation for Reinforcement Learning in practice, that often requires domain expertise or extensive iterative refinements. Instead, it directly leverages demonstrations from optimal agents. This advantage becomes even more compelling when learning tasks requiring collaboration or competition between multiple agents, where reward assignment constitutes an extra ambiguity (Sunehag et al., 2017; Nagpal et al., 2025; Choi et al., 2025). While many works successfully tackle single agent IL (SA-IL, Ho & Ermon (2016); Ng et al. (2000); Ross & Bagnell (2010)), their extensions to multi-agent settings (Song et al., 2018; Zhan et al., 2018; Mehr et al., 2023) inherit fundamental limitations. In particular, they produce imitation policies that can be exploited by unilaterally deviating strategic agents (Tang et al., 2024; Freihaut et al., 2025). In this work, we study the question of learning a Nash equilibrium using demonstrations from an expert Nash equilibrium, given fixed imitation errors commonly measured in practice. More precisely, assuming a known behavioral cloning or measure matching error, we measure the exploitability of the learned policy as its distance to a Nash equilibrium. We characterize situations where we can derive both consistent and tractable bounds on the Nash gap (see Section 3 for a formal definition), where • A consistent bound vanishes with the imitation error; making the imitation error an intuitive proxy of the exploitability by guaranteeing a pure Nash equilibrium from no imitation error. • A tractable bound is efficient to compute based on the game assumptions. It can be computed in polynomial time to measure exploitability during IL training. Intuitively, a consistent bound ensures that a Nash equilibrium is learned from an imitation error of zero. Consistency can be implicitly assumed by SA-IL extensions to multi-agent domains, but we show that this is a strong assumption that does not hold in general games. Specifically, we prove how not assuming full-state support of the expert or only matching its state distribution can lead to bound inconsistencies. Then, we present continuity conditions under which both consistent and tractable upper bounds on the Nash gap can be computed. In summary, we make the following contributions: • In Section 4, we show the impossibility of deriving consistent Nash gap bounds in general Markov Games. We provide concrete examples where even exactly matching expert occupancy measures can result in highly exploitable policies. • We further demonstrate in Section 5 the impossibility of deriving tight tractable exploitability lower bounds in general games, even if we know both the rewards and transition dynamics. • Finally, Section 6 presents a new notion of best-response continuity not observed in SA-IL and shows how assumptions on this continuity property can be used to construct tractable upper bounds. As a special case, we prove that a “good” approximate Nash equilibrium can be learned from Behavioral Cloning with a dominant strategy expert. To keep the arguments straightforward, we present our results for infinite-horizon games in the main document. These results also extend to finite-horizon games, as demonstrated in Appendix F. 2 Previous work Single-agent Imitation Learning. Given a dataset of demonstrations produced by an expert, SA-IL aims to extract a near-optimal policy from the data. The expert is considered optimal in maximizing a reward function over time, as in the reinforcement learning framework. Without requiring access to the environment or expert oracles, imitation learning is done through Behavioral Cloning (BC, Pomerleau (1991)), Inverse Reinforcement Learning (IRL, Ng et al. (2000); Abbeel & Ng (2004)) or Adversarial Imitation Learning (Ho & Ermon, 2016). These methods essentially fit one of: the expert policy function, the reward function, or the expert occupancy measures (Finn et al., 2016a; Ho & Ermon, 2016). In the single-agent setting, performance of such approaches are well-understood, measured by the sub-optimality gap of the learned policy with respect to the expert (Ross et al., 2011; Foster et al., 2024). Multi-agent Imitation Learning. A growing body of work focuses on imitation learning in multi-agent domains (Song et al., 2018; Lin et al., 2018; Wang et al., 2021; Shih et al., 2022; Mehr et al., 2023), with applications such as autonomous driving (Bhattacharyya et al., 2018) or robotic interactions (Bogert & Doshi, 2018; Chandra et al., 2025). MA-IRL inherits the ambiguity of reward design from the reinforcement learning framework (Sunehag et al., 2017; Freihaut & Ramponi, 2025; Ward et al., 2025). More simple methods (BC, Adversarial IL) are therefore tempting and have been extended from their single-agent counterpart (Song et al., 2018; Zhan et al., 2018). However, they do not carry guarantees on the extracted policy in terms of robustness to the presence of strategic interactions. Theoretical Barriers for MA-IL. Indeed, previous work showed that BC and GAIL policies are exploitable in general games (Cui & Du, 2022; Freihaut et al., 2025; Tang et al., 2024). Among those works, Freihaut et al. (2025) introduces the first regret upper bound for multi-agent behavioral cloning, bounding the sub-optimality of the imitation policy from any unilateral deviations. They rely on a new concentrability coefficient related to broader concentrability assumptions (Cui & Du, 2022; Yin et al., 2021; Cai et al., 2023). This coefficient is intractable in general games and can become unbounded, making their bound both inconsistent and hard to use in practice. There remains a gap in the literature in identifying the phenomena behind impossibility results from prior work, and conditions to make offline MA-IL well-behaved are still unclear. We reduce this gap by characterizing such issues and deriving conditions for consistent and tractable Nash gap bounds. 3 Preliminaries 3.1 Markov Games We use the tuple G=(,,P,rii=1n,ν0,γ)G=(S,A,P,\r_i\_i=1^n, _0,γ) to define an n-player Markov Game. Players in [n]≔1,…,n[n] \1,…,n\ take joint actions in =1×⋯×nA=A_1×…×A_n while navigating a shared state space S. The dynamics of the system are described by the transition function P:×→ΔP:S×A→ _S and the initial state distribution ν0∈Δ _0∈ _S, where ΔU _U denotes the probability simplex over a space U. All players simultaneously take actions by sampling from their individual policy πi:→Δi _i:S→ _A_i. The resulting joint policy is π≔π1×⋯×πnπ _1×…× _n, also denoted by πi×π−i _i× _-i where π−i _-i represents the joint policy of all players but i. Lastly, we define the reward function of player i∈[n]i∈[n] as ri:×→[−1,1]r_i:S×A→[-1,1], and define a discount factor γ∈[0,1)γ∈[0,1). We will use Π=Π1×⋯×Πn = _1×…× _n to denote the set of joint policies π, with πi∈Πi _i∈ _i for each i∈[n]i∈[n]. A trajectory (st,at)t≥0\(s_t,a_t)\_t≥ 0 of the policy π starts in an initial state s0∼ν0s_0 _0 and successively samples joint actions at∼π(⋅|st)a_t π(·|s_t) and future states st+1∼P(⋅|st,at)s_t+1 P(·|s_t,a_t) for every t≥0t≥ 0. This procedure induces the following state-only and state-action occupancy measures for every state s∈s , respectively: μπ(s)≔(1−γ)∑t=0∞γtℙ(st=s),ρπ(s,a)≔μπ(s)π(a|s), _π(s) (1-γ) _t=0^∞γ^tP(s_t=s), 50.00008pt _π(s,a) _π(s)π(a|s), where ℙ(st=s)P(s_t=s) is the probability of reaching state s after rolling out the policy π for t steps. Intuitively, μπ(s) _π(s) is the discounted visitation frequency of state s after infinitely many steps. Similarly, ρπ(s,a) _π(s,a) is the discounted frequency of the state-action pair (s,a)(s,a). This allows us to define for every state s∈s , the state-value functions as the expected discounted cumulative rewards of the players: Viπ(s)=11−γ⋅(s,a)∼ρπ[ri(s,a)]∀i∈[n],V_i^π(s)= 11-γ·E_(s,a) _π[r_i(s,a)] ∀ i∈[n], where (s,a)∼ρπ[⋅]E_(s,a) _π[·] samples state-action pairs from the density function ρπ _π. By extension, we also define Viπ(ν)=s∼ν[Viπ(s)]V_i^π(ν)=E_s ν[V_i^π(s)] for any state distribution ν∈Δν∈ _S. Markov Games extend Markov Decision Processes (MDPs, when n=1n=1 (Puterman, 2014)) to multi-agent games, where each agent has its own reward function. While in MDPs we consider a policy to be optimal if it maximizes Vπ(ν0)V^π( _0)111Or V1π(ν0)V^π_1( _0) using the notation above, the distinct individual rewards of a Markov Game necessitate the introduction of the solution concept of a game-theoretic equilibrium to model the outcome of interactions. 3.2 Measuring optimality in games Fixing other players’ policies as π−i _-i, the performance of a player i in terms of average (discounted) rewards is measured with Viπ(ν0)V_i^π( _0). Therefore, we can denote the set of optimal policies for player i as the optimal policies in the MDP induced by π−i _-i using the concept of best-response mapping. Definition 1 (Best-response mapping). For an agent i∈[n]i∈[n], the best-response mapping to π−i _-i is defined as BRi(π−i)≔argmaxπi′Viπi′,π−i(ν0).BR_i( _-i) _ _i V^π _i, _-i_i( _0). Intuitively, when playing a best-response πi∗∈BRi(π−i)π^*_i _i( _-i), player i cannot improve by unilaterally deviating from πi∗π^*_i. From this definition, we define a Nash equilibrium as a combination of independent policies where no player would be better off by unilaterally deviating from their equilibrium policies. Definition 2 (Nash equilibrium). A policy π is a Nash equilibrium of the game if π is a product policy and each individual policy is a best-response to the other policies, i.e. πi∈BRi(π−i)∀i∈[n]. _i _i( _-i) ∀ i∈[n]. As is common in multi-agent games, we use Nash equilibria as solution concepts to model interaction outcomes throughout this paper. Specifically, our goal is to learn (approximate) Nash equilibria222An (approximate) ϵε-Nash equilibrium πEπ^E is a product policy where Viπi,π−iE(ν0)−ViπE(ν0)≤ϵV _i,π^E_-i_i( _0)-V^π^E_i( _0)≤ε for all i∈[n],πi∈Πi∈[n], _i∈ _i. from a dataset of trajectories sampled from a Nash equilibrium policy πEπ^E termed the expert policy. 3.3 Offline Imitation learning Given a dataset of finite-length trajectories333While we consider stationary policies maximizing cumulated rewards over an infinite horizon, IL usually assumes a set of N trajectories τkk=1N\ _k\_k=1^N of length |τk|∼Geometric(1−γ)| _k| (1-γ). produced by rolling-out πEπ^E in a given Markov Game G, an imitation learning procedure aims to recover a “good” joint policy π without access to the environment. Following the above discussion, we measure the performance of π with the following metric. Definition 3 (Value gap). Given an expert policy πEπ^E of G, the Value gap of a policy π is: ValueGap(π)≔maxi(ViπE(ν0)−Viπ(ν0)).ValueGap(π) _i (V^π^E_i( _0)-V^π_i( _0) ). This is essentially the maximum sub-optimality gap among the agents for playing π instead of the optimal expert πEπ^E. This value gap is the standard optimality metric used in single-agent MDP settings (Ross et al., 2011; Foster et al., 2024). In the multi-agent case, however, the performance of individual players is usually not a sufficient guarantee as we use the imitation policy in an environment with strategic agents. Hence, we need to measure the impact of individual policies deviating from the learned joint behavior π. We will therefore evaluate the exploitability of π, as a measure of its gap to a Nash equilibrium. Definition 4 (Nash gap, see Ramponi et al. (2023)). We define the Nash (imitation) gap of a product policy π of the game G as NashGap(π)≔maxi(Viπi∗,π−i(ν0)−Viπ(ν0))NashGap(π) _i (V^π^*_i, _-i_i( _0)-V^π_i( _0) ) (1) with any πi∗∈BRi(π−i)π^*_i _i( _-i). The Nash gap is a notion of maximal regret (Tang et al., 2024) for the individual players. It directly links to Nash equilibria as an ϵε-Nash equilibrium is any product policy πϵ∈Π _ε∈ satisfying NashGap(πϵ)≤ϵNashGap( _ε)≤ε. Note that to ensure the imitation policy π is a product policy, it suffices to learn all individual policies πi _i independently, for example through behavioral cloning. In the general case, both ValueGap(π)ValueGap(π) and NashGap(π)NashGap(π) are upper bounded by 21−γ 21-γ as differences of cumulative normalized rewards. The goal of an imitation learning procedure is to leverage the expert data in order to minimize these gaps. Regressing on the training data, BC and Adversarial IL bring one of the following error assumptions: a BC Error from matching the empirical distribution of the individual agents, or a Measure Matching Error measuring a discrepancy in occupancy measures (state-only or state-action). They are respectively defined as: ϵBC≔maxis∼μπE[∥πi(⋅|s)−πiE(⋅|s)∥1], _BC _iE_s _π^E [ _i(·|s)-π^E_i(·|s) _1 ], (2) ϵμ≔∥μπ−μπE∥1,andϵρ≔∥ρπ−ρπE∥1, _μ _π- _π^E _1, _ρ _π- _π^E _1, where s∼μπE[⋅]E_s _π^E[·] is the expectation with respect to the state-occupancy induced by πEπ^E. While general consistent and tractable upper bounds are known on the Value gap assuming either ϵBC _BC or ϵρ _ρ444ValueGap(π)≤nϵBC/(1−γ)2ValueGap(π)≤ n _BC/(1-γ)^2 from the Performance Difference Lemma (see e.g. Xiao (2022)) and ValueGap(π)≤ϵρ/(1−γ)ValueGap(π)≤ _ρ/(1-γ) by Hölder’s inequality., deriving similar bounds for the Nash gap remains an open problem. Under the assumption of a fixed imitation error, we therefore lack an understanding of the distance of π to a Nash equilibrium. More information about the connection between adversarial imitation learning and occupancy measure matching can be found in Appendix A. 4 Impossibility results for exact measure matching As a first step to understand the difficulty of extracting Nash equilibria from expert demonstrations, we focus in this section on the idealized case of exact occupancy measure matching. This is a crucial step for determining when a bound can be consistent, while the assumption is relaxed in later sections. Specifically, this section addresses the following question: When does exact occupancy measure matching learn a Nash equilibrium? We start by showing that under the strong assumption of full-state support, exact state-action occupancy measure matching (shortened state-action matching below) recovers an exact Nash equilibrium. Then, we show how relaxing any of these two assumptions can lead to catastrophic errors. Note that assuming exact state-action matching (i.e. ϵρ=0 _ρ=0) is equivalent to assuming state-only matching (i.e. ϵμ=0 _μ=0) and exact Behavioral Cloning (i.e. ϵBC=0 _BC=0). To make our statement more precise, note that any policy π of a Markov Game partitions the state space S into a visited region π+=s:μπ(s)>0S^+_π=\s: _π(s)>0\ and an unvisited region π−=s:μπ(s)=0S^-_π=\s: _π(s)=0\. We prove that state-action matching (ϵρ=0 _ρ=0) and full-state support (πE+=S^+_π^E=S) recovers the Nash expert, i.e. π=πEπ=π^E. When the state-support is incomplete (πE+≠S^+_π^E ) or only state-matching (ϵμ=0 _μ=0) holds, we can only guarantee the trivial bound NashGap(π)≤(1/(1−γ))NashGap(π) (1/(1-γ) ). 4.1 Sufficiency of state-action matching under full-state support Under full-state support (π+=S^+_π=S), we show how state-action matching is sufficient to learn a Nash equilibrium. This is the direct consequence of the following fact: a policy π is uniquely characterized by its state-action occupancy measure ρπ _π on the visited region π+S^+_π. We formalize this idea in the following theorem, and explain its implications for measure matching. Theorem 1. Let π,π′∈Ππ,π ∈ be such that ρπ=ρπ′ _π= _π . Then, π+=π′+S^+_π=S^+_π and π(⋅|s)=π′(⋅|s)π(·|s)=π (·|s) for every s∈π+s ^+_π. The proof can be found in Appendix B.1. This shows that in the limit of infinite data where state-action matching is attainable, the empirical state-action occupancy measure is a sufficient statistic for learning πEπ^E on its state support πE+S^+_π^E. Assuming full-state support, we can then derive the following corollary for state-action matching. Corollary 1. Let πE,π∈Ππ^E,π∈ be such that πE+=S^+_π^E=S and ρπE=ρπ _π^E= _π; then, NashGap(π)=0NashGap(π)=0. Matching state-action occupancy measure under full-state support is therefore a sufficient condition for learning the expert Nash equilibrium. In the next section, we show that only assuming state-only matching μπE=μπ _π^E= _π becomes insufficient to learn a Nash equilibrium. 4.2 Insufficiency of state-only matching with full-state support In this section, we show that even with full-state support, state-only matching doesn’t provide exploitability guarantees in general Markov Games. This is because rewards are functions of state-action pairs but state distributions are not necessarilly tied to specific transitions. We can therefore construct examples of games where a given state distribution can be realized by distinct transitions and very different rewards. To prove that state-only matching with full-state support cannot extract Nash equilibria (Nash gap of zero) in general games, we demonstrate below that it can even incur a Nash gap linear in the effective horizon 1/(1−γ)1/(1-γ). Lemma 1. There exists a game and a corresponding expert policy πEπ^E such that πE+=S^+_π^E=S. Moreover, there exists a policy π such that μπE=μπ _π^E= _π and NashGap(π)≥Ω(1/(1−γ))NashGap(π)≥ (1/(1-γ) ). Proof. We prove this lemma by constructing an example of such a game. Let G be a cooperative two-player game with action sets 1=2=a1,a2A_1=A_2=\a_1,a_2\, state space =s0,s1,s2S=\s_0,s_1,s_2\, discount term γ, and uniform initial state distribution νU _U. The rewards and transition dynamics of G are shown in Figure 1. By definition, μπ′(s)≥(1−γ)νU(s)>0 _π (s)≥(1-γ) _U(s)>0 for all s∈s and π′∈Ππ ∈ . Therefore, all policies have full-state support. s0s_0s1s_1s2s_2(a1,a1)(a_1,a_1)else(a1,a1)(a_1,a_1)elseelse(a1,a1)(a_1,a_1) (a) Description of the game transition dynamics. Note that a tuple (ai,aj)(a_i,a_j) corresponds to player 1 playing aia_i and player 2 playing aja_j. Arrows represent deterministic transitions from a state to another. s0s_0s1s_1s2s_21/31/3−1-12/32/3−1-1−1-111 (b) Description of the reward function. The number on each arrow is the reward associated with the corresponding transition. The rewards are the same for both players. 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π^E with full-state support and a policy π such that μπE=μπ _π^E= _π with a Nash gap linear in the effective horizon 1/(1−γ)1/(1-γ). A Nash equilibrium of G is the constant policy πE((a1,a1)|s)=1π^E((a_1,a_1)|s)=1 for all s∈s with uniform occupancy measure μπE(⋅)=1/3 _π^E(·)=1/3. This is a Nash equilibrium because mixed actions in this game always incur the worst possible value. A formal argument can be found in Appendix B.2. Let the learned policy be the constant π((a1,a2)|s)=1π((a_1,a_2)|s)=1 such that μπ=μπE _π= _π^E and V2π(νU)=−11−γV_2^π( _U)=- 11-γ. Noting that V2πE(νU)=2/31−γV_2^π^E( _U)= 2/31-γ, this concludes the proof as: NashGap(π)≥V2πE(νU)−V2π(νU)=5/31−γ≥Ω(11−γ).NashGap(π)≥ V_2^π^E( _U)-V_2^π( _U)= 5/31-γ≥ ( 11-γ ). ∎ Lemma 1 emphasizes that state-based occupancy approaches as in Wu et al. (2025) cannot guarantee convergence to equilibria in general games even when policies are guaranteed to have full state coverage. 4.3 Insufficiency of state-action measure matching with unvisited states Assuming again state-action matching, we show that full-state support is essential for learning a Nash equilibrium in general games. We draw on the example given by Tang et al. (2024, Figure 2) to point out issues from a non-visited region πE−≠∅S^-_π^E≠ and derive the following theorem. Theorem 2. (Adapted from Tang et al. (2024, Theorem 4.3)) There exists a Markov Game with expert policy πEπ^E and a learned policy π such that even if ρπE=ρπ _π^E= _π, the Nash gap scales linearly with the discounted horizon; i.e., NashGap(π)≥Ω(1/(1−γ))NashGap(π)≥ (1/(1-γ) ). The key idea and intuition behind this theorem is that the imitation dataset misses information about the unvisited region SπE−S^-_π^E. An illustrative example of when this is undesirable is shown in Figure 2. s1s_1starts2s_2…s2′s _2sexps_exp Figure 2: Transitions of a two-player Markov Game. The unique initial state is s1s_1. The rest of the chain (⋯·s) and reward functions can be designed to induce linear Nash gap for state-action matching. We can design reward functions for the transitions of Figure 2 such that the expert would always take the solid arrows. The dataset missing information about πE(⋅|s2′)π^E(·|s _2), a best-response can lead to states s2′s _2 then sexps_exp. This last state sexps_exp can be designed to incur high rewards for one player, while the expert region SπE+S^+_π^E incurs linear less. For completeness, we adapt the proof of Tang et al. (2024) for infinite horizon games in Appendix B.3. 5 On the Infeasibility of Tractable Lower Bounds for Exploitability The analysis of Section 4 reveals that even under the idealized assumption of exact occupancy measure matching, MA-IL can still fail drastically. This prevents us from deriving consistent exploitability bounds in the general case. For practical settings, focusing on the idealized case of no learning error is however not sufficient as most IL procedures will incur an approximation error. This is due to two main reasons: First, because of the finite number of samples in the dataset, matching empirical statistics is inevitably different from matching the expert ones. Second, tbe function approximations in the non-tabular setting (Song et al., 2018; Wu et al., 2025) can only approximate the desired distributions. This shift from an exact to an approximate matching regime introduces new challenges. We know that the value gap always enjoys a consistent and tractable upper bound of rate (ϵBC/(1−γ)2)O ( _BC/(1-γ)^2 ) (Ross & Bagnell, 2010) or (ϵρ/(1−γ))O( _ρ/(1-γ)). However, we will demonstrate in the current and the next sections that even small approximation errors can make exploitability bounds intractable. A natural step in assessing the exploitability of the imitated policies is to quantify the best-case Nash gap they might induce under approximation errors. Given an approximation error, this quantity corresponds to the smallest achievable Nash gap among all the possible imitation policies π. Formally, we define it as follows: Definition 5 (Tight Nash gap lower bound). Let G be a Markov Game and let ΠE ^E the set of Nash equilibria of G. We define the tight Nash gap lower bound for G with occupancy matching error ϵρ _ρ as mρ(G,ϵρ)=minπE∈ΠEminπ∈ℳϵρ(πE)NashGap(π),m_ρ(G, _ρ)= _π^E∈ ^E _π _ _ρ(π^E)NashGap(π), where ℳϵρ(πE)=π∈Π:‖ρπ−ρπE‖1=ϵρM_ _ρ(π^E)= \π∈ : _π- _π^E _1= _ρ \. For a game G, given only the approximation error assumption ϵρ _ρ, mρ(G,ϵρ)m_ρ(G, _ρ) corresponds to the best possible achievable Nash gap. This quantity is in general intractable to compute for the case of bimatrix games as we show below in Theorem 3. Theorem 3. The problem of computing mρ(Gbi,ϵρ)m_ρ(G_bi, _ρ) given an arbitrary bimatrix game GbiG_bi and an arbitrary ϵρ∈ℝ+ _ρ _+ is PPAD-hard555See Appendix A for more formal details on the PPAD complexity class.. Proof outline. If computing this lower bound can be done efficiently, then it is also efficient to compute the support of a Nash equilibrium in a general bimatrix game. As we prove, the latter is PPAD-hard, so is our problem. In the proof, we provide a polynomial reduction to the problem of computing a support of an approximate Nash equilibrium. Then, we show that this can be polynomially reduced to the problem of computing a Nash equilibrium itself. This concludes the proof as finding an ϵε-Nash equilibrium is a PPAD-complete problem (Chen et al., 2009). See Appendix B.4 for the formal proof. ∎ This theorem tells us that evaluating the best-case Nash gap for a given ϵρ _ρ is not a tractable problem even when the game is fully known. This observation on the specific case of bimatrix games naturally extends to (infinite) repeated games and allows us to derive the following corollary on a larger class of Markov games. Corollary 2. The problem of computing mρ(G,ϵρ)m_ρ(G, _ρ) given an arbitrary Markov game G and an arbitrary ϵρ∈ℝ+ _ρ _+ is PPAD-hard. We further note that the hardness results do not imply the impossibility of deriving analytical bounds, for example involving min-max optimization problems (that are known to be hard to compute (Daskalakis et al., 2021)). However, they imply that finding bounds with polynomial computation time is no easier than finding the Nash equilibria themselves, even if the game is known. This makes any potential tight lower bound on the Nash gap intractable. 6 Tractable and Consistent Exploitability Upper Bounds from Best-Response Continuity In the previous section, we worked on a lower bound to understand the best possible Nash gap that we can hope to achieve from given approximation errors. In this section, we study and characterize worst-case exploitability guarantees with a new notion of best-response continuity. For general n-player Markov Games, the worst-case Value gap for a given BC error (Equation 2) is given by a consistent and tractable uniform bound: ValueGap(π)≤nϵBC/(1−γ)2ValueGap(π)≤ n _BC/(1-γ)^2. However, the exploitation nature of the Nash gap makes it impossible to derive such a bound for a fixed error term. We reveal how this phenomenon, not present in SA-IL, is characterized by a form of best-response continuity, leading to game-dependent bounds. 6.1 Characterization of Markov Games via Best-Response delta-continuity We introduce below a notion of continuity of the best-response mapping of Markov Games that will allow us to derive new general upper bounds on the Nash gap in the next subsections. Definition 6 (δ-continuity of the best-response correspondence). For a given game G, the best-response mapping is said to be δ-continuous at equilibrium πEπ^E for some δ:ℝ+→[0,2]δ:R^+→[0,2] if for all i∈[n]i∈[n], and ϵ>0ε>0, we have: s∼μπE[∥π−i(⋅|s)−π−iE(⋅|s)∥1]≤ϵ⟹maxπi∗∈BRi(π−i)s∼μπE[∥πi∗(⋅|s)−πiE(⋅|s)∥1]≤δ(ϵ).E_s _π^E [ _-i(·|s)-π^E_-i(·|s) _1 ]≤ε _π^*_i _i( _-i)E_s _π^E [ _i^*(·|s)- _i^E(·|s) _1 ]≤δ(ε). This is a notion related to the maximal change over all i∈[n]i∈[n] of the optimal policy πiE∈BRi(π−iE)π^E_i _i(π^E_-i), when the induced MDP for player i is produced by π−i _-i instead of the equilibrium behavior π−iEπ^E_-i. This continuity will be used below to reduce the complexity of computing Nash gap upper bounds to computing a valid δ. This definition is naturally extended for a class of games as follows. Definition 7 (δ-continuity of a class of games). A class C of Markov Games is δ-continuous if every game G∈G is δ-continuous at all its Nash equilibria. Provided with a δ-continuous class of games, we will therefore be able to derive bounds without assuming a specific game. However, we note that even for the class of games with a consistent bound as presented in Section 4, we cannot guarantee more than the trivial δ(ϵ)=2δ(ε)=2 for ϵ>0ε>0. Lemma 2. Let C be the class of games with consistent bounds. This class is δ-continuous only for trivial δ such that δ(ϵ)=2δ(ε)=2 for all ϵ>0ε>0. Proof. Suppose C is δ-continuous. For every ϵ>0ε>0, γ∈(0,1)γ∈(0,1), we show that there exists a two-player game G∈G with Nash equilibrium πEπ^E where ϵBC≤ϵ _BC≤ε can incur s∼μπE[∥π1∗(⋅|s)−π1E(⋅|s)∥1]=2E_s _π^E [ π^*_1(·|s)-π^E_1(·|s) _1 ]=2 for some π1∗∈BR1(π2)π^*_1 _1( _2). We let MkM_k be a chain of k=⌈log(ϵ2(1−γ))log(γ)⌉k= ( ε2(1-γ)) (γ) consecutive states and define its transitions as follows. s0s_0startMkM_ksexps_expa1=a1ra_1=a^r_1anya1=a2ra_1=a^r_2any Figure 3: Deterministic transition dynamics of a two-player game G, with states s0s_0, sexps_exp and sub-Markov chain MkM_k. Player 1 has action space 1=a1r,a2rA_1=\a^r_1,a^r_2\ and player 2 has action space 2=a1c,a2cA_2=\a^c_1,a^c_2\. The rewards r1,r2r_1,r_2 are independent of a1a_1 and defined as: r1(⋅,a1c,sexp)=1,r2(⋅,a2c,sexp)=1,r1(⋅,a2c,sexp)=−1,r_1(·,a^c_1,s_exp)=1, r_2(·,a^c_2,s_exp)=1, r_1(·,a^c_2,s_exp)=-1, and r1=r2=0r_1=r_2=0 otherwise. A Nash equilibrium of this game is the constant policy πE((a1r,a2c)|s)=1π^E((a^r_1,a^c_2)|s)=1 for all s∈s . The expert is such that μπE(sexp)≤ϵ/2 _π^E(s_exp)≤ε/2. Therefore, the policy π((a1,a2)|s)=πE((a1,a2)|s)π((a_1,a_2)|s)=π^E((a_1,a_2)|s) if s≠sexps≠ s_exp and π((a1r,a1c)|sexp)=1π((a^r_1,a^c_1)|s_exp)=1, has BC error at most ϵε. A best-response to π2 _2 is the constant policy π1∗(a2r|s)=1π^*_1(a^r_2|s)=1 for all s∈s which incurs s∼μπE[∥π1∗(⋅|s)−π1E(⋅|s)∥1]=2E_s _π^E [ π^*_1(·|s)-π^E_1(·|s) _1 ]=2. Note that G has a consistent bound for any error assumption (ϵBC=0⇔ϵμ=0⇔ϵρ=0 _BC=0 _μ=0 _ρ=0 for G, and πE+=S^+_π^E=S). ∎ 6.2 Provable convergence under strategic dominance The previous section showed that even for the class of games with consistent bounds, we cannot do better than the trivial δ-continuity where δ(ϵ)=2δ(ε)=2 for ϵ>0ε>0. We study in this section the other extreme for δ: the constant δ(⋅)=0δ(·)=0, before studying the general case in the next section. In fact, we show that this special case corresponds to the class of Dominant Strategy Equilibria, for which we can thus derive consistent and tractable exploitability upper bounds. Definition 8 (Dominant Strategy Equilibrium (DSE)). A policy πEπ^E is a (weak) dominant strategy equilibrium if for every player i, πiEπ^E_i is a weak dominant strategy, i.e.: ViπiE,π−i(ν0)≥Viπi,π−i(ν0)∀π∈Π.V_i^π^E_i, _-i( _0)≥ V_i _i, _-i( _0) ∀π∈ . Note that the key property induced by the DSE assumption is that πiEπ^E_i is a best-response policy to any deviations π−i _-i for every player i, which corresponds to δ-continuity of the best-response for δ(⋅)=0δ(·)=0. This allows us to derive the following consistent and tractable upper bound on the Nash gap. Lemma 3. Suppose πEπ^E is a (weak) Dominant Strategy Equilibrium. Then, any learned policy π with BC error ϵBC _BC satisfies NashGap(π)≤2nϵBC/(1−γ)2NashGap(π)≤ 2n _BC/(1-γ)^2. Proof outline. We leverage the fact that the Dominant Strategy Equilibrium assumption removes the ambiguity in how far the best-response of any player is from its individual expert policy, i.e. we have: NashGap(π)=maxi[ViπiE,π−i(ν0)−Viπi,π−i(ν0)].NashGap(π)= _i [V_i^π^E_i, _-i( _0)-V_i _i, _-i( _0) ]. (3) Using Equation 3, we can add and subtract the expert value ViπE(ν0)V_i^π^E( _0) for every i∈[n]i∈[n] and apply the performance difference lemma (see e.g. Xiao (2022, Lemma 1)) twice to get: NashGap(π)≤1(1−γ)2⋅maxis∼μπE[∥π−i(⋅|s)−π−iE(⋅|s)∥1+∥π(⋅|s)−πE(⋅|s)∥1].NashGap(π)≤ 1(1-γ)^2· _iE_s _π^E [ _-i(·|s)-π^E_-i(·|s) _1+ π(·|s)-π^E(·|s) _1 ]. We conclude the proof using the definition of the BC error and the fact that both π and πEπ^E are product policies. The formal proof is deferred to Appendix C.1 ∎ Note that when n=2n=2, this recovers the upper bound of Freihaut et al. (2025) with a fixed BC error. Providing such an upper bound allows assessing an imitation policy a posteriori, given a specific BC error. As a bound polynomial in the game parameters, we consider it to be tractable. Alternatively, we can interpret the bound as a criterion on the BC error to ensure a fixed Nash approximation error. Corollary 3. Suppose πEπ^E is a (weak) Dominant Strategy Equilibrium; then, the recovered behavioral cloning policy π is an ϵε-Nash equilibrium if ϵBC≤ϵ(1−γ)22n _BC≤ ε(1-γ)^22n. Proof. This is a direct consequence of Lemma 3 derived by inverting the Nash gap bound. ∎ 6.3 Relaxing the dominance assumption Using a similar proof technique, we extend Lemma 3 by assuming general best-response δ-continuity. This is demonstrated in the following lemma which we prove in Appendix C.2. Lemma 4. Suppose the equilibrium expert is πEπ^E and the game is δ-continuous at πEπ^E. Then, NashGap(π)≤2nϵBC+δ(ϵBC)(1−γ)2NashGap(π)≤ 2n _BC+δ( _BC)(1-γ)^2. This is a generalization of Lemma 3 where the DSE case is recovered by setting δ(⋅)=0δ(·)=0. A numerical validation of the bound is provided in Appendix E. Note that we do not claim that the above bound is tight due to our worse-case guarantee. However, this characterization of the Nash gap with δ-continuity offers several advantages. Properties of the bound. Consistence and tractability properties of the bound are directly related to the properties of the δ function: the bound is consistent if δ(0)=0δ(0)=0 and it is tractable if δ itself is tractable. Lemma 4 then provides the key insight that deriving exploitability upper bounds reduces to characterizing δ for the considered game. On the sensitivity of game equilibria. In comparison to the previous bound of Freihaut et al. (2025) obtained via a change of measure, our bound doesn’t necessarily become vacuous if strategic deviations on the imitation policy explores regions of the state space not visited by the expert. In fact, δ-continuity of games serves as a spectrum to characterize their sensitivity to perturbations at equilibrium points. The first extreme case is δ(⋅)=0δ(·)=0 that corresponds to games with only dominant strategy Nash equilibria. This assumption essentially reduces the Nash gap computation to a Value gap, recovering the known bound ValueGap(π)≤nϵBC/(1−γ)2ValueGap(π)≤ n _BC/(1-γ)^2 for single-agent behavioral cloning666The joint policy π can be viewed as a single-agent policy with behavioral cloning loss (Equation 2) upper bounded by nϵBCn _BC (see Lemma D.2 in Appendix). (Ross et al., 2011) up to a constant factor 22. The other extreme is δ-continuity with the constant δ(⋅)=2δ(·)=2, reducing to a trivial upper bound greater than 2/(1−γ)2/(1-γ) and achieved by the limit of pathological games, as shown with the example given in the proof of Lemma 2. Intuitively, a well-behaving δ can be imposed by regularizing the game, essentially smoothing the best-response map by promoting exploration (Ahmed et al., 2019; Geist et al., 2019). Furthermore, we note that large discontinuities in δ are favored by high variance in the expert rewards, where small deviations from the expert can induce large differences in expected rewards. Similarly, these high variations at the equilibrium can be penalized by risk-aversion (Mazumdar et al., 2024), and we hypothesize that it could lead to the derivation of better δ functions. We provide additional numerical validations of the impact of entropy regularization on δ-continuity in Appendix E. 7 Conclusion In this work, we consider the problem of learning a Nash equilibrium from a given dataset of expert demonstrations in a multi-agent system. Assuming a Nash equilibrium expert and a given imitation learning error (BC or measure matching), we study the derivation of both consistent and tractable guarantees on the Nash gap of the learned policy. In the idealized case of exact measure matching, we demonstrate that only full-state support and state-action matching can guarantee non-trivial Nash gaps. Moving to practical settings, we show how approximation errors introduce challenges that are not present in the single-agent case. For behavioral cloning, we then introduce the notion of delta-continuity related to strategy dominance, and show how this can be used to bound exploitability of the learned policy. Looking forward, we see reachability assumptions and policy distribution-norms (Wei et al., 2017; Maillard et al., 2014) as good candidates for tighter game-dependent bounds. A potential improvement might also be achieved from the data part, by augmenting expert demonstrations with suboptimal trajectories (e.g. in SA-IL (Kim et al., 2021)), inspired by online IL (Ross et al., 2011; Freihaut et al., 2025) and unilateral deviation assumptions (Cui & Du, 2022). Acknowledgments This work was supported in part by the National Science Foundation (NSF) under grants number ECCS-2438314 (CAREER Award) and CCF-2423134, the Army Research Laboratory (ARL) under grant number W911NF-26-1-0002, and institutional support from EPFL. References Abbeel & Ng (2004) Pieter Abbeel and Andrew Y Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the twenty-first international conference on Machine learning, p. 1, 2004. Ahmed et al. (2019) Zafarali Ahmed, Nicolas Le Roux, Mohammad Norouzi, and Dale Schuurmans. Understanding the impact of entropy on policy optimization. In International conference on machine learning, p. 151–160. PMLR, 2019. Alatur et al. (2024) Pragnya Alatur, Anas Barakat, and Niao He. Independent policy mirror descent for markov potential games: Scaling to large number of players. In 2024 IEEE 63rd Conference on Decision and Control (CDC), p. 3883–3888. IEEE, 2024. Bhattacharyya et al. (2018) Raunak P Bhattacharyya, Derek J Phillips, Blake Wulfe, Jeremy Morton, Alex Kuefler, and Mykel J Kochenderfer. Multi-agent imitation learning for driving simulation. In 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), p. 1534–1539. IEEE, 2018. Bogert & Doshi (2018) Kenneth Bogert and Prashant Doshi. Multi-robot inverse reinforcement learning under occlusion with estimation of state transitions. Artificial Intelligence, 263:46–73, 2018. Cai et al. (2023) Yang Cai, Haipeng Luo, Chen-Yu Wei, and Weiqiang Zheng. Uncoupled and convergent learning in two-player zero-sum markov games with bandit feedback. Advances in Neural Information Processing Systems, 36:36364–36406, 2023. Chandra et al. (2025) Rohan Chandra, Haresh Karnan, Negar Mehr, Peter Stone, and Joydeep Biswas. Multi-agent inverse reinforcement learning in real world unstructured pedestrian crowds. In 2025 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), p. 18668–18675. IEEE, 2025. Chen et al. (2009) Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player nash equilibria. Journal of the ACM (JACM), 56(3):1–57, 2009. Choi et al. (2025) Seoyeon Choi, Kanghyun Ryu, Jonghoon Ock, and Negar Mehr. Craft: Coaching reinforcement learning autonomously using foundation models for multi-robot coordination tasks. arXiv preprint arXiv:2509.14380, 2025. Conitzer & Sandholm (2002) Vincent Conitzer and Tuomas Sandholm. Complexity results about nash equilibria. CoRR, cs.GT/0205074, 2002. Cui & Du (2022) Qiwen Cui and Simon S Du. When are offline two-player zero-sum markov games solvable? Advances in Neural Information Processing Systems, 35:25779–25791, 2022. Daskalakis et al. (2009) Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. The complexity of computing a nash equilibrium. Communications of the ACM, 52(2):89–97, 2009. Daskalakis et al. (2021) Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, p. 1466–1478, 2021. Finn et al. (2016a) Chelsea Finn, Paul Christiano, Pieter Abbeel, and Sergey Levine. A connection between generative adversarial networks, inverse reinforcement learning, and energy-based models. arXiv preprint arXiv:1611.03852, 2016a. Finn et al. (2016b) Chelsea Finn, Sergey Levine, and Pieter Abbeel. Guided cost learning: Deep inverse optimal control via policy optimization. In International conference on machine learning, p. 49–58. PMLR, 2016b. Foster et al. (2024) Dylan J Foster, Adam Block, and Dipendra Misra. Is behavior cloning all you need? understanding horizon in imitation learning. Advances in Neural Information Processing Systems, 37:120602–120666, 2024. Freihaut & Ramponi (2025) Till Freihaut and Giorgia Ramponi. On feasible rewards in multi-agent inverse reinforcement learning. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. Freihaut et al. (2025) Till Freihaut, Luca Viano, Volkan Cevher, Matthieu Geist, and Giorgia Ramponi. Learning equilibria from data: Provably efficient multi-agent imitation learning. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. Garg et al. (2021) Divyansh Garg, Shuvam Chakraborty, Chris Cundy, Jiaming Song, and Stefano Ermon. Iq-learn: Inverse soft-q learning for imitation. Advances in Neural Information Processing Systems, 34:4028–4039, 2021. Geist et al. (2019) Matthieu Geist, Bruno Scherrer, and Olivier Pietquin. A theory of regularized markov decision processes. In International conference on machine learning, p. 2160–2169. PMLR, 2019. Goodfellow et al. (2020) Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. Communications of the ACM, 63(11):139–144, 2020. Ho & Ermon (2016) Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. Advances in neural information processing systems, 29, 2016. Kim et al. (2021) Geon-Hyeong Kim, Seokin Seo, Jongmin Lee, Wonseok Jeon, HyeongJoo Hwang, Hongseok Yang, and Kee-Eung Kim. Demodice: Offline imitation learning with supplementary imperfect demonstrations. In International Conference on Learning Representations, 2021. Lin et al. (2018) Xiaomin Lin, Stephen C Adams, and Peter A Beling. Multi-agent inverse reinforcement learning for general-sum stochastic games. arXiv preprint arXiv:1806.09795, 2018. Maillard et al. (2014) Odalric-Ambrym Maillard, Timothy A Mann, and Shie Mannor. How hard is my mdp?” the distribution-norm to the rescue”. Advances in Neural Information Processing Systems, 27, 2014. Mazumdar et al. (2024) Eric Mazumdar, Kishan Panaganti, and Laixi Shi. Tractable equilibrium computation in markov games through risk aversion, 2024. URL https://arxiv.org/abs/2406.14156. Mehr et al. (2023) Negar Mehr, Mingyu Wang, Maulik Bhatt, and Mac Schwager. Maximum-entropy multi-agent dynamic games: Forward and inverse solutions. IEEE transactions on robotics, 39(3):1801–1815, 2023. Nagpal et al. (2025) Kartik Nagpal, Dayi Dong, Jean-Baptiste Bouvier, and Negar Mehr. Leveraging large language models for effective and explainable multi-agent credit assignment. arXiv preprint arXiv:2502.16863, 2025. Ng et al. (2000) Andrew Y Ng, Stuart Russell, et al. Algorithms for inverse reinforcement learning. In Icml, volume 1, p. 2, 2000. Papadimitriou (1994) Christos H Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and system Sciences, 48(3):498–532, 1994. Pearce et al. (2023) Tim Pearce, Tabish Rashid, Anssi Kanervisto, Dave Bignell, Mingfei Sun, Raluca Georgescu, Sergio Valcarcel Macua, Shan Zheng Tan, Ida Momennejad, Katja Hofmann, et al. Imitating human behaviour with diffusion models. In The Eleventh International Conference on Learning Representations (ICLR 2023), 2023. Perolat et al. (2015) Julien Perolat, Bruno Scherrer, Bilal Piot, and Olivier Pietquin. Approximate dynamic programming for two-player zero-sum markov games. In International Conference on Machine Learning, p. 1321–1329. PMLR, 2015. Pomerleau (1991) Dean A Pomerleau. Efficient training of artificial neural networks for autonomous navigation. Neural computation, 3(1):88–97, 1991. Puterman (2014) Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014. Ramponi et al. (2023) Giorgia Ramponi, Pavel Kolev, Olivier Pietquin, Niao He, Mathieu Laurière, and Matthieu Geist. On imitation in mean-field games. Advances in Neural Information Processing Systems, 36:40426–40437, 2023. Ross & Bagnell (2010) Stéphane Ross and Drew Bagnell. Efficient reductions for imitation learning. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, p. 661–668. JMLR Workshop and Conference Proceedings, 2010. Ross et al. (2011) Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, p. 627–635. JMLR Workshop and Conference Proceedings, 2011. Shih et al. (2022) Andy Shih, Stefano Ermon, and Dorsa Sadigh. Conditional imitation learning for multi-agent games. In 2022 17th ACM/IEEE International Conference on Human-Robot Interaction (HRI), p. 166–175. IEEE, 2022. Song et al. (2018) Jiaming Song, Hongyu Ren, Dorsa Sadigh, and Stefano Ermon. Multi-agent generative adversarial imitation learning. Advances in neural information processing systems, 31, 2018. Sunehag et al. (2017) Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Marc Lanctot, Nicolas Sonnerat, Joel Z Leibo, Karl Tuyls, et al. Value-decomposition networks for cooperative multi-agent learning. arXiv preprint arXiv:1706.05296, 2017. Tang et al. (2024) Jingwu Tang, Gokul Swamy, Fei Fang, and Zhiwei S Wu. Multi-agent imitation learning: Value is easy, regret is hard. Advances in Neural Information Processing Systems, 37:27790–27816, 2024. (42) Bernhard von Stengel. Algorithmic game theory. http://w.maths.lse.ac.uk/Personal/stengel/TEXTE/agt-stengel.pdf. Accessed: July 10, 2025. Wang et al. (2021) Hongwei Wang, Lantao Yu, Zhangjie Cao, and Stefano Ermon. Multi-agent imitation learning with copulas. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, p. 139–156. Springer, 2021. Ward et al. (2025) William Ward, Yue Yu, Jacob Levy, Negar Mehr, David Fridovich-Keil, and Ufuk Topcu. Active inverse learning in stackelberg trajectory games. In 2025 American Control Conference (ACC), p. 1547–1553. IEEE, 2025. Wei et al. (2017) Chen-Yu Wei, Yi-Te Hong, and Chi-Jen Lu. Online reinforcement learning in stochastic games. Advances in Neural Information Processing Systems, 30, 2017. Wu et al. (2025) Runzhe Wu, Yiding Chen, Gokul Swamy, Kianté Brantley, and Wen Sun. Diffusing states and matching scores: A new framework for imitation learning. In The Thirteenth International Conference on Learning Representations, 2025. Xiao (2022) Lin Xiao. On the convergence rates of policy gradient methods. Journal of Machine Learning Research, 23(282):1–36, 2022. Yang et al. (2023) Shuo Yang, Wei Zhang, Ran Song, Jiyu Cheng, Hesheng Wang, and Yibin Li. Watch and act: Learning robotic manipulation from visual demonstration. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 53(7):4404–4416, 2023. Yin et al. (2021) Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal provable uniform convergence in offline policy evaluation for reinforcement learning. In International Conference on Artificial Intelligence and Statistics, p. 1567–1575. PMLR, 2021. Zhan et al. (2018) Eric Zhan, Stephan Zheng, Yisong Yue, Long Sha, and Patrick Lucey. Generative multi-agent behavioral cloning. CoRR, 2018. Appendix A Additional background A.1 PPAD complexity class In computational complexity theory, problems are categorized into classes to formally reason about their inherent difficulty and whether they are likely to be tractable. In game theory, the NP and PPAD classes are of crucial importance, as it has been shown that computing Nash equilibria is PPAD-complete (Daskalakis et al., 2009; Chen et al., 2009) and many decision problems around Nash equilibria are NP-hard (Conitzer & Sandholm, 2002). These key results also reinforce the arguments under which finding expert policies without demonstrations can be computationally intractable. We define below the PPAD class introduced by Papadimitriou (1994) and related to some of our negative results. Definition 9 (PPAD class). A search problem Π belongs to the complexity class PPAD (Polynomial Parity Arguments on Directed graphs) if and only if it is polynomial-time reducible to the End-of-the-Line problem defined as follows: End-of-the-Line Problem Input: • A directed graph G=(V,E)G=(V,E) implicitly represented by two polynomial-time computation mutually inverse functions P and S: – P:V→VP:V→ V maps every vertex v∈Vv∈ V to its unique predecessor, or itself. – S:V→VS:V→ V maps every vertex v∈Vv∈ V to its unique successor, or itself. • A source vertex s∈Vs∈ V such that P(s)=sP(s)=s and S(s)≠sS(s)≠ s. Output: Either a sink vertex or another source vertex. PPAD problems belong to the larger TFNP class (Total Function NP), containing search problems for which a solution is guaranteed to exist (the problems are said to be total). The fundamental property that makes PPAD problems total (guaranteed to have a solution) is based on the parity argument: in any directed graph where each vertex has at most one incoming and one outgoing edge, if there exists a source, there must exist either another source or a sink. Therefore, the End-of-the-Line problem always has a solution. It is believed that PPAD is not part of P, and hence PPAD-hard problems are believed intractable. A.2 GAIL and occupancy-measure matching Generative Adversarial Imitation Learning introduced by Ho & Ermon (2016) equivalently solves the following Inverse Reinforcement Learning (IRL) problem IRLψ(πE)=argmaxc∈−ψ(c)+(minπ∈Π−H(π)+π[c(s,a)])−πE[c(s,a)]IRL_ψ(π^E)= _c -ψ(c)+ ( _π∈ -H(π)+E_π[c(s,a)] )-E_π^E[c(s,a)] for a cost c∈c followed by standard Reinforcement Learning (RL) for policy extraction RL(c)=argminπ∈Π−H(π)+π[c(s,a)],RL(c)= _π∈ -H(π)+E_π[c(s,a)], with sets ,ΠC, constrained by modelization expressivity, ψ:ℝ×→ℝ∪∞ψ:R^S×A ∪\∞\ a convex cost function regularizer, and H(π)=π[−logπ(a|s)]H(π)=E_π[- π(a|s)] the causal entropy of policy π. Their key innovation is to show that for a particular instance of ψ, both problems can be solved simultaneously by training a discriminative classifier D:×→(0,1)D:S×A→(0,1) and a generator policy π∈Ππ∈ in a GAN-like (Goodfellow et al., 2020) manner. For a non-restricted =ℝ×C=R^S×A, we can exchange the max-min for a min-max (Ho & Ermon, 2016; Garg et al., 2021) and end up with the following practical optimization formulation: minπ∈ΠmaxD∈(0,1)×π[log(D(s,a))]+πE[log(1−D(s,a))]−λH(π), _π∈ _D∈(0,1)^S×AE_π[ (D(s,a))]+E_π^E[ (1-D(s,a))]-λ H(π), where λ is a regularization factor. This problem in particular is shown to be equivalent to the following regularized state-action occupancy matching objective: minπDJS(ρπ,ρπE)−λH(π) _πD_JS( _π, _π^E)-λ H(π), with DJSD_JS denoting the Jensen-Shannon divergence. In the more general case, Ho & Ermon (2016) propose that imitation learning can be done by state-action occupancy measure matching problems of the form: minπψ∗(ρπ−ρπE)−H(π) _πψ^*( _π- _π^E)-H(π) where the entropy regularization makes the optimal BC policy unique and ψ∗ψ^* denotes the convex conjugate of ψ. Appendix B Proofs of hardness results B.1 Proof of Theorem 1 See 1 Proof. Let π,π′π,π be two policies such that ρπ=ρπ′ _π= _π . We will first prove that π+=π′+S^+_π=S^+_π then prove that the policies are equal on the visited region π+S^+_π. 1) The policies π,π′π,π visit the same region of the space state. Suppose towards contradiction that there exists some s∈s such that s∈π+s ^+_π and s∉π′+s ^+_π . Since π(⋅|s)π(·|s) is a probability distribution, there must be an action a∈a such that π(a|s)>0π(a|s)>0. Hence ρπ(a,s)>0 _π(a,s)>0 but ρπ′(a,s)=μπ′(s)π′(a|s)=0 _π (a,s)= _π (s)π (a|s)=0 by assumption. This is a contraction since ρπ=ρπ′ _π= _π , hence π+=π′+S^+_π=S^+_π . 2) The policies π,π′π,π are equal on their shared visited region. We again proceed with a proof by contradiction. Suppose there exists a∈a and s∈π+s ^+_π such that π(a|s)≠π′(a|s)π(a|s)≠π (a|s). Since ρπ(a,s)=ρπ′(a,s) _π(a,s)= _π (a,s), μπ(s)>0,μπ′(s)>0 _π(s)>0, _π (s)>0 and π(a|s)≠π′(a|s)π(a|s)≠π (a|s), we must therefore have μπ(s)≠μπ′(s) _π(s)≠ _π (s). Without loss of generality, assume μπ(s)>μπ′(s) _π(s)> _π (s); thus, for all a′∈a , π(a′|s)<π′(a′|s)π(a |s)<π (a |s) by the equality of the state-action occupancy measures. This is a contradiction since that would mean ∑a′∈π(a′|s)<∑a′∈π′(a′|s)=1 _a π(a |s)< _a π (a |s)=1 but π(⋅|s)π(·|s) is a probability distribution. ∎ B.2 Proof of Nash equilibria for the game in Figure 1 We want to show that πE((a1,a1)|s)=1π^E((a_1,a_1)|s)=1 for all s∈s is indeed a Nash equilibrium of the two-player game described in figure Figure 1. Suppose towards contradiction that πEπ^E is not a Nash equilibrium, as some player i∈1,2i∈\1,2\ is better off from unilaterally deviating. By the performance difference lemma (Lemma D.1), there must exists a state s∈s with positive advantage AiπE(ai,s)=QiπE(s,ai,a−i)−ViπE(s),with a−i=a1A^π^E_i(a^i,s)=Q^π^E_i(s,a^i,a^-i)-V^π^E_i(s), a^-i=a_1 when the player i chooses ai=a2a^i=a_2 and QiπE(s,ai,a−i)≔ri(s,ai,a−i)+γ∑s′∈P(s′|s,a)ViπE(s′)Q^π^E_i(s,a^i,a^-i) r_i(s,a^i,a^-i)+γ _s P(s |s,a)V^π^E_i(s ). This is a contradiction since, when fixing ai=a2a^i=a_2, for all s∈s we have AiπE(ai,s) A^π^E_i(a^i,s) =ri(ai≠a−i,s)−ViπE(s)+γQiπE(s,ai,a−i) =r_i(a^i≠ a^-i,s)-V^π^E_i(s)+γ Q^π^E_i(s,a^i,a^-i) =−1−(1−γ)ViπE(s)+γAiπE(ai,s) =-1-(1-γ)V^π^E_i(s)+γ A^π^E_i(a^i,s) ≤γAiπE(ai,s) ≤γ A^π^E_i(a^i,s) Which is a contradiction as we assumed AiπE(ai,s)>0A^π^E_i(a^i,s)>0. Hence πEπ^E is a Nash equilibrium. B.3 Proof of Theorem 2 See 2 The proof below has been extracted from Tang et al. (2024) and only slightly adapted for infinite horizon games. Proof. We explicitly construct a two-player common payoff Markov Game with infinite horizon and a common action space i=a1,a2,a3A_i=\a_1,a_2,a_3\ for each agent i=1,2i=1,2. The state space S is countably infinite and ordered. The action-independent (shared) reward function is defined as r(si)=1r(s_i)=1 if i is odd, and r(si)=0r(s_i)=0 if i is even. The transition dynamics are described in Figure 4. s0s_0s1s_1s2s_2s3s_3s4s_4s5s_5s6s_6s2k−1s_2k-1s2ks_2k…(a2,a1)(a_2,a_1)else(a2,a1)(a_2,a_1)elseallallall⋯·s⋯·s Figure 4: Transition dynamics for the two-player game. s0s_0 is the initial state. The top branch contains all odd states while the bottom branch together with s0s_0 comprises all even states. We define the expert as the Nash policy πEπ^E such that πE((a1,a1)|s0)=1π^E((a_1,a_1)|s_0)=1, πE((a3,a3)|s1)=1π^E((a_3,a_3)|s_1)=1 and the actions for the other states are arbitrary. Similarly, we define the trained policy π such that π((a1,a1)|s0)=1π((a_1,a_1)|s_0)=1 and π((a1,a1)|s1)=1π((a_1,a_1)|s_1)=1, and plays the same as the expert on the other states. In this case ρπ=ρπE _π= _π^E but NashGap(π)≥V1π1′,π2(s0)−V1π(s0)=11−γ−1≥Ω(11−γ)NashGap(π)≥ V_1^π _1, _2(s_0)-V_1^π(s_0)= 11-γ-1≥ ( 11-γ ) where π1′(a1|s)=1if a1=a2 and s∈s0,s10if a1≠a2 and s∈s0,s1π1(a1|s)otherwiseπ _1(a^1|s)= cases1&if a^1=a_2 and s∈\s_0,s_1\\\ 0&if a^1≠ a_2 and s∈\s_0,s_1\\\ _1(a^1|s)&otherwise cases ∎ B.4 Proof of Theorem 3 See 3 Before proving Theorem 3, let us prove the following intermediary lemma. This will allow us to conclude by doing a reduction to the problem of finding an ϵε-Nash equilibrium. Lemma 5. Finding an ϵε-Nash equilibrium support in a general bimatrix game is PPAD-complete. B.4.1 Proof of Lemma 5 Before proving Theorem 5, we introduce below a simpler version for exact Nash equilibria. Theorem 4. Finding the support of any Nash equilibrium in a bimatrix game is PPAD-complete. Proof. We prove this by a polynomial reduction from the problem of finding the equilibrium in a bimatrix game to the problem of finding its support. The other direction is trivial. Let =(A1,A2)G=(A_1,A_2) be a bimatrix game with payoff matrices AiA_i for each player i∈1,2i∈\1,2\. For simplicity we further assume that A1,A2∈ℝn×nA_1,A_2 ^n× n (i.e. both players have the same number of actions n). Let π1,π2 _1, _2 the unknown policies at equilibrium of our game, with respective supports ν1,ν2⊆1,…,n _1, _2 \1,…,n\. Using our support finding oracle, we compute ν1,ν2 _1, _2 from the payoff matrices. We note that from the definition of a Nash equilibrium, π1 _1 is a best-response of player 1 to player 2 having policy π2 _2. This means: π1⊤A1π2=maxiA1,i⊤π2⟹A1,j⊤π2=A1,k⊤π2∀j,k∈ν1, _1 A_1 _2= _iA_1,i _2 A_1,j _2=A_1,k _2\ ∀ j,k∈ _1, and a similar argument holds for π2 _2, this is known as the indifference principle. Using this, we can rewrite the problem of finding a Nash equilibrium as follows: Find x∈ℝ|ν1|,y∈ℝ|ν2| x ^| _1|,\ y ^| _2| s.t. ∑i=1|ν1|xi=∑i=1|ν2|yi=1 _i=1^| _1|x_i= _i=1^| _2|y_i=1 (A2,j−A2,k)⊤x=0∀j,k∈ν2 (A_2,j-A_2,k) x=0 ∀ j,k∈ _2 (A1,j−A1,k)⊤y=0∀j,k∈ν1 (A_1,j-A_1,k) y=0 ∀ j,k∈ _1 xi≥0∀i∈ν1 x_i≥ 0 ∀ i∈ _1 yi≥0∀i∈ν2 y_i≥ 0 ∀ i∈ _2 This is a linear program that can be solved in polynomial time. By solving this optimization problem we recover π1=x _1=x and π2=y _2=y (see also Algorithm 3.4 in von Stengel ), which is valid with our assumptions of equilibrium supports ν1,ν2 _1, _2. However, as shown in Chen et al. (2009), finding an equilibrium of a bimatrix game is PPAD-complete. This concludes our proof by showing that finding the support of a Nash equilibrium in general bimatrix games is PPAD-complete. ∎ Using similar arguments, we argue that the theorem also holds for epsilon Nash equilibria with the following proof. Proof of Lemma 5. The proof follows by adapting the linear program used in the proof of Theorem 4, replacing the equality constraints due to the indifference principle by two inequality constraints allowing some slackness of magnitude less ϵε as follows Find x∈ℝ|ν1|,y∈ℝ|ν2| x ^| _1|,\ y ^| _2| s.t. ∑i=1|ν1|xi=∑i=1|ν2|yi=1 _i=1^| _1|x_i= _i=1^| _2|y_i=1 (A2,j−A2,k)⊤x≤ϵ∀j,k∈ν2 (A_2,j-A_2,k) x≤ε ∀ j,k∈ _2 (A1,j−A1,k)⊤y≤ϵ∀j,k∈ν1 (A_1,j-A_1,k) y≤ε ∀ j,k∈ _1 (A2,k−A2,j)⊤x≤ϵ∀j,k∈ν2 (A_2,k-A_2,j) x≤ε ∀ j,k∈ _2 (A1,k−A1,j)⊤y≤ϵ∀j,k∈ν1 (A_1,k-A_1,j) y≤ε ∀ j,k∈ _1 xi≥0∀i∈ν1 x_i≥ 0 ∀ i∈ _1 yi≥0∀i∈ν2 y_i≥ 0 ∀ i∈ _2 This allows finding an ϵε-Nash equilibrium which is also known to be PPAD-complete (Chen et al., 2009). The other direction is trivial. ∎ B.4.2 Reduction for the proof of Theorem 3 Recall the statement to prove See 3 Proof. We prove the result by a polynomial reduction from the problem of finding the support of an ϵε-Nash equilibrium in a general bimatrix game to the problem of computing mρ(Gbi,ϵρ)m_ρ(G_bi, _ρ) for any GbiG_bi, ϵρ _ρ. Note that in this one-state game, the state-action occupancy measure is equal to the policy distribution. We assume maxi,jmax|A1i,j|,|A2i,j|<1 _i,j \|A_1_i,j|,|A_2_i,j|\<1. If it’s not the case, it suffices to divide the payoff matrices by 22 and apply the same argument for ϵρ/2 _ρ/2. Assume access to an oracle L(Gbi,ϵ)L(G_bi,ε) for mρm_ρ for any Gbi=(A1,A2)G_bi=(A_1,A_2), ϵρ∈ℝ+ _ρ _+. We will show that polynomially many calls to this oracle are sufficient to find the support of any ϵε-Nash equilibrium of GbiG_bi. Specifically, Algorithm 1 described below is sufficient for this task. Algorithm 1 Lower bound reduction Given a game A1,A2A_1,A_2 and a target Nash precision ϵε. Define A1ν=A1A_1^ν=A_1, A2ν=A2A_2^ν=A_2. Define K such that −1<K<−maxi,jmax|A1i,j|,|A2i,j|-1<K<- _i,j \|A_1_i,j|,|A_2_i,j|\. Define ν1=ν2=∅ _1= _2= . Define δ=∥ϵ/K⋅e1∥1δ= ε/K· e_1 _1 such that s=L((A1,A2),δ)≤ϵs=L((A_1,A_2),δ)≤ε, for a canonical vector e1e_1. for i∈1,…,ni∈\1,…,n\ do Define A1iA_1^i such that • A1ia,b=A1νa,b∀a,b∈[n]∖i×[n]\A_1^i\_a,b=\A_1^ν\_a,b\ ∀ a,b∈[n] \i\×[n] • A1ii=K⋅1\A_1^i\_i=K· 1 Use the oracle to compute l1i=L((A1i,A2),δ)l_1^i=L((A_1^i,A_2),δ). if l1i>sl_1^i>s then ν1←ν1∪i _1← _1∪\i\. else A1ν←A1iA_1^ν← A_1^i. for i∈1,…,ni∈\1,…,n\ do Define A2iA_2^i such that • A2ia,b=A2νa,b∀a,b∈[n]∖i×[n]\A_2^i\_a,b=\A_2^ν\_a,b\ ∀ a,b∈[n] \i\×[n] • A2ii=K⋅1\A_2^i\_i=K· 1 Use the oracle to compute l2i=L((A1,A2i),δ)l_2^i=L((A_1,A_2^i),δ). if l2i>sl_2^i>s then ν2←ν2∪i _2← _2∪\i\. else A2ν←A2iA_2^ν← A_2^i. Return ν1,ν2 _1, _2 To prove this fact, it suffices to note that replacing AkνA_k^ν by AkiA_k^i for any k∈1,2,i∈[n]k∈\1,2\,i∈[n] changes the value of the lower bound only if πk,i>0 _k,i>0 for every s-Nash equilibrium π with supports supersets of ν1,ν2 _1, _2. Formally, let Πmins ^s_ be the set of policies minimizing the Nash gap with the imitation error ϵε: Πmins≔argminπ1,π2:∥π1π2⊤−π1Eπ2E⊤∥1=sNashGap(π1,π2), ^s_ _ _1, _2: _1 _2 -π^E_1π^E_2 _1=sNashGap( _1, _2), and arrange the set in lexicographic order of the concatenated indicator vector encodings of the supports of the two players. We show that (ν1,ν2)( _1, _2) is equal to the first element of Πmins ^s_ which we denote (ν10,ν20)(ν^0_1,ν^0_2). Let j∈1,2j∈\1,2\ be a fixed player, then for every i∈[n]i∈[n]: • Case i∈νji∈ _j: then there doesn’t exist any element with a smaller lexicographic index in Πmins ^s_ . Hence, νj⊆νj0 _j ν^0_j. • Case i∉νji∉ _j: then there must be an equilibrium such that player j takes action i with null probability. Hence, νj0⊆νjν^0_j _j Thus, νj=νj0 _j=ν^0_j and (ν1,ν2)( _1, _2) are valid supports for an ϵε-Nash equilibrium. Applying Lemma 5 allows us to conclude that finding L is a PPAD-hard problem. ∎ Appendix C Proofs of upper bounds C.1 Proof of Lemma 3 See 3 Proof. Following the proof outline from the main text, we use the Dominant Strategy Equilibrium assumption to simplify the Nash gap as follows: NashGap(π)=maxi,πi∗[Viπi∗,π−i(ν0)−Viπi,π−i(ν0)]=maxi[ViπiE,π−i(ν0)−Viπi,π−i(ν0)]NashGap(π)= _i,π^*_i [V_i^π^*_i, _-i( _0)-V_i _i, _-i( _0) ]= _i [V_i^π^E_i, _-i( _0)-V_i _i, _-i( _0) ] We can then add and subtract the expert value for every player, and apply the performance difference lemma (Lemma D.1) twice: NashGap(π) (π) =maxi[ViπiE,π−i(ν0)−Viπi,π−i(ν0)] = _i [V_i^π^E_i, _-i( _0)-V_i _i, _-i( _0) ] =maxi[ViπiE,π−i(ν0)−ViπE(ν0)+ViπE(ν0)−Viπi,π−i(ν0)] = _i [V_i^π^E_i, _-i( _0)-V_i^π^E( _0)+V_i^π^E( _0)-V_i _i, _-i( _0) ] ≤11−γ⋅maxis∼μπE[∑aQπ(s,a)(πE(a|s)−π(a|s))] ≤ 11-γ· _iE_s _π^E [ _aQ^π(s,a) (π^E(a|s)-π(a|s) ) ] −11−γ⋅maxis∼μπE[∑aQπiE,π−i(s,a)(π−iE(a−i|s)−π−i(a−i|s))πiE(ai|s)] - 11-γ· _iE_s _π^E [ _aQ^π^E_i, _-i(s,a) (π^E_-i(a_-i|s)- _-i(a_-i|s) )π^E_i(a_i|s) ] where the Q-functions are defined as in Lemma D.1. Now upper bounding the Q-functions using ∥Qπ′∥∞≤1/(1−γ) Q^π _∞≤ 1/(1-γ) for any policy π′∈Ππ ∈ : NashGap(π) (π) ≤1(1−γ)2⋅maxis∼μπE[∥π(⋅|s)−πE(⋅|s)∥1+∥π−i(⋅|s)−π−iE(⋅|s)∥1] ≤ 1(1-γ)^2· _iE_s _π^E [ π(·|s)-π^E(·|s) _1+ _-i(·|s)-π^E_-i(·|s) _1 ] Using Lemma D.2 we conclude, NashGap(π)≤(2n−1)ϵBC(1−γ)2≤2nϵBC(1−γ)2NashGap(π)≤ (2n-1) _BC(1-γ)^2≤ 2n _BC(1-γ)^2 ∎ C.2 Proof of Lemma 4 See 4 The key is to use a very similar construction as for the proof of Lemma 3, leveraging the triangle inequality to introduce the slackness δ(ϵBC)δ( _BC). Proof. Using similar arguments, we apply Lemma D.1 and get: NashGap(π) (π) ≤1(1−γ)2⋅maxis∼μπE[∥π(⋅|s)−πE(⋅|s)∥1+∥(πi∗,π−i)(⋅|s)−πE(⋅|s)∥1] ≤ 1(1-γ)^2· _iE_s _π^E [ π(·|s)-π^E(·|s) _1+ (π^*_i, _-i)(·|s)-π^E(·|s) _1 ] Them we conclude using Lemma D.2 and our assumption: NashGap(π)≤(2n−1)ϵBC+δ(ϵBC)(1−γ)2≤2nϵBC+δ(ϵBC)(1−γ)2NashGap(π)≤ (2n-1) _BC+δ( _BC)(1-γ)^2≤ 2n _BC+δ( _BC)(1-γ)^2 ∎ Appendix D Additional lemmas Lemma D.1 (Performance Difference Lemma, see e.g. Theorem IX.5 in Alatur et al. (2024)). For any π,π′∈Π,i∈[n]π,π ∈ ,i∈[n], Viπi′,π−i(ν0)−Viπi,π−i(ν0)=11−γs,a∼ρπi′,π−i[Qiπ(s,a)−Viπ(s)],V_i^π _i, _-i( _0)-V_i _i, _-i( _0)= 11-γE_s,a _π _i, _-i [Q^π_i(s,a)-V^π_i(s) ], where Qiπ(s,a)≔ri(s,a)+γ∑s′∈P(s′|s,a)Viπ(s′)Q^π_i(s,a) r_i(s,a)+γ _s P(s |s,a)V^π_i(s ). And more generally, Viπ′(ν0)−Viπ(ν0)=11−γs,a∼ρπ′[Qiπ(s,a)−Viπ(s)],V_i^π ( _0)-V_i^π( _0)= 11-γE_s,a _π [Q^π_i(s,a)-V^π_i(s) ], Proof. See proof of Theorem IX.5 in Alatur et al. (2024). ∎ Lemma D.2. Let n∈ℕn , and let pi,qi∈Δmi−1p_i,q_i∈ _m_i-1 be probability distributions over a discrete set of size mim_i isomorphic to [mi][m_i]. Further, note p=×i=1npi,q=×i=1nqip=×_i=1^np_i,q=×_i=1^nq_i. Then, ∑j∈[m1]×⋯×[mn]|p(j)−q(j)|≤∑i=1n∑j=1mi|pi(j)−qi(j)| _j∈[m_1]×…×[m_n] p(j)-q(j) ≤ _i=1^n _j=1^m_i p_i(j)-q_i(j) Proof. We proceed with a proof by induction. The statement trivially holds for n=1n=1. Assume it holds for n, we show that it also holds for n+1n+1. For simplicity, note Sn=×i=1n[mi]S_n=×_i=1^n[m_i] and pn=×i=1npi,qn=×i=1nqip^n=×_i=1^np_i,q^n=×_i=1^nq_i. ∑j∈Sn×[mn+1]|p(j)−q(j)| _j∈ S_n×[m_n+1] p(j)-q(j) =∑j1∈Sn∑j2∈[mn+1]|pn(j1)pn+1(j2)−qn(j1)qn+1(j2)| = _j_1∈ S_n _j_2∈[m_n+1] p^n(j_1)p_n+1(j_2)-q^n(j_1)q_n+1(j_2) =∑j1∈Sn∑j2∈[mn+1]|pn(j1)pn+1(j2)−qn(j1)pn+1(j2) = _j_1∈ S_n _j_2∈[m_n+1] p^n(j_1)p_n+1(j_2)-q^n(j_1)p_n+1(j_2) +qn(j1)pn+1(j2)−qn(j1)qn+1(j2)| +q^n(j_1)p_n+1(j_2)-q^n(j_1)q_n+1(j_2) ≤∑j1∈Sn∑j2∈[mn+1]|pn(j1)pn+1(j2)−qn(j1)pn+1(j2)| ≤ _j_1∈ S_n _j_2∈[m_n+1] p^n(j_1)p_n+1(j_2)-q^n(j_1)p_n+1(j_2) +∑j1∈Sn∑j2∈[mn+1]|qn(j1)pn+1(j2)−qn(j1)qn+1(j2)| + _j_1∈ S_n _j_2∈[m_n+1] q^n(j_1)p_n+1(j_2)-q^n(j_1)q_n+1(j_2) =∑j1∈Sn|pn(j1)−qn(j1)|+∑j2∈[mn+1]|pn+1(j2)−qn+1(j2)| = _j_1∈ S_n p^n(j_1)-q^n(j_1) + _j_2∈[m_n+1] p_n+1(j_2)-q_n+1(j_2) ≤∑i=1n∑j=1mi|pi(j)−qi(j)|+∑j2∈[mn+1]|pn+1(j2)−qn+1(j2)| ≤ _i=1^n _j=1^m_i p_i(j)-q_i(j) + _j_2∈[m_n+1] p_n+1(j_2)-q_n+1(j_2) =∑i=1n+1∑j=1mi|pi(j)−qi(j)| = _i=1^n+1 _j=1^m_i p_i(j)-q_i(j) ∎ Appendix E Numerical Validation To better illustrate how our theoretical insights are related to practical empirical settings, in the following, we provide the example of a game in which a tight δ function can be estimated from data. Below, we show two main properties empirically: (1) we show that our theoretically-derived upper bound indeed holds, (2) we show the impact of entropy-regularization on the tightest delta function estimate. We would like to emphasize though that the tightness of our upper bound will ultimately depend on the precise environment and imitation setting that is considered. For both experiments, we consider the following Tag-Game environment: Tag-Game. An infinite horizon two-player zero-sum game played on a 2x3 grid. For this game, we set γ=0.8γ=0.8. For each time step t, one of the player is the tagger, whose goal is to hit/collide with the other player who is then being chased. When the collision happens, the roles are inverted. The action spaces 1=2=0,1,2,3A_1=A_2=\0,1,2,3\ represent actions corresponding to moving one step in one of the four cardinal directions. For each of the experiment, we consider results from all the initial states where players start at different corners of the grid. However, we reduce the number of initial states to two non-symmetrical states, while all the others can be recovered by symmetry of the game. The rewards are zero-sum, penalize the tagger with a constant reward, while also penalizing players from trying to escape the grid. In this environment, we first compute the unique regularized Nash equilibrium πEπ^E using a Nash Value Iteration algorithm (see e.g. Perolat et al. (2015)). Then, we perturb the equilibrium at every state with different noise levels to randomly generate a set of BC policies. For each imitation policy πiπ^i we compute its empirical behavioral cloning error ϵ^ij ε_ij using 2⋅1032· 10^3 episodes to estimate the expert state distribution. We can then again apply value iteration in the induced MDPs to compute best-responses and estimate a tight delta function. E.1 On the validity of the upper bound (Lemma 4) Following Definition 6, we compute a tight δ by taking the cumulative maximum of the expected L1 norm between the expert and the best response, maximizing over the two players. Similarly, we compute the tight Nash gap upper bound as a cumulative maximum over the empirical Nash gaps. For this experiment, we use 400400 noise levels evenly sampled from [0,0.4][0,0.4], and a fixed temperature of 0.10.1 for computational efficiency. In Figure 5 we show how in this simple setting δ increases when ϵBC _BC increases, as well as the NashGapNashGap. 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. This plot shows that the Nash gap tends to increase together with δ. Our upper bound, being greater than δ(ϵBC)H~2δ( _BC) H^2 with H~:=1/(1−γ) H:=1/(1-γ) the effective horizon, is therefore valid. Note that in an arbitrary toy environment, the bound cannot be required to be tight. This is expected behavior as the bound is uniform on the class of δ-continuous games, thus corresponding to a worst-case scenario. In particular, the H~2 H^2 factor corresponds to the worst-case expected advantage of the best-response with respect to the expert in the newly induced MDP. A similar behavior will appear with concentrability-based bounds. E.2 On the impact of entropy regularization We now again use Definition 6 to compute a tight estimate of δ(ϵBC)δ( _BC) for various BC errors. Related to the ideas mentioned in Section 6.3, we vary the entropy regularization factor and show its impact on δ. In Figure 6(a) we run the experiment by generating 250250 BC policies on a large range of [0,1.0][0,1.0] for the noise levels. This reveals that increasing the temperature tends to lower the δ(ϵBC)δ( _BC) when ϵBC∈[0,1] _BC∈[0,1] for the simple Tag-Game environment. However, we note that fixing a game G, this does not necessarily mean that the NashGapNashGap is reduced by increasing the temperature, since our upper bound Lemma 4 is not tight for G in general. (a) Large range of ϵBC _BC (b) ϵBC _BC at scale 10−210^-2 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 _BC values. The appropriate ϵBC _BC scale of importance ultimately depends on the application, the trajectory budget, expressiveness of the imitation model, as well as other factors. In the tabular setting, where ϵBC≈10−2 _BC≈ 10^-2 is achievable with tens of thousands of examples (see e.g. Freihaut et al. (2025)), the behavior of regularization coefficients remains consistent, as shown in Figure 6(b). For practical work, this matters because when humans are used as experts, we often assume entropy regularization to model humans’ irrationality. Having a sense of how this can also help control the exploitability of the imitation policies is therefore important. For theoretical work, this is useful as it tells us that beyond simplifying the analysis of optimal policies, entropy regularization might also lead to better guarantees on the worst-case Nash gap. Appendix F Finite horizon case The main content of the paper focuses on the infinite horizon case for notation simplicity. We show in this section how the results also translate to the finite horizon case. The statements are usually the same, but replacing the effective horizon 11−γ 11-γ by a finite horizon H. We formalize this intuition below by first providing alternative definitions for the finite agent case, and then reproving our main results. F.1 Definitions F.1.1 Finite horizon Markov Games A finite horizon n-player Markov Game is defined similarly to its infinite horizon equivalent with a tuple (,,P,rii=1n,ν0,H)(S,A,P,\r_i\_i=1^n, _0,H). The discount factor γ has been replaced by a finite horizon H∈ℕH . Further, rewards and policies of this game are now time-dependent: for all t, rewards are now denoted rit:×→[−1,1]r^t_i:S×A→[-1,1] and policies become non-stationary πit:→Δπ^t_i:S→ _A. The transition dynamics remain Markovian and P is unchanged. Because of introduced time dependence, occupancy measures are usually not generalized but denote the visitation frequencies at time t of a state and state-action pair, respectively. μπt(s)≔ℙ(st=s)ρπt(s,a)≔μπt(s)πt(a|s)μ^t_π(s) (s_t=s) 50.00008ptρ^t_π(s,a) μ^t_π(s)π^t(a|s) This allows the definition of time-dependent value functions as follows Vi,tπ(s)≔∑h=tH−1(s,a)∼ρπt[rit(s,a)]∀i∈[n],V_i,t^π(s) _h=t^H-1E_(s,a) ρ^t_π[r^t_i(s,a)] ∀ i∈[n], For ease of notation we define Viπ(s)=Vi,0π(s)V_i^π(s)=V_i,0^π(s) for all s∈s and policy π. Again, the definition of value functions is extended to Vi,tπ(ν)V_i,t^π(ν) for any distribution ν∈Δν∈ _S. F.1.2 Assumptions on matching errors The assumptions on errors at convergence are adapted as follows. BC Error: Error from directly matching the empirical distribution of the independent individual players ϵBC≔maxi,ts∼μπEt[∥πi,t(⋅|s)−πi,tE(⋅|s)∥1] _BC _i,tE_s μ^t_π^E [ _i,t(·|s)-π^E_i,t(·|s) _1 ] Measure Matching Error: Error on matching occupancy measures. - State-only occupancy measure: ϵμ≔maxt‖μπt−μπEt‖1 _μ _t μ^t_π-μ^t_π^E _1 - State-action occupancy measure: ϵρ≔maxt‖ρπt−ρπEt‖1 _ρ _t ρ^t_π-ρ^t_π^E _1 F.2 Performance difference lemma for finite horizon In this section we adapt the previously stated Lemma D.1 to finite horizon Markov games. This will allow us to generalize the results of the paper in Appendix F.3. Lemma F.1 (Finite horizon version of Lemma D.1). For any π,π′∈Π,i∈[n]π,π ∈ ,i∈[n], Viπi′,π−i(ν0)−Viπi,π−i(ν0)=∑t=0H−1s,a∼ρ(πi′,π−i)t[Qi,tπ(s,a)−Vi,tπ(s)],V_i^π _i, _-i( _0)-V_i _i, _-i( _0)= _t=0^H-1E_s,a ρ^t_(π _i, _-i) [Q^π_i,t(s,a)-V^π_i,t(s) ], where Qi,tπ(s,a)≔rit(s,a)+∑s′∈P(s′|s,a)Vi,t+1π(s′)Q^π_i,t(s,a) r^t_i(s,a)+ _s P(s |s,a)V^π_i,t+1(s ). And more generally, Viπ′(ν0)−Viπ(ν0)=∑t=0H−1s,a∼ρ(π′t[Qi,tπ(s,a)−Vi,tπ(s)],V_i^π ( _0)-V_i^π( _0)= _t=0^H-1E_s,a ρ^t_(π [Q^π_i,t(s,a)-V^π_i,t(s) ], Proof. We only prove the first version. The generalization can be proven by the exact same construction. To simplify, given a policy π~ π we overload the notations of the Q functions as follows. For every player i∈[N]i∈[N] we denote the state-actions values of i in the MDP induced by π~−i π_-i as: Qi,tπ~(s,ai)=a−i∼π~−i,t(⋅|s)[rit(s,a)+s′[Vi,t+1π~(s′)]],0≤t≤H−1Q π_i,t(s,a_i)=E_a_-i π_-i,t(·|s) [r^t_i(s,a)+E_s [V_i,t+1 π(s ) ] ], 0≤ t≤ H-1 Now, let 0<t≤H−10<t≤ H-1. Developing Vi,tπi′,π−i(νt)V_i,t^π _i, _-i( _t) for any distribution νt∈Δ _t∈ _S we have Vi,tπi′,π−i(νt) V_i,t^π _i, _-i( _t) =Vi,tπi′,π−i(νt)−s∼νt,ai∼πi,t′(⋅|s)[Qi,tπ(s,ai)]+s∼νt,ai∼πi,t′(⋅|s)[Qi,tπ(s,ai)] =V_i,t^π _i, _-i( _t)-E_s _t,a_i π _i,t(·|s) [Q^π_i,t(s,a_i) ]+E_s _t,a_i π _i,t(·|s) [Q^π_i,t(s,a_i) ] =s∼νt,ai∼πi,t′(⋅|s)[Qi,tπi′,π−i(s,ai)] =E_s _t,a_i π _i,t(·|s) [Q^π _i, _-i_i,t(s,a_i) ] −s∼νt,ai∼πi,t′(⋅|s)[Qi,tπ(s,ai)]+s∼νt,ai∼πi,t′(⋅|s)[Qi,tπ(s,ai)] -E_s _t,a_i π _i,t(·|s) [Q^π_i,t(s,a_i) ]+E_s _t,a_i π _i,t(·|s) [Q^π_i,t(s,a_i) ] =Vi,t+1πi′,π−i(νt+1)−Vi,t+1πi,π−i(νt+1)+s∼νt,ai∼πi,t′(⋅|s)[Qi,tπ(s,ai)] =V_i,t+1^π _i, _-i( _t+1)-V_i,t+1 _i, _-i( _t+1)+E_s _t,a_i π _i,t(·|s) [Q^π_i,t(s,a_i) ] where νt+1∈Δ _t+1∈ _S is the distribution over the next state after following policy (πi′,π−i)(π _i, _-i). Subtracting Viπ(νt)V_i^π( _t) on both sides and applying the recursion we get for the initial distribution ν0 _0, Viπi′,π−i(ν0)−Viπ(ν0)=∑t=0H−1s∼μπi′,π−it[ai∼πi,t′(⋅|s)[Qi,tπ(s,ai)]−Vi,tπ(s)]V_i^π _i, _-i( _0)-V_i^π( _0)= _t=0^H-1E_s μ^t_π _i, _-i [E_a_i π _i,t(·|s) [Q^π_i,t(s,a_i) ]-V_i,t^π(s) ] where we recognized νt∼μπi′,π−it _t μ^t_π _i, _-i. Rearranging the terms gives the final result Viπi′,π−i(ν0)−Viπi,π−i(ν0) V_i^π _i, _-i( _0)-V_i _i, _-i( _0) =∑t=0H−1s,a∼ρ(πi′,π−i)t[Qi,tπ(s,a)−Vi,tπ(s)] = _t=0^H-1E_s,a ρ^t_(π _i, _-i) [Q^π_i,t(s,a)-V^π_i,t(s) ] ∎ F.3 Results For completeness, we reprove below our results now considering finite horizon games. The counter-examples remain largely the same, as well as the proof structures. F.3.1 Section 4 Lemma F.2 (Finite version of Lemma 1). There exists a game and a corresponding expert policy πEπ^E such that πE+=S^+_π^E=S. Moreover, there exists a policy π such that μπE=μπ _π^E= _π and NashGap(π)≥Ω(H)NashGap(π)≥ (H ). Proof. The example provided in the main text is also valid to prove this lemma, by assuming an arbitrary horizon H. ∎ Theorem F.1 (Finite horizon version of Theorem 2). There exists a Markov Game with expert policy πEπ^E and a learner policy π such that even if ρπEt=ρπtρ^t_π^E=ρ^t_π for all 0≤t≤H−10≤ t≤ H-1, the Nash gap scales linearly with the horizon; i.e., NashGap(π)≥Ω(H)NashGap(π)≥ (H ). Proof. The proof is exactly the same as in Appendix B.3, except the state space which is finite (therefore still countable). ∎ F.3.2 Section 6 Lemma F.3 (Finite horizon version of Lemma 2). Let C be the class of games with consistent bounds. This class is δ-continuous only for trivial δ such that δ(ϵ)=2δ(ε)=2 for all ϵ>0ε>0. Proof. A similar proof to the one provided in the main text is valid for the finite horizon case. It suffices to adapt the k for the finite horizon, ensuring we keep the property μπE(sexp)≤ϵ/2 _π^E(s_exp)≤ε/2. ∎ Lemma F.4 (Finite horizon version of Lemma 3). Suppose πEπ^E is a (weak) Dominant Strategy Equilibrium. Then, any learned policy π with BC error ϵBC _BC satisfies NashGap(π)≤2nϵBCH2NashGap(π)≤ 2n _BCH^2. Proof. The Dominant Strategy Equilibrium assumption gives: NashGap(π) (π) =maxi,πi∗[Viπi∗,π−i(ν0)−Viπi,π−i(ν0)] = _i,π^*_i [V_i^π^*_i, _-i( _0)-V_i _i, _-i( _0) ] =maxi[ViπiE,π−i(ν0)−ViπE(ν0)+ViπE(ν0)−Viπi,π−i(ν0)] = _i [V_i^π^E_i, _-i( _0)-V_i^π^E( _0)+V_i^π^E( _0)-V_i _i, _-i( _0) ] Fixing i, we apply the Performance Difference Lemma (Lemma F.1) to get: ViπE(ν0)−Viπi,π−i(ν0) V_i^π^E( _0)-V_i _i, _-i( _0) =∑t=0H−1s,a∼ρπEt[Qi,tπ(s,a)−Vi,tπ(s)] = _t=0^H-1E_s,a ρ^t_π^E [Q^π_i,t(s,a)-V^π_i,t(s) ] =∑t=0H−1s∼μπEt[∑aQi,tπ(s,a)(πtE(a|s)−πt(a|s))] = _t=0^H-1E_s μ^t_π^E [ _aQ^π_i,t(s,a) (π^E_t(a|s)- _t(a|s) ) ] ≤H∑t=0H−1s∼μπEt[∥πtE(⋅|s)−πt(⋅|s)∥1] ≤ H _t=0^H-1E_s μ^t_π^E [ π^E_t(·|s)- _t(·|s) _1 ] ≤H2⋅max0≤t≤H−1s∼μπEt[∥πtE(⋅|s)−πt(⋅|s)∥1] ≤ H^2· _0≤ t≤ H-1E_s μ^t_π^E [ π^E_t(·|s)- _t(·|s) _1 ] where the Q-functions are defined as in Lemma F.1. Similarly, applying the PDL in the reverse order, ViπiE,π−i(ν0)−ViπE(ν0) V_i^π^E_i, _-i( _0)-V_i^π^E( _0) =∑t=0H−1s,a∼ρπEt[Vi,tπiE,π−i(s)−Qi,tπiE,π−i(s,a)] = _t=0^H-1E_s,a ρ^t_π^E [V^π^E_i, _-i_i,t(s)-Q^π^E_i, _-i_i,t(s,a) ] =∑t=0H−1s∼μπEt[∑aQi,tπiE,π−i(s,a)(π−i,t(a|s)−π−i,tE(a|s))πi,tE(ai|s)] = _t=0^H-1E_s μ^t_π^E [ _aQ^π^E_i, _-i_i,t(s,a) ( _-i,t(a|s)-π^E_-i,t(a|s) )π^E_i,t(a_i|s) ] ≤H∑t=0H−1s∼μπEt[∥π−i,t(⋅|s)−π−i,tE(⋅|s)∥1] ≤ H _t=0^H-1E_s μ^t_π^E [ _-i,t(·|s)-π^E_-i,t(·|s) _1 ] ≤H2⋅max0≤t≤H−1s∼μπEt[∥π−i,t(⋅|s)−π−i,tE(⋅|s)∥1] ≤ H^2· _0≤ t≤ H-1E_s μ^t_π^E [ _-i,t(·|s)-π^E_-i,t(·|s) _1 ] We conclude using Lemma D.2. NashGap(π)≤(2n−1)ϵBCH2≤2nϵBCH2NashGap(π)≤(2n-1) _BCH^2≤ 2n _BCH^2 ∎ Lemma F.5 (Finite horizon version of Lemma 4). Let π be the learned policy, and assume for all i∈[n]i∈[n] and 0≤t≤H−10≤ t≤ H-1 that s∼μπEt[∥πi,t∗(⋅|s)−πi,tE(⋅|s)∥1]≤(δ(ϵBC))E_s μ^t_π^E [ _i,t^*(·|s)- _i,t^E(·|s) _1 ] (δ( _BC)) for some function δ, where πi∗∈BRi(π) _i^* _i(π). Then, NashGap(π)≤(2nϵBC+δ(ϵBC))H2NashGap(π)≤ (2n _BC+δ( _BC) )H^2. Proof. Using similar arguments, applying Lemma F.1 and Lemma D.2: NashGap(π) (π) ≤maxi(max0≤t≤H−1s∼μπEt[∥πtE(⋅|s)−πt(⋅|s)∥1] ≤ _i ( _0≤ t≤ H-1E_s μ^t_π^E [ π^E_t(·|s)- _t(·|s) _1 ] . +max0≤t≤H−1s∼μπEt[∥πtE(⋅|s)−(πi,t∗,π−i,t)(⋅|s)∥1])H2 .+ _0≤ t≤ H-1E_s μ^t_π^E [ π^E_t(·|s)-(π^*_i,t, _-i,t)(·|s) _1 ] )H^2 ≤((2n−1)ϵBC+δ(ϵBC))H2 ≤ ((2n-1) _BC+δ( _BC) )H^2 ≤(2nϵBC+δ(ϵBC))H2 ≤ (2n _BC+δ( _BC) )H^2 ∎