Matching Multiple Experts: On the Exploitability of Multi-Agent Imitation Learning
Authors: Antoine Bergerault
Volkan Cevher
Negar Mehr
Venue: ICLR 2026 Poster (2026)
Keywords: imitation learning
multi-agent systems
behavioral cloning
Nash imitation gap
Primary area: reinforcement learning
TL;DR: Study of exploitability of multi-agent imitation learning and efficient bounds on the Nash imitation gap.

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.

Published as a conference paper at ICLR 2026
MATCHING MULTIPLE EXPERTS:
ON THE EX-
PLOITABILITY OF MULTI-AGENT IMITATION LEARNING
Antoine Bergerault* EPFL, UC Berkeley
Volkan Cevher EPFL
Negar Mehr UC Berkeley
ABSTRACT
Multi-agent imitation learning (MA-IL) aims 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 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 new hardness result on characterizing the Nash gap given fixed measure matching error. We then show how these challenges can be overcome using strategic dominance assumptions on the expert equilibrium. Specifically, for the strategy expert equilibria, assuming Behavioral Cloning error <Bc, this provides a Nash imitation gap of O (neBC//() [1 - -))²) for discount factor 7. We generalize this result with a new notion of best-response continuity, and argue that this is implicitly encouraged by standard regularization techniques.
of dominant
INTRODUCTION
Learning from expert demonstrations via imitation learning (IL) has recently seen growing adoption the Machine Learning and Robotics communities (Finn et al. 2016b Shih 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) 199I)), fitting plausible reward function and extracting a
policy via Reinforcement Learning (Inverse Reinforeement Learning (Ng et al. |000;Abbbec) Abbeel & Ng
2004)). or implicitly matching expert occupancy measures (Finn et al. 201 6a;
Ho & Ermon] 2016).
Crucially, imitation learning bypasses the need of designing reward function, 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 al. (2000): :
Ross & Bagnell (2010)) their extensions to multi-agent settings (Song et al.
2018 Zhan et al. 2018
Mehr al. 2023) inherit fundamental limitations. In particular, they produce imitation policies that
can be exploited by unilaterally deviating strategic agents (Tang 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 the learned policy its distance a Nash equilibrium. We characterize situations where can derive both consistent and tractable bounds on the Nash gap (see Section 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 compute based on the game assumptions. It can be computed in polynomial time to measure exploitability during II. training.
"The work was done when the first author was EPFI. master's 's student visiting UC Berkeley. Now at the University of Zurich. Correspondence to lantoine.hergeneee uzh.ch

---

Published as a conference paper at ICLR 2026
Intuitively, consistent bound ensures that a Nash equilibrium is learned from imitation error of zero. Consistency can be implicitly assumed by SA-IL extensions to multi -agett domains, but we show that this is 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 lead to bound inconsistencies. Then, 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:
we show the impossibility of deriving consistent Nash gap bounds in gen- eral Markov Games. We provide concrete examples where even exactly matching expert occupancy measures can result in highly exploitable policies.
In Section 4
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 presents 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 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 mnite-horizon games, as demonstrated in Appendix
PREVIOUS WORK
Single-agent Imitation Learning. Given dataset of demonstrations produced by expert, SA-IL aims to extract near-optimal policy from the data. The expert is considered optimal in maximizing a reward function over time, 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 al., 2016a Ho & Ermon 2016). In the single-ages 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. agent domains (Song et al., 2018 Lin et al. 2018 Wang al.) 202 Shih et al. 2022 Mehr
A growing body of work focuses on imitation learning in multi-
et al. 2023), with applications such autonomous driving (Bhattacharyya al. 2018) or robotic 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 II.) are therefore tempting and have been extended from their single-agent counterpart (Song al. 2018 Zhan al. 2018). However, they do not carry guarantees on the extracted policy in terms of robustness to the presence of strategic interactions.
interactions (Bogert & Doshi 2018:
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,/Freihauu 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 2002
Yin et al. 2021 Cai 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 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.
2

---

Published as a conference paper at ICLR 2026
3 PRELIMINARIES
3.1 MARKOV GAMES
We use the tuple G (S.
to define n-player Markov Game. Players in
[n] = [l....,. n take joint actions in A, x.... ..... A, while navigating a shared state space S. The dynamics of the system state distribution My E As. where Ac denotes the probability simplex over a space U. All players simultaneously take actions by sampling from their individual policy मं S + A A, The resulting joint policy is क = का X ... X Rn. also denoted by मं X т- where т- represents the joint policy of all players but i. Lastly, we define the reward function of player [n] as r; S x A - [-1, 1]. and define discount factor
described by the transition function P: S x A + As and the initial
[0. 1). We will use II = II1 x ... IIn to denote the set of joint policies T, with n, IT; for each E [m)]
A trajectory {(5t, az) 1220 of the policy starts in an initial state so Vo and successively samples joint actions at (-188) and future states 8t+1 ~ P(-|st, az) for every 2 0. This procedure induces the following state-only and state-action occupancy measures for every state E S, respectively:
Me (8) = (1 (1-7) Σ PP((s s),
(=(8, = Ma (s)
(=0
where (ss = s) is the probability of reaching state s after rolling out the policy a for t steps. Intuitively, (s) is the discounted visitation frequency of state after infinitely many steps. Similarly, Pr (s, a) is the discounted frequency of the state-action pair (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:
(s) 1
Vi [n],
where E ((..))=p. []] samples state-action pairs from the density function Pa- By extension, we also define V (v) = Eewn [V, for any state distribution v E As.
Markov Games extend Markov Decision Processes (MDPs, when n 1 (Puterman 2014)) to multi-agent games, where each agent has its own reward function. While in MDPs we consider policy to be optimal if it maximizes V (" the distinct individual rewards of 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 -- the performance of a player terms of average (discounted) rewards is measured with V/2 (up). Therefore, we can denote the set of optimal policies for player as the optimal policies in the MDP induced by T using the concept of best-response mapping. Definition 1 (Best-response mapping). For an agent i E [n]. the best-response mapping to m is defined as
(T. = arg max V -- (Vo))
Intuitively, when playing a best-response n| (R.(T= player i cannot improve by unilaterally deviating from ... 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 N is Nash equilibrium of the game if π is a product policy and each individual policy is a best-response to the other policies, i.e.
Tyy E (R,( Vi E [n).
As is common 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 equilibriæ from a dataset of trajectories sampled from a Nash equilibrium policy ा
(app
the expert policy.
'Or Vi (vo) using the notation above
An (approximate) e-Nash equilibrium T. is product policy where V."h E V. (vo) V, (vo) S for all
i [n], m IT.
3

---

Published as a conference paper at ICLR 2026
3.3 OFFLINE IMITATION LEARNING
Given a dataset of finite-length trajectorie producee G, imitation learning procedure aims recover "good" joint policy without access to the environment.
produced by rolling-out Th in a given Markov Game
Following the above discussion, measure the performance of ग with the following metric. Definition (Value gap). Given an expert policy xB of G. the Value gap of a policy π is:
ValueGap(m) == max (V:** (vo) v;" (vn))
This is essentially the maximum sub-optimality gap among the agents for playing n instead of the optimal expert x.. This value gap is the standard optimality metric used in single-agent MDP settings (Ross al. 2011 Foster al. 2024).
In the multi-agent case, however, the performance of individual players is usually not sufficient guarantee we use the imitation policy in an environment with strategic agents. Hence, 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 (Nash gap, see Ramponi et al. (2023), ). We define the Nash (imitation) gap of a product policy πt of the game G
NashGap(T) = max
( - V2" (v6)
with any xं (T-()
The Nash gap is a notion of maximal regret (Tang et al.] 2024) for the individual players. directly links to Nash equilibria an e-Nash equilibrium is any product policy II satisfying NashGap(T.) S e. Note that to ensure the imitation policy æ a product policy, suffices to learn all individual policies π; independently, for example through behavioral cloning.
In the general case, both ValueGap(T) and NashGap(TT are upper bounded by 12. as differences of cumulative normalized rewards. The goal of an imitation learning procedure is to leverage the expert data in order minimize these gaps.
Regressing on the training data, BC and Adversarial IL bring one the following error assumptions: BC Error from matching the empirical distribution of the individual agents, Measure Matching Error measuring a discrepancy in occupancy measures (state-only or state-action). They respectively defined
CBC == max E. ES-pEE (-]s - =-(((>))]
Cμ = M, f lla. and cp cp= 1l Pr ll
where Ee is the expectation with respect to the occepoccy induced by F
While general consistent and tractable upper bounds are known on the Value gap assuming either EBC or e, 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 x to Nash equilibrium.
More information about the connection between adversarial imitation learning and occupancy measure matching can be found in Appendix A
IMPOSSIBILITY RESULTS FOR EXACT MEASURE MATCHING
As first step to understand the difficulty of extracting Nash equilibria from expert demonstrations, we focus in this section on the idealized case exact occupancy measure matching. This 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:
'While consider stationary policies maximizing cumulated rewards an infinite horizon, II. usually assumes set of trajectories (ne of length 17x Geometric(1 - -?).
(ValueGap(T) < nepc/(1 (1 - 7) from the Performance Difference Lemma (see e.g. Xiao 2022 and
ValneGap(T) S <p((1 7) by Hölder's inequality.
4

---

Published as a conference paper at ICLR 2026
When does exact occupancy measure matching learn Nash equilibrium?
We start by showing that under the strong assumption of full-state support, exact state-action oceu- pancy measure matching (shortened state-action matching below) recovers 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. cp 0) is equivalent to assuming state-only matching (i.e.
S, = 0) and exact Behavioral Cloning (i.e. CBC = 0).
To make statement
precise, note that any policy x of a Markov Game partitions the state space into a visited region S = {s M4 (s) > 0} and an unvisited region S = (n = 0}. We prove that state-action matching (Ep = 0) and full-state support (S EE S) recovers the Nash expert, i.e. = ,² When the state-support is incomplete (S * S) or only statc-
(c = 0) holds, we can only guarantee the trivial bound NashGap(T) S O (1/(1- (1(11-))
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 actton occupancy measure P. on the visited region S We formalize this idea in the following theorem, and explain its implications for measure matching.
Theorem 1. Let n. T' E TI be such that px= = Pzt. Then, S = S and π (-18)) = x'(11) for every E S
The proof can be found in Appendix B.I
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 F on its state support St Assuming full-state support, we can then derive the following corollary for state-action matching.
Corollary 1. Let R π E 11 be such that St = S and P Pxi then, NashGap(T) = 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 #, = plx becomes insufficient to learn a Nash equilibrium.
4.2 INSUFFICIENCY OF STATE-ONLY MATCHING WITH FULL-STATE SUPPORT
In this section, 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 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 Nash gap linear the effective horizon 1/(1- - 7).
Lemma 1. There exists a game and corresponding expert policy R such that S S. Moreover, there exists policy such that 5 1bx and NashGap(T) Q (1/(1(1))
Proof. We prove this lemma by constructing an example of such game. Let G be cooperative two-player game with action sets A₁ A₂ {a1, ag). state space S = {so, $1, 52), discount term y, and uniform initial state distribution nu. The rewards and transition dynamics G are shown in and n II. Therefore, all policies
Figure I By definition, (s) (1 (1- (s) 0 for all have state support.
A Nash equilibrium of G is the constant policy π T a1 (s) 1 for all s S with uniform occupancy measure (,,=()) = 1/3. This 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
5

---

Published as a conference paper at ICLR 2026
else
(a1,00 a1)
else
80
clse
$2
80
82
(a1, a1)
81
(a1, a1)
1/3
2/3
(a) Description of the game transition dynamics, Note that tuple (as; aÿ) corresponds player playing a, and player 2 playing aj- Arrows represent deter- ministic transitions from a state to another.
(b) Description of the reward function. The number each arrow the reward associated with the responding transition. The rewards are same for both players.
Figure Cooperative two-player game G: the transitions and rewards are described by the left and right sub- sub-figures, respectively. In this game, there exists Nash equilibrium म with full-state support and a policy x such that UxE fy with a Nash gap linear in the effective horizon 1/(1 - 7).
Let the learned policy be the constant x ((a), a2)]s) = such that Mrr M and (2r) = T-7
2/3 Noting that V/2" (vu) T-7' this concludes the proof as:
NashGap(#) 2 V/r" (vu) - (vu) 5/3
2 Ω
1-7 1 1-7
Lemma 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 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 Nash equilibrium in general games. We draw on the example given by Tang et al. (2024 Figure 2) to point out issues from non-visited region ST F 0 and derive the following theorem.
Theorem 2. (Adapted from Tang et al. 2024 Theorem 4.3)) There exists Markov Game with expert policy π and learned policy such that even if P. Ps. the Nash gap scales linearly with the discounted horizon; i.e., NashGap(T) 2 (1/(1111)))) (0(1--1)) -)).
The key idea and intuition behind this theorem is that the imitation dataset misses information about the unvisited region ST An illustrative example of when this is undesirable is shown in Figure
We can design reward functions for the transitions of Figure such that the expert would always take the solid arrows.
8/2
Sexp
start
81
82
The dataset missing information about T (-1s)), best-response can lead to states s/ then Sexp- This last state Sepp be designed to incur high rewards for one player, while the expert region S incurs linear less.
Figure Transitions of two-player Markov Game. The unique initial state is 81. The rest of the chain (...) and reward functions can designed to induce linear Nash gap for state-action matching.
For completeness, adapt the proof of Tang al. (2024) for infinite horizon games in Appendix B.3

---

Published as a conference paper at ICLR 2026
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 however not sufficient as most II. 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, the function approximations in the non-tabular setting (Song et al., 2018 Wu et al. 2025 can only approximate the desired distributions.
the idcalized case of no learning error
This shift from an exact an approximate matching regime introduces new challenges. We know that the value gap always enjoys consistent and tractable upper bound of rate O (EBC/(L (1 7) (Ross& & Bagnell 2010) or ((cp/ (1 - 7)). However, we will demonstrate 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 to quantify the best-case Nash gap they might induce under approximation errors. Given approximation error, this quantity corresponds to the smallest achievable Nash gap among all the possible imitation policies т. Formally, we define follows:
Definition 5 (Tight Nash gap lower bound). Let G be a Markov Game and let I the set of Nash equilibria of G. We define the tight Nash gap lower bound for G with occupancy matching error ep as min x = xEM:p
cp)
min NashGap(T),
where (T)) {TT II: ||xx- Ep}.
For game G, given only the approximation error assumption Cp. mp(G, (p) corresponds 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 mp(Goar cp) given an arbitrary bimatrix game Gb and an arbitrary Ep E R4 is PPAD-hare
Proof outline. If computing this lower bound can be done efficiently, then it is also efficient to compute the support Nash equilibrium in a general bimatrix game. As we prove, the latter is PPAD-hard, so is 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 c-Nash equilibrium is PPAD compleo 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 ep is not 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 derive the following corollary on larger class of Markov games.
Corollary 2. The problem of computing mp(G, ep) given an arbitrary Markov game G and an arbitrary 6p E 124 is hPAD-hard.
We further note that the hardness results do not imply the impossibility deriving analytical bounds, for example involving min-max optimization problems (that are known to be hard to compute (Daskalakis et al.) (02T)). 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.
"See Appendix for formal details the PPAD complexity class.
7

---

Published as a conference paper at ICLR 2026
TRACTABLE AND CONSISTENT EXPLOITABILITY UPPER BOUNDS FROM BEST-RESPONSE CONTINUITY
In the previous section, we worked on 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 new notion of best-response continuity.
For general n-player Markov Games, the worst-case Value gap for given BC error (Equation 2) is given by a consistent and tractable uniform bound: ValueGap(1 I néBc/ - 7)² However, the exploitation nature of the Nash gap makes it impossible to derive such a bound for fixed error term. We reveal how this phenomenon, not present SA-II, characterized by form best-response continuity, leading to game-dependent bounds.
6.1 CHARACTERIZATTIN MARKOV GAMES VIA BEST-RESPONSS DELTA-CONTINUITY
We introduce below notion of continuity of the best best-response mapping of Markov Games that will allow us derive new general upper bounds on the Nash gap the next subsections.
Definition 6 (ó-continuity of the best-response correspondence). For given game G, the best-
response mapping is said to be ó-continuous at equilibrium π for some ô : IR - [0, 2] if for all i [n], and > O, we have:
EsSp E (1))- (+bs)) S
=
max I. (T-,(
E 5 (11)) - n. (+16)]] < 5(6).
This is notion related the maximal change over all E [n] of the optimal policy 5. E BR, when the induced MDP for player is produced by -hz instead of the equilibrium behavior x = This continuity will be used below to reduce the complexity of computing Nash gap upper bounds to computing valid This definition naturally extended for class of games as follows.
Definition (6-continuity of class of games). A class C of Markov Games 8-continuous if every game G &
C is 6-continuous at all its Nash equilibria.
Provided with a ô-continuous class of games, we will therefore be able to derive bounds without assuming specific game. However, we note that even for the class of games with consistent bound as presented in Section[4 we cannot guarantee more than the trivial ō(e) = 2 for > O.
Lemma 2. Let C be the class of games with consistent bounds. This class 8-continuous only for trivial 8 such that 5(c) for all > 0.
Proof. Suppose C is 5-continuous. For every >> 0, 7 E (0, 1), show that there exists two-player game G C with Nash equilibrium T where EBC can incur Eswn, (-1ss) of (+Is)]l 2 for some BR, (T2).
We let M2 be chain of ls (og(f(1-1)) log(?)
consecutive states and define its transitions as follows.
aj
any
start
80
M
Sexp
any
a1
of
Figure 3: Deterministic transition dynamics of a two-player game G, with states Sexp and sub-Markov chain Mg. Player has action space An {ai, o5} and player 2 has action space Ag {af, ag).
The rewards Tı, 12 are independent of aj and defined as:
ri af sexp) 1, ra(; ag seep) 1,
ri(: sexp) 1,
and r1 r2 otherwise.
8

---

Published as a conference paper at ICLR 2026
A Nash equilibrium of this game is the constant policy x ([a a5]ls) for all S. The expert such that Wx (8exp) I c/2. Therefore, the policy π (((11, a2) 8) = x ( a2) () # Sexp and T ((af, sesp))) = has BC error at most e.
best-response to T2 is the constant policy कं [a]]s) 1 for all s E S which incurs Es-p,E (i-1s) - मं [-1s)]l1] = 2. Note that G has a consistent bound for any error assumption (еBC = =0 =0# Ep = 0 + Cp = 0 for G, and S = 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 8 d-continuity where ō(e) = 2 for >> O. We study in this section the other extreme for 8: the constant (() = 0, before studying the general case in the next section.
In fact, we show that this special case corresponds 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 Th is (weak) dominant strategy equilibrium if for every player i, !. is weak dominant strategy, i.e.:
(vo) 2 V. A (vo) VT E II.
Note that the key property induced by the DSE assumption is that ,.." is best-response policy to any deviations -- for every player which corresponds to ó d-continuity of the best-response for 6(.) 0. This allows us to derive the following consistent and tractable upper bound on the Nash gap.
Lemma 3. Suppose π is (weak) Dominant Strategy Equilibrium. Then, any learned policy ι with BC error egc satisfies NashGap(TT S 2nc 77)
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.c. have:
NashGap(T) = max [. -- (vo) V.T.. ((vo)
Using Equation 3
we can add and subtract the expert value V. (v)) for every E [r]] and apply the performance difference lemma (see e.g. Xiao 2022 Lemma 1)) twice to get:
NashGap(m) s (1 7)
max E Eggn,R m
ग <-(s) = [|((([)) - (-1s))]
We conclude the proof using the definition of the BC error and the fact that both and are product policies. The formal proof is deferred to Appendix C.I
Note that when n = 2, this recovers the upper bound Freihaut et (2025) with a fixed BC error.
Providing such an upper bound allows assessing imitation policy posteriori, given specific BC error. As bound polynomial in the game parameters, we consider it to be tractable. Alternatively, we can interpret the bound criterion on the BC error to ensure fixed Nash approximation error.
Corollary 3. Suppose E is a (weak) Dominant Strategy Equilibrium; then, the recovered behavioral cloning policy an e-Nash equilibrium EBC <
<(1-1)
2n
Proof. This is direct consequence of Lemma dderived by inverting the Nash gap bound.
6.3 RELAXING THE DOMINANCE ASSUMPTION
Using a similar proof technique, we extend Lemma by assuming general best-response 5-continuity. This is demonstrated in the following lemma which prove in Appendix CC2
Lemma 4. Suppose the equilibrium expert is F and the game is 8-continuous at T Then, NT)hGap(TT < 2neae +51em:)
(1-7)²

---

Published as a conference paper at ICLR 2026
This is a generalization of Lemma where the DSE case is recovered by setting 8(-) 0. A numerical validation of the bound is provided in Appendix
Note that we do not claim that the above bound is tight due to worse-case guarantee. However, this characterization of the Nash gap with d-continuity offers several advantages.
Properties of the bound. Consistence and tractability properties the bound are directly related to the properties of the ö function: the bound is consistent if 6(0) = 0 and it is traciable if itself is tractable. Lemma 4 then provides the key insight that deriving exploitability upper bounds reduces to (2025) obtained via a change measure, our bound doesn't necessarily become vacuous if strategic deviations the imitation policy explores regions of the state space not visited by the expert. In fact, 6-continuity of games serves as spectrum to characterize their sensitivity to perturbations at equilibrium points.
characterizing ó for the considered game.
On the sensitivity of game equilibria. In comparison to the previous bound of Freihaat al.
The first extreme case is 8()) = 0 that corresponds to games with only dominant strategy Nash equilibria. This assumption essentially reduces the Nash gap computation Value gan, recovering the known bound ValueGap(1) I négc/ (1 - 7)2 for single-agent behavioral cloning (Ross et al. 2011) up constant factor 2. The other extreme is d-continuity with the constant 8(-) reducing to trivial upper bound greater than 2/(1 - 7) and achieved by the limit of pathological games, as shown with the example given the proof of Lemma
Intuitively, a well-behaving 8 can be imposed by regularizing the game, essentially smoothing the best-response map by promoting exploration (Ahmed et al.) [019 Geist al.) 2019). Furthermore. we note that large discontinuities in 5 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 8 functions. We provide additional numerical validations of the impact of entropy regularization on ô-continuity in Appendix B
CONCLUSION
In this work, we consider the problem of learning Nash equilibrium from a given dataset of expert demonstrations in a multi-agent system. Assuming a Nash equilibrium expert and a given imitation learning еπгоr (BC or measure matching), guarantees on the Nash gap of the learned policy. In the idealized case of exact measure matching, 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 present in the single-agent case. For behavioral cloning, 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.
study the derivation of both consistent and tractable
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 al. (02T)), inspired by online II. (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-2423 134, the Army Research Laboratory (ARL) under grant number 1NF-126-6--0000 and institutional support from EPFL.
'The joint policy can be viewed as single-agent policy with hehavioral cloning loss (Fquation upper bounded by nepc (see Lemma D>2 in Appendix).
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Pieter Abbeel and Andrew Y Ng. Apprenticeship learning via inverse reinforcement learning. In
Proceedings of the twenty-first international conference on Machine learning. pp. 2004.
Zafarali Ahmed, Nicolas Le Roux, Mohammad Norouzi, and Dale Schuurmans. Understanding the impact of entropy on policy optimization. In International conference on machine learning, pp. 151-160. PMLR, 2019.
2019.
Pragnya Alatur, Anas Barakat, and Niao He. Independent policy mirror descent for markov potential games: Scaling large number of players. In 2024 IEEE 63rd Conference on Decision and Control (CDC), pp. 3883-3888. IEEE, 2024.
Raunak P Bhattacharyya, Derek J Phillips, Blake Wulfe, Jeremy Morton, Alex Kuefler, and Mykel Kochenderfer. Multi-agent imitation learning for driving simulation. In 2018 IEEE/RSJ Interna- tional Conference on Intelligent Robots and Systems (IROS), pp. 1334-5339 IEEE, 2018.
Kenneth Bogert and Prashant Doshi. Multi-robot inverse reinforcement learning under occlusion with estimation of state transitions. Artificial Intelligence, 263:46-73, 2018.
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 Neural Information Processing Systems, (6.36364-364000 2023.
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), pp. 18668-18675. IEFE, 2025.
Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player nash equilibria. Journal of the ACM (JACM), 56(3): 2009.
Scoyeon 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. /4380, 2025.
Vincent Conitzer and Tuomas Sandholm. Complexity results about nash equilibria. CoRR, cs.GTT70000074 2002.
Qiwen Cui and Simon S Du. When offline two-player zero-sum markov games solvable? Advances in Neural Information Processing Systems, 35:25779-25791, 2022.
Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. The complexity of computing a nash equilibrium. Communications of the ACM, 52(2):29 97, 2009.
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. In Proceedings of the 53rd Anmual ACM SIGACT Symposium on Theory of Computing, pp. 1466-1478, 2021.
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.03855 2016a.
Chelsea Finn, Sergey Levine, and Pieter Abbeel. Guided cost learning: Deep inverse optimal control via policy optimization. In International conference on machine learning, pp. 49-58. PMLR, 2016b.
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: 37:12060 120666, 2024.
Till Freihaut and Giorgia Ramponi. On feasible rewards multi-agent inverse reinforcement learning. In The Thirty-minth Annual Conference Neural Information Processing Systems, 2025.
11

---

Published as a conference paper at ICLR 2026
Till Freihaut, Luca Viano, Volkan Cevher, Matthieu Geist, and Giorgia Ramponi. Learning equilibria from data: Provably efficient multi-agent imitation learning. In The Thirty- Annual Conference on Neural Information Processing Systems, 2025.
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-4034 2021.
Matthieu Geist, Bruno Scherrer, and Olivier Pietquin. A theory of regularized markov decision processes. In International conference on machine learning, pp. 2160-2163 PMLR, 2019.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farles Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. Communications of the ACM, 63(1 1):139-144, 2020.
Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning, Advances in neural information processing systems, 29, 2016.
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.
Xiaomin Lin, Stephen C Adams, and Peter A Beling. Multi-agent inverse reinforcement learning for general-sum stochastic games. arXiv preprint arXiv:1806.099: 2018.
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.
Eric Mazumdar, Kishan Panaganti, and Laixi Shi. Tractable equilibriumm computation in markov games through risk aversion, 2024. URL htt.atppee/aaxiii.rrr///////////
Negar Mehr, Mingyu Wang, Maulik Bhatt, and Mac Schwager. Maximum-entropy multi-agent dynamic games: Forward and inverse solutions. IEEE transactions robotics, 3903)1180111815, 2023.
Kartik Nagpal, Dayi Dong. Jean- -aan-tBptiste Bouvier, and Negar Mehr. Leveraging large language models for effective and explainable multi-agent credit assignment. arXiv preprint arXiv:2502.16863 2025.
Andrew Ng. Stuart Russell, et al. Algorithms for inverse reinforcement learning. In Icml, volume 1, pp. 2, 2000.
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.
Tim Pearce, Tabish Rashid, Anssi Kanervisto, Dave Bignell, Mingfei Sun, Raluca Georgeseu, 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.
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, pp. 1321-1329. PMLR, 20155
Dean A Pomerleau. Efficient training of artificial neural networks for autonomous navigation. Neural computation, 3(1):88-9) 97,89991111 1991.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Giorgia Ramponi, Pavel Kolev, Olivier Pietquin, Niao He, Mathieu Laurière, and Matthieu Geist. On imitation in mean-fiel games. Advances in Neural Information Processing Systems, 36: 40426-40437, 2023.
12

---

Published as a conference paper at ICLR 2026
Stéphane Ross and Drew Bagnell. Efficient reductions for imitation learning. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 661-668. JMLR Workshop and Conference Proceedings, 2010.
Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pp. 627-635, JMLR Workshop and Conference Proceedings. 2011.
Andy Shih, Stefano Ermon, and Dorsa Sadigh. Conditional imitation learning for multi-agent games. In 2022 17th ACM/IEEE International Conference on Human-Robor Interaction (HRI), pp. 166-175. IEEE, 2022.
Jiaming Song, Hongyu Ren, Dorsa Sadigh, and Stefano Ermon. Multi-agent generative adversarial imitation learning. Advances in neural information processing systems, 31, 2018.
Peter Sunchag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Z. Leibo, Karl Tuyls, et al. daloosdecomoositionn networks for cooperative multi-agent learning. arXiv preprint arXiv: wwXiv:/706.05296, 2017.
Jingwu Tang, Gokul Swamy, Fei Fang, and Zhiwei S Wu. Multi-agent imitation learning: Value is casy, regret is hard. Advances in Neural Information Processing Systems, 37:27790-278111 2024.
Bernhard von Stengel. Algorithmic game theory.
http:/ //wp://www... ma ths sse. aese.ac... / Accessed: July 10, 2025.
1 ////E/EE//ttteee /TSXTE/agt--ttengell .pdf
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 Databuses, pp. 139-156. Springer, 2021.
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), pp. 1547-1553. IEFE, 2025.
Chen-Yu Wei, Yi-Te Hong, and Chi-Jen Lu. Online reinforcement learning in stochastic games. Advances in Neural Information Processing Systems, 30, 2017.
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.
Lin Xiao. On the convergence rates of policy gradient methods. Journal of Machine Learning Research, 23(282):1 2022.
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):440444466 2023.
Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal provable uniform convergence offline policy evaluation for reinforcement learning. In International Conference Artificial Intelligence and Statistics, pp. 1567-1575. PMLR, 2021.
Eric Zhan, Stephan Zheng, Yisong Yue, Long Sha, and Patrick Lucey. Generative multi-agent behavioral cloning. CoRR, 2018.
13

---

Published as a conference paper at ICLR 2026
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, PPAD 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.
has been shown that computing Nash equilibria is
We define below the PPAD class introduced by Papadimitriou (1994) and related to some of our negative results.
Definition (PPAD class). search problem II belongs to the complexity class PPAD (Polynomial Parity Arguments on Directed graphs) and only if is polynomial-time reducible the End-of-the- Line problem defined as follows:
End-of-the-Lite Problem
INPUT:
A directed graph G = EV implicitly represented by two polynomial-time computation mutually inverse functions and
-P:V maps every vertex v E to its unique predecessor, or itself.
S:V V maps every vertex U V its unique successor, or itself.
A source vertex V such that P(s) = s and ((s) +
OUTPUT: Either sink vertex 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 the parity argument: in any directed graph where each vertex has at most one incoming and one outgoing edge, there exists source, there must exist either another source or sink. Therefore, the End-of-the-Line problem always has a solution.
It is believed that PPAD is not part of and hence PPAD-hard problems believed intractable.
A.2 GAIL AND OCCUPANCY-MEASURR MATCHING
Generative Adversarial Imitation Learning introduced by Ho & Ermon (016) equivalently solves the following Inverse Reinforcement Learning (IRI.) problem
(RL = arg max (c)( + min - HH() + E, /css, a)) - E, [c(s, a)] Fell
oEC
for a cost e followed by standard Reinforcement Learning (RL) for policy extraction
RL(c) = arg min - ((T) + Ex (c(s
well
RSXA R U foo} a convex cost function regularizer, and ( = 1- π [a]s)] the causal entropy policy म. Their key innovation is to show that for particular instance of tb, both problems can be solved simultancously by training a discriminative classifier D : S x A - (0, 1) and a generator policy E II GAN-like (Goodfellow al. (2220) manner. For non-restricted = R
with sets C, II constrained by modelization expressivity,
exchange the max-min for a min-max (Ho & Ermon 2016 Garg et al. 1021) and end up with the following practical optimization formulation:
min max Ex (olo((((ss a)) + E, log(1 - D(s, - #ETI ()x
where À is regularization factor.
14

---

Published as a conference paper at ICLR 2026
This problem in particular is shown to be equivalent to the following regularized state-action oceu- pancy matching objective: ming (Pr Px=) - XH (T), with DJs denoting the Gensen-Shamme divergence.
In the more general case. Ho Ermon (016) propose that imitation learning can be done by state-action occupancy measure matching problems of the form:
min v/" (pa p= (T))
where the entropy regularization makes the optimal BC policy unique and vf denotes the convex conjugate of vb.
B PROOFS OF HARDNESS RESULTS
B.1 PROOF OF THEOREM 1
Theorem 1. Let n. T' be such that Ps Pxt. Then, 8 S and x-|ss) T'(ss) for every E St
Proof. Let π. x' be two policies such that Pr Pr' We will first prove that S = S then prove that the policies are equal the visited region S
The policies ,, n' visit the same region of the space state.
Suppose towards contradiction that there exists some 8 E S such that 8 E S# and & & St. Since (-|ss) 9) is probability distribution, there must be action a E A such that (als)) > 0. Hence Pr (a, s) > 0 but Par (a, s) = p (s) n/ ()ss by assumption. This is contraction since Pr Pr', hence S S
2) The policies n, n' are equal on their shared visited region.
We again proceed with proof by contradiction.
Suppose there exists A and S such that ((ass) + (a)ss) Since Pm (a(as) s) par s).
(s) > 0, (s) > 0 and (als) o x' (als), we must therefore have (*(() # Mr (s).
Without loss of generality, assume μ+ (s) > (s): thus, for all a' E A. <a'lss) < (a () by the equality of the state-action occupancy measures.
This is contradiction since that would mean
Σ
T(alls) Σ <''lss) =1
e'EAA
a'EA
but (-1s)) is probability distribution.
B.2 PROOF OF NASH EQUILIBRIA FOR THE GAME IN FIGURE
We want to show that x ((a1, (1){s) 1 for S indeed a Nash equilibrium of the two-player game described in figure Figure
Suppose towards contradiction that = is not Nash equilibrium, as some player {1, 2} is better off from unilaterally deviating. By the performance difference lemma (Lemma D.I. there must exists a state s E S with positive advantage
E A (a' s) " (s,a',a-t) -.Te (s), with a- 01
when the player i chooses a' = a2 and Q (s,a', = Ti(s,a',a)) + Eves P(5l(s, (s').
15

---

Published as a conference paper at ICLR 2026
This is contradiction since, when fixing a' a22 for all E S we have
AT (a' = ri(a" + a fa - V. 7 (s,a',a =- (1-1)) V) + (a',s)
S , (n',
Which is contradiction as we assumed 17 (a', 8) > 0. Hence N is Nash equilibrium.
B.3 PROOF OF THEOREM 2
Theorem 2. (Adapted from Tang al. 2024 Theorem 4.3)) There exists Markov Game with expert policy x" and a learned policy a such that even if Px = Pa. the Nash gap scales linearly with the discounted horizon; i.e., NashGap(1) 2 (1/(1 -0-)) -)))
The proof below has been extracted from Tang et al. (0244 and only slightly adapted for infinite horizon games.
Proof. We explicitly construct a two-player common payoff Markov Game with infinite horizon and common action space A; {a1, 02 03) } for each agent 1,2. The state space is countably infinite and ordered.
The action-independent (shared) reward function is defined r((:) 1 if i is odd, and r(s.) 0 if i is even. The transition dynamics are described in Figure 4
(a2, a1)
all
81
$3
85
82k-1 1
(a2, a1)
clse
80
else
all
all
$4
$2k
Figure 4: Transition dynamics for the two-player game. so is the initial state. The top branch contains all odd states while the bottom branch together with sg comprises all even states.
We define the expert the Nash policy B such that π ( = 1, aT ( ((a3,()))))) = 1 and the actions for the other states are arbitrary.
Similarly, we define the trained policy such that plays the same as the expert on the other states.
and ( (1)[s1 = and
In this case Pa E but
NashGap(T) 2 VT ViT(s))
2 Ω
1
1 1-
1
where
if a 02 and E (80, 81)
(a=
af + 02 and E (s0, 81 otherwise
m (a=1s)
16

---

Published as a conference paper at ICLR 2026
B.4 PROOF OF THEOREM!
3
Theorem 3.
The problem of computing mp Ep) given an arbitrary bimatrix game Gb and an arbitrary E 4 is PPAD-hard "
Before proving Theorem 3 let us prove the following intermediary lemma. This will allow us to conclude by doing reduction to the problem of finding e-Nash equilibrium.
Lemma 5, Finding an e-Nash equilibrium support in a general bimatrix game is PPAD PPAD-complete.
B.4.1 PROOF OF LEMMA
Before proving Theorem 5 we introduce below 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 bimatrix game to the problem of finding support. The other direction trivial.
Let G = (A1. A2) be a bimatrix game with payoff matrices A; for each player i E (1,2}. For simplicity we further assume that A2 R"** (i.e. both players have the same number of actions v.).
Let mi n2 the unknown policies at equilibrium of our game, with respective supports v1, M2 S {1, (1.....n) Using our support finding oracle, we compute v1, V2 from the payoff matrices.
n).
We note that from the definition of Nash equilibrium, क a best-response of player 1 to player having policy т2. This means:
प A1 max A1,i T = A1, Tmy AL, 22 En
and similar argument holds for 72, this known as the indifference principle.
Using this, we can rewrite the problem of finding Nash equilibrium as follows:
Find
y
E R
P1
[22
s.t.
Σ
Σ yi =1
1=1
t=1
(A2,)
)2,x) T 0
Vj, v2
(Ai.) AI,x) y== Vj,keM
24 0 Vi 1/1
/ 2 Vi E 122
This is linear program that can be solved in polynomial time. By solving this optimization problem we recover Ii x and 2² (see also Algorithm 3.4 in von Stengel), which is valid with our assumptions equilibrium supports M2,
However, shown in Chen et al. (209),, finding an equilibrium of a bimatrix game is PPAD- complete. This concludes our proof by showing that finding the support Nash cquilibrium in general bimatrix games is PPAD-come 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
"ee Appendix for formal details the PPAD complexity class.
17

---

Published as a conference paper at ICLR 2026
Find
E
RM,,
y
Rl
11
|22
Σ Ij
Σ
s.t.
1/4 =
1=1
1=1
(A2.5 x2,)) S Vj,k
(A1, A1,)) T 3 S Vj,kEn
(A2,x - T SSE Vi,k
(A1, - T US 4j.kEn
32 2 0 ViEM
y: 20 vi E
This allows finding an e-Nash equilibrium which is also known to PPAD-complete 2009). The other direction is trivial.
Chen et
B.4.2 REDUCTION FOR THE PROOF OF THEOREM
Recall the statement to prove
Theorem 3. The problem of computing mp(G Ep) given an arbitrary bimatrix game Gm and an arbitrary& cp E 1R4 is PPAD-hard
Proof. We prove the result by polynomial reduction from the problem of finding the support of
an e-Nash equilibrium in a general bimatrix game the problem of computing mp(Gmi 6,) for any Gai. 6p- Note that in this one-state game, the state-action occupancy measure is equal to the policy distribution. We assume max;, max[[Arspl- A2i,i < 1. it's not the case, suffices to divide the payoff matrices by 2 and apply the same argument for ep/
Assume access to an oracle L(Gni; e) for mp for any Gm = (Ai, A2), ep R.. We will show that polynomially many calls to this oracle are sufficient to find the support of any e-Nash equilibrium of Gbi- Specifically, Algorithm| I deseribed below is sufficient for this task.
To prove this fact, it suffices note that replacing AK by A for any & {1,2), E [n] changes the value the lower bound only if .R. for every s-Nash equilibrium π with supports supersets of V/, Formally, let II be the set of policies minimizing the Nash gap with the imitation enror e:
I min
arg min मاا - =f -1 NashGap(T1, Nas m2),
and arrange the set in lexicographic order of the concatenated indicator vector encodings of the supports of the two players. We show that (2), is equal to the first element of TI which we denote (v), ug).
Let j E 21, be a fixed player, then for every [n]:
Case i E My: then there doesn't exist any element with smaller lexicographic index in Ih Hence, 2/ Er..
Case i $ My: then there must be an equilibrium such that player takes action i with null probability. Hence, v C Mj
Thus, Vi = = and (Pi v2) are valid supports for an e-Nash equilibrium.
Applying Lemma 5 allows us to conclude that finding L is a PPAD-hard problem.
*See Appendix A for formal details the PPAD complexity class.
18

---

Published as a conference paper at ICLR 2026
Algorithm 1 Lower bound reduction
Given game 1, A2 and target Nash precision
Define AI = A1. A = A2.
Define K such that -1 K - mwwpmaaxxaia A2
Define 11 = = 0.
Define 8 ||c/K eill1 such that L((A1, A2), 6) S c, for canonical vector e1-
for i E {1, , ,n) do
Define Af such that
{Ai)a.b {AP)ab Va,b e [n] \ {t} [n]
{Ai}; = K
Use the oracle to compute 1 L((AA,()))
i > s then
1/1 11 (t).
else
A + Ai.
for i E {1,....
, fl,...,n} do
Define A3 such that
(Ab {A Va, e [n] {i} [n]
(A)): = K
Use the oracle to compute 1/ T((AA1, (((AA,Ab)))) if 12 > then
1/2 + (i).
else
A/ Ag.
Return V1,42
C PROOFS OF UPPER BOUNDS
C.1 PROOF OF LEMMA 3
Lemma 3. Suppose E is (weak) Dominant Strategy Equilibrium. Then, any learned policy π with BC error egc satisfies NashGap(T) 2nc (1-7)²
Proof. Following the proof outline from the main text, we use the Dominant Strategy Equilibrium assumption to simplify the Nash gap follows:
NashGap(z) = max V. t *(V)) V.T.. ((26) = max [ ((vo) - V. Fu. (vn) (,5,
We can then add and subtract the expert value for every player, and apply the performance difference
lemma (Lemma D.I twice:
NashGap(T) = max
V x- (vo) - -V....--((n) (V,))-V,..."-100
V E x ((V)) - V.T² (vo) 1,
1-:7(((10) (vo) V.T. (vo) (=((s -
max
max Eswu
(s.0 ボ (a)(ss)))) (a:ls))
max BE Espp,E #
where the Q-functions defined in Lemma
D.1
19

---

Published as a conference paper at ICLR 2026
Now upper bounding the Q-functions using ||QT 1lo0 11((1 7) for any policy x'' E II:
NashGap(T) v (1 -)²
max B [-|s( x (-1s))] + +| - [-
Using Lemma D.2 we conclude,
(2n - 1)cRC
2TERC
NashGap(T) <
(1 7)2
(1 7)
C.2
PROOF OF LEMMA 4
Lemma 4. Suppose the equilibrium expert is Th and the game is 8-continuous at x F. Then,
NashGap(T) S 2nemc+ +5(ssc)
(1-7)²
The key is to use a very similar construction as for the proof of Lemma 3 leveraging the triangle
inequality to introduce the slackness 6(EBC).
Proof. Using similar arguments, we apply Lemma D.1 and get:
1 max Bowa,n
NashGap(m) I
(-Is) x (+1s)) + [[(m) m - = (+[s)]]]]
(1 7)2
Them conclude using Lemma D.2 and our assumption:
NashGap(T) < (2n 1)eBC + 5(ecc)
2ne + d(EBC)
71
(1 7)-
D ADDITIONAL LEMMAS
Lemma D.1 (Performance Difference Lemma, see e.g. Theorem IX.5 in Alatur al. 2024 ) For any n, x' E II, E [n).
Vila ((v)) V.N,,-- = 1-7 E. Baarp _ (s, (s),,
where Q (8, = (x) + + EvEs (()1),,)VV?()))
And more generally,
(PO) - (P6) = 1- E BRaap (Q) - (s)),
Proof. See proof of Theorem IX.5 in Alatur et al. 2024).
Lemma D.2. Let n E N, and pis qi Am, be probability distributions over discrete set of
size my isomorphic to [m.). Further, note p x² T=1Pss = x x Then,
Σ
- s ΣΣ (x()) a()
JE [m)] ((m.)
==
Proof. We proceed with proof by induction.
The statement trivially holds for n = 1. Assume it holds for n, we show that also holds for m 1. For simplicity, note S,, x__[mm, and nd x xhi
x x
20

---

Published as a conference paper at ICLR 2026
E
(p() - - = E E
11"(iipa+t())) -1 (n (12)
JESn (ma+11)
Σ
E
(p"(i)pnnt((a))) (i))))nn+11)))
11 Jo [
o' (ii)Pat1 (12) - ("))""())nn)) (J2)
< Σ
E
(((i)Pn+((2))
J1 ES mm(ma)
Σ
E
1dt (iii)oo+1 -
hES fm
Σ
(n((1) - ("(i+)
E
Pn+1(j2) gn+1 (f2)
52e|ma+1]
pi(i) :0(i)l
P (f2) 9a+1 (72)
jo [m]
a+1 my
p:(i) 2
E NUMERICAL VALIDATION
To better illustrate how our theoretical insights related practical empirical settings, in the following, we provide the example of a game in which a tight 8 function can be estimated from data.
Below, show two main properties empirically: (1) show that theoretically-derinn bound indeed holds, (2) we show the impact of entropy- cerropy-reuularization 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.
upper
For both experiments, 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 y 0.8. For each time step f, one the player is the tagger, whose goal is hit/collide with the other player who is then being chased. When the collision happens, the roles are inverted. The action spaces A₁ A₂ {0, 1, 2.233 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 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 - using a Nash Value Iteration algorithm (see e.g. Perolat et al. 5). Then, we perturb the equilibrium at every state with different noise levels to randomly generate a set BC policies. For each imitation policy n' we compute its empirical behavioral cloning error εÿ using 2 103 episodes estimate the expert state distribution. We can then again apply value iteration in the induced MDPs to compute best-responses and estimate tight delta function.
21

---

Published as a conference paper at ICLR 2026
E.1 ON THE VALIDITY OF THE UPPER BOUND (LEMMA
Following Definition 6 we compute a tight ė by taking the cumulative maximum of the expected LI 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 400 noise levels evenly sampled from [0, 0.4], and fixed temperature of 0.1 for computational efficiency. In Figure we show how in this simple setting d increases when Egc increases, well as the NashGap.
Comparison of tight delta computation and tight Nash gap (r=0.1) 0.11
Nash gep upper
0.5
volue
0.2
0.3
0.0
0.7%
0.30
0.00
Estimate Behavior Claning Emror Esc
Figure 5: Evolution of the tight Nash gap upper bound and the tight 8 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 increase together with 8. Our upper bound, being greater than 0(CBc) 2 with H 1/(1 7) 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 uniform on the class of d-continuous games, thus corresponding worst- case scenario. In particular, the f72 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 tight estimate of 5(CBC) for various BC errors. Related the ideas mentioned Section 6.3 we vary the entropy regularization factor and show its impact on 8.
In Figure 6a we run the experiment by generating 250 BC policies on large range of [0. 1.0) for the noise levels. This reveals that increasing the temperature tends to lower the ò(Cgc) when <BC E [0, 1] for the simple Tag-Game environment. However, we note that fixing a game G, this does not necessarily mean that the NashGap is reduced by increasing the temperature, since our upper bound Lemma is not tight for G in general.
The appropriate éвC scale of importance ultimately depends on the application, the trajectory budget, expressiveness of the imitation model, as well as other factors, the tabular setting, where EBC Ry 10 10-2 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 Figure 6b
For practical work, this matters because when humans used experts, often assume entropy regularization to model humans' irrationality. Having a sense how this can also help control the exploitability of the imitation policies is therefore important.
22

---

Published as a conference paper at ICLR 2026
BelLACE Chiingg
(a) Large range of
(b) CRC at scale 10-2
Figure 6: Evolution of the tight for different entropy temperature parameters. This shows that greater temperature leads better control on 8. This behavior is consistent the full range of EgC values.
For theoretical work, this useful as tells us that beyond simplifying the analysis of optimal policies, entropy regularization might also lead to better guarantees the worst-case Nash gap.
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 T- by 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 tuple (S, P, (ra ) Vo. H). The discount factor y has been replaced by finite horizon E N. Further, rewards and policies of this game now time-dependent: for all f, rewards now denoted rf : S x - [-1, 1] and policies become non-stationary क. + 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 of state and state-action pair, respectively.
p4 (s) Pps
p (s, a) 2² (s)="(a)))))
This allows the definition of time-dependen value functions follows
#-1
(x)(s) = Σ
Fo Vi E [n].
h=t
For of notation define V. (s) (s) for all E S and policy Again, the definition of value functions is extended (v) for any distribution As.
1.1 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 eBc. := maxi, Espp'' (T.ss) (-)
23

---

Published as a conference paper at ICLR 2026
Measure Matching Error: Error matching occupancy measures.
State-only occupancy measure: E/ == max, | 1
State-action occupancy measure: Cp = max; | Prelli lh
F.2 PERFORMANCE DIFFERENCE LEMMA FOR FINITE HORIZON
In this section we adapt the previously stated Lemma D. to finite horizon Markov games. This will allow generalize the results of the paper in Appendix
Lemma F.1 (Finite horizon version of Lemma D.I
For any n. o''S E II, E [n].
H-1
Vi (1b) - -V, V,m,, (mo) =
Σ Bsaap
[Q.((,,)) V[T(s)]+
1=0
where (s, = (s, + Eves
And more generally,
H-1
V (vo) (vo)
Σ
Bsa (s) -V7((s)
Proof. We only prove the first version. The generalization can be proven by the exact same construc- tion.
To simplify, given a policy स we overload the notations of the Q functions as follows. For every player i E [N] we denote the state-actions values of in the MDP induced by #- as:
(8, a:) Pa-iaa-a (a(le) (r)(s)) + Ry (V))1
SESS H
Now, let 0 < < H - 1. Developing Vi - (m)) for any distribution E As we have
V.L 1,6
(w)) V.l (w1) Eowe (1))) (s, + Eonn (1)) (s,
-Esnn (11))) 100 as.
Beom (1+) [0,, ai)] Barmmaare [0T,((s a:]]
(1+1 (M++1) (++1 ( + HR Esrn
[8,, a:)]
where 1/41 E As is the distribution over the next state after following policy (5/, m-)).
Subtracting (v:) on both sides and applying the recursion we get for the initial distribution
H-1
point (po) (TT
E Es
(Eaint (8, v(((s)
where we recognized Pt ~ u
Rearranging the terms gives the final result
H-1
V (vo) - V,tt:-(((0)) = Σ E
Be (afo-1))
(s, (s)
0=
F.3 RESULTS
For completeness, we reprove below our results now considering finite horizon games. The counter- examples remain largely the same, well as the proof structures.
24

---

Published as a conference paper at ICLR 2026
F.3.1 SECTION 4
Lemma F.2 (Finite version of Lemma D. There exists a game and a corresponding expert policy Th such that gE = S. Moreover, there exists a policy g such that Ux = fax and NashGap(T) 2 (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
Th and a learner policy n such that even if p R psm for all 0 S t H - 1, the Nash gap scales linearly with the horizon; i.e. NashGap(T) (T) 2 2 (H).
Proof. The proof is exactly the same in Appendix (therefore still countable).
B.3
except the state space which is finite
F.3.2 SECTION 6
Let C be the class of games with consistent bounds. Lemma F3 (Finite horizon version of Lemma D).
This class is d-continuous only for trivial 5 such that ō(c) = for all >> 0.
Proof. A similar proof to the one provided in the main text is valid for the finite horizon case. suffices to adapt the & for the finite horizon, ensuring we keep the property Px (Sexp) t/2.
Lemma F.4 (Finite horizon version of Lemma 3) Suppose T is (weak) Dominant Strategy Equilibrium. Then, any learned policy π with BC error bpc satisfies NashGap(T) I 2n.
Proof. The Dominant Strategy Equilibrium assumption gives:
NashGap(1) = max [,
V
*(vo) - V.T... (vo)
a (vo) Vire (vo) + V.Te (vo) - V, (
max
Fixing i, we apply the Performance Difference Lemma (Lemmal F.I to get:
H-1
Vi"" (vo) - V,m..T- =
E Exaapp Σ
R (Q),(ssa) - ViT((s)]
t=
Σ
E E
Eei((s,)) (T =<(ass))
t=
H
<
E Banue
[-10) - (e(-)))]la]
< H22
E Bani [1| =111
max USISH-
where the Q-functions are defined as in Lemma F.I
Similarly, applying the PDL in the reverse order,
4-1
(pO) v.ae (20) =
E s.a
v 6it
E m (s)
- 0 af (s.
t=
E Egnp ø
Σ o (s, (s) - (a,s())s)) rff()).ls)
1=0
H-1
H
E Eany's
H2
Eanpy e [|T== - ==((((1))1]]
max
0515H-1
25

---

Published as a conference paper at ICLR 2026
We conclude using Lemma D.2
NashGap(T) S (2n 1)EBC H22 - 2nencH2
Lemma F.5 (Finite horizon version of Lemma 4). Let a be the learned policy, and assume for all i [n] and 0 S t S H - that Ey x [ n E. (+)((l s ((((<BC)) for some function ö,
where पे E (T). Then, NashGap(T) & (2negc + 5(esc)) H²
Proof. Using similar arguments, applying Lemma E. and Lemma D.2
NashGap(T) & max
max 0S1SH-1
E Bonue x [|] - me(-1>)l11]
E, B [| (11)) - (m (1a))11))))))) H²
max 051SH-1
S ((2n L)EBC + 8(Enc)) H²
S (2nEBC + Ö(EBC)) !!²
26


Reviews:
[{"review_id": "gNe1y9YF3I", "reviewer": "Reviewer_ngLP", "summary": "This paper investigates the theoretical limits of learning Nash-equilibrium-like policies from expert demonstrations in multi-agent imitation learning (MA-IL), especially in offline settings.  The authors first prove impossibility results, showing that even exact occupancy measure matching may lead to highly exploitable policies in general Markov games.  They further establish the PPAD-hardness of computing tight lower bounds on exploitability, linking the challenge to classical game-theoretic complexity.  Finally, the paper introduces a novel concept of best-response δ-continuity, allowing derivation of tractable and consistent upper bounds on the Nash gap—particularly under dominant strategy equilibria (DSE). The results unify several prior observations and provide theoretical guidance for designing robust MA-IL algorithms.", "questions": "Please address the concerns in Weakness, especially that related to empirical validation", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper presents a strong theoretical contribution, providing clear impossibility and hardness results that formalize the limits of multi-agent imitation learning (MA-IL).  \n- The proposed δ-continuity framework is a novel and interesting concept that bridges equilibrium stability and policy learning theory.  \n- The PPAD-hardness argument is rigorous and well-motivated.  \n- The proofs are detailed and supported by illustrative examples (though I did not check all the details).  \n- The work clarifies when common imitation learning methods (such as BC and GAIL) can or cannot recover equilibria, which is of both theoretical and practi", "weaknesses": "- My major concern is that, although the paper is theoretically strong, it lacks empirical validation to demonstrate how the theoretical insights (e.g., δ-continuity effects and dominance structures) manifest in practical game settings.  \n- The theory assumes access to known imitation errors (e.g., Equation 2), but it does not discuss how these quantities can be estimated or bounded in real applications.  \n- The assumptions of dominant strategy equilibria (DSE) or δ-continuity, while mathematically elegant, are quite restrictive and may not hold in general-sum or more complex multi-agen", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Hv6bI9Rkck", "reviewer": "Reviewer_itJa", "summary": "This theoretical paper studies multi-agent imitation learning with the goal of recovering a Nash equilibrium from demonstrations generated by an expert equilibrium. Exploitability is defined as the distance of the learned policy to a Nash equilibrium, and the authors derive both consistent bounds, which vanish with imitation error, and tractable bounds, which can be efficiently computed. They show that even perfectly matching expert occupancy measures can yield exploitable policies, proving the impossibility of deriving consistent Nash equilibria or tight tractable exploitability lower bounds in general Markov Games. To address this, they introduce the notion of best-response continuity, which allows constructing tractable upper bounds and provides conditions under which consistent and tractable Nash gap bounds can be achieved.", "questions": "* Having tractable bounds is nice, so why not craft a scenario where the last bound involving delta is tractable and show empirically how tight or simply how informative it is, in a simple toy application?\n* I believe the paper provides important and sound theoretical contributions, and that the exposition is such that even non-seasoned researchers can learn valuable concepts from it. That being said, the ultimate bounds derived in the work provide limited intuitive value. Adding practical “knobs” that give insights as to how to control such bounds could go a long way in that direction.\n\nStyle, typos, suggestions:\n* [minor] L085-086: \"MA-ILR\" -> \"MA-IL\" or rather \"MA-IRL\"?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 4, "contribution": 3, "strengths": "* Excellent exposition of the concepts, related work, and background. It is difficult to do based on the sheer quantity of concepts that the work introduces and uses, which makes it all the more impressive and appreciated. Sec. 3 is well balanced with just enough depth to grasp the problem.\n* The proof outline of Th. 3 is appreciated and very useful.\n* The paper presents its results with an extremely high level of polish.", "weaknesses": "* The finding that deriving exploitability upper bounds ultimately depnds on characterizing delta (and on the conditions that make delta consistent and tractable) is an interesting and valuable contribution. Still, the paper could better connect this result to more practical considerations. It would help to illustrate how specific techniques or settings might influence/shape delta in applied contexts. The brief mentions of “promoting exploration” and “penalizing risk aversion” (last lines of Sec. 6) move in that direction by linking delta to concrete mechanisms, but expanding on these examples could make the results feel more actionable. In particular, clarifying how delta might be operationalized or controlled through standard control or learning methods (practical “knobs”) would strengthen the paper, since the central result of the paper depends entirely on delta behaving well enough.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6pZ4HzaOSJ", "reviewer": "Reviewer_znH1", "summary": "This paper studies imitation learning in Markov games. It first demonstrates that several previously used metrics, such as BC error or measure matching error, fail to provide theoretical bounds on the performance of learned equilibria. The paper then establishes that obtaining exact lower bounds for the Nash gap is PPAD-hard. Finally, the paper proposes a new notion of best-response continuity and provides theoretical guarantees on the Nash gap under the new condition.", "questions": "- I find it hard to believe that Theorem 3 holds for any $\\epsilon_{\\rho} > 0.$ It is well-known that computing $\\epsilon$-Nash for some constant $\\epsilon$ is easy (see [1] for example). What is the connection between $\\epsilon_{\\rho}$ and the approximation error $\\epsilon$ in your reduction?\n\n----\n[1] Constantinos Daskalakis, Aranyak Mehta, and Christos H. Papadimitriou. A note on approximate nash equilibria. Theor. Comput. Sci., 410(17):1581–1588, 2009.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Overall the paper is well-written, the question studied in this paper is clearly stated and most proofs are easy to follow.\n- The paper provides constructive examples where BC error and measure matching error fail to capture the performance of learned equilibria.\n- Although the paper is not mathematically heavy, I believe the result carries some significance to the game theory community.", "weaknesses": "- One issue with the definition of the tight Nash gap lower bound is that $\\mathcal{M}_{\\epsilon}(\\pi^{E})$ is not a convex set due to the equality constraint. Given this non-convex nature, it is not surprising that computing this bound leads to some hardness results (maybe even NP-hardness). While it is understandable to impose such equality constraint, the authors could consider more natural way to capture this gap.\n\n- To obtain a meaningful result from Lemma 4, one would expect $\\delta(\\epsilon)$ to be a polynomial function of $\\epsilon$. However, this essentially implies that when $\\epsilon = 0$, $\\pi_i^{E}$ is the unique best response policy given $\\pi_{-i}^{E}$. This notion appears quite restrictive as it is well-known that multiple best-response strategies may exist against a fixed policy. \n\n- No numerical experiments are provided.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)