Learning Equilibria from Data: Provably Efficient Multi-Agent Imitation Learning
Authors: Till Freihaut
Luca Viano
Volkan Cevher
Matthieu Geist
Giorgia Ramponi
Venue: NeurIPS 2025 poster ()
Keywords: Reinforcement Learning
Multi-Agent Reinforcement Learning
Imitation Learning
Multi-Agent Imitation Learning
Primary area: reinforcement_learning

Abstract: This paper provides the first expert sample complexity characterization for learning a Nash equilibrium from expert data in Markov Games.
We show that a new quantity named the *single policy deviation concentrability coefficient* is unavoidable in the non-interactive imitation learning setting, and we provide an upper bound for behavioral cloning (BC) featuring such coefficient. BC exhibits substantial regret in games with high concentrability coefficient, leading us to utilize expert queries to develop and introduce two novel solution algorithms: MAIL-BRO and MURMAIL. The former employs a best response oracle and learns an $\varepsilon$-Nash equilibrium with $\mathcal{O}(\varepsilon^{-4})$ expert and oracle queries. The latter bypasses completely the best response oracle at the cost of a worse expert query complexity of order  $\mathcal{O}(\varepsilon^{-8})$. Finally, we provide numerical evidence, confirming our theoretical findings.

Learning Equilibria from Data: Provably Efficient Multi-Agent gent Imitation Learning
Till Freihaut"
Luca Viano* EPFL luca. viano@epf1.ch
University of Zurich
freihaut@ifi.c uzh.ch
Volkan Cevher
Matthieu Geist
Giorgia Ramponi
EPFL
Earth Species Project
University of Zurich
volkan. cevher@epfl.ch
matthieeeeertsspciee..om
ramponi sipponi@iiii .zh. ch
Abstract
This paper provides the first expert sample complexity characterization for learning a Nash equilibrium from expert data in Markov Games. We show that new quantity named the all policy deviation concentrability coefficient unavoidable the non-interactive imitation learning setting, and provide upper bound for behavioral cloning (BC) featuring such coefficient. BC exhibits substantial regret in games with high concentrability coefficient, leading develop and introduce two novel solution algorithms: MAIL-BI BRR and MURMAIL. The former employs best response oracle and learns an N-Nash equilibrium with O(e expert and oracle queries. The latter bypasses completely the best response oracle the cost of worse expert query complexity of order Os--)). Finally, we provide numerical evidence, confirming our theoretical findings.
utilize expert queries
Introduction
Learning in systems with multiple agents is common in real-world applications, such as autonomous driving (Shale--hwwrtz et al. 2016), traffic light control (Bakker et al. 2010), and games (Samvelyan al. 2019). Designing reward functions in these applications is challenging, as it requires defining multiple, potentially opposing, objectives. However, expert data often available, making Multi- Agent Imitation Learning (MAIL) an important approach for learning policies that perform well in underlying Markov Games (MGs) with unknown reward functions. MAIL has the potential to ensure the alignment of agents with the original experts' goals and to avoid potentially exploitable policies that can lead to socially undesirable behavior [Hammond et 2025
key distinction between Multi-Agent Imitation Learning and Single-Agen Imitation Learning (SAIL) is that the performance of strategy in MAIL depends on the strategies of other agents. This means that an expert need not maximize reward directly; instead, the goal is to reach a state where no agent benefits from unilaterally deviating from its strategy, typically referred to The most common equilibrium concept is the Nash equilibrium (NE). To evaluate how close a given strategy an NE, the objective must consider strategic deviations of one agent while holding the others fixed.
equilibrium.
In this work, we consider 2-player Zero-Sum Markov Game where the agents' rewards are perfectly opposing, ie.,, (1 a, = (2,
s, a, b). this setting, denoting the state value function a strategy
Eqqual contribution.
For the sake of simplicity, the main text will focus on this case. The appendix outlines the extension to player general-sum games.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

where p is any state state dis- Table 1:
For simplicity, we report results for the two-player semo-sum with discount factor y finite state space S| finite action spaces A, B. Let |mmax| = max , Being consis- tent with Tang et al. [2024]. we denote 3 min.es di _ (s), by the recoverability co- efficient and with H the finite horizon of the considered game. Moreover, we refer to Tang al.] [2024] for the definition of the convex functions (MALICE and BLADDSS Additionally, for the behavioral cloning (BC) output pair J. V with an input dataset D we define Cmax
m. max mmax.
tribution, in BC we set it to p= de For this comparison, notice that the main text by Tang et al. 2024) focuses on learning correlated equilibria, but as specified in their appendix, the same proofs can be performed for the problem of learning Nash equilibria. For the algorithms presented by Tang al. [2024), we can not specify the bound on the number of expert queries since their analysis as an error propagation only flavor. As final minor difference, we apply our analysis to the infinite horizon discounted setting, which is more relevant for practical settings. Finally, abbreviated Queriable Expert by QE
Algorithm
MG assum,
Cumputational Cost
Nach Gap
Expert Data
Required Computational Oracke
QF
BC Tung al. 2024
8 3-
(amalytical solution is available)
0 (uIl=:-1)
Not specifiid
t-sceuraee TV minimizer
x
MALICE
2024
8
exp ([Si)
(ulle)
Not speciiiide
c-sccuate ESAALIUS minimizeer
x
BLADES Tang
exp ([S[)
(udte)
specilied
e-accurae foLaDes minimizer
BC (Our mnalysis)
Cassc do
Il fanalytical solution available)
(
None
X
MAIL-ERO (Ours)
Noaz
poly([S) J/Auaal. -1)"",1""
(6)
Best respouse oracle
/
MURMAHL (Ours)
poly([S) JA (1--011--))) -e)"t
(+)
None
pair μl, ViC. S + R, we measure the gap of strategy pair to NE by the following metric Nash-Gap(u, D) == V ((s) ) Vur" (so),
where so is the starting state of the game and D² denotes one of the strategies from the set of best-response strategies to μ.. That is, μ³ E br(v) := argmax,, (*y(ss) and V* E bb((u) := argmin, Vula(s (se). This objective has been widely adopted in Agent Reinforcement Learning (see, c.g., (Cui and Du 2022a(b] and it is casily motivated by the fact that any strategy profile output by an algorithm under study (Pout: Vout) such that Nash-Gap(Mon) Mott) S E is an E-approximate Nash equilibrium, often shortened c-NE. However, it remained largely unexplored in the MAIL setting until the seminal work of Tang et al. (0024). who showed that minimizing the Nash Gap is fundamentally hard in MAIL since deviations in outto--distiobution states can incur linear regret.
limitation of Tang et al. [2024] that they provide an error propagation analysis only. While their analysis has the advantage of suggesting meaningful losses that can be minimized to ensure small Nash-Gap, it falls short in characterizing the amount of expert samples needed to learn a e-NE from expert data. Moreover, their BLADES and MALICE algorithms have computational complexity that scales exponentially with the number of states in the game due to their for loops over the set of all possible deviations. This set has cardinality exponential in (S].
This work presents the first theoretical analysis of sample complexity in MAIL, and notably, achieves this without exponential dependencies. Specifically, our contributions are as follows:
1. We provide a sample complexity analysis for BC, revealing the emergence of all deviation concentrability coefficient (Theorem b.I.
2. We formally separate MAIL from SAIL, proving in Theorem 3.2 that even with fully known transitions, for any non-interactive imitation learning algorithm (like BC) there exists Markov Game with infinite single deviation concentrability coefficient where the Nash Gap remains constant with infinite expert data.
We will relax this to stochastic starting state in the next sections.

---

3. On the positive side, we show that the dependence on the concentrability coefficient can be avoided if an interactive expert available. In particular, assuming access to a Best Response Oracle, we propose an algorithm that achieves an g-NE with O(e-t) expert queries and oracle calls (Algorithm 2
4. Additionally, we develop algorithm that avoids the Best Response oracle and the con- centrability coefficient simultancously, achieving an e-NE with O( *) expert queries. Moreover, the algorithm is computationally efficient. Its design is based on the novel principle of maximum uncertainty response.
For clarity, we report a comparison of our results with existing MAII. algorithms in Table 1
2
Preliminaries
We start by formalizing the concept of Two-Player Zero-Sum Markov Games. Then, we define the imitation learning settings considered in this work dubbed interactive and non non-interactive respectively.
Two-Player Zero-sum Markov Game An infinite-horizon two-player zero-sum Markov game is defined by the tuple g = (S, A, , P. P,r, r, do), where S is the finite (joint-)star >state space, .A is the finite action space of the first player, B is the finite action space of the second player, P E R (|]B) [AA] is
the (unknown) transition function, r E [-1, |||s| [|||a|] the reward vector, a discount factor 7 E [o, 1) and do a distribution over the state space from which the starting state is sampled. In zero-sum Markov Game there is one player trying to maximize the rewards and one player aims to minimize the rewards. We assume that the first player is maximizing the reward and the second player aims to minimize it. It holds that r (s, a, b) -r²(s, (s, a, b) (s, a, b) E S X A x B. Therefore, we can omit the superscript in the reward and simply refer to the reward as We define a policy of player as μ S + A and the policy of player as v S - Ag. where A is the probability simplex over the finite action spaces A and B, respectively. Next, we define the value function for a given state 8 E S and the state-action value function for a given state E S and joint actions (a, b) A B for given policy pair (H, To this end, let us denote by {St. As, B, j the stochastic process generated by the interaction of the policy pair (n, v) in the Markov Game, then 30 we can define the value functions as follows (s) (s) = En, Di= r(S,, Ar, B.) So = s] and Qu,"(s, a, b) Ey,," IEeo r(S,, A,, B,) Su Ao a, Bu = b].
Additionally, we define the state visitation probability induced by policy pair (w, u) as (s") == (1 (1-7) 2 "=1 so do} If one player's 's policy is fixed, then the Markov Game induces a Markov decision process (MDP). Assuming that player 2 fixes their strategy, the induced transition function for given state-action pair (s, a) S A new state s' E S is given by (s a,a) := Epen w(b 8) P(s' 8, a). It is analogously defined if the policy of player is fixed. Additionally, for a fixed strategy of the opponent player, we define the best response set as br()) argmax (du, Vi.") and br(4))
argmin (do. VP."), respectively, where II denotes the set of all possible policies and μ=,, .²* as elements of these sets. is important to note that the best response may not be unique, but the value is. A pair of policies is called Nash equilibrium both policies are best responses to each other. Last, we introduce the Nash gap, which measures how close given policy pair (μ, v) is to NE:
Nash Mash-ap((u,e)) v) == -do, Vu' ViLe"
The Nash-Gap has the desirable property, that Nash Nash-Gap(u, = 0, if (H, is a NE and Nash (ash-Gap(u,)) v/ > 0, otherwise.
Non-interactive Multi-Agent Imitation Learning. In non-interactive MAIL, the learner observes dataset D = (Tx) containing N trajectories collected in the two-player zero-sum Markov Game, where the actions are sampled from the NE expert policy pair (1E, vF. For each trajectory The a random length H Gco(1 -)) is sampled and then the sequence of states and (joint-)action)) up to time H are saved, i.e. T := {(st, dz, by) After such dataset is collected, the learner can no longer collect new expert data. For this reason, we refer to this setting as non-interactive. Moreover, the learner might know the transition function of the Markov Game The learner's goal to adopt an algorithm Alg that takes as input D, and outputs a pair of policies (7, 7) such that Eaig Nash-Gaple ?)]
3

---

Interactive Multi-Agent Imitation learning. In interactive MAIL, there is no initial dataset D. The learner interacts with the environment for a certain number of rounds. At each round, the learner can collect a trajectory with a chosen policy pair and decide to query the expert at the visited states. The learner's goal to adopt an algorithm Alg that after poly(e-1) main expert queries outputs pair of policies (7,, 2) such that Baig Gapsh, D)] < e. Compared to the non-interactive setting, the expert can be queried during learning.
In the following, we present the theoretical results concerning the two above settings. In the next section, we study the inniiteracctiv setting.
3 On the sample complexity of Multi-Agent Behavior Cloning
In this section, we give our first result, which concerns the sample complexity of Behavior Cloning.
Interestingly, our upper bound depends on novel quantity Cmax R dubbed all policy deviation concentrability coefficient, which an infinite norm ratio between the occupancy distributions related to the notion of data coverage assumptions needed in Offline Zero-Sume Markov Games (Cui and Du 2022a| Zhong et al., [022] and concentrability coefficients in approximate dynamic programming Scherrer et al. 2012 Geist al., 2019 Vieillard et al.] 2020). Contrary to the analysis of Tang et al.) [024].. we do not require that the occupancy measure of the equilibrium policy pair used to collect D lower bounded by B. Therefore, our analysis also applies to the realistic setting where some states
have zero probability to appear in D.
We conclude this section with lower bound inspired by the construction of Tang et al. (2024),
which separates Multi-Agent Imitation Learning from Single-Agent Imitation Learning, showing the necessity of the concentrability coefficient in the multi-agent non-interactive setting even with a known transition model.
Behavioral cloning in Markov Games. In the context of Markov games, BC aims to recover a pair of policies (7i, D) from expert demonstrations D based on maximum likelihood estimation. Formally, we have that (7t, 7) = argmaax ΣTED log (IP(T; 11, v)), where P(r; pt, v/ = do())) I u(a s)u(b P s, o. b) is the probability of generating trajectory T under policies (p. 1), where I1 Geo(1 - 7) In the tabular set-up, we can obtain the closed-form solution of the above optimization problem Ça(a 8) = N(s.e) if (()) > O and 7a(a
8) 1 otherwise. Similarly, this LAI holds for {b s) by replacing N(s, a) with ((s, b). Here N(s, (s. b) and N(s) denote the number of times that state-action pair (s, a), (s, b) and state appear in D.
N(s)
Now, we can state our result for the upper bound of Behavior Cloning when minimizing the Nash Gap ①.. We give a proof sketch below the theorem and the full proof can be found in Appendix C Theorem 3.1. Let (nE, DB denote Nash equilibrium policy pair in two-player zero-sum Markov game, and let D contain trajectories from this expert policy pair. Let (f., D) be the policies obtained via Behavior Cloning from D of size N. Then, with probability least 1 - 8, it holds:
8
S Amaxi log 2 (2
Nash G(al-GGap S Craxx (1
71-
N
where Ciaxx max,,v max mmax) Ebr(m) du
.mx (
and we set p=
du R. R
Proof Sketch. In the first step of the proof, we add and subtract the value function of the Nash equilibrium expert. Additionally, we use the definition of the Nash equilibrium, in particular that the policies are best responses to each other, to upper bound it by replacing it with the best responding policies and e respectively.
yu x (50) Va." (so) S VV' D (00) va E (so) + Vu . (so) Vêr*
Error(D)
: Brror(
where 1² E br(D), v² E br(ā). Next, we can upper bound the two error terms separately. Note that the error terms each share one fixed policy, therefore, we can apply version of the performance

---

difference lemma, the triangle inequality, and fix one best response for each player to obtain
2 max E M.DE
0c
(rror S 1 pEbr(P)
Σ
7 TV (v F( s))
(2)
We note that maXpue)(D)) contains the random variable ú but can be upper bounded with the best response to with respect to the general policy class max max Last, we do a change of measure to get the expectation with respect to the expert policy pair. Then, we bound the ratio of the state visitation distribution and bound the expectation with concentration inequalities to obtain with probability of at least -
Vu .0 (80) Vu eB (so) S
8 max max wEll pebr(2)
di... du d
S B log 2 (2)))
41-
Analogous calculations for the second player complete the proof. The full proof is given in Appendix C
We now discuss several important implications of the derived theorem, particularly focusing on the quantity Cmax. referred as the all policy deviation concentrability coefficient (see, e.g., [Cui and
Du 2022a Zhong et al., 2022 ). Intuitively, the theorem indicates that if a best response against a possible recovered policy shifts the support of the state visitation distribution away from the one induced by the observed Nash equilibrium, the corresponding objective becomes unbounded.
Remark 3.1. While restricting, this requirement is weaker than uniform lower bound on the equilibrium state occupancy measure assumed by TTang el al. 2024), that is duE.E 2 3. In particular, always holds that Cmax S B-1
Next, we introduce a lower bound on Cmax. that intuitively describes how different the cov- erage of different Nash equilibrium policies can be. Formally, we introduce C(yB, (UB) which we refer to as the expert policy
du F., du d 00
max maxppebr(e))
maxxebr((a))
deviation concentrability coefficient. Clearly, we have that Cmax 2 C(p vB) as the latter only consider the best responses the Nash equilibrium policies.
Unfortunately, we show that even for this smaller quantity there exists a zero-sum Markov game in which C(uB, E) is unbounded, and show that in such game, no interrettactte algorithm can recover a Nash profile even with an infinite amount of data. We present this result in the next section. Note, that remains an open question if it is possible have bounded C(p B) but an unbounded Cmax- We discuss this further in Section
The observations are similar in spirit those obtained in the offline setting [Cui and Du 2022a Zhong et al.) 2022]. In these works, the authors derive a lower bound that shows the necessity of a unilateral concentration assumption minimize the Nash gap. However, their construction does not apply to the Imitation Learning setting.
3.1 Necessity of C(uE; VE) non-interactive MAIL
In this section, we provide the negative result, that Markov Game exists, such that the expert deviation concentrability coefficient of Theorem 3.1 is unbounded.
The first hardness results to minimize the Nash Gap in Multi-Agent Imitation Learning were derived by [Tng al. (2024] Thm. 4.3]. Next, we will give a stronger result, showing that even in the case of full knowledge of the transition model and perfect recovery of the state visitation distribution of the
expert, the Nash gap is of the order (1 7) -1 A detailed discussion on the difference between the
following result and the one obtained by Tang et al. [2024] Thm. 4.3] can be found in Appendix [[ An illustration of the Zero-Sum Markov game can found Fig. I and the full proof in Appendix D
Theorem 3.2 (Construction of MG). For any learning algorithm Alg in the non-interacee interactive imitation learning setting, there exists a zero-sum Markov game with C(yF, (B) = oo such that the output policies ju, i satisfy EAgg (do, Vu", 10 VR."" >} 2 -1 The result continues to hold even if Alg is aware of the transition dynamics of the game.
5

---

This theorem illustrates a fundamental limitation of BC in zero-sum Markov games. Specifically, it reveals that even perfect recovery of the Nash expert's state visitation distribution, along with complete knowledge of the transition model, is insufficient for minimizing the Nash gap. The key insight is that a Nash equilibrium only guarantees robustness against unilateral deviations. regions of the Markov game that require joint deviations to be visited may remain underexplored by the expert, leaving the learner vulnerable in those regions. This can be seen in Fig. [ if the learner has (jointly) inaccurate policy in state 81, the best response of the agents can change the expert path to exploit the opponent in the red path the Markov Game and the green one respectively. Notably, this phenomenon persists even when the transition model is known. This can be seen as Sxplt1, Sxptt2 and Scopy are sets of states, and each action combination leads to a different unique state, i.e. [Spptt1 U Sxplt2 U Scopyl |A] [B]. This highlights the necessity of interactive Imitation Learning to explore strategically important but unobserved regions of the state space.
result,
This issue marks a critical distinction between multi-agent and single-agent imitation learning. In single-agent settings, BC suffices to achieve good performance [Rajaraman al., 2020 2021a Foster et al. 2024
Moreover, it is important to notice that in the construction used by Tang et knowledge of the transition model enables learners to steer toward expert-visited trajectories. In contrast, our result establishes hardness construction the zero-sum setting showing that the guidance provided by transition knowledge is insufficient.
2024 Thm. 4.3],
Sxplt1
all
a1 b1, a2b2
else
Scopy
all
agbi, abbz
else
80
Sxpl22
all
a3b3
all
$2
83
all
Figure 1: 2 Player Zero-Sum Game with Linear Regret in case of full knowledge of transition.
Possible ways to learn under unbounded C(uE, B). The above theorem makes clear that no algorithm can learn in the non-interactive setting if C(2 DB co. We can think of several remedies to this fact. First, we could require to observe data from the possible strategies in the set of Nash equilibria. In this case, would encounter smaller concentrability coefficient which features the average of the equilibria occupancy measures in the denominator. second remedy is to move to the interactive MAIL setting which allows the learner collect reward free trajectories in the Markov Game and query the expert policy pair along the visited states.
that actively queries expert demonstrations to reduce the Nash gap of the resulting policy. Since the former assumption is rarely realistic, we later propose an interactive algorithm (Algorithm) 2
Avoiding the single deviation concentrability in interactive MAIL
In this section, we introduce two algorithms (MAIL-BRO and MURMAIL) designed to avoid dependence on C(uF, F) at the cost of moving to the interactive imitation learning setting.
Both of our algorithms address key limitations of the approaches proposed in BLADES and MALICE by Tang et al. 2024). as their methods require exponential compute and focus solely on error propagation analysis without providing convergence guarantees for the resulting policies. In contrast, our algorithms are accompanied by both convergence guarantees and polynomial computational cost. To motivate these algorithms, let us briefly revisit the structure of the original proof. In offline BC,

---

we lack data corresponding to the best responses against the estimated expert policies. As result, it not feasible directly estimate the expectation in Eq. (2). To circumvent this, we apply a change of measure at the cost of introducing the all deviation concentrability term.
Our first approach to overcome this limitation is to introduce Best Response oracle, which enables sampling from the distributions (H,v²) and (1², z), where E br( and v E br thereby allow- ing us to estimate the relevant expectations without incurring the concentrability coefficient. Formally, we have the following definition, also used in previous works (see e.g. Hellerstein et al. (2019))
Definition 4.1 (Best Response Oracle). Let (ji, D) be a pair of policies for a Markov Game g. Then, a Best Response Oracle generates policies μ E br(D) and E br(ā).
However, it is not straightforward to use the policies given by the Best Response Oracle. Starting from 2 we derive the following optimization problem
20
min max ENP., wEllwebriA
Σ
7 TV (M 6))
Even under the assumption of being able to generate samples from n², where V/ E br(ū),, two problems remain. First of all, the optimization problem Eq. (3) non-convex in J.. Secondly, in order to estimate the minimizer Ji, we need to collect data from the occupancy measure of the policy pair J.P, for v E br (7),, which depends on the minimizer itself.
To overcome this issue, we make use of the following bound, here only obtained for fixing pn:
Ek= (do. VIE. - V.e.E) < K
1
Ex= E un | (s) - [)]? K(1->)² kk=l
Amaer
where v E br(x))). This expression can be derived via the performance difference Lemma, Cauchy- Schwarz, and eventually Jensen's inequality, and it analogously holds for Vx fixed. The above inequality is crucial for the design of our algorithms in the interactive setting, shown next.
4.1 Efficient algorithm with a best response oracle
In this section, we present our statistically and computationally efficient algorithm with a best response oracle defined as follows.
Algorithm 1:
Multi-Agent Imitation Learning with Best Response Oracle (MAIL-BRO)
Input: number of iterations K, learning rates 1), BR oracle, initial policies (μ1, v1) Output: e-Nash equilibrium (ń², D)
for k = to K do
Update policies:;
Query BR oracle to obtain 1 E br(ik), vt E br((ix);
Sample 5% ~ d'uipt Alt Mg( Shh,, 5% dliien Ale vE(.1)))
(s, a) ps(a] Sh sp - =
(s a) va(a 1k) -1z==0
Mk+1(a 5) x pa(a exp (-ng (s.g) ())
(b 8) x (b 8) exp (8,
end
return
Ng. up for Te ~ Uni
With the best response oracle and the bound in Eq. in place, we can aim at applying a no-regret
algorithm to the loss sequence E = [ s) px((- s)]|}} k=1 Since these losses are not directly observable, MAIL-BRO (see Algorithm|] [ at each iteration performs a step of exponential weights updates with stochastic unbiased gradient denoted by of and 9h for the two players respectively. These gradient estimates can be shown to have almost surely bounded noise too.
Exploiting these facts in the analysis of MAIL-BRO, we can attain the following formal result.
7

---

Theorem 4.1. Let us run Algorithm I for K = =o 0 12 Amer (og(1/8) iterations with (1-9)8c+
learning rate 2 log Amaxl,
Then, the sequence of policies {uk, Mie he satisfies with probability
K max (do, V minven (dg, Viuee) S O Therefore, setting
at least 1 1-50 56 that K
Ek=1
5 -=) ensures that for certain i ~ Unif([K] it holds that E Mash-GGa((yg vx] S c. That
is, Mgg Mg is an e-Nash equilibrium in expectation.
The proof can be found in Appendix We observe that, compared to standard BC, the sample complexity now is of the order O( which is worse by a factor of E However, this trade-off allows to completely avoid dependence on the all policy deviation concentrability coefficient in the MAIL-BRO upper bound. That is, MAIL-BRO is able to effectively recover an approximate equilibrium from expert data in larger class of games.
E
Unfortunately, assuming best response oracle might be limiting some cases. For those cases, we can replace the call to the oracle with the maximum uncertainty responding policy as we explain in the next section.
4.2 Avoiding the best response oracle thanks to the maximum uncertainty response
Here, we introduce our algorithm MURMAIL (Algorithm 2 which can be applied in the most general setting where C(u D oo and the best response oracle is not available. The idea is again to start from 4 but instead of querying the Best Response Oracle, the objective is upper bounded by the maximum uncertainty policy. It is important to note that the exploration follows in a decentralized way, avoiding the curse of multi-agents by exploring induced MDPs instead of the original Markov Game,
Algorithm 2: Maximum Uncertainty Response Multi Ageet Imitation Learning (MURMAIL)
Input: number of iterations K, learning rates 7) inner iteration budget T, initial (41, v1) Output: --Nash equilibrium (p, i))
for k = 1 to K do
Inner Single-Agent RL Updates:
% Maximum uncertainty response to μ-player update
Define single agent transition PH,, (s' 8, b) = E Me<(a P(s' |s, b):
Define single agent stochastic reward Rys (s) - (An=AAs) - (AE 8) + (+1))1)))
where Ag, A'E Mg(-1) s); (s);
yk = UCBVI R Ryy);
%6 Maximum uncertainty response to v-player update
P., (8'(s,0) a)= = ELEB (()s)))((s ss a,,)), b):
Ru, (s) + 1Am=A'a) - 22 8) + [|xx(- 8)12 where AR, A'p ~ vol 88;;
2 = UCBVI Ryr)
Update policies:
Sample St ~ due.ve Aft ~ M. (: St Sk ~ denive Ag ~ DEl. 5%)
(5, a) = Ma(a 1 1 1A/=0
(s a) = vv(a 1k) -AR==
Ma+1(a 8) x (a 8) exp (-ng) (s, a)):
(b s) x (b s) exp (g a))
end
return
ug. up for ke ~ Unif([K])
If the best response vg E br(w)) cannot be computed, we can majorize the above quantity by the
policy yi such that ya E argmax,eul K[I->)²
[Amazl Ey-d
[| 8) pk(- s)]|?] words, yh is
the policy that solves a single-agent MDP with reward [| s) - (= s) where the opponent
keeps the strategy μ4 fixed and the player with strategy v seeks to maximize the probability of
visiting uncertain states where the uncertainty captured by [| s) pa( |)]] This intuition motivates the name maximum uncertainty response.
8

---

At this point, since both the policies μ4 and yi are known, it is possible to roll out such policy pair in the environment and collect data to control [| s) / s)ll for states in the support of dlu.-M, Of course, exact computation of yk is not possible because we know neither the transition dynamics nor m (which enters the reward function) exactly. However, approximate solution can be computed, for example, via UCEVI adapted to handle the stochastic nature of the reward and the discounted setting considered in this work.
The following result states the theoretical guarantees for Algorithm A proof can be found in Appendix
Theorem 4.2. Let run Algorithm 2 for K =0 (15i)Amex)
=0(15) Plog Amaax log(1/=) outer iterations (1-7))=4
and T O [ISP) |Ap"l A (ee(1/e)) inner iterations with learning rate rj 2|5] log Amoxl
Then, for
(1-73)
K
certain k ~ Uni it holds that E
ug)] S.
It is easy to see that since the total number of expert queries is of order O(K . T), the total number of
expert queries to achieve an e-approximate Nash equilibrium in expectation is Ö [SS |si"|_mmel
(1~>)17
Again, notice that there is no concentrability requirement in the upper bound and that the result is achieved without the need to call a best response oracle. This comes at the cost of a worse sample complexity bound but is applicable to larger class of games, even in those where best response oracle is not available.
While this may appear suboptimal in the two-player zero-sum setting, is important to emphasize that the underlying algorithms support decentralized execution. In particular, in Algorithm 1 the dependence on A does not stem from the two-player structure, but rather from the reformulation of the objective necessary to obtain an unbiased estimator for the gradient update. Similarly, the |Amax] dependence Algorithm 2 arises from the squared objective and the RL imner loop. Crucially, in this inner loop. each agent solves a single-agent MDP, ensuring that the algorithm remains fully decentralized. Altogether, these observations indicate that our algorithms scale linearly with Amaxl and do not suffer from the curse of multi-agents in the n-player setting. sketched version for n-player general- sum games can be found in Appendix H
Remark 4.1. Note that our algorithms scale with
5 Numerical Validation
In this section, we provide a numerical evaluation of our proposed algorithms in the Markov Game considered in the lower bound construction (Fig.[) 11 as this environment allows us to control C(uB BB by considering different convex combinations of the two pure Nash equilibria profiles (i.e., the black and the blue path in Figure T. This environment serves
proof of concept to demonstrate the practical fcasibility of our methods. In particular, we aim to highlight that the performance of BC depends the concentrability coefficient C(u DB) even when it is bounded, and completely fails when C(uF, B) = oo. Note that in all considered cases, we have that 3 = and therefore the BC bound proven in Tang al. 2024] would always be vacuous, while Theorem 3.1 remains valid. The code used for the experiments is available at http:///ttuub..om///eehaa///////
We evaluate Multi-Agen BC and MURMAIL (Algorithm 2 in the considered environment and measure the exploitability of the resulting policies with respect to the number of expert queries (for MURMAIL.) and dataset size (for BC). The results are presented in Fig. 2
As predicted by our theoretical analysis, Multi-Agent BC fails in settings with C(HF, oc. whereas MURMAIL still succeeds in minimizing the Nash gap. However, in environments where EE < co, BC can outperform MURMAIL in terms of efficiency - compared e- Never- theless, one should also consider that the performance of MURMAIL is independent of C( () and therefore MURMAIL can outperform BC in cases where C(μ F) is bounded but large. This highlights the importance of algorithm selection based on the underlying environment. Additional details, experiments in another environment, and practical insights for improving MURMAIL's performance are discussed in Appendix !
or any other algorithm for solving single agent discounted tabular Markov decision process.

---

(a) C(pP, (e) 2
(b) C(H P) & 1000
(c) C(p,, $ 10000
(d) C(p ,0,)
Nosh Gap
MURMAIL
2
3
4
10
7
8
9
2 3 4
7 8 9 10
Querkey D Dataset Sizr:10
-10*
-10
-10*
Figure 2: Empirical evaluation for environments with different C(p B).
Conclusion and Future Directions
This paper provides the first sample complexity analysis of behavioral cloning in the multi-agent setting. The provided upper bound depends on the all policy deviation concentrabilityy coefficient. Additionally, which is shown to be unavoidable in general. Unfortunately, it is quite easy come up with MGs where the concentrability coefficient is unbounded. In particular, we introduce the smaller quantity C(u 2 is unbounded and where no non-interactive MAIL algorithm can learn an cquilibrium from data. In this situation, we resort to expert queries and we introduce novel algorithms dubbed MAIL-BRO and MURMAIL, which achieve an e-approximate Nash equilibrium with polynomial number of expert queries and computational cost polynomial in all problem parameters.
We outline few interesting future directions and research questions left open by work.
Lower Bound. This work has provided a hardness result, showing that if C(u v2) is un- bounded, there exists no non-interactive MAIL algorithm that can learn. However, it holds true that Cmax 2 C(uE, D) and it remains an open question if there exists a Markov Game, where C(uB, v²) bounded but Cuax Answering this would close the gap between the provided upper bound of BC and the lower bound. In particular, this would answer what the fundamental quantity of non-interactive MAIL is. Additionally, it remains an open question if one can prove statistical lower bound featuring C(p v) or Cmax and whether BC rate optimal E.
oo and no non-interactive MAIL algorithm can recover an equilibrium.
Improving the theoretical bounds in and problem dependent parameters. The focus of this work was to show the first sample complexity bound for a computationally efficient algorithm the queriable expert setting. For the sake of simplicity, upper bound in the accuracy parameters E, effective horizon (1 - 7) states and actions cardinality |8] and [A]. A possible direction of improvement is derive tighter analysis of the outer loop using faster rates for the regret of the squared loss (see for example [Cesa-Bianchi and Lugosi 2006 Chapter 3)).
did not try to optimize the dependence of the
Moreover, the upper bound could be improved by removing the need of the RL inner loop in MURMAIL. In general, replacing it with a regret learner that minimizes the regret in an MDP with changing reward function and transitions not possible because of the negative result by Abbasi- Yadkori et al. [2013]. On the positive side, it is known from the game theoretic literature that no regret learning would be possible under these conditions if the state space is tree structured as in an extensive form game [Osborne and Rubinstein, 1994]. We leave the study of this improvement, which can be relevant for several games such as Poker, for future works.
Extension to deep imitation learning. The current analysis is limited tabular Markov Games. However, the main conceptual ideas easily carry on to deep imitation learning experiments. The largest theory-practic gap would be the inner loop where UCBVI would need be replaced by Deep RL algorithm such as DQN Mnih et al. (0155] or Soft Actor Critic Haarnoja et al. (0018 just to name few.
References
Y. Yadkori, I.. Bartlett, and C. Szepesvari. Online learning markov decision processes with adversarially chosen transition probability distributions, 2013,
10

---

P. Alatur, A. Barakat, and N. 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), pages 3883-3888, 2024. doi: 10.1 101109//CDC55573322221118888 108888884..
N. Alon and J. H. Speneer. The Probabilistic Method. Wiley, New York, second edition, 2004. ISBN 0471370460 9780471370468 04717221 0780071772255 0471653985 9780471653988
M. G. Azar, I. Osband, and R. Munos. Minimax regret bounds for reinforcement learning. In International conference on machine learning, pages 263-272. PMLR, 2017.
Y. Bai and C. Jin. Provable self-play algorithms for competitive reinforcement learning. In Interna- tional conference on machine learning, pages 551-560. PMLR, 2020.
Y. Bai, C. Jin, H. Wang, and C. Xiong. Sample-efficient learning of stackelberg equilibria in general- sum games. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 13799-25811 Curran As- sociates, Inc., 2021. URLLattps://proceednngg neurips ctcpiissccccccee cttpcc/ppaa paper faaperfflesee wiweslileppeee ftless/appee//2211 0Tl1://8118770333400000155591133
.pdf
B. Bakker, S. Whiteson, L. Kester, and F. C. A. Groen. Traffic Light Control by Multia- gent Reinforcement Learning Systems, pages 475-510. Springer Berlin Heidelberg, Berlin, doi:
Heidelberg, 2010. ISBN 3-602-33642---- 642 11688-9 9_18.
1168-99 1007 9970-
111---442-18----- 11688-9_1888 URL
D. Berend and A. Kontorovich. On the concentration of the missing mass. Electronic Communications in Probability, 18, 10 2012. doi: 10. 18-3999..
T. V. Bui, T. Mai, and T. H. Nguyen. Inverse factorized soft q-learning for A. Globerson, I.. Mackey, D. Bel-
operative multi-agent imitation learning. grave, A. Fan, U. Paquet, J. Tomezak, and C. Zhang, editors, Advances in Neu- ral Information Processing Systems, volume 37, pages 27178-27206. Curran Associates, Inc., 2024. URL httpps:/pproeeednng. wwwripscccppppp.prr.... www.fileeepppee sateerffffeeeppeeeeeee pttlle///pper/22///1eeee pdf
htwpeeeedddinnnnnnnun..reeeeee nwurips. cc
N.
and G. Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Q. Cui and S. S. Du. When are offline two-player zero-sum markov games solvable? In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages wwwess/apee//eeeeeoeeeeaaaaaeeee /ap1://22///// Inc., 2022a. URL http:s///prrocceennggss wwwp:ddiiinnnnnnunnneeeeeee cc/ cc/paper
Curran Associates,
Q. Cui and S. S. Du. Provably efficient offline multi-agent reinforcement learning via strategy- bonus. In Koyejo, S. Mohamed, Agarwal, D. Belgrave, K. Cho. and Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 11799-1177 11791 Curran Associates, Inc., 2022b. URL htttps://proceeddiiee neurips cc/ paper files/papall /ptprr//222//i1le// 2oc65442887446666444000000013312 Papeeaaaaaaaaa--aeeeeeeeeee- Cenaer--Coffrennee pdf
D. J. Foster, A. Block, and D. Misra. Is behavior cloning all you need? un- derstanding horizon in imitation learning. In A. Globerson, L. Mackey, D. Bel- grave, A. Fan, U. Paquet, J. Tomezak, and C. Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pages 120602- 12022-12066.... Curran Associates, Inc., 2024. URL https::/ppocceddeee 1aa266996e1110005511004656606000
neurips. cc/cccc/aa/o cc/paper.... wwwes/llappaeee sille//aaprr/2224fiill Paper Paper-Conference pdf
M. Geist, B. Scherrer, and O. Pietquin. A Theory of Regularized Markov Decision Processes. In International Conference on Machine Learning (ICML), 2019.
T. Haamoja, A. Zhou, P. Abbeel, and S. Levine. Soft actor-critic: Off Off-policy maximum entropy deep reinforcement learning with a stochastic actor. International Conference on Machine Learning (ICML), 2018
11

---

L. Hammond, A. Chan, J. Clifton, J. Obbermair,,er,.iirr....e. A. Khan, E. McLean, C. Smith, W. Barfuss, Foerster, Gavenčiak, T. Han, E. Hughes, V. Kovařík J. Kulveit, J. Z. Leibo, C. Oesterheld, C. S. de Witt, N. Shah, M. Wellman, P. Bova, 'T. Cimpeanu, C. Ezell, Q. Squillade-Montixy M. Franklin, E. Kran, Krawezuk, M. Lamparth,
Lauffer, A. Meinke, S. Motwani, A. Reuel,
V. Conitzer, M. Dennis, I, Gabriel, A. Gleave, G. Hadfield, N. Haghtalab, A. Kasirzadeh, S. Krier,
K. Larson, J. Lehman, D. C. Parkes, G. Piliouras, and I. Rahwan. Multi-agent risks from advanced ai. Technical Report 1, Cooperative AI Foundation, 2025.
L. Hellerstein, T. Lidbetter, and D. Pirutinsky, Solving zero-sum games using best-response oracles with applications search games. Oper Res., 673)773, May 2019. ISSN 0030-364X. doi: 10. 10.1287/opre.201 2019 URL hww.::tttt//ooo ot/p//2b...rr//11.1188//p/e 2019.1853
C. Jin, Q. Liu, Y. Wang, and T. Yu. V-learning-4 simple, efficient, decentralized algorithm for multiagent reinforcement learning. Mathemutics of Operations Research, 49(4):2295-2327 2024.
R. Kidambi, J. Chang, and W. Sun. Mobile: Model-based imitation learning from observation alone. Advances in Neural Information Processing Systems, 34:28598-28611 2021.
T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
H. M. Le, Y. Yue, P. Carr, and P. Lucey. Coordinated multi-agent imitation learning. In Proceedings of the 34th International Conference Machine Learning Volume 70, ICML'17, page 1995-2003. JMLR.ogg org, 2017.
Y. Li and C. Zhang. On efficient online imitation learning via classification. Advances in Neural Information Processing Systems, 35:32383-32397, 2022.
Q. Liu, T. Yu, Y. Bai, and C. Jin. A sharp analysis of model-based reinforcement learning with self-play. In International Conference on Machine Learning, pages 7001-7010. PMLR, 2021.
V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Ried- miller, A. K. Fidjeland, G. Ostrovski, S. Petersen, C. Beattie, A. Sadik, I. Antonoglou, H. King, D. Kumaran, D. Wierstra, S. Legg, and D. Hassabis. Human-level control through deep reinforce- ment learning. Nature, 518(7540);529-533 2015.
A. Moulin, G. Neu, and L. Viano. Optimistically optimistic exploration for provably efficient infinite-horizon reinforcement and imitation learning, arXiv preprint arXiv:2502. 2025.
Orabona, modern introduction to online learning, 2023.
M. J. Oshorne and A. Rubinstein. course in game theory. MIT press, 1994.
J. Perolat, B. Scherrer, B. Piot, and O. Pietquin. Approximate dynamic programming for two-player zero-sum markov games. In Bach and D. Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 1321-1329, Lille, France, 07-09 Jul 2015. PMLR. URL URL httpttttt///ooceediiiii mlr press// v37 v37/perolat15. html
D. A. Pomerleau. Efficient training of artificial neural networks for autonomous navigation. Neural Computation, 3(1):88-97, 1991.
N. Rajaraman, L. Yang, J. Jiao, and K. Ramchandran. Toward the fundamental limits of imitation learning. Advances in Neural Information Processing Systems, 33:2914-2924, 2020.
N. Rajaraman, Y. Han, L. Yang. J. Liu, Jiao, and K. Ramchandran. On the value of interaction and function approximation in imitation learning, Advances in Neural Information Processing Systems, 34:1325-1336, 2021a.
N. Rajaraman, Y. Han, L. F. Yang, K. Ramchandran, and J. Jiao. Provably breaking the quadratic error compounding barrier in imitation learning, optimally, 2021b. https:// org/ abs has//210.. 12948.
12

---

G. Ramponi, P. Kolev. O. Pietquin, N. He, M. Lauriere, and M. Geist. On imitation in mean-fiell games. In A. Oh, Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine. editors, Advances in Neural Information Processing Sysiems, volume 36, pages 40426-40438 Curran As- sociates, Inc., 2023. htRL//ttpps:/prcceddnng
httpccppper___eeeeeee www.flllsppppllee / pdf
A. Rosenberg, A. Cohen, Y. Mansour, and H. Kaplan. Near-optimal regret bounds for stochas- tic shortest path. In H. D. III and A. Singh, editors. Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 8210-8219 PMLR, 13-18 Jul 2020. URL httt/httsss///e/ httpp::/pproceedings mlr malr.pres//v19/ rosenberg20a.
S. Ross, G. Gordon, and D. Bagnell. A reduction of imitation learning and structured prediction to no-regret online learning. International Conference on Artificial Intelligence and Statistics (AISTATS), 2011.
M. Samvelyan, T. Rashid, C. Schroeder de Witt, G. Farquhar, N. Nardelli, T. G. J. Rudner, C.- M. Hung, P. H. S. Torr, J. Foerster, and S. Whiteson. The starcraft multi-agent challenge. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS '1,, page 2186-2188, Richland, SC, 2019. International Foundation for Autonomous Agents and Multiagent Systems. ISBN 9781 9781450363099.
B. Scherrer, M. Ghavamzadeh, V. Gabillon, and M. Geist. Approximate modified policy iteration. In Proceedings of the 29th International Coference on International Conference on Machine Learning, ICML' 12, page 1889-1896, Madison, WI, USA, 2012. Omnipress. ISBN 9781 4503 12551.
S. Shalev-Shwartz, S. Shammah, and A. Shashua. Safe, multi-agent, reinforcement learning for autonomous driving, 2016. URL
www. abs/ 1610. 03295
J. Song, H. Ren, D. Sadigh, and S. Ermon. Multi-agent generative adversarial imitation learn- ing. In Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31, Curran Associates, Inc., 2018 URL attps://prooceednngg hww.eeddiiiinnnunnns..... cc/paper.ppp.....ppcpp 0ww.:456607980113444662222202222
wwtpcpppeeflleeeeppeepeeeeeeeeee Shraperffles//ee www.ee/paapr///18/////// pdf
W. Sun, A. Vemula, B. Boots, and D. Bagnell. Provably efficient imitation learning from observation alone. In International conference machine learning, pages 6036-6045. PMLR, 2019.
G. Swamy, S. Choudhury. J. A. Bagnell, and Wu. Of moments and matching: A game- theoretic framework for closing the imitation gap. In International Conference on Machine Learning, pages 10022-10032. PMLR, 2021.
G. Swamy, N. Rajaraman, M. Peng, S. Choudhury, J. Bagnell, S. Z. Wu, Jiao, and K. Ramchandran. Minimax optimal online imitation learning via replay estimation. Advances in Neural Information Processing Systems. 35:7077-7088, 2022.
G. Swamy, D. Wu, S. Choudhury, D. Bagnell, and S. Wu. Inverse reinforcement learning without reinforcement learning. In International Conference on Machine Learning, pages 33299-33318. PMLR, 2023.
J. Tang, G. Swamy, F. Fang, and Z. S. Wu. Multi-agent imitation learning: Value is easy, regret is hard. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomezak, and C. Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pages 27790-27816. Cur- Associates, Inc., 2024. URL httpt:tttt//.ceeeeeee neur.sg httpipppp.cppppppppeeeee cc/paper_p.p..e..e f files/pper// .pd
L. Viano, A. Kamoutsi, G. Neu, I. Krawezuk, and V. Cevher. Proximal point imitation learning. Advances in Neural Information Processing Systems, 35:24309-24326 2022.
L. Viano, S. Skoulakis, and V. Cevher. Imitation learning in discounted linear MDPs without exploration assumptions. Forty-first International Conference on Machine Learning, 2024. URL htttps://ppereviiee .nt. hwt.:eeneeeeooorrrrae--o-hhaaaaa
13

---

N. Vieillard, T. Kozuno, B. Scherrer, O. Pietquin, R. Munos, and M. Geist. Leverage the average: an analysis of kl regularization reinforcement learning. Advances in Neural Information Processing Systems, 33:12163-1211
2020.
S. Viel, L. Viano, and V. Cevher. Il-soar: Imitation learning with soft optimistic actor critic. In Forty-second International Conference on Machine Learning. 2025.
K. Waugh, B. Ziebart, and D. Bagnell. Computational rationalization: The inverse equilibrium problem. pages 1169-1176, 03 2011.
Q. Xie, Y. Chen, Z. Wang, and Z. Yang. Learning zero-sum simultaneous- markov games using function approximation and correlated equilibrium. In Conference on learning theory, pages 3674-3682. PMLR, 2020.
Xie, Jiang, Wang, Xiong, and Y. Bai. Policy finetuning: bridging sample-efficient offline and online reinforcement learning. In Proceedings of the 35th International Conference on Neural Information Processing Systems, NIPS 221, Red Hook, NY, USA, 2021. Curran Associates Inc. ISBN 978171384539
T. Xu, Z. Li, Y. Yu, and Z.-Q. Luo. Provably efficient adversarial imitation learning with unknown transitions. In Proceedings of the Thirty-Nints Conference on Uncertainty in Artificial Intelligence, UAI 233 JMLR.org. 2023.
L. Yu, Song, and S. Ermon. Multi-agent adversarial inverse reinforcement learning. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 7194-7201. PMLR. 09-15 Jun 2019. URL https::/
mlr ppwss//97/yyuue htt.9/9../.../mmm/
H. Zhong, W. Xiong, J. Tan, L. Wang, T. Zhang, Z. Wang, and Z. Yang. Pessimistic minimax value iteration: Provably efficient equilibrium learning from offline datasets. K. Chaudhuri, Jegelka, I. Song, C. Szepesvari, G. Niu, and S. Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 271 27117-27142, PMLR, 17-23 Jul 2022. URL htl.https:// https::/procceddii mlr http://s.ww..ppps///e..eemes press/vv62. zhong22b.. html
14

---

Contents of Appendix
This appendix provides supplementary material to support the main findings the paper. It begins with an overview of all the relevant notations used throughout the work, followed by review of related work. We then present the complete proofs for key results (Appendix [C Appendix G which were omitted from the main text. Appendix [ outlines how our framework can be extended to n-player general-sum games. Further details on our experimental setup, results, and practical application considerations are provided in Appendix this section also features comparison with the lower bound from Tang et al. (2024). Finally, the appendix compiles list of useful results, along with their proofs, that are referenced throughout this work. For better overview provide table of contents.
Notation
16
Related Work
17
Proofs on BC Upper bound
18
Proof for necessity of C(p
21
Analysis of BR Oracle Algorithm
22
Analysis of Algorithm
26
Analysis for the RL inner loop
28
Showing validity of the bonuses
30
G.2 Bound the bonus sum
32
G.3 3 Final UCBVI bound
33
Properties of the reward estimate
33
Extension to n-player general-sum games
33
Comparison Lower Bound in Tang al.
39
J
Experiments
40
Environments
40
J.2
Experimental Setup
J.3
Practical considerations
J.4
Additional plots
41
Useful Results
15

---

A
Notation
Notation
Description
g
Two-Player Zero-Sum Markov Game
S
Finite (joint-)state space
A
Player I's finite action space
B
Player 2's finite action space
Amar
Max action space size, max([A), [B]) max; max;((AA)) Transition function
P
r γ
Reward vector
Discount factor
do
Initial state distribution
AA,A9
Probability simplex over action spaces A, B
μ
S + A. Policy of player
V
S As. Policy of player 2
VR.
State value function for policy pair (H, v) at state State-action value for (1,, v) at (s, a, b)
QUA (8, a, b)
dun (s')
State visitation probability for policy pair (μ,, v)
Nash Gap(u,v)
Gap to Nash Equilibrium (NE) for strategy pair (1,, v) Best response set
br(.)
nº E br(v)
Best response strategy for player to Best response strategy for player 2 μ E-approximate Nash Equilibrium
D* E br(H)
E-NE
(s'(ss,
Induced transition to s' from (s, a) with fixed v
II
Set of all possible policies Dataset of N trajectories Number of trajectories in dataset k-th trajectory in dataset
D
N
Th
H
Trajectory length, H ~ Geo -7) Algorithm outputting policy pair Output/Behavior Cloning policy pair Single policy deviation concentrability of (J,, v) Probability of trajectory т given policies (n, v)
Alg
(0,0)
C(H,V)
P(T;HL,)
N(s, a), (),
Counts of (s, a), (s, b), s in D
8
Probability threshold (confidence bounds)
Error(D) Error
Error term for player 2's estimated policy Error term for player I's estimated policy State sets in constructed Markov Game Stochastic unbiased gradient estimates Learning rate
Septtl, Smpt12, Scopy u g n
yk: 2k
Policies from UCBVI in MURMAIL
Ryn (s), Ri (s)
Single agent stochastic reward in MURMAIL Optimality gap for RL inner loop Policy of player i and others in n-player games Total Variation distance
Eopt
Ti, -- (V,,,)
16

---

B Related Work
Here, we present the most related work to our results.
Single-Agent Imitation Learning. There has been significant progress in the theoretical analysis of single-agent imitation learning. In the fully offline setting, Behavior Cloning (BC) [Pomerleau [991] has recently been revisited by |Foster et al. (2024) using the log loss as supervised learning notion to be minimized between the imitator and the expert policy. Foster et al. (2024) shows an expert sample complexity bound independent of the horizon parameter under deterministic stationary policies and sparse reward function. Therefore, a dependence on the horizon appears only the reward function is dense or if the class containing the expert policy is non stationary. Moreover, they prove that, without further assumptions, interactive imitation learning cannot outperform BC in a worst case sense.
This last finding is surprising given the seminal results showing that interactive imitation learning algorithms such as Dagger [Ross et al.) 2011), Logger [Li and Zhang 2022] and On-Q In-Q or reward moments matching (Swamy et al. 2002 outperform BC with the 0/1 or total variation loss in terms of error propagation analysis. Alternatively, better error propagation analysis properties can be derived if resetting to states sampled from the expert state occupancy measure is allowed (Swamy et al. 2023
Some benefits over BC in the single-agent setting can be instead obtained with known transitions and initial distributions. Along this line Mimic-MD (Rajaraman et al. 2020) shows that the expert sample complexity can be improved by factor vH where // is the finite horizon of the problem. Moreover, this is the best possible improvement without further assumptions given the lower bound of Rajaraman et al. (021b] for N 2 6H. Swamy et al. [2022] improve further the upper bound in the small data regime N < H. Later, MB-TAIL [Xu et al. [2023] achieves the optimal sample complexity for the large sample regime just under trajectory access the environment (without requiring perfect knowledge of dynamics and initial state distribution).
Moreover, given trajectory access the MDP, imitation learning in the single-agent setting is possible without observing the expert actions. For example, is possible to imitate observing only the states visited by the expert (Sun et al. in Linear MDPs [Moulin et al.
Kidambi et al. |021 Viel et al., 2025) or from reward features 2025 Viano et al. 2024 2022]. To summarize, we have seen that in the single agent setting, interactive expert does not give an advantage while knowledge of the transition or sampling access to the environment comes with two main advantages (improved horizon dependence in the tabular setting and possibility of imitation without seeing expert actions).
2019
Strikingly, the scenario is completely swapped in the multi-agent setting. Our negative result Theorem 3.2 shows that given knowledge of the transition no significant improvements over BC can be expected. On the other side, our positive result Theorem 4.2 shows that in the interactive setting a consistent improvement is expected over BC if C(1., F) large.
Multi-Agent Imitation Learning. Theoretical work in multi-agent imitation learning is limited. Existing studies mainly focus on empirical results in cooperative [Bui et al. 2024| Le et al. 2017] and adversarial (Yu et al., 2019 Song al., 2018 settings, typically optimizing a value-gap gap objective, which does not capture the strategic component of multi-agent interactions. This is in contrast with the usual objective in most forward multi- aalti-agent methods which instead minimize Nash or regret gaps to measure deviations. To cite few examples, Bai and Jin (2020) learn Nash equilibria in zero-sum games with online access, Xie et al. 20200) extends the result to linear turn-based Markov Games, Liu et al. [021]] Jin et al. [2024] learn 8- CE. e-CCE and s-NE with or without suffering the curse of multi-agent respectively, Cui and Du 2022a] learn Nash equilibria in an offline manner and, finally, Bai et al. 2022 with bandit feedback and online interactions with the environment.
In imitation learning, the first to adopt the Nash gap Normal Form Games are Waugh et al. [011]] Recently, the Nash gap has also been considered in Imitation Learning for mean- mean-field games Ramponi
et al. 2023). The authors provide an upper bound for BC and adversarial Imitation Learning that is exponential in the horizon in case the dynamics and the rewards depend on the population distribution. To overcome this exponential dependency, the authors introduce a proxy to the Nash imitation gap, based on a mean field control formulation, that allows to construct an upper bound that is quadratic in the horizon. Overall, they focus on finding metrics that, if minimized they imply a small Nash gap in virtuc of the above error propagation analysis. However, their work left open how the Nash Gap can
17

---

be minimized algorithmically. In this work, we take an alternative approach that works directly on upper-bounding the Nash Gap and focuses on developing an algorithmic rather than general error propagation analysis. The closest to our work is Tang et al. [024], extending this to finite-horizon Markov games where the observed expert data are sampled from a correlated equilibrium profile. They show that when the transition dynamics are unknown, the regret scales linearly with the horizon, even if behavior cloning successfully recovers the expert policy within the support of the expert's 's state distribution. To address this issue, they propose two algorithms: BLADES, which explicitly queries all single-policy deviations from the current strategy, incurring an exponential dependence on the size of the state space, and MALICE, which assumes full state coverage in the offline dataset and still incurs in a computational cost exponential in the number of states. While Tang et al. (2024) present an error propagation analysis. neither MALICE or BLADES are accompanied by a formal sample complexity analysis, leaving open questions about their statistical efficiency in practical settings.
Our work proposes an algorithm MURMAIL which is provably statistically and computationally efficient, marking a significant step forward with respect to the current literature on the topic. Moreover, on the lower bound side, we extend the construction by Tang al. [2024] to hold even if the learner knows the transition dynamics of the game.
Offline Zero-Sum Games. In offline zero-sum Markov games, Cui and Du [202a and Zhong al. [222]] show that learning is impossible the dataset only covers Nash equilibrium strategies. Instead they show that a unilateral concentration is required to recover Nash equilibrium strategies. This result highlights a fundamental gap between offline learning in multi-agent versus single-agent settings. Their lower bound is constructed by considering two distinct Normal Form Games that differ only in the reward of single joint action, resulting in different Nash equilibria. The dataset includes actions from the equilibrium and suboptimal strategies but omits data corresponding to deviations from the observed equilibrium. As a result, the two games become indistinguishable under the available data, as the missing deviations preclude disambiguation. However, this argument does not extend to the imitation learning setting, where the dataset is restricted to the (deterministic) expert policy, resulting in perfect recoverability for their considered Normal Form Game In this case, establishing hardness requires a more nuanced analysis that leverages the multiplicity of equilibria. Furthermore, it is important to note that their deviation coefficient is defined with respect to the maximum over all possible policies, whereas in imitation learning, it is defined only relative to the estimated Nash equilibrium strategy.
C Proofs on BC Upper bound
In this section, we give the omitted proofs for Theorem 3.1 In the first step we state the error decomposition of the Nash Gap
Vaa (P'"((ss) Viie" =Va" -Va''(so) VuBUE (5o) + Vu B (5o) Vāav
<vu" ((u))(so) Vua wB (so) VuP N² (so) Vū.u"
(p)
where n² br()) and D$ E br(ū). We recovered for player depending on the estimation of player 2's policy (Frror(D)) and for player I's policy respectively (ū)). In the following, we will only give the proofs for player 1, as the proofs for player 2 follow analogously. Next, we give a useful lemma that upper-bound the value difference in two-player game, when one player's ss policy is fixed in both value functions, by the total variation. We give the general result and then apply it to our case.
that we can split the error into an error for the policy
Lemma C.1. For any policy μ of the max-player, we have that
(Vm'(s)) vua! vu. (so) S
(v(- (())))
Similarly, for any policy u of the min-player, we have that
(BO) - Vul (8o)) 5 1
E
7 TTV (u(- s), ())
18

---

Proof. Here, we only prove the first statement. The second statement can be proved by the same idea. we have that
By K.I
(Bass)oees [quiur (s,a,b)) [qm Baa. (0, (0..a
(s0)(s)) Var (Bo) = Bus Σn
Applying the triangle inequality leads to
Vu (8o) Vune (su)
s Bup
Σ x Blabo)num
- Blaoorau (Quir' (s, [s,aab]]]
For the term ((OND)<(u)) (Que (o, a bi] Bladrimn [Quir (s, a, [aabbb]] we have that
E ((ab))((m)) [QuIn (s. E(ad))(me)) [Quur' (s,a,))
Σ Σ pla 8) (v(b) 8) -b ((bls)) Qui' (s,a
AEA
2
< ula 5) Σ
|u(b) 8) - 1/(b| s)s
bEB
2
TV (v( s., ())
where we again applied the triangle inequality and the fact that the rewards are bounded by Additionally, in the last equality we used the definition of the total variation and the fact that u(. s) a probability distribution.
Combining the obtained results we get
(so) Vu. (
2 1-9 BuN
Σ
7
(V(((-1)))
which completes the proof of the first statement.
Applying the result to the BC setting and noting that by definition of the best response have Va (so) Va u (so) 2 0 for 2² br( and that the result needs hold true Aμ br(v), we
obtain
Σ ET'TV (. (8)8 1n)) t=0
Error(0) = V*" (30)
VH L (8o) S 1-
max E ERD pEbr(D)
Similarly, for any policy of the min- min-player, we have that
max BnE,D (fror( = yu" .0' (so) - vu.u" (80) S 1- MEbI(a)
Σ
7 TV (4 s). P(- [s)]
The reason for the additional max (and min) is that the best response map for a given policy is generally not unique, so we need to pick a distribution from that set. To make the bound apply to all possible best responses, we pick the maximum (or minimum) from the best response set.
Using the definition of the expectation and doing a change of measure, we get
Vu ( - Vu (5o) <
2 Y
max EE EP mEbr(D)
Σ
TV (N (-1 (s, $))
dunc (s)
que WE (s)TV (,=(.1s),0 s))
max - ? (Ebr(P)
due wut (s)
1=0
SES
du R
<
max ? mEbr(P)
Σ
7
TV (u
s), D() ((((s)))
1==0
19

---

Note that we can do the change of measure also with respect to more general offline distribution p. Here, we use p p= du " " If we would use the general offinn sampling distribution, we would have
dR.u" R
2
VA (s0) VHT." (50)
((s)TV s),0((11))
max MEbr(P)
1-
1=
SES
2
diccc
TV (v (- ()) s))
max
E
1 Y MEbr(P)
P
Next note that j E br(() depends on the estimation of the policy n and therefore is a random variable. To avoid such term in the upper bound of the expression make use of the following upper bound:
2
dR.cE duR
(PT.s))))))) (1)))))))) 181)
max (ebr(()
B L.E
Σ TV
1- Y
du
2
Σ TTTV (V 10))
5
max max 7 well nEbr(w)
du
where v II is any admissible policy for the second player. Taking the maximum over the best responses to this more general policy class forms an upper bound.
Additionally, note that the expectation is now over the expert policy, therefore we can use the dataset to get an estimate. Therefore, we apply the standard concentration argument to upper-bound term E, / vs ES
TTV (v s), D( s))] K.2 and union bound, with probability at least 1-5 55/2,
2| log(2)
TV (15())) S
max (N((),
Then, we can have that
ER عي
E
TTV (191s),))))))
<
B
(s)
2 B log S1/5)
7)
max N (s),
1=0
SES
2 wD (s) log (2g( max (N(),, 1}
due WE (s)
(1 7) SES
.R (s) 2|Bladu
(og((((11))
7)
1s)
BES
16 log 2 (2/S//8)
7)
N
SES
4
[S||B] log 2 (2(51/5)
(1
(1-7)
N
where in (i) we applied Cauchy Schwarz and in (ii) we applied Lemma K.3 size of the dataset. Finally, we obtain the policy value bound.
and we denoted N as the
dunce dun we
|||| [ log" (2 (8))
V4" ( VK" R (5o) S (1 7)2 well MEhr(y)
max max
N
20

---

and doing the same analysis for player we get
vuew" (su) Vùin (su) -
8
du du ce
[S] LA log (2|5)
max max MEt vEbr(M)
(1 (1-
Finally, by using the error decomposition derived in the first step, defining Cmax == with = du "0" and use
max maxven maX(u)) dic max maXyetr(a) qa
that [Amax] = max[|AA] B we obtain with probability of at least 1
8
S Amax log (2/51/6))
VN (su) Vir (so) S Cuaxx (1 y)-
N
completing the proof of Theorem 3.1
D Proof for necessity of C(pE, vE)
In this section we give the proof of Theorem 3.2 showing the necessity a bounded C(uB, uB) for non-interactive imitation learning even if the learner is fully-aware of the transition model. For
better understanding of the following proof it is essential to remind ourselves of a (simplified) Markov Game hardness construction introduced in Section 3.1 and illustrated in Fig. I
Proof of Theorem 3.2 Let
us
consider the following family of Zero-Sum | with action spaces of the same cardinal- (aI,a2..., ag, (it1,..,,,...11........ "IA1). B
Markov
Games
Goc
ity [A]
given by A
(b), be.b.............. be_.,,,, bi+1....... b and shared state space for both agents S
From now on we can divide the state space into parts. We have Sexpert == {sy, 82, Sy the states visited by the expert, $1 the gating state, Sxplt1 == {sxplti, ..... Sxpli the states where player I can be exploited, Sxplt2 == ( (x)))2 the states where player 2 can be exploited and Scopy := {s's, ..... - , that are copies of the final states visited by the expert in the sense that they are sharing the same reward. Additionally, consider dirac on state so distribution, i.e. ds(s) = 8eg The transition model is deterministic and in states except so and 81, simply transition to one neighboring state. Therefore, we only give a detailed description for these two states. And for the gating state $1, we only consider the next potential set of states, as states inside these sets share the same reward function and each action pair leads to unique state inside these sets, i.c. every action combination leads to a different state. particular, we have
{so, 81, 82, $3, 8/, ...., 32 -1 explt), 8xplt1, 1121-1))/22 Sxplt2, 2xph
initial state
if (a, b) = a,,;
(. 50, a.
$1 otherwise.
Scopy: if (a, ((a;,bi) U b(a,,)) b.) Vj Vi e).
Sxpli, (a, Ep.q
Sxpt22
otherwise.
where Eng = {aas, by) vj + i} U {(in)) bj,) | <
q S - 11 and jm ig (1..... [A)) (i). The state-only reward, which equals across all games inside the sets 9, G is given by
(x()) - ff-
if Sexplt2
if E Sexpltl. otherwise.
As the considered Markov Game is Zero-Sum Game, it holds that R2(s) - (s). While the transition dynamic looks complicated, the two important things to keep mind that, once an agent differs from action a and b, respectively, an action can be chosen in such a way, that the following state is inside Sxpltl or Sxplt2 respectively and all action combinations has a unique follow up state, i.c. |Scopy| U [Sppti| U [Sxph2l
[A] [B]
21

---

It follows that the actions taken by the agents only matter in the states So and s1. For these states
we consider the following Nash equilibrium expert policy p=(a, so) r so) 1 and
[a $1) (b; 81) = 1. It follows immediately, that the given policy is indeed a Nash
equilibrium as no single agent benefits by deviating. Additionally, note that for all actions a, j # i,
each player is exploitable in 81.
An illustration of the described Markov Game for |A| = [B] 3 can be found in Fig. a, ag and b; bz.
| where
Next, note that for all 9s E 9oo it indeed holds that C(u 22)
fixing for example policy
f another best response for player, i.e. μh E br(v") is given by 2 (a, (S)) = 1, for j * and
u (a: $1) = (a, $1) = 1, meaning that the only states visited by the policy pair (uă, BB) are 80, $1, 8/4
Now we show that for the family of Markov Games 9x where for each G3 E 9-0 it holds that C(pB,vB) = 0o, any learning algorithm Alg has a Nash Gap of the order (1 - --- For that let (D, be the output of any non-interactivv imitation learning algorithm Alg with data from (4 v²). It is important to observe that since all games in Goo. are identical in s0 and they differs only in transition dynamics from 81. However, no information about 81 is available in D. Therefore, the learner has no mean to distinguish which game she is facing. For this reason pr, D' do not depend on the game index i. Then denoting by AAIg and Baig the action played by the learner in the state $1, holds true that
max V 1 (80) 0.E9
-V
V.-L" (8o)
9,
Vaa $ (80)
Viee
G; (50)
|AI
1
Σ
tb:) P(BAI & bi)
Σ1A1 P(ANII i 4 ai)
+
(1-7)
|AI
A
Σ/ D(bs) 111))
+ E/ (1 Ta(a [81))
(1 (1-))
[AA
|A|
|AA| 11
[AI
-1-1
(1 (1-))
1 |A|
AA
1-7
where (1) follows from the construction of 9, E C(p (VH,, as all actions, but actions ag by are exploitable by the opponent in the game Gi.
Additionally, note that even if the learner has access to the transition dynamics, the learner can not differentiate the actions from 81 as all actions lead to different states. Therefore, she cannot use this knowledge to recover an action that would lead to s E Scopy. which would avoid a regret of the order(1 -1- This completes the proof.
E Analysis of BR Oracle Algorithm
This section presents the analysis of Algorithm | which provides a sample complexity guarantee without requiring single deviation concentrability under the assumption of a Best Response Oracle (Definition 4.1. The difference the later presented algorithm MURMAIL Algorithm that here we can query the best response oracle to sample from the expectation that contains the best response of the current policy μæ and Vs respectively. discounted state distributions. However, as noted in our discussion around Eq. 3 we first have to transform the optimization problem into a convex one as the original objective our optimization problem is non-convex. This results in Eq. (4), from where
particular, we sample a state from the induced
obtain Martingale difference
22

---

sequence and a regret term, which then can be minimized as we now can construct an unbiased gradient estimator and use a version of online mirror descent construct an update of our policies.
Now, we restate the theorem and give the complete proof.
Theorem 4.1. Let us run Algorithm for K = =O (
|S||Amma IngglAmaa (og(1/)) iterations with (1-7)'e²
learning rate 17 2|5] log, Amaxl
) k= satisfies with probability max (do. -oin)) (do, Vikie) I O Therefore, setting
Then, the sequence of policies {pk: Vi
K
at least 1 55 that K Ei=1
5 (e) ensures that for certain k ~ Unif((K)) it holds that E Wash-Gap(1es "g) S e. That is, Mg Mg is an e-Nash equilibrium in expectation.
Proof. In the first step, square the optimization problem and decompose into part that considers policy μaf for player 1 and vi for player 2.
min (do, Vuulo) ) well
1
do, Vuim - puule) ))
max (do, V..t
K
MElI
K
K
do. VAiie VARUE VURRER VHA.
K
do Vuiin VARINR + Vuo.t - Vmmlii)
K
K
2 dos Vulinn vuive)) +2
do. VrEet vunee)
(5)
K
K
where m E br(vk) and oi E br(us). At this point, dividing by K squaring and applying the performance difference Lemma K.I that allows to decompose the global regret into a weighted some of regrets at each state, we obtain
do VuENS vunres) )
2
t K (un pa( na((ss)]] 2
E
2
- (-ee))))))-))) v Ammax (1 (1-))-1
E
1=1
K
Amuxx
<
E
(6)
K(1
7)
Joml
where the second last step used the Cauchy-Schwarz inequality and the last step used the Jensen's inequality and the concavity of the square root, Analogous steps give
do, Vužia -VHt.e) ))
Amaax K(1 7)2
[IIEE((s)) rr((1ss))]] (7)
K
E
anva u
At this point, we see that the expectation over the best response and the current policies of iteration k. Therefore, we now make use of the Best Response Oracle to sample St d'a.rt and S% ~ d Next, we can add and subtract the terms [ na (+(()) 1|2 in (6) and ||vx(11S)) vx (=1
23

---

in and we obtain that
K
do, Vue. - vua.i)
K
k=1
Amaxx
[IuE(+ss) (+(+)s)))] [1ux((1)))) (-s()))))))))
K(1 7)²
k=1
(Martingale)
Amaax
Σ K(1 7)2
-
(Regret)
We have that (arttigale) can be bounded follows via Azuma-Hoeffding inequality (see c.g. Theorem 7.2.I in [Alon and Spencer 2004)). In particular, define Xx Eand [||ME(||s) - px (-1s)]1 (Iee(-1s)) pu p (1 notice that {X+) is a martin-
gale difference sequence almost surely bounded by Therefore, it holds with probability at least 1 that
Σ Ea [I
pxx(1s))l - [1 - / log(116)
Finally, for (Regret) let us define the loss (x() = ||ME(-) - ua- 11 and notice that lu (NE) 0. Therefore, by convexity of lx.
Regret
Σ (a(()) lx (ME) S Σ (alx(px): me)
where we have that V = respect policy evaluated particular state are given
V (n and the gradients with
-
- ME(-1S) 5 = St
V Vu(lose((ME)
= 0 otherwise
Since we do not have complete knowledge of the expert policy but only sampling access to it, we need introduce the stochastic gradient estimator d To this end, we sample an action A (=(()))) and we define the following gradient estimator
(4(-1s) eAy if = St.
gh -
otherwise
Notice that of unbiased and we have that llot (e(le) S oAx - S 22.
Therefore, the sequence {
j- where Y2 (Vnls(us) Lt Ms mE) is a martingale difference
sequence adapted to the filtration J. which includes the algorithmic randomness up to the generation of μa. Indeed we have that E [Y][F,] 0 and
E [
S R [1o:
Ilme (E(1) -
well 1r < 4 (S].
Therefore, thanks application of the Hoeffiigg inequality, with probability at least 5
(pla(ux)= 2hh pk HE) S /2K log(1/8).
24

---

Therefore, we can bound the regret as follows
Vulalue), ux - -ME)
Σ Sh pa - ME) +
V Vuln(uu)) - Ik PN pE)
|S] log A
17
K
(u(1sk)) - -cat + 22K |S| log(1/6)
+
2
k=
|S] log |maax
n₁K
+ 2K (0g(18))
7f
2
K |S] log Amaa
2K log((1))
2
where for the first term, recognized that the policies updates in Algorithm [ can be as mirror descent updates (see Lemma E.I and we used the standard regret bound for online mirror descent (see for example Orabona (2023) instantiated with the following Bregman divergence
Eoes DR (p(()s),, pl (-Is) and with learning rate 7) 2|5] log Amaxl as done in Algorithm All K
in all, we obtain via union bound that with probability at least 40
do, VARNE VAL.i )
K k=1
Amax
(2 + 1) log(1 (1/6)
S log Amaxl
7)²
2K
Moreover, analogous calculations give
K
do, VHime - VALuE)
K
k=1
Amax )
(2|5) + 1) (og((10))
S log Amaxl
K
2K
Then, plugging into (5,, using union bound and taking square root both sides, obtain via another union bound that with probability at least 55
max (do, Vu.ee Nell
min (do, VuR.") well
Amaxl - 7)
(2|5) + 1) log(1/6)
S ||g log Amax
K
2K
At this point, setting K 0 (15) log Amax log(1 (og(1/8)
ensures that with probability at least 1-58
(1-7)a4t
Σ
max (do, Vioay min (do, VIL.U) < (E)).
well
well
Therefore, the total number of expert queries is O(K) =0 (0111) ||5|| log Amax log (1/8)
(I --
The next results shows that the policies updates used in Algorithm and Algorithm 2 are mirror descent updates for an appropriately chosen Bregman divergence. To this end for any p. d E A define the KL divergence as KL(p.g) q) Ene p(a) (p((()(((()) with the convention that (p. 0 if there exists an action such that p(a) 0 and g(a) > 0.
25

---

Lemma E.1. The updates used in Algorithm and Algorithm 2 that is
Mb+ (a 8) x pa(a 8) exp (-19% (8, a)) Uk++ 8) vx(b 8) exp (8,9) (8, (
equivalent mirror descent updates for the Bregman divergence Eees KL (L(u(-]ss (u That is, the updates can be equivalently rewritten as
Pk-1 argmin (gt p)
pell
and
argmin (g% 1/) well
Σ KL(p(((s),
Mk+1
Proof. We prove the result for one player the js player) The result for the other player would follow exactly the same steps. Let us consider the proximal update
Pk-1 = argmin (gth (i) + 1 Σ KL(u((o))
SES
The Bregman divergence chosen is induced by the function (1) EE,es EeEA u(als) log u(als) sum of the negative entropy over the state space. Notice that the gradient norm tends to infinite 1 approaches the border of the policy space (i.e.
entries p(als) tends to zero), that is limp--5m || (n)]l. This means that the first order optimality condition implies that the derivative F(n) = (ok 14) + E.es KL(((--)s), (+(s) equals zero at the minimizing policy which is pk+1 by definition. Therefore, in the following we use this fact to derive the exponential weight updates used in Algorithm and
VF((-1) =0 (e a) + log (H++z(als)
[xx(ass)
=
for some c E IR which ensures normalization of pk+1. Therefore, inverting the last expression, we get (a)s) = Ma (als) exp (miC (s,
Choosing E R to ensure that Vs E S it holds that EeEA Mx+1 (als) = 1 concludes the proof.
F
Analysis of Algorithm 2
This section presents the analysis of Algorithm 2 which provides sample complexity guarantee without requiring neither concentrability or best response oracle.
Theorem 4.2. Let us run Algorithm for K = O (1 [|
log Amari log(1/e)
outer iterations
(1 15
and T = O |SP|Ame (og(11/)) inner iterations with learning rate 2|S Amax!
Then, for a
(1-1)884
K
certain lc Un]] it holds that E [Nahh [Nash-Gap(ug: (p))))u))))) S.
Proof. The proof follows similar to the one of Theorem 4. with the addition of an RL inner loop. In
first step, first derive the same decomposition as in (5). Again, dividing by K squaring, applying the performance difference, the Cauchy-Schwarzz Schwartz inequality leads to (6) and using Jensen's 's inequality and the concavity of the square root get
1 K
do VuEii Vmlee))
[Amaxl
K
<
E
[1HE((1s) ((c((ss)<(((ss)]]) (x)(1s))1
(8)
K(1 - 7)2
A=
where vx E br(ux) and analogously for ux
k
do, Vulue vuisen))
K(1 - 7)
Amax
D
20 k=1
[IIE(-1s) rn(-ls))?]
(9)
k=1
26

---

where ya E br(x)). At this point, as we do not assume to have access to a Best Response oracle, let us introduce the sequence {= and {yk ] produced by UCB-VI in the inner loop of Algorithm Since the stochastic reward used in the inner loop is unbiased and almost surely bounded by by
[IS)) AAml) log(1/8)
Lemma G.7 Lemma G.6 run for a number inner iterations =
ensures
that with probability
35
E in pk
< grdd [|ve(11s) p((()s))1]]
[11ee(1ss)) (x((1s))l Eopt
(10)
and
E dnint
[1E(118)) - S Ba-dde Me |IuE(-1s) na (+s)))]
Eopt
(11)
Note that now we can sample St ~ du and 5% ~ dann Therefore, we can again add and subtract the terms (1u=(11$)) uu (-15 in (8) and [|v=(115)) Px (-15%)) in ! we obtain that
do. Viee' - -
K
1=1
Amaxl
((uu(1))-wa(((s)))) BendRe.vs [1uEE(1s) m=(()=)1 -1Iu=((1St)- (0c((tt-ma((($300 -a(-15()11)
(12)
K(1
?)
k=1
Ammax
K
+ K( )
(uE(11()) -xx0))))(--1))) (=((11()11
(Regret)
Ammaxl
+
(1 7)2 Copt
(Inner RL Loop Error)
We have that
(12 can be bounded analogously as in Eq. Martingale) with S ~ dl
recognize that the policies updates performed by Algorithm 2 are instances of online mirror descent see Lemma E.T) Therefore, we can bound the regret term follows
Again, done in the proof of Theorem 4.1
K |S] log A
(Vlll(u)) mB) S
+ /2K (og((()))))
All in all, obtain via union bound that with probability at least 48
K
2
do. VRE Vmnees))
K
1=
Amax
(2 + 1) log( 1/5)
S log Amax
<
Eopt
7)
K
2K
Moreover, analogous calculations give
2
do. Vuiie VuLuEE)
Amaal
(2 + log log( 1/8)
S log Amax
<
71-
K
2K
Eopt
Then, using the same decomposition presented in (5) using union bound and taking square root both sides, we obtain via another union bound that with probability at least - 55
K
max (do, VH.Pk) - min (do, Vix.ar pell
K
well
k
4 Ammax
(2|5] + 1) log(1/8)
S log Amaxx
<
+
Eopt
(1 - 7
2K
27

---

At this point, setting O (15I) & log Amax 1o6(1/6)
ensures that with probability at least
(1-7)*5*
1 - 56
Σ max (do; V(mn)- - min (do, Hell
|Amax| (1 - 7) E
K
wEll
Finally, setting Capt
= AAmax -1 (1 E) that is T
O S Amar
Amgg Ing(1/8)
[1-7)-e4
ensures that with probability 1 56, have that R 2k maxдeπ (do, Viiee millee (do, VuE.") I O(e). Therefore, the total number of expert queries in O(K T) O [S||Amma Caannn/logglee AoglA 1og(1/6) | log((1/)) (1-7)5et
K
(1-7)*c*
G Analysis for the RL inner loop
For the RL inner loop analyze UCBVI for stochastic rewards in the discounted setting with a random reward. In particular we have that each time a state-action pair is visited we observe stochastic reward which is unbiased and with almost surely bounded noise. Compared to the standard analysis in Azar et al. (2017), we handle the discounted infinite horizon setting. In principle, MURMAIL can be used replacing UCBVI with other RL algorithms in the inner loop.
Algorithm 3: UCBVI
Input: iteration budget T, transition dynamics P. unbiased reward function sampler R. Initialize (s, = (1 - -) and Vi(s) = (1 - 7) for all s, a A.
for t t= 1 to T do
(s)s) argmax dEA Q,(s,a)
Sample A, ~ d= St P(, A.).
Generate stochastic reward function R₁ ~ R(S.).
Update counts Nr(s, a) Ni(s, a) + (S.AAs))))
Ne(s,a, s') Ne(s, a) + [(s. A,
Estimate transitions and reward
P,(5'ss,a)= = ((ss,,,8)
P((8,0)= Σt. (s
Ni(s,a)+1
Ni(s, +1
Set bonuses
4|51
log(2T(T + 1) (8))
by(s, a)
1-7 1
(1(s, +1
Update state action value functions
Pr + P.V, + b 10
Q4+1
V(+1()) max Q++1 (s,a aeA
end
return Tout such that dout = T -
-1=1 d
The first step our analysis is to invoke standard extended performance difference lemma in the infinite horizon setting.
We first introduce some Lemmas which will be useful in the rest of the analysis
(S,A, 7, P,r, do) and two policies n, ,, - AA Then consider for any Q I [AI and (*()s) (-(ss) (s..)) and Q yx' be respec- tively the state-action and state value function of the policy a in MDP M. Then, it holds that
Lemma G.1. Consider the MDP
28

---

(1 (L-2) (do, v= v equals
( @ -r--ppp + E Band
((((s, ( (11)))
Proof. A proof can be found in Viel et al. 2025
assume for the moment to have valid bonuses, that functions by such that they guarantees for all i [T] and for all 8, E S A
r(s,a) and we prove that under the above conditions pointwise optimism hold. This point made precise in the next Lemma.
- - - bs
Lemma G.2. Given sequence b. : x A IR such that
/P..vi(s.a) ( PV, a) + (s. r(s,a) s b,(s,a)
for all t (T), and 8,a S A it holds that
2 Va Qi Q=2 A tE
Proof. First, let us proof the base case. This is easy since (s, = and Vi(s) = - for all 1
8, S x A and it holds that Q" (s, S T and V* (8) I T-o for all s, a E S x A. For the
inductive step, let us set as inductive hypothesis that Qt - Q 2 0 and V - V" 2 0. Then, recall the update for Q++1.
Q++1= - 7 b:)
case the upper truncation triggered in generic state action pair 8, a, we have that Q++1 (8, a) QF (s, a) = Qs a) Q" a) 2 0 by the inductive hypothesis. For the state action pairs, where the upper transitions is not triggered we have that
Q4118, Q= ( + bb( 7 Q (s,a)
f((s,)) = + bb((s,)) - -r(s, -PV (s.a)
-PV=* (s,a)
+
>PVi(s.a) -PV* (s, 2.
Notice that the second last step follows from the validity of the bonuses and the last one follows from the monotonicity the operator and by the inductive hypothesis V V=
At this point we have proven that Q++1 Q* 2 0. For proving the optimism of the estimated state value functions we proceed as follows. Let a* = argmax Q (8,a).
V++( V= (s) max Q++1 a) max QT (s,
aεA
aEA
max (8,1 Q"' (s,a*) aeA
Qe41(s,a") - Q" (s,a") 0.
The next lemma bounds the regret of UCBVI (Algorithm) with sequence of valid bonuses with the sum of expected on policy bonuses.
29

---

Lemma G.3. Let us consider UCBVI run for T iteration with sequence of valid bonuses {be b then it holds that
1 (d. do. V
1V"--EA -V S T(1
2
T
d b.) +
|S| A - 2)
T
7)
t=1
Proof.
Using the point wise optimism in Lemma G.2 and the decomposition in Lemma G.1 we have the following decomposition the regret of UCBVI
do. V* -Vo)
T
(do, V₁ V
1
1
T
Σ
(d 0,,11 r + PPV) +
(d Qs - Qu+1)
T
T
1=1
1 T
T
Σ
dd Fc + 7 + be - r +PV)
+
(d Qu Q(+1)
T 1=1
T
T
2
Σ
(d bi) +
Σ dd (d", Q(+1)
-(41))
T
T
where last inequality holds thanks to the validity of the bonuses. For the second term, can get the following bound which crucially use in the first inequality the fact that the sequence (Qt) is decreasing.
T
f Q. Q+t1)
Σ
ae(s,a)-
T
Qe(s, - Qc-1(s,a)
T
8,0
t=1
Σ
a)
T 5,
|
(1 T)T
G.1 Showing validity of the bonuses
We show in this section how to design a valid sequence of bonuses.
Lemma G.4. Let us consider run UCBVI for T for stochastic reward almost surely bounded by 2, i.e. Rmaxx S 2 iterations and consider the following transition and reward estimators
Ni(s,a,s')
ΣT -t=1 N1(
(.
P((s'(s, Ne(s. a) +1 +1
Pe(s,a)
then the bonus sequence defined as
4|8] bx(8,a) 1-71
log(22([ + 1))
Nr(s. a) +1
satisfies
PP/ (((, + +-P.V((0,))) -r(8,a) (PV((.. 5 bb((,a)) e 2 21-20 28.
30

---

Proof. For all t E (T) simultaneously, we have the following high probability upper bound
P((s'ss,a) P(s'Is. ss,a]
Σ (s,, M, =. (
Ne(s,a) - +1
1 (S,AA,=,,)) |(5.),,=,00))(((/bs... ((s
a) +1
N)(s.a)
N((s,a) +1
1(St,Ar=sa)) (1(8)=x) P(s)|s,a))
1 (s.,
N1(3, +1
(N( +1)
T Di 11 (1(8;=0) P()'(s,a)
Ez (S. (()))s0)
(((s,0) +1
Ni(s,a) a) +1)
v (o (N + 1)/6)
ΣT (1, xa)) P(5|ss
ar(s,a) +1
( +1)
log(T(T + 1)/0) Σ l ( ((ss.)(V((s.o))
<V N)(s,))+1 +1
where the last inequality follows with probability - 5 from application of the Azuma Hoeffding inequality making special care of the fact that the total number of visits (e(s, a) is not an independent random variable with respect to the random variables of which
computing the mean, that
is {1 (s... (...A,=).a) 1 For this reason we pay the factor log( log(N, bound. We refer the reader to [Lattimore and Szepesvári 2020 Exercise 7.1 for details. Therefore, by triangular inequality and a union bound over the state space.
a) + 1)) in the upper
log(2T(T + +1) ())5)
Σ =.,n) Ni (N) +1)
P.((1s.0) - a( - V
+
Ne(s, a) +1
1og(2T(T + +1) (5)
No(s, a) +1
aN) +1)
For the reward concentration we have that
T (1 (Re r(s,a))
Ei I (s
Ir(s,a) - as)
Ni(5, a) +1
(N(s,a)(N((s, a) +1)
T (S,,A,, (Rs r((s,a))
+ (s,
Ne(s, a) +1
Rmax log (TT + 1)/5)
Rmax
N1 a) +1
(No(s, a) +1)
where the last inequality holds with probability 1-6 thanks the double sided Azuma-Hoeffdite inequality.
For the second part of the statement consider that each possible element of the sequence (V) T |S generated by UCBVI satisfies [|V]]l I 1-7- Therefore, holds that
P)Va(s,)) - (Vi,,, a)) < [7,(11s, (1 a) P(-1s, ||Vall
< |
- PP(-ss,))
|S]
(v
1og(2T(( + 1) [S| /6)
1-7
N1(s,a)+ +1
(Nr(s,a++1) +1)
31

---

where the last inequality holds with probability - 8. Therefore, it follows that for all t E [T]
simultaneously, with probability at least
26
Rmaa + |S|
a((s.a) PPV.(ss. r(s,a) - PV, a)
1 1-7
log(2T 1) 1)
1
No a) +1
(Ne(s,, a) + +1)
by (s,
where the final upper bound by the bonus uses that |S| 2 2 and
logd 11))
(s(s,))+1
(No(s.))1))
G.2 Bound the bonus sum
Lemma G.5. The expected on policy bonus sum is bounded as follows with probability 1 5
T
4|6] / log ( 1) ()|5//0)
Σ 1=1
|2|
1-7
16 [||
2T
Vlog(2T(T + 1) /8) log
1
| T log(1/6) (l00\/)(11))))
1 1-7
Proof. We apply Rosenberg et al.
2020
Lemma D.4] conclude that with probability at least 6
T Σ
16 ||
2T
th bi) 2 by (S, A,) + Vlog(2T(T + 1) /8) log
8
[=1
Then, we have that
T
T 4 ||
log (2g( + 1)
Σ (S, A,)
Σ 1=1
1
N,(S,, A,) +1
1=1
4 4|8|
12g + 1) 18/8)
T Ni Ar) +1
1-?
4|5] log (T)
T
1-3
Nr At) +1
t=l
Finally, it holds that
A.
NYSS, Ar) +1
t=1 1+ Ei=n 118,A.=8.at
S |A| lTg(T))
where the last inequality follows applying everything together concludes the proof.
Orabona 2023
Lemma 4.13) for f(x) -1. Putting
32

---

G.3 Final UCBVI bound
Lemma G.6. Let us consider UCBVI (Algorithm 3 in an environment with a stochastic unbiased
reward almost surely bounded by run for T iteration with a sequence of valid bonuses {be } specified in the statement of Lemma G.4 then it holds that with probability at least 36
T
SS) |AI (l]oo((1/))
|
dd.
- V <ō
+
T
(1 (1-7)*I
(1-7)
Therefore, for the mixture policy Tout such that 1 35
T Et=z d = drow it holds that with probability
do, V= V/oott
S Eopt
for T -O- -1(SS1-A))oo
(1-7))
Proof. The proof follows trivially from the combination of Lemma G.5 and Lemma G.3 and union bound over the event that the bonus are valid and the event under which the bound in Lemma G.5 holds.
G.4 Properties of the reward estimate
Lemma G.7. For any policy ı E 1l and expert policy E 11 consider a particular state s E S and sampling Ag (T)sss), A'g ~ TT(-ss) Then, the following facts hold
E
[fA== A 2n (m + [[ || (+)ss))
and
(A= A'23 2T (Anls) | S 2 almost surely
Proof.
First note that
[T x||²= = [|T((-1))] - -2(TE(-(s), (+1ss) + [+|s|1
Σ T 8)² + Σ a(a| 8)² - 2 - < s)x(a s)
Σ E s) Σ x(a s)² -2E (o s)].
Now, note that for a given a E A. we get that
TTE(a s) P(Ag a)²² ((Ag a))((A' a) P(Aş A'r) EE1 (A. 1gyl where Ag, A'g independent samples from T {). Therefore,
conclude that an unbiased estimator of || π | The second statement is easy to show
(A A A/g)= 2n (A s)) + | (-1s))]
11 {Ag A'2 - 2 (A4gss s) + [++(++ 1 (Ag A'e + [|T(-|))] < 2.
H Extension to n-player general-sum games
In this section, we sketch the analysis for the n-player general sum extension. The goal of this section to show that the algorithm design decentralized, meaning that can avoid the curse of multi-agents in re-laaer general-sum Games as stated in Remark 4.1 The idea is that the introduced algorithms keep the other players fixed, in the RL inner-loop and the BR oracle calls respectively. This results in decentralized execution. This section starts with the introduction of r-player general-sum
33

---

Games and all the necessary notations. Then, we show how the objective varies slightly from the one in Zero-Sum Games. Last, we give the proof sketch for the n-player general sum case.
First note that, an infinite-horizon general-sum Markov game is defined by g = (n, A, P.r. P.r.% do), where is the number of players, S is the finite (joint-)stann >state space, A == A ... An is the finite (joint-)action space, where A, is the action space of player i [I.....,,], P E IR (AAIIAI is the (unknown) transition function, a distribution over the state space from which the starting distribution is sampled. In general-sum games there is additional restriction the reward function. A policy of player i is defined as T; S - A, and we denote the joint policy as π = (T1,-.- "01....,Ty,, Fn) = (Ty π - where -- denotes the policy of all players except player i. We also use (i..)) to denote all players but players j. Additionally, we denote a joint action as a (a1,..., ,d,). The value function and state-action value function for any player for a given state s E S, and any state-action pair (s, a) E S x A is given by
R ||S||A|| the reward vector, discount factor y (0. and do
8
(T*(s) ET
(S () S =s
Q (s, a) :- Ex
(S, A) S 5, Ao
All other expressions are defined as in Section 2 with the extension that the joint actions are now given by a and one fixes the policies all players expect player i.e. T- for the induced Games.
The important difference for our analysis is in the change of the objective. In the two player sero-sum case the objective of the the Nash Gap (T is already simplified form. In general, the Nash Gap is defined as the sum of exploitabilities of each player, i.e.
Nash-Gap(mT = Σ max Vili
'(80) ViTiaa '(80).
(13)
m
One can easily see the structure of the 2 player zero-sum Game leads to
max V x (so) V,n..a-t -(s))
Nash-Gap(TT)
max Vi i (so) - 1/T1. (so) max 1/2 T (so) (2217=(50))
max VI V (so) - Vimi. (sp) min V T (sp) + TT (so)
mi
max Vi (so)
(so),
where in the third equality, we used the assumption the reward for two player zero-sum games, i.e. r'(s, a, b) = --2((s, a, b). Noting that π = (m1, (u, this is exactly the definition of (I).
In the following, will show the implication of the change of the objective the Multi-agent Imitation Learning setting. We start again by rewriting the objective with the expert policies
Nash-Gap(T)) = max p (su)
Vil - -- (so) V TB. (so) + V. TB (5o) - -V. V.T..t-(ss
y po (60) Vg m (so) + TE (80) - V, V. (80)
<
Exploit- Gap.
Value Gap
The Exploit-Gap is similar to the objective analyzed in the zero-sum case with the difference that now that the policies of the other players are varying in n cases. The Value-Gar Gap is new and does not appear in the zero-sum case can again use the structure of the reward in that case. However,
34

---

the latter is easy to analyze as it can be seen as single-agent MDP with the joint policy æ and the joint expert π e respectively.
We can now compute the analysis for Behavior Cloning and start by bounding Exploit - Gap
sc TV (-1 a. (.1)))
Exploit Gap, 5 - 7 m,Ebr(
m18x
E ET
S - Y %. Ebr(x(-.))
max
E Ex,
y TV (TE( (c(((s))),.))) s). ((((ss))))
8
m88x 7 m:Ebr(
d NB
E
r
TV (T (.).)
i)
1=0
Next, we can use that the policies are conditionally independent in the state as we assumed have a NE expert. Therefore, it holds true that
n Σ TV (),
TV (T ()) S
Similar arguments can be used to minimize the Value-Gap Gap without the change of measure to obtain
2 1 7
Σ (TV(TE,
Value Gap
(14)
Using this for each player we obtain
8n1
d
S E Ar) log2 (n [S]
Nash-Gap(1 ( <
(1 7)
max
(BR(
max
d B
N
Next, we want to sketch the extension of Algorithmm for n-player general-sum games. We only give the extension for this algorithm the ideas translate analogously to Algorithm I In first step
35

---

have to adjust the decomposition in 5 We get
K
n
do. V V,tinn))
do, vytkerte)) >)
max J.ell
K
K
do, Vi v ))
K
V. m 2
do, V.
V, m
+ m
K
2
do, V.Tii
V, x ME
V. satt
K
k=
2
1
K
n2
2
do, V
K
Expliit Gapp
do. V. -B. -
+2 2
K
km
(i) Value Gap
do. Vi be(at Wort br(*** 115 1 1)
$ 2n
-V,
do, v aiitt Vn ber(r mitte
do. V; Vi RRR v vnstine)) ))²
+2
K
k=l
i=1
where T. E br(m2,). We will focus on (i) first. Then, we tackle the Value Gap. In particular, will focus on the composition for any player E (1,..., n). For (i), we cannot continue directly as
done in proof of Theorem 4.2 as now the policies inside differ in 1 other policies and therefore
36

---

we cannot directly apply the performance difference lemma. Instead, we first have to do the following
K
1. /. _T )) 1(72
2
(1) =
do, V.
K
1=1
K
2
Vere (a 1onn 1 1 R
do V/2
K
Veal (1 .....
v.ni"" ((x -o (4: .... t (T
dos
(
TEa Vi
+V," : (
(x
K ((#
2
< - 1)
[
do, Ve
1=1
K
1 K
do. Vi: ", (B. TE mT Te,)
(TE, 11
+
Vg
k=
Note that by the telescopic sum construction, we now have that each difference of value function only differs in one policy and last we applied (a + 6)2 < 2(a² + b²). We will now focus on one term for the exploit Gap for any Therefore, we can proceed similar as in proof Theorem[4.2 442 by dividing out K2, applying the performance difference lemma ((n 1) times, for every player but player i), Cauchy Schwarz and Jensen we get
do, V. ni ( (nt m th v (*/ oo (:
(n 1)
K
do, Vi x (xx .igi...hh
(n 1) Amax
and io || [s)]ss) - TE. ( (1.))]]]] 1t1
(1 - ?
[| 8) - (-1 {s]]]]]]]]]]]
+ in
snad
1=
(n- 1)|Amase
K
|| 11 (s) -E.n-jt (s)][3]
E
+ cup
(1 21
jæti
37

---

where we introduced n - RL inner loops for the player to approximate the maximum incertainty response policy denoted by Vij * for j [ni]. More precisely, we have
[I (1 (8) - NE, (+)
I s ( j.
E
sna dnnyn t..1.) [| mEm---- (+)] cop
For the Value Gap, we obtain the following:
vattars ))
1
-
do,
V,
(15)
K
Iem i=1
TV (Te(: x |)]] 2
2n
E Soudah
(16)
1 γ K
k=
4n 2
1
K
E
ESndTH
[TV2 (TE(- s),=*(( (-1s)) [s)]]]]]]]]]]]]
(17)
(1 7)2 K
k=1
4n²
2
K
E A
[TV2 (TE (: [)sss,, (- |s)]
(18)
(1 7)2
K
(19)
where for the first inequality we have applied the performance difference lemma to the joint policies F and π² as well as Hölder with |1-I|; and |I-1| and bound the value function with its maximum value 1 For the second inequality we used Cauchy Schwarz/Jensen's inequality and in the last step that the policies are all conditional independent on s. Therefore, the whole objective can be upper bounded by
4n2
1 K
n
E s
[TV2 (TE. s), (-1 s))]
(1 - 7)2 K
1=
+ (n- 1)
Ammax
K
(e mp || (| TEn-s+1(s)]] +
di Eope
(1-
end
k=1 i=1 itt
K
4n2
smott [TV2 (TE [s), (. [s)]
K
(1 - 7)²
k= i=1
(n - |Amxx
Σ
sou Anf ( (1 - (==))+ + Enj
+
(1 71
jtt
n1. |maax
1
K
E
Baattt [1TTE] (s) [+)))
722
K
k=
1=1
[| - (+))l + eog
E
An
where we used that TV2 (TE, TE) I As ||TE, - 11.
Now note that can sample according to all state occupancy measures. In particular, we have S du'z"
12
mn and ST ~ d=* Again adding and subtracting [.. Sg - x ST
and TE (- ( - ( ( || we get
38

---

n2.
A A
1
7)2
K
imn i=1
Σ
E
|| m (+1(-++(111 (-11) ME,- j+1( (-1((1))))))))))))))) [0]]
aTE,a-+t(
soudh
= "n-jt1( (-1 (1st)))) (x.01 ||
TE 11/)))
|| (- 1-1 s) x- [1>))11]]] - TE, ||x - x-11 ((ssg) }|²
+ B
(Martingale)
TEm--41((: 1 m |
5% 1||
+ TE. (- S (- (
(Regret)
+ nt" |mmax]
(1 7)2 Eopt
Note that now again, we have analogously (12 martingale term here and regret term that can control by updating the policies with online mirror descent. In particular, we can rearrange the regret term as follows
Regrel
E
(Enta-i-1| TE, (-15% (11) nf (-1s) 11 || + +||TEE
(55)) (
(11ST))) 1l')
At this point, following an analogous analysis as done in proof of Theorem 4.2 we get total bound in the order of O [oll(m///////Amxx((1->-111
Similar steps can also be done for Algorithm obtain
6*
O( poly(n,|S),,) Amax ((11 (10-->)-)) -))-) This shows that the algorithm design indeed allows avoid the curse of multi-agents and instead scales polynomial in the number of agents n.
I Comparison to Lower Bound in Tang et al.
In this section, we compare our result Theorem 3.2 to Theorem 4.3 in Tang et al. [2024). In particular, we emphasize how their construction allows to avoid a linear regret in the case of a fully known transition model. Note that they consider a finite horizon setting and general-sum games with correlated equilibrium expert. For better readability first restate their Theorem in infinite horizon setting.
) There exists a Markov Game, an expert policy pair (R.. v) and a learner policy (H,V), v), such that even when the state visitation distribution of (p, v) exactly matches (p. R. "²),, the Nash gap satisfies
Theorem 1.1 (Theorem 4.3 in Tang et al. 2024)).
Nash Nash-Gap(u, v) 2 Ω ((1-))-))
The Markov Game that they construct is given in Fig. 3
The Markov Game consists of the action space A {ai, a2 as} and the state space S = For the transition model, which is unknown to the learner, it holds true that
{Sp, 81, S2, $3, $4). 84).
-(1 [11 if (a, aga1.
P(-|s. a,
84 otherwise.
and for all other states transition to neighboring state with probability one, independent of the chosen action. The state-only reward of the cooperative Markov Game is given by
{1
if S3.
(s)
0 otherwise.
39

---

a2a1
83
all
Q241
else
80
else
all
$2
94
all
Figure 3: Cooperative Markov Game with Linear Regret in case of unknown transitions
It follows immediately, that expert with Nash-gap of 0, i.e. NE is given by the following policy pair
r (az su) = (a su) = 1, 1, (as 81) = va =1
and in the other states any action E A be chosen. As the expert data is not covering data for state $1. it only covers the blue path in Fig. 3 Tang et al. (2024) argue that any policy can be chosen However, if we know the transition model, the learner can be steered to choose a robust action such that the learner will be taken back states known from the expert data, i.e. state sg. even when one agent would deviate from the current policy. This is highlighted in green in Fig. 3 The only action that is considered robust action ag for both agents, exactly the action chosen from the expert. This implies that the learning policy in the case of a fully known transition model has
for the learner in state s1 and choosing ((ai $1 = r(a s1)
Nash-Gap(u,1)
This in contrast to our construction in Fig. where even under a known transition there is no way to steer the learner known paths. Therefore, Theorem 3.2 shows the necessity of the expert agent deviation coefficient and separates MAIL form SAIL, where effective learning is possible under known transitions Rajaraman al. [2020]. Additionally, we consider Zero-Sum Markov Game, not considered in Tang et al. Tang et al 2024]]
J Experiments
In this section, we give detailed description of the underlying environments used for the numerical validation of MURAIL and describe the setup in general. Additionally, we give some practical insights that could speed up convergence.
J.1 Environments
We consider two different environments for our numerical validation, one that has C( B) < 20,
and the lower bound construction Fig. 1 with different NE experts control C(pB B). In particular we have multiple with C(yE, u < oo and the same NE expert as Theorem 3.2 to get C(p F) Dc.
Environments with C( P) < co. For this we consider two environments. For the first en- vironment, we generate random Zero-Sum Markov Game with [S] 10, |AI |B] and reward between -1 and 1. To ensure that the expert covers all states we use a uniform initial state distribution, i.e do (s == Unif(S). We set the discount factor 0.9.
Additionally, we choose the Markov Game from the Lower bound construction and use that the set of Nash equilibria is convex for Zero-sum Games. This way take mixture of Nash equilibria that chooses the Scopy path and the blue path, for detailed description see Appendix J.2
Environment with C(NE, (B) = =c. xc.
For C(NE ())) oo, we use the Zero-Sum Markov Game given in Fig. with the simplification that [Sxptal [Sxptta| = |Sropyl = 1 as our goal here is only to verify the theoretical insights, but not to prove that also the transition model cannot be used for interacttattve Imitation Learning algorithms. This means that we have [| 7. Additionally,
40

---

have |A] = [B] = 3 and do (s() = 8z, We set the discount factor to 0.9. The reward is given by R(Sxpit2) ((Sxltt) 0.1 and 0 otherwise.
Exploitability. To calculate the exploitability, we fix the current policies of one player iteratively and then run standard Value Iteration for single-agent MDPs under the true underlying reward function.
J.2 Experimental Setup
We run the experiments for each environments 1000 times over different seeds and average the results. For both environments we compute the optimal learning rate 7/. For simplicity, we use UCBVI algorithm for a state only reward as the RI. inner loop of MURMAIL.. Note, that this can be replaced by any other no regret algorithm.
Expert distributions for different C(uP, vD). To get control over v note that the set of Nash equilibria is convex for Two Player Zero-Sum Games. Therefore, consider the Lower bound example illustrated in Fig. Note that we have pure NE that chooses action agby to get on the blue path. Choosing a different pure action, let us assume ag, by will lead the agent to choose the path that goes on 81, Scopy. Now, as the set of NE convex, we can also mix these equilibria. To choose the minimal C(pP,v/ DB. we pick for (a) the Nash equilibrium such that
(a2 so) = va So) = 4L / so) va(as so) 0.5. To increase C(u vP), we have to increase the probability of the experts to take action as and by respectively. We choose for (c) (a sn) = (a3 sn) = 0.999, for (c) we pick 2² (a3 sn) = va so) = 0.9999. For (d), we use the same expert policy as the lower bound construction, i.e. /Paa3 80) D 80) = 1.
To generate the expert distributions, we use a Value lteration algorithm for Two Player Zero-Sum Games c.g. described in Perolat et al. [2015] for the randomly generated Markov Game
J.3 Practical considerations
Next, we list practical considerations for our algorithms, that could speed up the performance. First, note that while solving the RL inner loop in Algorithm 2 can be computationally expensive, the objective between successive iterations changes only through the updates of the policies μa and vi- Consequently, if these policies change only slightly between iterations, the optimal solutions for yk and 2ạ may also vary only marginally. This observation suggests that initializing the optimization with the solution from the previous iteration, common technique known warm-start optimization, can significantly accelerate convergence.
Second, although the samples generated in the RL inner loop cannot formally be reused for the outer loop policy updates due to measurability issues of the resulting Martingale sequence, in practice often beneficial to recycle these samples. Doing can reduce the total number of required samples without noticeably affecting empirical performance.
Last, note that we assumed for our analysis that there is no initial dataset for interactive Imitation Learning Section _ However, in general it is possible to consider an initial dataset D. from which we can learn initial policies with a non-interactive Imitation Learning algorithm like BC. This can speed up the convergence of our proposed algorithms as the maximum uncertainty exploration will mainly focus on states out of the distribution from the initial dataset. We give the algorithm of MURMAIL with an initial dataset in Algorithm Similarly, one can adjust Algorithm
J.4 Additional plots
In this section, we list an additional plot for the second more involved environment that has C(x FvF) oc. Here we observe similarly to case (a) of Fig. 2 that the speed of conver- gence from BC is higher compared to MURMAIL.. It indicates that the chosen algorithm has a small concentrability coefficient C(, E and again highlights the importance of algorithm selection depending on the underlying environment.
K
Useful Results
In this section, we list useful theorems and lemmas used to prove the main results.
41

---

Algorithm 4: MURMAIL with initial dataset
Input:
number of iterations K, learning rates v), inner iteration budget T, dataset D, non-interactive Imitation Learning algorithm Alg
Output: e-Nash equilibrium (ft, 2)
% Run non-interactive Imitation Learning algorithm to initialize policies
(pI, 21) (D) for k = to K do
Inner Single-Agent RL Updates:
Maximum uncertainty response to μd-playe update
Define single agent transition PHu (s' 8, b) EeesHe uola s) s. s. a.a.b):
Define single agent stochastic reward Rya 11 (As=A(s) (Ax (s) [+
where AE. A'r ME(- (s);
yh = UCBVI , Pau+ Ryg )i
Maximum uncertainty response v-player update
Pue (s'(s, a) = EIEB (() s, s.a.bi b);
Re, (s) - (AE=A's) 2 (A 8) + || s]l? where AE, A'g vEl. 1s);
Fk UCBVI(T, Pery Ruy)
Update policies:
Sample 5% ~ d' A ~ pg(. Sh), Sk ~ d A ~ vEl. 5%)
( a) = us(a 5% sp
AÑ=0
(s a) = vz(al ss - LAz=a
Ma+1(a 8) x pa(a 8) exe (-no (s,a));
1b 8) x uk (b) 8) exp - (8,a)
end
return
16g up for Te ~~ Unif([A])
C(e,,
SEUILMAIL
Nach Gap
BU
10
20
30
40
(0
70
100
Expert Querion/Dotrren Daizoett Sizee
-10P
Figure Nash Gap for MURMAIL and BC
Lemma K.1 (see e.g. Lemma IX.5 by Alatur et al. (2044). For any policy of the max-player and two policies of the min-player and we have
(su) V.L. (su)
+ ((ab))((a [Qur (s, B(ab))-(urr [Q (s, [s,
En,
Similarly, for any two policies of the max-player and şa and policy of the min min-player v, we have (sa)
(su)
Σ A "Baaa (s, - ((a,))))a (sun"(s, (s.0,
= E
Proof. The proof can seen as the two player case of the standard simulation lemma for MDPs as one player remains fixed. For completeness reasons we the first statement, the second one follows analogously. By the Bellman equation holds true that
Vi (s) Ea-n,bo [r(s, a, b) + DE (V (s')]]-
42

---

Applying this to the difference of the value functions yields
(s) 17 (s)
Bow [r(s, a, /B (V" - Bara,brw ((ss, a. b) ( (6')]
(Bargu ((s, - (V.. (s')] Bany,bro a, + (s')
+ (Boribbrl (T,, a. + - (s'] Bary ((),,,,b) + >12x (s')]
yolarrpt (V (5')) E P (s')]
+ (Eangibou Quii (s, a, b)] Eawpybww {Qur (p (s,a. bs))
where we used that the immediate reward cancels out for a ~ b ~ Applying the same argument inductively for so completes the proof.
Lemma K.2 (Concentration Inequality for Total Variation Distance, see e.g. Thm 2.1 by Berend and Kontorovich (2012)). Let X 21, , be finite set. Let P be a distribution on X. Furthermore, let P be the empirical distribution given m i..dd samples 2 I2," : II from P, i.e.
PG) - M 11 =}
-
Then, with probability at least 8, we have that
P
P
Σ FEX
P(x) -(x) s
2 log(18)
n
Proof. Define the function f ; Emex P(x) - P(=)). where P is the empirical dis- tribution. Replacing one sample F; can change f by at most 2/n, since the empirical frequencies change by most 1/n per coordinate and total variation sums these differences.
By McDiarmid's inequality, we have for any
n 2
Pr B[ 2 E)
S exp
2
Berend and Kontorovich (2013) show that E[ʃ] solve
S
X
Setting the failure probability to 6, we
n
2 log (1/8)
exp
= 5
8
2
n
Therefore, with probability at least 1 - 5,
|
2 1og((15)
2| log(1
p
P
n
n
n
Lemma K.3 (Binomial concentration, see e.g. Lemma A.I by Xie al. (2021) ). Suppose N Bin(n,p) where n 2 1 and E j0, 1]. Then with probability at least 1 6, we have
P
8 8log(1/0)
NVI
where N VVl== == N.
43

---

Proof. We consider two cases. Case 1: _ Blog(1/81, As N 2 1, we have NvI S S Blog(1/8)
(1)((1/)) Note, that then E = up > 8log(1/6) and by the
almost surely. Case 2: >
multiplicative Chernoff bound, for any 0 = it holds true that
E²
P < (1 E)mp) exp
2 nop
Now, with E = we have
P(V < (1 - s)mp)) S exp
np 8
S 8.
Therefore, with probability of least 5 holds N ap and therefore on this event also In total we get NVT _ 8log(1/8) Combining both cases completes the proof.
nv1 -
44

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
the itemization our contributions, that match the contributions mentioned in the abstract, reference the corresponding theorems that show these results. Addition- ally, we provide an empirical evaluation our results in Section | and provide the details in Appendix
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We address the limitations of this work, namely the complexity in expert queries in the main text and in Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
45

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: In each theorem we state the underlying assumptions and provide the full proofs in the appendix Appendix C Appendix
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
We give all needed information to reproduce the experiments in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
46

---

reproducible, they 5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [NA]
The main contributions of this paper are theoretical and the provided figures are numerical validations of the theoretical results. Additionally, we provide clear description on how to reproduce the numerical verifications in Appendix[] The full code will be released after publication.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//mips.cc/public/gu.ude httppplliiiggu.eeeeeeeeeeeiieeee
wrriiisssiiniiiyyyy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We give all the details in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: All figures include error bars, see Fig
and Fig.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
47

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The numerical validations run in this work do require lot of compute as the environments are simple and only serve as proof of concept. They have been run on standard laptop.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
The paper is conform with NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The main contributions of this paper are theoretical. None of them will have a direct impact society.
Guidelines:
48

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
49

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
50

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM for what should or should not be described.
51


Reviews:
[{"review_id": "S8Oe4kLcfQ", "reviewer": "Reviewer_8iNH", "summary": "This work concerns multi-agent imitation learning and, more specifically, learning equilibria of zero-sum Markov games (MG) using a dataset of trajectories. I.e., an algorithm is provided with a number of trajectories sampled from a Nash equilibrium, and it needs to output a policy for each agent s.t. they jointly form a Nash equilibrium. The authors further demonstrate the impossibility of this task when the dataset does not satisfy a rather strict condition. To circumvent this, the authors allow *interactive* imitation learning, meaning that the algorithms is allowed to query the expert (who collected the dataset in the first place) for further demonstrations. In the latter setting, the authors manage to offer two algorithmic solutions for the task of equilibrium learning from data with only polynomial sample complexity. Further, behavior cloning and its shortcomings is extensively studied in this paper. Finally, the authors provide some experimental verification of their theoretical claims.\n\nBehavior cloning is a common heuristic to tackle the problem in single-agent Markov decision processes (and also a previous multi-agent work Tang et al 2024). In behavior cloning, one needs to compute a maximum likelihood estimate of the two player policies for that particular dataset of trajectories. Under a bounded concentration coefficient, this works well and the authors prove this in Theorem 3.1. \n\nThe contributions further include:\n* a clear separation between single-agent and multi-agent imitation learning without interactions (Theorem 3.2). The authors construct a MG where behavior cloning will output a pair of policies with exploitability lower bounded by a constant of the game. \n\n* using an interactive expert assumption to design two algorithms for Nash equilibrium learning. The first algorithm assumes access to a policy best-response oracle and the second one circumvents by tweaking the first algorithm.\n\n\nIn Algorithm 1,\n* at every iteration $k$, the best-response oracle is queried for a best response to minimizer's policy $\\mu_k$ and maximizer's policy $\\nu_k$.\n\n* then, the algorithm queries the expert to provide trajectory samples.\n\n* the samples are used to construct a feedback vector which will in turn be used with a policy optimization update (exponential weight updates).\n\n* the algorithm samples a joint strategy from all iteration and outputs it.\n\nThe guarantee is that in expectation, the output is an approximate Nash equilibrium. (Theorem 4.1)\n\n\nAlgorithm 2 essentially goes beyond the need of a best response oracle by using an upper confidence bound value iteration subroutine. This extension requires non-trivial technical work.", "questions": "* Can you reduce MAIL to a (potentially) general-utility Markov decision process? (single agent) What are the connections to convex MDPs or convex Markov games? (Gemp et al 2024)\n\n* In algorithm 2 for uncertain states, why did you not pick the KL divergence between $\\mu_E$ and $\\mu_k$ (lines 266-271)?\n\n* Would you be able to extend your results to games with some low rank interaction assumption, e.g. (Kalogiannis and Panageas 2023, Park et al 2023, Zhan et al 2024)? \n\n* Does the uniqueness of the equilibrium of zero-sum games play an crucial role in your results so much so that it would not extend your results as asked by previous question?\n\n* What would be some further benchmarks for this setting?\n\n\n\nGemp, I., Haupt, A.A., Marris, L., Liu, S. and Piliouras, G., Convex Markov Games: A New Frontier for Multi-Agent Reinforcement Learning\n\nZhan, W., Fujimoto, S., Zhu, Z., Lee, J.D., Jiang, D.R. and Efroni, Y., 2024. Exploiting Structure in Offline Multi-Agent RL: The Benefits of Low Interaction Rank. \n\nPark, C., Zhang, K. and Ozdaglar, A., 2023. Multi-player zero-sum markov games with networked separable interactions.\n\nKalogiannis, F. and Panageas, I., 2023. Zero-sum polymatrix markov games: Equilibrium collapse and efficient computation of nash equilibria", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Among the strengths of this paper are its clear-cut improvement from previous work (Tang et al 2024). They set apart single-agent and multi-agent imitation learning with a clean and simple MG example. The separation is robust to even the strong assumption of knowledge of the game dynamics; the corresponding result by (Tang et al 2024) was not as strong as knowledge of the dynamics was enough to ameliorate things.\n\nHaving proven the impossibility of learning a policy pair whose exploitability does not depend on the *single policy deviation concentrability coefficient*, they consider the setting of interactive imitation learning. Then, they provide a strong algorithmic solution to the problem of learning a Nash equilibrium. The algorithm and its guarantees' proof make use of a broad array of the theoretical toolbox of RL and learning theory.\n\nTo the paper's weaknesses, I would list, the weak empirical evaluation without any code. There is no benchmark. Further, the setting the authors consider is only tabular MGs and they did not offer any function approximation guarantees.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful, detailed, and positive feedback, and for recognizing that our work presents a *“clear-cut improvement from previous work”* and  *“the algorithm and its guarantees' proof make use of a broad array of the theoretical toolbox of RL and learning theory.”*\n\nIn the following, we would like to address the different questions and few mentioned weaknesses raised by the reviewer:\n\n**Benchmarking**\n\nIn the current submission, we focus on providing theoretical guarantees, leaving more practical extension for future work.  Our numerical simulation on the same Markov Game used for the hardness result in Theorem 3.2 were thought to verify our theoretical results, in particular showing that the degradation of BC under high concentrability is a real effect.\nMoving forward, we plan to explore experiments in route recommendation, inspired by the motivating example in [1]. Importantly, in this setting, a low Nash gap ensures that no agent (car driver) has benefits in taking a different route.\n\nOther interesting experiments can be performed in recent libraries such as BenchMARL [2]. \nHowever, the design of Deep MAIL experiments requires care in estimating how the concentrability coefficient behaves in practical environments and in computing the Nash Gap for evaluation purposes.\n\n**Relation with Convex Markov Games**\n\nWe see a twofold relation with the work of Gemp et al. 2024, which we outline below:\n\n- *Imitation as Convex Markov Game:* First, notice that in their section 5.2, they use the convex formulation for imitation learning. However, they use this technique in presence of reward for equilibrium selection purposes. When one sets the reward to zero in their formulation, we are left with an occupancy measure matching problem which is akin to minimize the value gap according to (Tang et al 2024) terminology. Therefore, their technique does not seem to be suitable to learn equilibria from data in presence of high concentrability coefficient.\n- *Imitating equilibria in Convex Markov Game:* As a final connection, we point out that one might study the question of learning equilibria from data in convex markov games which is a more general setting than the markov games studied in our work. If the markov game functional has G-bounded gradients our techniques still apply via a standard reduction from convex to linear losses in online learning. However, studying imitation in convex markov games with unbounded gradients is an interesting open question.\n\n\n**Extension to Low-rank interactions games**\n\nThe low rank interaction assumption might help in bypassing the concentrability coefficient.\nIn particular, if the norm of the difference between the learnt and expert policy is a low interaction rank function. It is, in our opinion, unclear under which conditions this can be proven. Moreover, notice that in [4] this assumption allows the authors to avoid the exponential dependency on the number of players in Offline MAIL. Under our setting, the dependence is polynomial even without the low rank assumption, see Remark 4.1.\n\n**KL divergence in algorithm 2**\n\nWe did not use the KL divergence in Algorithm 2 because our analysis relies on the Cauchy–Schwarz inequality (see Equation 8 in Appendix G), which naturally leads to a squared norm. While one could derive an upper bound on Equation 8 using the strong convexity of KL and formulate updates that minimize this bound, doing so would likely result in suboptimal performance. Specifically, such an alternative would optimize a possibly looser bound than what Murmail currently minimizes (Equation 8).\n\n**Uniqueness of equilibria**\n\nOur analysis does not rely on a uniqueness assumption for equilibria. In Zero-Sum Games, the value is unique, but not the strategy. Under the uniqueness assumption, the lower bound construction is no longer valid, and the concentrability coefficient could be avoided. This is an interesting open question. Moreover, our theorems can be extended to the general-sum Markov Game setting, where not even the uniqueness of equilibrium value holds true as stated in Remark 4.1 and sketched in Appendix I.\n\nWe hope these responses clarify the raised points. We are grateful for the reviewer’s detailed and constructive feedback and would be happy to incorporate any further suggestions in the camera-ready version. \n\nWe would be glad to further clarify any additional points the reviewer may have.\n\nBest,\nAuthors\n\n[1] J. Tang, G. Swamy, F. Fang, and Z. S. Wu. Multi-agent imitation learning: Value is easy, regret is hard. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang, NIPS2024\n\n[2] Matteo Bettini, Amanda Prorok, and Vincent Moens. 2023. BenchMARL: Benchmarking Multi-Agent Reinforcement Learning.\n\n[3] Gemp, I., Haupt, A.A., Marris, L., Liu, S. and Piliouras, G., Convex Markov Games: A New Frontier for Multi-Agent Reinforcement Learning\n\n[4] Zhan, W., Fujimoto, S., Zhu, Z., Lee, J.D., Jiang, D.R. and Efroni, Y., 2024. Exploiting Structure in Offline Multi-Agent RL: The Benefits of Low Interaction Rank."}, {"review_id": "glzO6PwGAS", "reviewer": "Reviewer_sKo6", "summary": "The paper investigates a cutting-edge research topic, namely Multi-Agent Imitation Learning, for which theoretical results are currently scarce. It is mostly closely related to [Tang 2024] in the reference. The first result (Theorem 3.1) says that the Nash-Gap is close to zero if we use a behavior-cloning algorithm to learn the behavior very well, and a constant C(\\hat{\\mu},\\hat{\\nu}) is bounded. If the behavior are welled learned, C(\\hat{\\mu},\\hat{\\nu}) is expected to be close to C(\\mu^E,\\nu^E), where \\mu^E and \\nu^E are expert policies that achieve the Nash equilibrium. However, even if the nash equilibrium is unique, it may still be possible that C(\\hat{\\mu},\\hat{\\nu})=\\infty, since fixing one player's policy other player may still have non-unique policy. This observation is formalized in Theorem 3.2, which says that there are examples of offline two-player games where the Nash gap is not vanishing even when the transition probability matrix is exactly known. This highlights an interesting difference between multi-agent and single-agent imitation learning, since for the latter it was known that behavior cloning can be optimal. Then Section 4 discusses alternative strategies and information that can be used to again close the gap.", "questions": "Just to make sure I understand the setup, the reason for the counterexample in Theorem 3.2 is that even if the algorithm knows the (action,state)-> state transition exactly, it does not know the reward function r, so that if the trajectory deviates from the equilibrium, the algorithm will not know how to act, is that correct?", "limitations": "The experimental results seem to be artificially constructed Markov chains. Is there any practical settings where the framework and theoretical results in this paper can be applied? Also, the present results are limited to the tabular settings, and there is a gap to the widely used deep learning models.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "This paper is very well written and provides necessary background, literature review, and proof sketch for people who are not intimately familiar with the topic. I haven't checked the proofs, but the intuitions seem to make sense. The paper only deals with the tabular setting and some of the results are expected, so I suppose that the proofs are not very technical sophisticated/challenging.", "was_revised": true, "final_justification": "The rebuttal confirmed my understandings and I believe that this is a clear accept.", "rebuttal": "We sincerely thank the reviewer for their insightful and encouraging review. We are especially grateful for the recognition that our paper is *“very well written and provides necessary background, literature review, and proof sketch for people who are not intimately familiar with the topic.”* Please find some comments on your questions below.\n\n**Theoretical contributions**\n\nWe appreciate the reviewer’s assessment of our theoretical contributions. While the high-level ideas may seem intuitive, we would like to highlight that our analysis includes several technically non-trivial components.\n- In particular, our analysis tackles the non-convex optimization problem of interactive Imitation Learning: $$\\min_{\\widehat{\\mu} \\in \\Pi} \\max_{\\nu \\in \\mathrm{br}(\\widehat{\\mu})} \\mathbb{E}_{(\\mu_E, \\nu)} \\left[ \\sum\\_{t=0}^{\\infty}\\gamma^t , \\mathrm{TV}(\\mu_E(\\cdot \\mid s), \\widehat{\\mu}(\\cdot \\mid s)) \\right].$$\nThe key difficulty lies in the fact that  the data  generation process depends on the minimizer itself $\\widehat{\\mu}$. To be precise, the data is generated from the occupancy measure of $(\\mu_E, \\nu)$ and $\\nu$ is one of the best responses to the minimizer  $\\widehat{\\mu}$. \nThis makes the minimization too hard to be tackled in a computationally efficient manner.\nTo bypass these problems, we derived an upper bound on the optimization problem above (Equation 4 in the paper), which is easy to optimize leveraging a Best Response Oracle. For more details, see lines 230 to 237 of our paper.\nAdditionally, when the reward function is not known and a best response oracle is not available, we introduce the UCBVI inner loop to compute the maximum uncertainty response, which is by itself a new principle that could find further applications.  \n\nThese new techniques allow us to provide a computationally efficient algorithm with sample complexity guarantees for MAIL, which was an important open problem. \n\n**Theorem 3.2**\n\n- Regarding Theorem 3.2, the reviewer correctly understood the issue: without knowledge of the reward function, the learner cannot be guided to recover a good policy. We tried to give some more intuition why knowing the transition dynamics is not sufficient in Appendix E(l.725-726) of the paper: *“Additionally, note that even if the learner has access to the transition dynamics, the learner can not differentiate the actions from s1 as all actions lead to different states. Therefore, she cannot use this knowledge to recover an action that would lead to [a good state]”.* As the reviewer has identified correctly, this is due to the missing reward function.\n\n**Practical applications**\n\n- A practical example could be route navigation recommendations. In this example, minimizing the Nash gap ensures robustness of route recommendations against individuals that may deviate from recommendations to increase their personal utility to e.g. to avoid traffic jams.\n\n**Tabular setting and deep imitation learning**\n\n- The reviewer has raised a valuable point regarding the limitation of the tabular setting. Since this is the first work that gives a sample-efficient imitation learning algorithm, we leave the extension to function approximation as future work (see Appendix C). \n- As stated in lines 609-613, we believe that the same algorithmical framework presented in this work can carry over to deep settings and give insight into the main steps that need to be adjusted: *“..., the main conceptual ideas easily carry on to deep imitation learning experiments. The largest theory-practice gap would be in the inner loop where UCBVI would need to be replaced by a Deep RL algorithm..”.* To summarize, while our theoretical analysis may be limited to the tabular case, the ideas carry over to more general applied settings. \n\nWe hope this response has addressed the reviewer’s thoughtful questions and clarified the theoretical depth and practical relevance of our work. We are happy to incorporate any additional suggestions in the final version and thank the reviewer again for their constructive review.\n\n\nBest,\n\nAuthors"}, {"review_id": "Jigo4WrgXW", "reviewer": "Reviewer_KjGo", "summary": "The paper studies the problem of learning an approximate Nash Equilibrium (aNE) in two player, zero sum Markov games. The authors first study the non-interactive variation where the learners have access to samples from the game, but cannot simulate it. They prove that by using Behavior Cloning, they can compute an aNE, where the approximation factor depends on a novel coefficient, which is necessary to be bounded, otherwise obtaining the aNE is infeasible. The authors also provide positive results in the interactive setting; given best response oracles they provide an algorithm which finds an aNE with polynomial, in the parameters of the game, samples. Moreover, they provide an algorithm that computes an aNE without the need of Best Response oracles but with worse sample complexity.", "questions": "1. Is the single policy deviation concentrability coefficient a property of the game or the data trajectories? Can you explain more intuitively what having a very large coefficient means?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper is well written, easy to read, and has nice illustrations that are intuitive.\n2. The authors provide strong theoretical results that are coupled with experiments which verify them.\n3. The authors provide a comprehensive study of finding equilibria from data in two player Markov Chains. They study both the interactive and non-interactive setting, and they provide efficient algorithms in terms of sample complexity that compute aNE in each case. In the non-interactive setting, they identify exactly the cases where learning an aNE is infeasible.", "was_revised": true, "final_justification": "I do not have any modifications to my original score.", "rebuttal": "We sincerely thank the reviewer for their thoughtful and positive evaluation. We are especially grateful for the kind comments that *“the paper is well written, easy to read, and has nice illustrations that are intuitive”* and that we *“provide strong theoretical results that are coupled with experiments which verify them”.* Please find below the answer to your questions.\n\n**Is the single policy deviation concentrability coefficient a property of the game or the data trajectories?**\n\nThis is an excellent and important question. In the behavior cloning upper bound, the concentrability coefficient appears in terms of the estimated policies and, therefore, depends on the data. \nHowever, in our hardness result (Theorem 3.2), we pay for $\\mathcal{C}(\\mu_E,\\nu_E)$, which depends only on the game structure and on the expert policies pair that collected the dataset. \nImportantly, this is a data and algorithm independent quantity that no non-interactive imitation learning algorithm can avoid.\n\nTo summarize, the hardness result depends on a property of the game and of the particular expert policies pair that generates the dataset.\n\n**Intuition on concentrability coefficient**\n\nTo build more intuition, consider the example used in our experiments: \n\n - In the provided Markov Game, there exist two paths resulting from different pure strategies taken in $s_0$ with the same value. \n- The upper path is sensitive to deviations and therefore samples in the sensitive (worst case state) $s_1$ are required to recover a robust policy to deviations, i.e,. the Nash policy.\n- The concentrability coefficient can therefore intuitively be interpreted as the coverage of this worst-case state (the coverage is an upper bound on it). If the expert distribution does not cover this sensitive state, the coefficient can be infinite and if the observed equilibrium is a convex combination of both, then the concentrability coefficient decays with the convex coefficient for this upper exploitable path, reaching its minimum if both are covered equally (see Figure 2).\n\nWe would be happy to clarify this further and add a more intuitive explanation to the camera-ready version to improve accessibility.\n\n We thank the reviewer again for reading our paper and helping us to improve its quality. Happy to answer any further questions the reviewer might have.\n\nBest,\nAuthors"}, {"review_id": "nMP7qtahdl", "reviewer": "Reviewer_JkAh", "summary": "The paper deals with the setting of multi-agent RL where the agent tries to learn in a Markov game. In particular, the authors investigate the possibility of doing imitation learning in this setting.\n\nOne one hand, the paper derives a fundamental lower bound for the Behavioral Cloning algoritm. This shows that, even in the ideal scenario of inifite data and access to a generative model, there are environments where the learned policy can be exploited by the adversary. Therefore, it is not possible to learn an $\\varepsilon-$Nash equilibrium.\n\nAlso the authors design two alsorithms, one that is oracle-efficient and the other that gets rid of the oracle at a cost of a much higher sample complexity. the oracel here is a Best Response Oracle (BRO), who is assumed to output the best response for a given strategy.", "questions": "See weaknesses", "limitations": "Unfortunately, my very limited knowledge of the topic prevents me to understanding how groundbreaking this paper is w.r.t. the literature.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**strenghts**\n\nThe paper defines the Concentrability Coefficient $C$ and shows that this is a fundamental quantity to control the error of BC in this setting. To do this, the authors construct a Markov game in which no non-interactive algorithm, even with infinite data and full transition knowledge, can learn a near-Nash equilibrium, when $C$ is infinity. This result establishes a fundamental impossibility in offline MAIL, highlighting the need for interaction.\n\nIf I understand correctly, this is the main take-home message of the paper: in order to learn $\\varepsilon-$Nash equilibria for arbitrarily small $\\varepsilon$ from expert demonstrations, one must be able to interact with the expert to query demonstrations at specific points.\n\nThe negative result is completed by two positive result saying that 1) MAIL-BRO, which requires a best response oracle, achieves $\\varepsilon-$Nash with O($\\varepsilon^{-4}$) queries in Polynomial-time, with no dependence on concentrability 2) MURMAIL does the same without the need of an oracle at a price of an higher sample complexity.\n\n**weaknesses**\n\nThe only weakness that I see is the bad dependence of the upper bounds for the sample complexity in both $\\varepsilon$ and the constants. It is not clear if these results are optimal.", "was_revised": true, "final_justification": "I confirm my initial opinion that this was a good paper.", "rebuttal": "We thank the reviewer for their time and thoughtful and positive feedback. We appreciate that the reviewer recognized the significance of our results, especially the impossibility of offline MAIL without interaction and the corresponding positive results for the interactive setting.\nBelow, we address the reviewer's question regarding sample complexity.\n\n\n**Sample complexity**\n\nThe reviewer correctly points out that the current upper bounds for sample complexity leave room for improvement, which we also acknowledge in our paper *“the focus of this work was to show the first sample complexity bound for a computationally efficient algorithm in the queriable expert setting.”*\nBelow we would like to point out why it is non-trivial to improve the dependency on $\\epsilon$ for MAIL-BRO and MURMAIL. \n\n*Non-convexity of objective*\n\n- The original problem is non-convex, therefore, we first have to change the objective to make it convex, which involves squaring it. This leads to $\\epsilon^{-4}$ dependency for MAIL-BRO. Currently, we do not see a way to resolve this.\n\n*Missing knowledge of reward function*\n\n - Removing the assumption of a best response oracle and introducing MURMAIL brings up new challenges. The key one is how to upper bound the expectation that involves the *best response policy*, despite not having access to the reward function. This rules out the use of standard optimistic estimators. To overcome this, we introduce the *maximum uncertainty response policy*. This new principle leads to a further degradation in sample complexity to $\\epsilon^{-8}$.\n\nWe believe this technique is novel and key to enable our guarantees in the context of Multi-Agent Imitation Learning, where no reward knowledge is assumed. That said, we agree with the reviewer that improved bounds might be achievable with new techniques, and we view this as a promising direction for future research.\n\nOnce again, we thank the reviewer for their time and positive assessment of our paper. We hope this response clarifies the origin of the sample complexity bounds. We would be happy to address any further questions.\n\nBest,\n\nAuthors"}]

Author rebuttal:

Meta-review: The paper provides the first sample complexity bounds for learning Nash equilibria from expert data in Markov Games, introducing the critical single policy deviation concentrability coefficient. It shows behavioral cloning's (BC's) limitations in high concentrability settings and proposes two algorithms, MAIL-BRO, and MURMAIL, which are validated both theoretically and, to a lesser extent, also numerically. Strengths include clearly advancing current state-of-the-art work, robust RL theory, and useful illustrations. The main weakness is the restriction to tabular settings also in the empirical part. Four reviewers supported acceptance, praising theory and clarity, with authors addressing some issues are the concept of concentrability and the applicability of the work. The only remaining major concern after the panel discussion is the limited benchmarking that would allow more direct comparisons with prior work. 

Overall, all reviewers engaged in discussion with authors ensuring a thorough and high-quality review process. On these grounds, I recommend acceptance. Nevertheless, I still strongly encourage the authors to implement the minor revisions that resulted from the discussion with the reviewers for the camera-ready version to further strengthen their contribution.
Decision: Accept (poster)