On Feasible Rewards in Multi-Agent Inverse Reinforcement Learning
Authors: Till Freihaut
Giorgia Ramponi
Venue: NeurIPS 2025 spotlight ()
Keywords: Reinforcement Learning
Multi-Agent Reinforcement Learning
Inverse Reinforcement Learning
Multi-Agent Inverse Reinforcement Learning
Primary area: reinforcement_learning

Abstract: Multi-agent inverse reinforcement learning (MAIRL) aims to recover agent reward functions from expert demonstrations. We characterize the feasible reward set in Markov games, identifying all reward functions that rationalize a given equilibrium. However, equilibrium-based observations are often ambiguous: a single Nash equilibrium can correspond to many reward structures, potentially changing the game's nature in multi-agent systems. We address this by introducing entropy-regularized Markov games, which yield a unique equilibrium while preserving strategic incentives. For this setting, we provide a sample complexity analysis detailing how errors affect learned policy performance. Our work establishes theoretical foundations and practical insights for MAIRL.

On Feasible Rewards in Multi-agent Inverse Reinforcement Learning
Till Freihaut
Giorgia Ramponi
Department of Computer Science University of Zurich freihaut@ifi. uzh. ch
Department of Computer Science University of Zurich ramponi @ifi uzh. ch
Abstract
Multi-agent Inverse Reinforcement Learning (MAIRL) aims to recover agent re- ward functions from expert demonstrations. We characterize the feasible reward set in Markov games, identifying all reward functions that rationalize given equi- librium. However, cquilibrium-bate baseddd observations Nash equilibrium can correspond to many reward structures, potentially changing the game's 's nature multi-agent systems. We address this by introducing entropy- regularized Markov games, which yield unique equilibrium while preserving strategic incentives. For this setting, we provide sample complexity analysis detailing how errors affect learned policy performance. Our work establishes theoretical foundations and practical insights for MAIRL.
often ambiguous: single
1 Introduction
Multi-agent Reinforcement Learning (MARL) has garnered substantial attention in recent years due to its capacity to model scenarios involving interacting agents. Notable successes have been achieved across diverse domains, including autonomous driving (Shalev-Shwartz et al.] [0066] Zhou al. [2020], internet marketing (Jin et al., 2018). multi-robot control Dawood et al. [023] traffic control [Wang et al., 2019]. and multi-player games [Baker et al. 2019 Samvelyan et al. 2019). 9 A critical prerequisite for these applications is the careful design of reward functions, a task that proves challenging even in single-agent settings [Amodei et al.] 2016 HadfieldMMnnell et al.) 2017] and becomes significantly more complex in multi-agent environments where each agent's 's reward function must be tailored to their specific, potentially conflicting, objectives.
In numerous real-world scenarios, expert demonstrations of optimal behavior may be observable, while the underlying reward function driving these actions remains unknown. This is precisely the domain of Inverse Reinforcement Learning (IRI.) (Ng and Russell| 2000). The objective of IRL. is to recover plausible reward functions that can rationalize the observed behavior as optimal. However, early research in IRL highlighted fundamental challenge: the problem is inherently ill-posed, as multiple reward functions can potentially explain the same observed behavior. Subsequent research has therefore focused reformulating the IRL problem enhance its practicality and applicability
in real-world contexts Abbeel and Ng 2004 Ziebart et al. 2008 Ramachandran and Amir 2007 Ratliff al. 2006a]
The extension of IRI. to the multi-agent setting introduces novel complexities, particularly concerning the definition of optimality and the multiplicity of Nash equilibria, given that each agent's 's optimal strategy is dependent on the strategies of all other agents. This necessitates the adoption of game- theoretic solution concepts, with the Nash equilibrium being the most prevalent [Goktas et al. [2024] Song et al.) 2018 Ramponi et al.) 2023 Fu et al. 2021]. In contrast to the substantial progress understanding the theoretical underpinnings of single-agent IRL, the theoretical foundations of Multi-agent Inverse Reinforcement Learning remain comparatively underexplored. In single-
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

R Ri ANuuca
Rig.n
R #
Figure 1: Feasible Reward Sets of true sets of Nash equilibria and the recovered feasible reward sets for two different observed Nash equilibria.
agent IRL. Metelli al. 2021 established explicit conditions for feasible reward functions and developed efficient algorithms for unknown transition models and expert policies, assuming access to generative model. This work has been extended settings without a generative model [Lindner et al. 2022]. stricter optimality metrics [Zhao et al.) 2024 Metelli et al. 2023), and offline settings SattingsLLazze Lazzati al. [024bb. /Zhoo et al. 2024] However, these studies confined to single-agent scenarios
and evaluate performance based on criteria that are not directly transferable to general-sum Markov games. In Appendix B we provide an extensive discussion on related works.
This paper aims to bridge the existing gap between the theoretical understanding of IRL in single- agent systems and its application to multi-agent systems. Specifically, we first address the research question:
(Q1) What constitutes a rigorous definition of Multi Multi-agent Inverse Reinforcement Learning?
To address this question independently of a specific MAIRL algorithm, we derive properties of the feasible reward set, drawing inspiration from the initial work in single-agent settings by Metelli et al. (2021). First, we define straight-forwart extension from the single-agent feasible reward set to the multi-agent setting as all the rewards under which a single Nash equilibrium expert is optimal, meaning it is indeed Nash equilibrium. Then, demonstrate that single observed equilibrium is insufficient for identifying expressive reward sets, as distinct observed equilibria can induce different feasible reward sets (see Fig. 1 for illustration). This result in Nash Gap of order (1 >> due to the multiplicity of the Nash equilibria. To mitigate the equilibrium selection problem, we introduce
Multi-agent IRL. Then, we formally characterize the inherent increase in complexity associated with the multi-agent setting. Within this framework, we characterize feasible rewards and establish sample complexity bounds that account for errors in transition dynamics and policy estimation, assuming access to generative model.
In single-agent settings, the introduction of mutroyy-regulare experts has facilitated the derivation of conditions under which the reward function is identifiable [Cao et al. 2021 Rolland et al. 2022
This motivates second research question:
(Q2) Is reward identifiability achievable in Multi-agent settings?
We provide a partial positive answer to this question. We show that in general-sum Markov games without additional structural assumptions, reward identifiability is only possible in the average reward sense. However, we prove that if the underlying reward structure is linearly separable, meaning that the reward can be decomposed into reward for player I and player 2, R(s, a, RA(s, (s b). then reward identification (up to additive constants) is possible.
Preliminaries
We present the essential background and notation used throughout this paper, also summarized in Appendix A
Mathematical background. Let X' be a finite set, then we denote by R all functions map- ping from X' to Additionally, we denote by A the set of probability measures over X. For IN [n] = n2). We introduce for (pre)metric space (X, d) with y.y" C X

---

two non-empty sets the Hausdorff (pre)metric Ha 2x x 2* + [0. +o0) as (")) == max (supwey infyey d(y. v sup,yyy inf d(y. y')} Additionally, for two probability distri- butions jr' over a finite set X, we denote the total variation as TV( := E>>x
- (x))
Markov games. An infinite time, discounted n-person general-sum Markov game (Shapley 1953 Takahashi 1964 Fink 1964) without reward function (MG \. Rt) is characterized by tuple 9 N denotes the finite number of players; S the finite state space: A x ... x AA the joint action space of the individual action spaces A'; P x A + A the transition model; y is the discount factor and p is the initial state distribution. We will make use of the words persons, agents and players interchangeably. The strategy of a single agent, also called the policy, we denote by n' : S + AA', A joint strategy is given by π = (+ (r'......")
(n. P. P), where
x²)
where -F refers the (joint-) policy of all players except player i. A joint action (I") x x=),, "),
is denoted by = (a' (a'.....aa) aa) E A. Therefore, the probability of a joint strategy is given by
T r(a 8) == IT x (a 8). IT' denotes the set of all policies for agent i. The discounted probability of visiting state-(joint)actticn
pair, given that the starting state is drawn from p. is defined as ". = Σم "PP'(s a, p,,), where Ie denotes the probability of visiting the joint state action pair when drawing the initial state from p and following the joint policy π for steps. If the starting distribution is deterministic for state s, we omit the dependence on p and simply write w.
Reward function. The reward function for an agent, R S x A - [-R max: R takes a state and a joint action as inputs, mapping them to bounded real number. The joint reward is represented as R = (R' ...., ). The uniform reward bound across all agents is defined by Rmax == max Rmaxx A Markov game without reward G combined with a joint reward results in a standard Markov game denoted as G U R.
Value functions and equilibrium concepts. For a Markov game & U R with a policy π we define the O-function and the value-function of an agent i for a given state and action as Q R
E. BT "> >2 (S Ai) St A,A, = A] and COUR(S (s) = Σ. aia s) s)Q a). If it is clear from the context what the underlying Markov game is, we omit the subscript.
(s,
Nash Equilibrium. Various types of equilibrium solutions have been proposed to model optimal strategies in Markov games. In this work, focus on the NE similarly previous works on MAIRL [Goktas et al., 2024, Song et al.) 2018) IA strategy profile is a Nash equilibrium if no agent can improve their expected return by unilaterally deviating from their strategy, assuming the strategies of the other agents remain unchanged. Formally, a policy π Nash is a (perfect) Nash equilibrium strategy,
for every state s and every agent i Vi Nush (s) 2 V'.(T'== (=
(s) Va E II' To simplify the notation used in the remainder of this work, we will denote this as V V'(T NaNNh) ) > V'(T', -i,Nss))
GUR
GUR
The set of Nash equilibria, depending on the underlying reward, we will denote as I[Nahh (R).
Entropy Regularized Markov games. For better readability, let us consider the case = (p, v) and A : B. Then, the value function of player 1 in a À entropy regularized Markov game is detined as V.l(uue) = B((e) /E 7at (R² (S,, A., B,) A log((((, S,))) Sp = s]. Addi- tionally, we have Vyllamee) (p) = Eso (V,] ((me) (So)). The value function for player 2 is defined analogously. Additionally, the Q-function is defined as 22.000))) (s, b) R R' a, b) Σ.' P(s') 8, a, (,,b) b) (s').
Multi-agent Inverse Reinforcement Learning. Given Markov game without a reward function G
and a Nash equilibrium expert, the MAIRL problem is defined as the tuple (G, π Nash). ). If we only have access to an estimated version of (G, π Nash), we call it recovered MAIRL problem and denote it as (g. # Nashs) and analogously for entropy equilibria by replacing म Nash
3 Feasible reward set in multi-agent systems
This section addresses research question (Q1) First, we will define MAIRL for a single NE observa- tion. Then, we will show, that this can be ill-suited for multi-agent systems due to the multiplicity of equilibria. This motivates to consider entropy regularized Markov games to guarantee a unique equilibrium.
3

---

3.1 Nash equilibrium observations
In this section, we begin by revisiting single-agent Inverse Reinforcement Learning. The feasible reward set in single-agent IRL, first defined by Metelli et al. [2021] and later refined for different settings as e.g. the offline case in (Zhao et al., 2024 Metelli et al. [023] Lazzati et al. 2024b]. lacks multi-agent counterpart for observed expert equilibria. We thus translate the single- agent definition,
formalizing feasible rewards as in prior works [Lin et al. 2014 2018).
Definition 3.1. Let a MAIRL problem (G, π Nushh with a single (observed) Nash equilibrium policy be given. Then, the feasible reward set for general-sum Markov games is given by
Noob
Naali)
Nashh
No = E R Vi [n], Vs E S, VTy E II' OUR
(s)
GUR
(s)
Here, π Nash E Nach (R) is any Nash equilibrium, analogous to an optimal policy in single-agent IRL. A key difference in MAIRL is that different NEs can yield varying values, and we impose no restriction on the observed NE (pure or mixed) from N| (R). This is the first fundamental difference between IRL and MAIRL.
Since varying NE values make single-agent value-based gap objectives [Metelli et al. 2021 2023
Zhao et al. 2024, Lazzati et al. (2024b) unsuitable for MAIRL. we adapt the Nash Gap, recently used in mu mulln--geent imitation learning Ramponi et al. 2023
Tang et al. 2024]. as our objective.
Definition 3.2 (Nash Imitation Gap for MAIRL). Let G U R be the underlying n-person general-sum Markov game. Furthermore, let A be the policy recovered from the corresponding MAIRL problem. Then we define the Nash Imitation Gap of as
E # Rt) == max max V VOUR(T' --) - V (
sE|n] Ele
The definition possesses the desirable property that equals 0 if स is an NE, and, is > 0 Of f is not an NE in the underlying Markov game.
Normally, we cannot assume to know the expert equilibrium nor the transition function. Therefore, to analyze how estimation errors in the transition probability and expert policy affect the recovered feasible reward set, we relate them to our proposed optimality criterion.
Definition 3.3 (Optimality Criterion). Let R := nN be the exact feasible set and R = R==R((.)) the recovered feasible set after observing N 0 samples from the underlying MAIRL problem (G, Nash). An algorithm is (s, 6, N) -)-correct after N samples if, with probability at least 1 5, it holds that:
sup inf RER RER Not
sup
E(f, SE,
sup inf heR RER
sup E(A, R) SE. #ENNNaa((1))
where Nash (8) (R) = { VT VL
F. ((S II' Vs S. [n]} GUî
The optimality criterion in the Hausdorff metric style, see 2 The first condition ensures that the recovered feasible set captures reward function that makes sure that the recovered policy is at most an e-NE in the true Markov game. However, this would support choosing a set that captures all possible reward functions SXA, Consequently, the second condition ensures that this is not possible by requiring every recovered reward to also have a true reward function that captures the desired behavior. Additionally, note that the optimality criterion depends on A as î is the Nash equilibrium of the recovered Markov game Č U R.
The shortcomings of observing only single equilibrium are discussed next. For completeness, this framework is further analyzed in Appendix C
Feasible reward set and equilibrium ambiguity. this section, we show that observing only a
single equilibrium solution leads to non-expressive feasible reward set. Fu et al. (222] noted that relying on single Nash equilibrium for inverse learning introduces inherent limitations. Here, we extend this finding to the feasible reward set, rather than focusing solely on specific reward functions.

---

Tang et al. [024] showed that minimizing the regret gap is hard in Imitation Learning problems. However, in this work we do not consider the setting of mimicking the expert policy instead we examine the feasible reward set. In general, (MA)IRI. can be more powerful as it allows to transfer Appendix G we provide an experiment in a simple
the reward function to new environments. Grid World game that emphasizes this. Unfortunately, the next theorem shows, that learning under a recovered reward function from the feasible set stemming from a MAIRL problem with a single equilibrium observation can lead to NE that has Nash Gap of the order (1 -> in the original Markov game.
Proposition 3.4. Let us consider any MAIRL algorithm AlgMAIRL. that chooses ft E NNwb)) that is not a constant reward, i.e. R C for C' E |- Rmax- Rmasz) Furthermore, consider a MARL algorithm AlgMARI that guarantees learning policy it E 111Nushs(R) (Rt). Then, there exists Markov game, such that even त E IlNassh and R E ( it holds true that { is of order (1 7)--
The construction of the underlying general-sum Markov game can be found in Fig. 2 The idea of the proof is that Definition 3.1 only ensures that the recovered expert π Nash is a NE under R, an MAIRL algorithm cannot capture meaningful reward for other equilibria that potentially have different values. Therefore, the constraints on the rewards inside the feasible reward set only gives a relation for a fixed strategy of the opponent. Consider a simple example with two players where player plays action b with probability one. Then, for player one the constraints only tell us something about R (s, Nash b) 2 R2 (s, a, b) Va AA,, but nothing on rewards R (s, a, V(, B') E A A², This allows that the recovered reward functions allow for new equilibria, i.e. Nash (f) S IT R)) that can be exploited in the original Markov game. We empirically investigate this for the considered Game in Proposition 3.4 Summarized, the reward set captures too many reward functions and this flexibility in reward specification allows for undesirable scenarios, such as changing the nature of the game. This means the game can transform the set of all Nash equilibria e.g. from a coordination game into an coordinttinnn variant. For further intuition we provided additional examples in Example D.I
Average new equilibria
Exploitability under R
all
2
Average Nash Gap
a1 0101
1.5
1.5
01 010, 0241
Count
80
82
all
1
1
a202
0.5
0.5
0
0
83
all
Stag Hunt MG
Slag Hunt MG
Figure 2: Failure of single equilibrium observation.
To address this, we propose the following definition of the feasible reward set. Definition 3.5. Let Nash (R) denote the set of Nash equilibrium in the underlying Markov game G R. Then, the feasible reward set for general-sum Markov games is defined as: Reg,nNen) = R R. | Nach Nach E Nushh i [n), E n, E IT', A. (aWNaa Nash, Mash,
(s) > V. Nash
(s)
GUR
Note that, the subscript is now the set of equilibria instead of a single one. This definition ensures that the feasible reward set aligns with all equilibrium solutions of the original game, rather than single observed equilibrium. While this improves the interpretability of the feasible reward set, calculating even one Nash equilibrium computationally intractable in general-sun Markov games. Hence, this definition does not fully resolve the tractability issue in MAIRL.
The multiplicity of equilibria and the absence of unique value pose a significant challenge in Inverse Reinforcement Learning, in particular which equilibria should be chosen, commonly referred to as the Equilibrium Selection problem. This ambiguity complicates reward inference, as different equilibria can lead to inconsistent or unreliable outcomes.
5

---

Leonardos et al. [202]] address this by proposing game structure modifications, such as regularized Markov games. Techniques like entropy regularization refine the equilibrium set to a unique one, eliminating the selection problem. We will transfer this concept to MAIRL and investigate its implications subsequent chapters.
3.2 Feasible rewards for entropy regularized games
This section examines Rerroar-eg Markov games and their unique Quantal Response Equilibrium (QRE), which reflects bounded rationality. We show that QREs help avoid problematic reward configurations (cf. Fig. and yield recovered rewards more similar to the true game rewards. We then formally define the feasible reward set for QRE experts and provide a sample complexity analysis for MAIRL to achieve the entropy version of Definition 3.3 Technically, this is not the Nash Gap anymore, instead only measures the exploitability of policy in the entropy regularized game.
Avoiding the ambiguity with QRE expert. We begin by demonstrating that entropy regularization, yielding a unique fully mixed QRE, provides sufficient structure for reward recovery to avoid the degenerate cases highlighted in Fig. 2 Recalling our empirical validations (Fig. 2) single, potentially pure, equilibrium observations permitted exploitable new equilibria in the original game. We now present analogous experiments using QRE observations (see Fig. 3
Count new equilibria.
Average Correlations
-10
QRE
Frequency
0.6
Nash
Value
0.5
0.4
0.2
PCC
SCC
Figure 3: Recovered rewards under QRE equilibrium observations.
We can observe that in simple games the QRE ensures that no new pure equilibria arise and ad- ditionally the correlation of the recovered reward function and the true reward function measured by the Pearson Correlation Coefficient (PCC) and Spearman Correlation Coefficient (SCC) are significantly higher. The reason for this that the QRE enforces the equilibrium observation to explore the environment better and gets rid of the equilibrium selection problem. This can be further motivated by assumptions needed also in the Multi-agen Aulti-agent Imitation Learning setting, where Tang et al. (0224) showed that under coverage assumption equilibria can successfully be recovered. This is automatically fulfilled if the observed expert a QRE expert.
Characterization of feasible rewards. In the single-agent IRL setting, explicit characterization of the reward function in entropy-regulariize Markov Decision Processes (MDPs) was first derived by Cao al. 202T]. The authors introduced entropy regularization tackle the ill-posedness of the IRL problem. In particular, the authors established conditions under which the reward function is identifiable up to constant. These conditions were subsequently simplified by 'Rolland al. [2022). providing further insights into the structure of the reward function. This naturally motivates our second research question (Q2) which we will answer in Section 4 In this section we will first focus on the feasible reward set.
We begin analysis in manner similar the single-agent
For better readability from now on assume to only have two players, with policies μ., и. We can give an explicit characterization of the optimal policy for the agents. Next, we give this definition for player 1, it analogously holds also for player 2
exp (1 EvER s) =s, (s,
n² 8) EoEA exp Evee ( [s) (s,a'
where 1²" denotes the optimal policy, i.e. the quantal response equilibrium policy of player and I the corresponding Q-function for player 1. Several remarks are in order to clarify this equation.

---

First, the optimal strategy depends not only on the Q-function but also on the strategy of the opposing agent. This can be interpreted as fixing one agent and considering the induced MDP (see, for example, Definition 4.1 in Fu et al. (02T).
From now we will state everything from the perspective of player one. The results for player 2 follow analogously. Therefore, we will also omit the index of the reward and value functions. Next, using the definition of the Q-function and the value function, we can rewrite ( get an explicit formulation of the average reward that agent receives for playing a specific action a E A:
Σ (1(6' [s)R(s,,,b)) Alog (p" (a s)) + (x( - ΣΣ BEEB
v0 s))(( (V
BEE
(2)
Regarding the feasible reward set, our focus is to find an explicit reward formulation to characterize the reward functions in the feasible reward set. Rewriting equation (2) in terms of a specific reward, we get the following characterization.
Lemma 3.6. Let (n" v²)) be Iwo equilibrium policies for the 2 Person X Entropy-Regularized Markov game G. Then for the MAIRL problem (g, (n² v²" ) reward R is feasible if and only if there exists
a function E 1R and [B] functions R. IR5xAX such that for all (s, S A x B
R(s,a, (-()(s] (Alug(u (a [a| s]) + V(s) -E EnER [s)P(( s, -))))) - ( a)
As in practice, we do not have access to P. v² and jr,, our goal is to analyze the impact of estimating the transition probability and the expert's policy, and how this affects the existence of a recovered feasible reward. Therefore, we now want to analyze how recovered MAIRL problem (9, (n² )) translates to the original MAIRL problem. Care is required for this analysis, as we must consider the estimation of the expert itself, the induced transition model, which incorporates the estimation of the other expert's 's policy and their deviations for alternative actions.
Theorem 3.7 (Error propagation). Let the MAIRI. problem be given by (G, ,v")) and another MAIRL problem by (9, (Ø ;)")) Then, we have that
1 a) (asta,,b)R{(s,,, (b(b) s) (b s)
[l (a log (a |)]
+ max Σ V(s'')P(s s,a - P(s' 8, + RaaxXV(( )
The introduced theorem highlights the additional complexity of the problem. Specifically, it reveals two key challenges that arise in error propagation for multi-agent IRL. First, the maximum of the joint transition probabilities plays a critical role, amplifying the sensitivity of the system to inaccuracies in transition estimation. Second, any deviation in estimating the other expert's policy, quantified by the total variation distance, directly contributes to errors in the recovered reward.
Recovering feasible rewards. The previous section revealed, that also in the Multi-agent case, the explicit feasible reward can be decomposed into parts that depend on the policy of both agents and the transition model. Therefore, we will now analyze the amount of samples required to obtain a meaningful reward function. Let us first introduce the assumption, also common in single-agent IRL, that the lowest probability of an action taken from the experts is bounded away from zero by some constant (see e.g. Assumption D.I. in Metelli et al. (2023).
Assumption 3.8. Let p², v² be the QRE equilibrium expert policies. Then we assume that
min (H" (a s), (b s)) Amin Vs S. aEA
For both estimation tasks, the expert policies and the transition probability, we employ empirical estimators. For each iteration & E [K]. let ny (s, a, b, s') = Σt= (es,a) bw," denote the count of visits to the triplet (s, a, b, s') E S x (Ax B) x S, and let denote the count of visits to the state-action pair (s, a). Additionally, we introduce n a) =
b) = =>es T a, b, s')
Ek (().0))=((8.)) and n4(s,b) b) Σ (().)))=(s.)) as the count of times action and respectively
7

---

b was sampled in state s E S for each agent i, and ny (s) = = m a) as the count of visits to state s for any agent.
is important to note the distinction here: the count of actions must be done separately for each agent, whereas the count of state visits needs to be done for both of the agents.
In the following theorem we will assume to have access to a generative model, an assumption that is common in initial theoretical works on IRL [Metelli et al. 2021 Lindner et al. 2022, Metelli
et al. 2023]. We will discuss potential directions that loosen this assumption in Section 5
Theorem 3.9, Let Assumption h.8d true. Then, allocating the samples uniformly over S X x B
and using the empirical estimators introduced in Eq. (12) and Eq. (I3), we can stop the sampling procedure with a probability of at least 5 after iteration T and satisfy the optimality criterion
where the sample complexity is of order Ö R [SA||B]
Definition E.2
(1-7))<2A4 min
Some remarks are in order for this complexity bound. We observe that the sample complexity bound depends on the product of the action space of both players. Translating this to the n n-player setting would result in an exponential dependency in the number of players. Although this might seem unfavorable, is generally known that learning an NE in the worst case has an exponential bound. Zhang et al. [0233] show that even in model-based two player zero-sum games with access to generative model, where the reward knowledge can not be used during learning the sample complexity depends on |A| Therefore, the derived bound for the MAIRL setting aligns with the bounds derived for learning NE in the MARL setting. Additionally, we can see that the sample complexity bound is related to estimating the expert policies. This requires to estimate the log probabilities as well as the inverse probabilities of specific action taken by one player. To do so, we need the assumptions that the probabilities are bounded away from zero (Assumption 3.8
4 Identifiability in multi-agent games?
At the beginning of Section 3.2 we noted that entropy regularization has been introduced in the single- agent setting to derive conditions to identify the reward (up to constants). Unlike the single-agent case, multi-agent systems introduce additional challenges due to the interplay between agents' strategies and the underlying reward structure. These challenges make identifiability like in single-agent settings not possible, unless further assumptions section into two parts. First, we consider average reward characterization. Then, we introduce linear separable Markov games and investigate identification in this setting.
the underlying Markov game posed. We split this
Average reward identification. First, let revisit the derivations from the last section. In particular, note that the left-hand side of Eq. (2) shows, that agent I's average reward depends on agent 2's policy v(b' s) which averages over agent 2's action. Additionally, note that the reward function is in the multi-agent setting, has dimensionality ||]| while Eq. (T) only gives condition for |8| || and | respectively. This shows immediately that the resulting system of equations is under-determined.
However, the left hand side can be interpreted in terms of the induced MDP. In particular we derive an explicit reward function for the average reward (s a) = Eves vb' s){(s, a, B'). Next, let us additionally define the induced transition function, keeping the strategy of agent 2 fixed. Then, have ( s, a) := Eves v/b' P(s s, a, b'). Thus, agent I's decision problem, when facing fixed opponent policy v, is equivalent to single-agent MDP with the average reward function R. and the transition function p".
These findings indicate that single-agent IRL theory [Cao et al.) 2021 Rolland et al. 2022 can be applied. However, note that for identifiability in single-agent settings at least two environments with different transition dynamics and discount factors that induce experts with the same reward functions are necessary. multi-agent systems, one obtains a different transition model by varying the policy of the opponent and observing the best responds to this change of dynamics. This can be less restrictive than requiring a new environment as in the single-agent case. Next, we state the result for the average reward case for multi-agents this is similar to Theorem 3 by [Rolland et al. 2022
Theorem 4.1. Let Markov game be given with two different opponents v1, U2 that induce different dynamics pus, puz and discount factors 71, 72- Suppose that in both Games we observe QRE equilibrium policy pairs (Hi,V) and different v2 with best responding policy #2 such that they
8

---

have same average reward functions R = R Additionally, define P E & the induced transition matrix of expert i E {1.2]. Then, the average reward player receives can be recovered up to constant if and only if
I 7 Pii
1 7/2 PMz
a1
rank
:
2||S| 1.
(3)
I
I
Y/2 PIAl
Analogously this holds for player 2.
Therefore, for the average case this closely resembles the single-agent case. However, if we want to estimate the underlying problem, which is the more realistic setting, things change. In particular the error in the estimated induced transition | P is bounded by terms dependent on the policy estimation error and the underlying transition model error. Using the L1 norm we receive for a given
(s, a) P (- 8, a) - (- 8, a. < [| 8) E((- 8)]I + maxy (((s,,, - P(. 8, a, b111- We derive the following sample complexity for this.
Theorem 4.2 (Sample Complexity for Induced Transitions), To estimate the induced transition model P for Player I such that the maximum L1 error over all (s, a) rows is bounded by e with probability
at least 5, the total number of samples Noaa is in the order of O |S||A||
With this theorem we can recover the same result of the single agent case. In particular, we get for every player that if the estimated transition model satisfies Eq. (3), then also the true transition matrices satisfies this condition given that a condition on the second smallest eigenvalue holds true. We state the complete theorem in Appendix F
Reward identification in linearly separable Markov games. To get an identifiable reward not only in the average sense one needs to disentangle the reward from player 2's strategy. This shows that the multi-agent case is fundamentally harder than then the single-agent case. Intuitively, the reason is that the definition of the NE only ensures optimality against fixed opponent strategy. Additionally, note that the reward function is matrix of size ||||A||BB while the optimal policy is only defined on |S||AA| and [S]| respectively.
A potential assumption that disentangles the joint dependency of the reward is fulfilled in linearly separable reward Markov games, first introduced in the seminal work of Paatthasarathy et al. [1984]. This framework has also been leveraged in more recent studies (e.g., Péroolat et al. [2021]). A reward function is said to be linearly separable if can be decomposed into two independent terms, each depending solely on one player's 's action R! (s, a, b) ( a) + R' (s. b). This formulation immediately mitigates the complexity introduced by the product space dependency, as the reward
function now operates over individual action spaces instead. Now, we can rewrite the condition on a reward for a specific state action pair (s,a). a). We give the formulation directly for two observed environments, meaning that for every (s, a) E x A
(s Alog(ui(a s)) V((s) 7 Σ pui(s' (s1,,,))VV((s)
Σ vi(bl RB(.s)))
NEB
Aloo((g s)) V2(s) - Σ (ri (.,,
Σ bEB
v2 RB, (4)
We can observe the following two cases. If have two environments for which the reward RA a) is the same, and player 1 faces the same opponent strategy v², but different transition dynamics Pi and P2, then notice that Eseg v² ub(b] RB b) cancels out. Instead if we have different opponent policies vf # 1/2 then we get new rank requirement for the resulting system of equation. We give a detailed discussion in Appendix F and summarize the findings in the following proposition.
Proposition 4.3 (Identifiabilityy with Linearly Separable Rewards). Let two Markov games with linearly separable rewards be given. Then, the resulting system of equations from Eq. (4) is solvable, i.e. the reward is identifiable up to constant, if the matrix has rank 2|5] 1 and v v22 or rank 2) + 1) - 1 in case v + vn and for one action by E B we have RB (s by) 0.
Summarized, we have shown that identifiability is not possible in general in the multi-age setting for a particular R(s a, b). Additionally, we have given scenarios and conditions that make identifiability possible.

---

Conclusion and future work
We formalized Multi-agent Inverse Reinforcement Learning (MAIRL), highlighting its unique challenges over single-agent IRL, particularly the insufficiency of single equilibrium observations for meaningful reward construction due to equilibrium multiplicity and selection ambiguity. To address this, we focused regularized Markoy games to ensure equilibrium uniqueness. In this setting, we extended single-agent IRL bounds Metelli et al. [202T] to analyze error propagation from these estimations the recovered reward set, resulting in sample complexity bound for the Uniform Sampling algorithm for Quantal Response Equilibria. Additionally, we addressed the question of reward identifiability in multi-agent systems. This work gives theoretical foundation of MAIRL and opens many potential directions for future work. We outline a few of them next.
Removing assumption of generative model. In the provided sample complexity analysis we have assumed having to generative model and sampled uniformly from this. While this is common assumption in initial works also in single-agent IRL [Metelli et al. 2021 Lindner et al. 2022 Metelli al. 2023]. this can be restrictive in general. Therefore, it could be of interest to explore the offline setting as done in Lazzati et al. 2024b Zhao al.) 2024) for multi-agents. However, this might not be easy as in offline learning for multi-agent different coverage assumptions are needed compared to the single-agen setting even in case of reward knowledge [Cui and Du [002 Zhong et al. 2022]. Another direction would be to consider the active exploration direction, meaning how construct policies that actively the environment as done in Lindner et al. [0022] for the single-agent case.
Designing algorithms. Our analysis showed that single Nash equilibrium observations allow for an uninformative feasible reward set. One potential algorithmic implication of this finding could be to design an algorithm that guarantees that the observed NE the only equilibrium under this reward function. This algorithm could be in similar spirit as the Max-Gap IRL algorithm for single-agents Ratliff et al. 2006b], but now on an equilibrium level instead of a value-based design.
Observing multiple equilibria. As pointed out the discussion around Definition 3.5 and in Fu et al. 2021]. if one would be able to observe multiple or all equilibria from the set of Nash equilibria of the underlying game, the characterized feasible reward is more meaningful. As this might be restrictive in practice it could give important theoretical insights.
References
P. Abbeel and A. Y. Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the Twenty-First International Conference on Machine Learning, ICMI. '04, page 1, New York, NY, USA, 2004. Association for Computing Machinery. ISBN 1581 138385. doi: 10. 145/100303333 1015430. URL httpp::/://// orgo /111//11111131 1015430
D. Amodei, C. Olah, Steinhardt, P. F. Christiano. J. Schulman, and D. Mané, Concrete problems in AI safety. CoRR, 106.1606.66565. 2016. URL httpt://aa/xiii org/ abs/ /1066666000000 005655
B. Baker, I. Kanitscheider, T. M. Markov, Y. Wu, G. Powell, B. McGrew, and I. Mordatch. Emergent tool use from multi-agent autocurricula. CoRR, abs/1909.07528, 2019. URL http://arxiv org/abs/19099 07528
D. Berend and A. Kontorovich. On the concentration of the missing mass. Electronic Communications in Probability, 18, 10 2012. doi: 10. 00.1214/ECP:11-22555
H. Cao, S. N.N. Cohen, and L. Szpruch. Identifiability in inverse reinforcement learning. In Proceedings of the 35th International Conference on Neural Information Processing Systems, NIPS '21, Red Hook, NY, USA, 2021. Curran Associates Inc. ISBN 0781713845393.
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 Neurul Information Processing Systems, volume 35, pages 25779-25791 Curran Associates, Inc., 2022. URL htttps:://pocceediingggooooo www.wpe.......m cclipps.cc//pee wttccc//pppp...eeee 55778885945555444311111111282823 oog.rpppceeappppppoooooooeoeeeee
htteee/ffleeeeee//eee//e paaee///pper//22///iiee//
10

---

M. Dawood, S. Pan, N. Dengler, S. Zhou, A. P. Schoellig, and M. Bennewitz. Safe multi-agent reinforcement learning for formation control without individual reference targets. 2023. URL
ftopps://arxi.... org/ abs/ 2312. 1382112661111111 12861
A. M. Fink. Equilibrium in a stochastic SnS person game. Journal of Science of the Hiroshima Uni- versity, 28:89 93, 1964. URL https://api sewaneiscchhhslilsc....... wtw.:/aaarrrrrrouuuuuououou 120600263
J. Fu, A. Tacchetti, J. Perolat, and Y. Bachrach. Evaluating strategic structures in multi-agent inverse reinforcement learning. J. Artif. Int. Res., 71:925-951, Sept. 2021. ISSN 1076-9757. doi:
10.1 10.1613/jair. 1.t.iirr..1229... 12594. URL http:: ftttps:/ddo:: //t.i org/ 10. 1613/jair. 1. 12594
D. Goktas, A. Greenwald, S. Zhao, A. Koppel, and S. Ganesh. Efficient inverse multiagent learning. In The Twelfth International Conference on Learning Representations, 2024. URL https:// opearreriex.ntt//formmiiicc
D. Hadfield-Menell, S. Milli, P. Abbeel, S. Russell, and A. D. Dragan. Inverse reward design. CoRR, abs/1711.028221 2017. URL
wttp/org//////oooooooo 1711/08277 02827
J. Hu and M. P. Wellman. Nash q-learning for general-sum stochastic games. J. Mach. Learn. Res., 4 10391)1009,-169, dec 2003. ISSN 1532-4435.
J. Jin, C. Song. H. Li, K. Gai, Wang, and W. Zhang. Real-time bidding with multi-agent re- inforcement learning in display advertising. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management, CIKM '18. ACM, Oct. 2018. doi: 10.1 00.14455/269200.3222221.. UtL.ttpp://dx doi http::///x..oi..r//1......1... 1111////2111/////2666166 3272001
Kalyanaraman and Umans. The complexity of rationalizing matchings. In Proceedings of the 19th International Symposium on Algorithms and Computation, ISAAC '08, page 171-182, Berlin, Heidelberg, 2008. Springer- Verlag. ISBN 9783540921813. doi: 10.100079978--5540-921110 URL https: //oo. org/
S. Kalyanaraman and C. Umans. The complexity of rationalizing network formation. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 485-494, 2009. doi: 10.1 A.L1099FOSS.009...0
E. Kaufmann, Ménard, O. D. Domingues, A. Jonsson, E. Leurent, and M. Valko. Adaptive reward-free exploration. In Algorithmic Learning Theory, pages 865-891, PMLR, 2021.
K. Kim, S. Garg, K. Shiragur, and S. Ermon. Reward identification in inverse reinforcement learning. In M. Meila and Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 5496-5505. PMLR, 18 24-24JJ Jul 2021. URLhttpp http///erceeeennseeeeeeeeec mlr ppwss/v133 1tt///3////mmm. kim21c......... html
V. Kuleshov and O. Schrijvers. Inverse game theory: Learning utilities in succinct games. In Workshop on Internel and Network Economics, 2015. httpss//::/aap httt::::/aap.ssmmantieceette semanticacholar Org/Corpusll 2405324
F. Lazzati, M. Mutti, and A. M. Metelli. How does inverse rl scale to large state spaces? provably efficient approach. In A. Globerson, L. Mackey, D. Bel- grave, A. Fan, U. Paquet, J. Tomezak, and C. Zhang, editors, Advances in Neu- ral Information Processing Systems, volume 37, pages 54820-54871. Curran Associates, Inc., 2024a. URL
wewpeeedddinnnnnenii..eee. neurips. ccccccc///o.o cc/paper._.... filfs/iee//. ptsssaper//22///1eeee Paper- Conference, pdf
F. Lazzati, M. Mutti, and A. M. Metelli. Offline inverse rl: new solution concepts and provably efficient algorithms. In Proceedings of the 41st International Conference Machine Learning, ICML 224 JMLR.org, 2024b.
S. Leonardos, G. Piliouras, and K. Spendlove. Exploration-exploiittioon in multi-agent competition: Convergence with bounded rationality. In M. Ranzato, A. Beygelzimer, Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34. pages 26318 1-331- Curran Associates, Inc., 2021. URL https: / itw.eeeedddinnn.....ipree. neurips ec/ files/ httpa./.....poooo.......ooooaata
pddf

---

S. Levine, Z. Popovic, and V. Koltun. Nonlinear inverse reinforcement learning with gaus- sian processes. In J. Shawe-Taylor, R. Zemel, Bartlett, Pereira, and K. Weinberger, editors, Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc.. 2011. URL.
paper/2011/fille www.rieeespppp.ee pttpsseeerrr.pppppeeeeeeeeeeee / Paper. pdf
J. Liao, Z. Zhu, E. X. Fang, Z. Yang, and V. Tarokh. Decoding rewards in competitive games: Inverse game theory with entropy regularization. In A. Singh, M. Fazel, D. Hsu, S. Lacoste-Julien, F. Berkenkamp, T. Maharaj. K. Wagstaff, and J. Zhu, editors, Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 37610-37622. PMLR, 13-19 Jul 2025, URL http::ttt/pccceeeaiiaiaee wwt.:mmwww.ppm..e...m.mmmmmme.. press/v267 liao25i. html
mlr
X. Lin, A. Beling, and Cogill. Multi-agent inverse reinforcement learning for zero-sum games. CoRR, abs/1 650.6 2014. htt.lattp../aar....rgg/bbb/////
X. Lin, S. C. Adams, and P. A. Beling. Multi-agent inverse reinforcement learning for general-sum stochastic games. CoRR, 0ts//800.09977 2018. UtL/attpp//arxt/..org/////
09795
D. Lindner, A. Krause, and G. Ramponi. Active exploration for inverse reinforcement learning. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS 222 Red Hook, NY, USA, 2022. Curran Associates Inc. ISBN 978171387 1088.
A. M. Metelli, G. Ramponi, A. Concetti, and M. Restelli. Provably efficient learning of transferable rewards. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 7665-7676. PMLR, 7 2021. URL http://///r/ccceeingg.s. mlr wwwppreeeevee http///////mmmeeeememmm 1tt
A. M. Metelli, F. Lazzati, and M. Restelli. Towards theoretical understanding of inverse reinforcement learning. In Proceedings of the 40th International Conference on Machine Learning, ICML' '3. JoLR.org, 2023.
S. Natarajan, G. Kunapuli, K. Judah, P. Tadepalli, K. Kersting, and J. W. Shavlik. Multi-agent inverse reinforcement learning. 2010 Ninth International Conference on Machine Learning and Applications, pages 395-400, 2010. URL https:://///t.. /sttps://api.. www.nticscholee..t.... org/ Cas/Crrpuuss. 3440496
A. Y. Ng and S. J. Russell. Algorithms for inverse reinforcement learning. In Proceedings of the Seventeenth International Conference on Machine Learning. ICML '00, page 663-670, San Francisco, CA, USA, 2000. Morgan Kaufmann Publishers Inc. ISBN 1558607072.
T. Parthasarathy, S. Tijs, and O. J. Vrieze. Stochastic games with state independent transitions and separable rewards. Lecture Notes in Economics and Mathematical Systems, pages 262-271, 1984. URL https: //ap:::://i..... semanticscholar
merg/CorpuSID: 122647253
J. Pérolat, S. Perrin. R. Elie, M. Laurière, G. Piliouras, M. Geist, K. Tuyls, and O. Pietquin. Scaling up mean field games with online mirror descent. CoRR, abs/2103.00623, 2021. URL hhtps //arxiv... org/ /bbb/103.... 22103.0002233
D. Ramachandran and E. Amir Bayesian inverse reinforcement learning. In Proceedings of the 20th International Joint Conference on Artifical Intelligence, IJCAI'07, page 2586-2591, San Francisco, CA, USA, 2007. Morgan Kaufmann Publishers Inc.
G. Ramponi, P. Kolev, O. Pietquin, N. He, M. Laurière, and M. Geist. On imitation in mean-field games. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2023. Curran Associates Inc.
N. Ratliff, D. Bradley, J. A. Bagnell, and J. Chestnutt. Boosting structured prediction for imitation learning. Proceedings of the 20th International Conference on Neural Information Processing Systems, NIPS'06 '0, page 1153-1160 1660, Cambridge, MA, USA, 2006a. MIT Press.
12

---

N. D. Ratliff, J. A. Bagnell, and M. A. Zinkevich. Maximum margin planning. In Proceedings of the 23rd International Conference on Machine Learning, ICML '06, page 729-736. New York, NY. USA, 2006b. Association for Computing Machinery. ISBN 1595933832. doi: 10. 143844. 1143936. URL. https: org/ 10. 1145/11438444 1143936
Rolland, L. Viano, Schürhoff, B. Nikolov, and V. Cevher. Identifiability and generalizability from multiple experts in inverse reinforcement learning. Advances in Neural Information Processing Systems, 35:550-564, 2022.
M. San 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 19, page 2186-2188, Richland. SC, 2019. International Foundation for Autonomous Agents and Multiagent Systems. ISBN 9781 9781450363099.
Shalev-Shwartz, S. Shammah, and A. Shashua. Safe, multi-agent, reinorrctttttt Iearning for au- tonomous driving. CoRR, abs//160,.33295,, 2016. URL URL.ttpp///axxivvorr///aab/// 031223 03295
L. S. Shapley, Stochastic games*. Proceedings of the National Academy of Sciences, 39:1095 1100, 1953. URL httth:///ppp semanticscholar
J. Song, H. Ren, D. Sadigh, and S. Ermon. Multi-agent generative adversarial imitation learning. CoRR, Abss/807.09996, 2018. URL seeiartttecccolla.r..o///ooppppp orgp/orpps3D:2263441007
09936
M. Takahashi. Equilibrium points of stochastic non-cooperative SnS-person games. Journal of Science of the Hiroshima University, 28:95-99, 1964. httphhppp//ppp..sssaaaicaaaaiaia
org/CorpusIii 118906641
Tang, G. Swamy, F. Fang, and Z. S. Wu. Multi-agent imitation learning: Value casy, 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 http:: inwp:/ceeeeddinnnnnnneinr.reeeee cc hecc/appr__fille paper/ 222p:///w00222207777700000000100
X. Wang, L. Ke, Z. Qiao, and X. Chai. Large-scale traffic signal control using a novel multi-agent reinforcement learning. CoRR, Abs/1908.03761, 2019. URL http://arxiv org/ hatgg//b///// abs///9/b//9 1908 03761
Wu, W. Shen, F. Fang, and H. Xu. Inverse game theory for stackelberg games: the blessing of bounded rationality. In S. Koyejo. S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 32186-32198. Cur- Associates, Inc., 2022. URL https:://procceedings neurips cc/paper files/paper// iew.eeeedddinnnn.nnniisss..eeeee 02271111140033333350044442222223 Pwwaaaapeerrrerrrrrreeeeee .df
L. Yu, J. Song, and S. Ermon. Multi-agent adversarial inverse reinforcement learning. In International Conference Machine Learning, pages 7101-7201. PMLR, 2019.
A. Zanette, M. J. Kochenderfer, and F. Brunskill. Almost horizon-free structure-award best policy identification with a generative model. H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox. and R. Garnett, editors, Advances in Neural Information Processing Systems, vol- ume 32. Curran Associates, Inc., 2019. URL
wttp://wwwwee.ooaeeere..o..oo.oe cc/ppperrrcppppr -df
K. Zhang, S. M. Kakade, T. Başar, and L. F. Yang. Model-based multi-agent rl in zero-sum markov games with near-optimal sample complexity. J. Mach. Learn. Res., 24(1), Jan. 2023. ISSN 1532-4435.
I. Zhao, M. Wang, and Y. Bai. Is inverse reinforcement learning harder than standard reinforcement learning? theoretical perspective. In Proceedings of the 41st International Conference on Machine Learning, ICML'24. JMLR.org, 2024.
13

---

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, S. 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 27117-27144 PMLR, 17-23 Jul 2022. URL http:ttsss/////mt ptttpps://proceeddngss mlr zhong22b. html
www.mress.////p.mmm.mm.cmmm prwss/ press/vv62) vv62/
M. Zhou. Luo. J. Villela, Yang, D. Rusu, J. Miao, W. Zhang, M. Alban, I. Fadakar, Z. Chen, A. C. Huang, Y. Wen, K. Hassanzadeh, D. Graves, D. Chen, Z. Zhu, N. M. Nguyen, M. Elsayed, K. Shao, S. Ahilan, B. Zhang, J. Wu, Z. Fu, K. Rezaee, P. Yadmellat, M. Rohani, N. Nieves, Y. Ni, S. -Bnnjaamali, A. I. Cowen-Rivers, Z. Tian, D. Palenicek, H. Bou-Ammar, H. Zhang, W. Liu, J. Hao, J.d Wang. SMARTS: scalable multi-agent reinforcement learning training school for autonomous driving. CoRR, abs/2010.09776, 2020. URL https://axxi. wtw.g//aa//....///0// 09776
B. D. Ziebart, A. Maas, J. Bagnell, and K. Dey. Maximum entropy inverse reinforcement learning. In Proceedings of the 23rd National Conference on Artificial Intelligence Volume 3, AAAI'08, 08, page 1433 1438. AAAI Press, 2008. ISBN 9781577353683.
14

---

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]
Justification: The claims stated in the introduction are answered in Proposition 3.4 Theo- rem remm3.) and in Theorem
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in 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.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The limitations about the assumption of generative model are discussed and justified above and also outlined 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 a 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 (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn 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 on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be 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 low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to 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 faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in 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
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
15

---

Answer: [Yes]
Each Theorem states the assumptions clearly and contains a proof in the appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors 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 the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: The paper is mainly theoretical. However, simple empirical validations are given and the details for these examples can be found in Appendix G
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 be 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 to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
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 new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either 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 reprodueibility may be tricky in some cases, in which authors are welcome to 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 be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
16

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: The main contributions of this paper theoretical and only provide numerical verifications of the theory. However, details on the empirical validations are given in Appendix G
The full code will be released after publication.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS 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, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
y /nips. /nips.cc///pp http:/ccccccccguueeeeeeeeeeeeee/ huabbiiccguidee/odeeeuubiiis
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, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they 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 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 understand the results?
Answer: [Yes]
Justification: The paper does not have part that requires training. However, details on how to reproduce the plots are given Appendix G
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification: All plots contain error bars where applicable 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.
17

---

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: No specific requirements are needed regarding compute resources the experiments are only on small scale.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as 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 or failed experiments that didn't itdn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https//////errrppsccc////e itw.eeceeeiicccccieeeieeneeee
Answer: [Yes]
Justification:
The paper is conform, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
The main contributions of this work theoretical. However, reward learning in multi-agents can have a socictal impact as for example recovering a reward that is not exploitable, see Fig. and the introduction for discussion.
Guidelines:
18

---

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.
19

---

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.
20

---

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.
21

---

Contents of Appendix
This appendix provides supplementary material to support the main findings of the paper. First, we give an overview of the used notations, including some additional notations needed for the proofs the appendix. Then, we present the omitted analysis for the feasible reward set under a single equilibrium observation in Appendix C regularized Markov game setting in Appendix E Afterwards, Appendix [- we give the missing proofs for the identifiability section. Then, we give the details for our presented numerical validations and some additional experiments that show that MAIRL can be superior to BC. Finally, the appendix compiles list of technical results, along with their proofs, that are referenced throughout this work. For better overview we provide table contents.
We then present the complete proofs for key results for the
A Notation and Symbols
23
Related Work
25
Omitted analysis for Section
3
26
Sample Complexity analysis the Uniform Sampling algorithm
30
D Hardness result
34
Proofs of Section 3.2
36
Identifiability in multi-agent games?
46
Experimental evaluation
49
G. Numerical verifications for Nash and QRE equilibrium observations.
50
G.2 MAIRL vs. Behavior Cloning,
50
Technical Results
22

---

A Notation and Symbols
In this part of the appendix, we include notation used in the main paper and some additional notation used for the proofs in the appendix.
Notation
Description
Finite set
Rx
Sct of all functions mapping from X' to R
A
Sct of probability measures over
[n]
[1,...,
(2, ..)
(Pre)metric space
Hd
Hausdorff (pre)metric
g
Markov game without reward function (2,
n
Number of players
S
Finite state space
A
Action space for player Joint action space A A
A
a))
Transition model (probability of next state 8' given state and joint action a)
Discount factor Initial state distribution
P
x¹
Policy (strategy) for player i: A
Joint policy (T :..., x²) ( --/
(als))
Probability of joint action a under joint policy n in state s. 1[;=1 x² (a213)
II'
Set of policies for agent
joint policies
Discounted probability of visiting state-action pair (a, a) starting from under π Reward function for agent x A I- Joint reward function (R² R"))
(s,
Rmas: Ri maxd
Rmax
Maximum absolute reward across all agents, max;e[s] P maa Standard Markov game with reward Q-function for agent i under policy Value function for agent i under policy Nash Equilibrium policy
GUR
Qoun
VOUR(S)
π Nash
Set of Nash Equilibria for reward R
(illeess)) (s)
Value function for player in e--enrroyy regularized MG
Quluees (s.
Q- Q-function for player i in λ,-entropy regularized MG MAIRL problem definition
(G, Niasl)
(G, Noohi
Recovered MAIRL problem
Feasible reward set for single observed NE n Nash
A
Policy recovered from MAIRL problem
(())
Nash Imitation Gap for MAIRL
Feasible reward set for the set all NE Nash QRE equilibrium policies Average reward for player when player 2 plays (()s) Induced transition for player when player plays w: LveS w ((')s)
n², n".""
(s)
(=()'(s.a) a)
() (s)
Linearly separable reward for player
Amnn
Minimum probability bound for QRE policies Count of visits (s, s') up iteration h: Count visits (s. a, b) up to iteration
Na.s,a,b.s"))
(a(),
NA(s,a)
Count of player taking action in state s up to iteration k:
Na(s.b)
Count of player 2 taking action in state to iteration k Count of visits state up iteration &
NR(s)
Pa(s"ss,a.
Empirical estimate of transition probability at iteration k
Be(als)
Empirical estimate of policy at iteration & Empirical estimate policy at iteration k:
(b[8)
23

---

In this section, we introduce the additional notation needed for the matrix expression of the Q- function, the value function, and in particular, for an additional implicit condition for the feasible reward function (Theorem C.1 similar to the one derived in Lin et al. 2018 To achieve this we use similar notation from Lin et al. 2018), adjusted to this work. First, we introduce for every agent i [n]] the stacked reward R'. For every state $ E S the reward can seen matrix of dimension |44 x [[ |. Doing this for every state and stacking them, results in a vector R' R|S||AA, [A] is the dimension of the joint action space. We additionally introduce the operator π, which can [S] |S||A|] matrix, structured in the following way. First, we need to fix arbitrary order on the joint action space [[] in the same way as already done for stacking the Reward for every agent. Given the order, have that for lo E [|S]], the k-th row is given by
be written
D (k)) DA (R:).
where for j E [[A]]] we have
67(+)
0g...
0.
II क (a) b).
S
Therefore, the resulting matrix has in its first | columns diagonal matrix of size (S] (8] with the corresponding probabilities of playing the first joint action all possible states.
2 (ai
11)
(a1
0
0
0
n 1==1
n (a1 3)
0
I x (a1 |S)
The transition matrix P of Markov game also depends the joint actions, making the resulting transition matrix dimension |S||A| S. This allows us to write the value function as a column vector of dimension R| and the Q-value function as a vector, identically as the reward vector, of write:
dimension |S|| x 1. Therefore,
+ PVVI,, ViT TQ
24

---

B
Related Work
This work intersects with several fields of research, particularly Inverse Reinforcement Learning,
Multi-agent Inverse Reinforcement Learning. and Inverse (Algorithmic) Game Theory.
Theoretical Understanding of IRL. IRL was first introduced by Ng and Russell [000]. emphasizing
its ill-posed nature. Subsequent work tackled ambiguity via reformulations [Abbeel and Ng. 2004
Ziebart et al. 20088 |Ramachandran and Amir 2007 Ratliff et al., 2006a [evine et al. 2011]. To avoid the ambiguity in IRI,, recent research has addressed to characterize the set of feasible rewards instead of picking a single reward function. Theoretical efforts to characterize the feasible reward set were pioneered by Metelli et al.] [021]. The authors provide an explicit reward formulation, that shows that the reward depends on the expert policy and the transition dynamics. As in realistic scenarios it is not common to know the transition model and the expert policy, the authors provide an error propagation analysis on how estimation errors in these quantities transfer to the recovered reward. Additionally, they provide a uniform sampling algorithm with access to a generative model combined with a sample complexity analysis on how many samples are required to find suitable reward function from the set of feasible rewards, that also transferable to new environments. In [Lndder et al. [2022] the authors extend this to the finite horizon setting. Additionally, the authors provide the first algorithm that removes the assumption of a generative model and instead create exploration policies to mitigate the reward uncertainty dubbed active inverse reinforcement learning. Additionally, they provide a sample complexity analysis for the most general case and a problem-dependeee Further insights on the theoretical insights of IRL have been provided by [Metelli et al. 2023] The authors investigate different metrics for the IRL. problem, leading to a more nuanced analysis and the requirement of refined concentration inequalities. Additionally, they provide the first lower bound for IRL. addressing an open question that IRL is not harder than forward RL. The first offline algorithm for IRL combined with a sample complexity analysis has been provided in (Zhao et al.. 2024). The authors note limitations of so far introduced metrics in settings without a generative model. Additionally, the authors show that IRL is not harder than standard RL in the offline setting. The offline setting has also been considered in Lazzati et al. (2024b). The authors provide a new formulation of the feasible reward set, more suitable for the offline setting. They introduce two new efficient algorithms designed for the offline setting, overcoming the new introduced challenges as the data coverage cannot be controlled anymore. An investigation how IRL translates to large state spaces has been obtained in Lazzati et al. 2024aa]. The authors provide the negative result, that the feasible reward set cannot be learned efficiently in large state spaces without additional assumptions. Instead of the feasible reward set, they provide a new framework, rewards compatibility and an efficient algorithm for this setting.
variant.
While these works analyze distances to value functions and expert policies, applying them to Markov games remains challenging due to the need for equilibrium-based solutions. This implies that the standard objectives for IRL, namely value based gaps, cannot be applied in multi-agent settings. Additionally, we show that MAIRL introduces new challenges due to the multiplicity of equilibria.
Another line of works, considers the case of reward identifiability. In Cao et al. 2021 the authors give an explicit reward characterization in the setting of regularized MDPs. In particular, the authors note that the value function can be chosen arbitrarily for a given optimal policy and therefore identifiability is not possible by single expert policy. However, if one considers two MDPS with different transition dynamics and discount factors and the same optimal reward function, then identifiablity is possible if the MDPs are salue-distinguishabl.. Based on these observations, Rolland et al. [2022 derived explicit conditions what malue-distinguishabe identifiability problem as system of equations and derived rank conditions that need to be fulfilled to identify the rewards up to constants. Additionally, they provide insights for the case with unknown transition functions and transferability to new environments.
MDPs are. In particular, they rewrote the reward
In Kim et al. 2021] the authors study the type of MDPs under which reward identifiability is possible. Considering deterministic MDP with an entropy regularized objective, the authors provide necessary and sufficient conditions whether and MDP is identifiable. Additionally, building on these findings they provide efficient algorithms check if an MDP is identifiable.
In this work we address the question of identifiability the context of multi-agents. We show that is not possible to identify the reward function up constants without additional assumptions. Instead
25

---

it is only possible to obtain an average reward function or one poses additional structural assumptions on the underlying Markov game as e.g. linear separable rewards.
Multi-agent Inverse Reinforcement I Learning. The first extension of IRL. to multi-agent settings was introduced by Natarajan et al. (2000). focusing on a centralized controller in average reward
RL framework, but without addressing competitive settings requiring game-theoretic solutions. Lin al. [2044 extended this to Zero-Sum Markov games. introducing a Bayesian MAIRL framework based on observed Nash equilibria, later expanded by Lin et al. (2018) to incorporate various solution concepts, though without sample complexity bounds. Yu et al. [2019 extended Maximum Entropy IRL to multi-agent settings via the logistic best response equilibrium, focusing on recovering single reward function rather than analyzing the feasible reward set. More recently, Gootas al.) (2024) explored Inverse Multi-agent Learning with parameter-depender by assuming access to samples from the reward function. Fuu er al. (202T) approached MAIRI. by decomposing it into multiple single-agent IRI. tasks, applying utility-matching induced MDPs. Additionally, this work the first that notes that single Nash equilibrium observations can be limited. Instead of considering a single reward function, we formalize that that single equilibrium observations lead to an uninformative feasible reward set. Additionally, their approach does not address equilibrium multiplicity and lacks a sample complexity analysis. In a concurrent work, Liao et al. (2255 address regularization. They first analyze static (matrix) game under linear parametrization of the payoff matrix and derive a rank-condition on the feature kernel under which the reward parameters are uniquely identifiable. They then extend their framework to linear Markov games ceatoopy-egulaiizer zero-sum Markov decision processes) and propose algorithms with high-probabilig, finite-sample guarantees for recovering the feasible set of reward (and transition) parameters. Finally, [Tang et al.) (024) highlighted the inadequacy of value-based gaps in Multi-agent Imitation Learning, proposing regret as more suitable objective when observing Correlated Equilibrium experts. In this work, we consider the Multi-agent Inverse Reinforcement Learning framework and consider the Nash equilibrium well the QRE.
payoffs. simplifying the problem
IRI. algorithms on the
recovery in two-twwyer zero-sum games with entropy
Inverse (Algorithmic) Game Theory. There is significant overlap between Multi-agent Inverse Reinforcement Learning and inverse algorithmic game theory. Many works in this area apply game- theoretic solution concepts to rationalize the behavior of observed players in specific types of games KKllanaramaan and Umans 2008 2009). A related work is by Kuleshov and Schrijvers (2015), J, who algorithms for coarse correlated equilibria in succinct games, where the
developed polynomial-time structure of the game is known and noted that in cases where the game structure is unknown, the problem is NP-hard. Their theorems indicate that without additional assumptions or more specific settings, polynomial-tin
algorithms cannot be expected for inversely solving Nash equilibria. In a more recent work, [Wu et al. 2022] introduce bounded rationality, i.e. considering QRE as the observed behavior, in the context of Stackelberg Games. In particular, the authors show that QRE observations are more informative than Nash equilibrium observations. This means that bounded rationality helps to be more robust against an irrational opponent. Additionally, this makes possible to construct algorithms that have exponential dependencies on neither the number of leader actions nor the number of follower actions.
C Omitted analysis for Section 3
The first theorem serves as an extension of the two player version theorem by Lin et al. (2018) (see section 4.6 in Lin et al. (018)) to n-person games and general Nash equilibria. It makes use of the notation introduced in Appendix
Theorem C.1. Let G U R be n-person general-sum Markov game. A policy π is an NE strategy if and only if
Nash - (I-II Porhh
Nash M - 2 0.
with the meaning that without (s,a) symbols matrix notation and ît is the policy with - - Nash and n² plays action with probubility 1.
Proof. In the first step of the proof we state the theorem for the case where n with the use of the definition of an NE. We only write the condition for agent I to understand the structure. For every
26

---

action a' E and every state S it must hold true that:
Σ π ,2.Nasi (a² (s, Σ 6REA4
n 2.Nas (a² 8) Σ P(d' 8, a a (0) V
V. Nart
(8)
If we now want to generalize this to a n-pprron Markov game, we get that for every player i E [n]] every action a' and every state E it must hold true that:
Σ
i.Nash
(a- Rs,)
'EA
E P(s' ss a) (s) Va Nash (s)
+ y
EEA-
We can rewrite this equation in terms the Q-function and get
Σ (a-
s)Q Nush
(s, Nawhh (8).
(5)
Now want to rewrite the equation for all states simultameously. Therefore recall the notation We have that
introduced in Appendix A
Q
+ PVV." Vio = TQ"
Rewriting this equation for the Nash Policy π Nash gives us
Qia -1- Pr Nash)-11 R
Plugging in the derived equations in (5) using matrix notation for all states & E S simultaneously and additionally denote the joint policy, where agent plays action a' with probability and the other agents execute their Nash strategy π N,Nash as ग., we get
( π Nash) - PT Nash - R <.
The next lemma restates the condition by directly using the expectation of the advantage function with respect to the policy.
function Lemma C.2 (Feasible Reward Set Implicit). A reward function R = (R² ..... R²) ) is feasible if and only if for a Nash policy π Nash for every agent i E [n] and all (s,a') E S x A', it holds true that:
Σ
π Nash
= 0. if Nash (a* Nwb (s, (s,a', ()) Nuu
|s) > 0, a supp(1 i.Nash (-1s))
FEA
Σ
π -.Nhhash (a
(s,at (s)ATR S 0, Nash (s) a supp(T Supp(T-++Nashh (.Nash (- |s)).
Nach
Proof. As we know that a' E supp(r (. 8)) for both cases, we get for all agents i E [n] and
all actions Nash E A' that fulfill I iash (a Nash
8) > 0, that Ea IT i,Nash
Q)ii Nush (s, Noahaa)))
Ea-ie - Nash (a
s) s)Qi Nauls (s, a'aaa)) Additionally,
we have that for all NNNsh with T'.Nash (a Nash
0 that Ea a i,Nash (a
sQQ
Nash af -1) Viih (s).
In the following we will constrain to the case of pure NE, therefore holds true, that for some a- E -t, have It(a =) E S.
Lemma C.3. Let E (n] be arbitrary agent. Then the Q-function of player satisfies the optimality conditions of Lemma C.2 for pure Nash equilibrium if and only if for every (8, E there exists a function A S and V$ E R such that:
Q00k Norh
Naoh
(s,a)
Nuwk 0s)= 1[ (a (1s)=1} + (s(s)
(a
27

---

Proof. First we assume that the Q-function can be expressed as
QoUR
Ni (8,
As, a) Ni..Na (a)) (1r S.Nooiff =)=1) + Vs()..
We note that
Nashs
(s)
Σ n Nacbbaa $)Q (s,a)
Nash
GUR
EEA
Σ BEA
n Nash
(a 8) (-A'(s, a) (1i (x aNuaiia 116)=13 + Vi())
Vsss,
where the last equality follows from the fact, that if π Nash |s) >> 0, then (aih [=]{=)=)) and vice versa. Additionally, (*() is independent
and as the sum is over the joint action space it holds true that Σ A π Nash (a s) = We now have consider two cases. The first one 1 (a 1=)== = 0 and 1 {x- N.Nsh (a- [1))=1} = 1. Then it holds true that
Σ π Nash (al ( Q (s, a) ('()) = aEA
Mash
Vi. Nash
GUR
The second case is if 1 (a = 1 and 1(x a.Naslia =|a)=1} 1 for one action ä-i with --aā 8) as we assumed it is a pure NE. Then it holds true that
Σ π N.Nash (a- SORR
Nash (s,a'a-t)
aEA
= QoER (s, (s,
a) (a' (- (po + (s)
<V'(s) Vii Nooh
BUR
where we used the fact that (s' a) 5. If we now assume that the conditions of Lemma C.2 hold, we can set for every (s,a) E S A
(s) vr and A' a)
Nusk.
Nusla Namh
Nash
OUR
(s) QGuR
(s,
Lemma C.4 (Feasible Reward Set Explicit). A reward function R is feasible if and only if. for
each agent E [r]]. there exist function A' E SxS and a function V E H$ such that for all (s,a) E S x A, the following holds:
Rt -A'(s, (xi:Nun (xr Na (a=)))=)))==)) + Vi()) 7
p(s as))
Naah (s, = R' P(s'
Proof. Remembering that express the fuunctio as QOUR
8, a.a) Vi (s') and applying Lemma C.3 to express the Q-function for NE policy, we can conclude
OUR
OUR
R'(s,a) a) QOUR (s. - x P(s' s, VoiR Naoh (5')
-s ( (-- iNoobio Tacaaaaolpal 11)) + (i(ss) ((6)--7) >E (s)))
Theorem C.5 (Error Propagation). Let (G, πI Nush) and (g, Nashy be the true and the recovered MAIRL problem. Then, every agent i E [n] and any R; E Rr there exists R, E Rg such that:
a)( - Rs(s < (((sa))) 1 + Σ ('s)))((( s,a) - P(s' ssa)),
where E = Nast, (a" (s 0) N,Nash (a () 0}} and È = ((ft |s)
0} (iabb 5) = 1}}.
28

---

Proof. From the explicit expression of feasible reward C.4 we know that we can write the reward function of any agent E [nx] as
(s, = As, a)
(a 110)=1) + V'(ss - 7 Σ P(s (s)))
(6)
(s, - (
(a))))))) ( (o
(a)))))--))))) + +V((s) - E 1
88 ())
As pointed out in Metelli et al. [023], the rewards (s. a) do not have to be bounded by the same Rt (s,a) a) and therefore also not by the same Rmaxx. To fix this issue the authors point out, that the reward needs to be rescaled such that the recovered feasible reward set is bounded by the same value. In our case we have to be a bit more careful with the choice of the scaling, as we did not assume that the reward is bounded by 1. As we proof the existence of such reward function, we can choose (s) (s) for every E S and (s, a) (s, a) for every (8, a) E S x A, which results in reward
R a) (s, fst (a 1 (a Nab (a (1-)))==1 + (s)) + r Σ P(s' (s").
Now we need to rescale the reward with Rmaax + (s((s, where
e'(s, a) = A' a) (1 (a+)))== 0)= 1 Nooth - -1 (ct)) 1 1(x +7 EPP'' 1 8, - ())
such that it remains bounded by Rmaxx we receive
Rmax
(s, = (s, a) Rmax + (s a)l
Rmax
A'' a) Rmax + a))
1 (a) Nanh (at)))))) (e-n 1
Rmax (s)
Rmax Vi(s)
+ Σ P(s' 18 a) Rmax + (et a)
Raux + (s)
It then follows that:
Rmax R' (',, a)
(s, a) - it' (s, a)l = (s)
Rmax + 1st a)]
Riax
R Rmax + (s)
R' (s, a)
Rmax + +s, a)
Rmax
Rmax
[1 (s, a) - -s,'(s + (s, a)
< Rmax + +le"(s, a)
1t's (s a)
Rmax
RIDa
Rmax (I='(s, a)l + (e a))
5 Rmax + (s)
(le((5, a)l + +1:l++1''ss -s="(s,a))) <
Rmax
(ss, (1x-1g) + Σ (P(s' ss, P(s') s. (s)))
Lemma C.6. Let G U R be a n-person general-sum Markov game, P, P.P two transition probabilities and R, R two reward functions, such that tt is a Nash equilibrium strategy in & U R.. Then, it holds true that:
V V' ( - Vi
Σ
w * (R' -f) + (P('' s,a) - (a'') 1 (.)))(((())))
8.
Σ
wh (R''s,,)) (s, a) + E(P('' (s P(s' s,a))ia(s")))
+
29

---

Algorithm MAIRL Uniform Sampling Algorithm with Generative Model
Require: Significance & E (0, 1), target accuracy e
1: Initialize k 0, Eg +- +000
2: while > é do
3: Generate one sample for each (s, a) E x A
4: Update Ps as described in (12)
5: Update accuracy En - 1-7 (..)) (s,
6: end while
where π (T', a-).
Proof.
Vi V'(T' Vi
= - x-) ) x + -( - - -
( V' # + (* x - V'
Σ wh (1 - (s, + Σ (P(s' s,,)) - P(s s, s.a))
8,a
+
Σ (R - (s, + Σ (P(s') s.a) - P(s' a.))))\i* (s))) 8.a
where we used that ('(*, vi म カ) S as a NE policy and the last equation we applied H.2
C.1 Sample Complexity analysis of the Uniform Sampling algorithm
In this section we give the proofs of the sample complexity for Uniform Sampling algorithm and lemmas derived in Theorem C.12 and Lemma The structure is as follows:
1. We first state the Uniform Sampling algorithm.
2. Then, we state the optimality criterion based on the Nash Imitation Gap.
3. Next, we present Good Event Lemma bounds, using Hoeffding's inequality.
4. We define the reward uncertainty.
5. Then, we state theorem that provides conditions conditions-ddpendeen on the derived confidence bounds-under which the optimality criterion holds.
6. Finally, consolidate all results to prove the sample complexity bound for the uniform sampling algorithm.
The algorithm, that evaluating in this section is given in Algorithm !
Now, we can restate the optimality criterion of the algorithm.
Definition C.7 (Optimality Criterion). Let Nowh be the exact feasible set and Naah the recovered feasible set after sampling N 2 from (G, π Nashh). We consider an algorithm to be (e, 8, N))orrect after observing N samples if it holds with probability of at least 1 - 8:
sup RE RER Neaayy Rl R NaNahy
inf
max max Voun(T') A --) Vauua x-) S 1E(n] xtem
sup
inf
max max V (oUR(T *-1) VauR ( # #-) Se se
RER Neshi)
RER RE Nashy
8E|n] miem
We are now introducing the empirical estimator for the transition dynamic. For each iteration
I E [K], let næ a, s') = Σt (()= denote the count of visits to the triplet (s, a'))) S Ax S, and let (s(s,a) = =vves (s, as denote the count of visits to the state-action pair (s, a).
30

---

It is important to note the distinction here: the count of actions must be done separately for each agent, whereas the count of state visits needs to be done for any one of the agents. The cumulative count over all iterations At E [K] can then be written as:
(s)), Ens(s,a, JE(M]
The cumulative state visit count are given by:
(i(s,a)=
(n Wi
jE[K]
After introducing the empirical counts, now state the empirical estimators for the transition model:
Nels.a.d)) Ne(a.a)
if (x >
(& 88,a)
(8)
otherwise
Next, state the lemma that derives the good event by applying Hoeffding's inequality. As the Nash equilibrium is assumed to be a pure one, meaning it is deterministic for every s S, we only have to define the good event for the transition probability and for the experts policy require, that for each agent we have seen each state only once.
Lemma C.8 (Good Event), Let k be the number of iterations and π Nash be the stochastic expert policy. Furthermore let at Nash and P be the empirical estimates of the transition probability after k iterations as defined Eq. (8) respectively. Then for e (0, 1), define the good event as the event such that the following inequalities hold simultaneously for all (s,a) E x A and k 2 1:
Σ (P(8' ss,)) PP(s' 8. (s))))((s')
Rmax
84, a) N (s,a)
< 1->
Σ (P(5') ss,a) PM(s'' s.a))
Rmax
81y(s,a)
No (s,a)
where we introduced (x(8,)) = :loog [2| IA')(N (saa1))
Proof. We start with bound the two last equations. Therefore we define (x(8 a) =
log I2SIL IA' (NT((a)) and additionally we denote ANelea) = Buuz
24((s.)) NJ NT(aa)
Now we de-
fine the set
otrans
Σ (P(s' s, P(s'
ssa))\i 1 BNa(oa)
31

---

Then we get for V with probability of 1 - 8:
P (Etans)C)
P
3k (,,
ES A: Σ
(((s s,a) - Ps((s
s s, -
vi(5') > B (N)((
Σ
P
3k M 1: Σ
(P(' s,a) Pa(ss) s,a)) v'(s) (sslaa)
(a.0)ESAA
Σ (A.A)
P
3m 2 0: Σ
(P s,a) - Pa(s' s.a)) v-(6)/ > (Na(sa)(s,2)
IAE
8 (N. m0 7)2
2 2xxp
4mry² 122 Rax
(s.))SSAA m20
8
Σ
G|STTT (m+))
(s.))Sxx x A m220 20
5
6
where (a) uses a union bound over the state and joint-action space, (b) uses that we only consider the m-times, where we updated the estimated transition model and (c) uses an union bound over the update times m and an application of Hoeffding's 's inequality combined with the fact that we can bound the value function, i.e. (*(s") Renax for every s' S.
Following, we present the reward uncertainty metric, which allows demonstrate that the difference between the recovered reward function and the true reward function is bounded.
Definition C.9 (Reward Uncertainty). Let be the number iterations. Then the reward uncertainty after l iterations for any (s, S A is defined
4y 1-7
(V
84 (5, a)
Cn (8, a)
No. (s,
Theorem C.10. Let the reward uncertainty be defined as in C.9 any (s,a) E S x A that:
Under the good event it holds for
as, ( (s.a)) S Cs(s.a).
Proof. The theorem is an application of the error propagation Theorem C,5 followed by Lemma
(.8 C.8
[s, a) fs, a)l s 2
A' As - 1g + Σ (P s, a) P(s') s, asa)
4 Rmax
21 (s, a) Nit (s, a)
1-7
(
Rmaxx
(s,
1-7
(V
N (s,
= (s,
Corollary C.11. Let be the number of iterations for any allocation of the samples over the state- action space S x A. Furthermore, let R Nuay be the true feasible set and R Nu.sN the recovered one. Then the optimality criterion 3.3 holds true, if
max Cs (s, a) S 2 (sm)
32

---

Proof. We complete the proof for the first case of the optimality criterion, the second one follows analogously.
sup
inf
max max
sE(n] m'lll (VGuR(T', # #ー (
(e Nashy ER Nanao
(0)
sup
inf
max
ΣE
The (T (r, a) + - 1 as)
Re (G Masiy
8,a
E(p- [(P- p)(s' 8, 8.a)) (11111(111)
Σ W
(*(s,a) - R
IA3 IN
sup
inf
max
Σ
W
- a) +7 E(p P)(6' 88 a.)i (o)
RE ( Nash
i Nassh
6,
8.8
sup R R
inf R (9. Naahy
max 2 (,
Σ
Wh 3,a
A'(s,a) 1g
1el + 2 Σ (P. P)(s' s. (.))
(c, Nach,
(1)
max Cx a) S. (sa)
where in (a) we applied C.6. in (b) we used the fact that + b < 2 max mn, b) and denoted the corresponding policy as ग.; in (C) we used the error propagation Theorem C.3 and in (d) we used
C. 10
We can combine the derived results to now state the main theorem regarding the sample complexity of allocating the samples uniformly over the state action space.
Theorem C.12 (Sample Complexity of Uniform Sampling MAIRL). Allocating the samples uni- formly (see Algorithm|] [ over the state and (joint-) action space stops with a probability of at least 1 - å after iteration and satisfies the optimality criterion (seel 3.3 where the sample complexity is
of order
2 2 max
|S 144 72)
δ
Proof. We know from
C.11 that we need
Ca < Ek
max (a,a)
2
2 R max
81x (s, N (8, a)
V
(1 7)2 (0.a)
This is satisfied if
47 Rina
814(8,a)
(1 7)2 //
No (s,a)
To achieve the first condition, we get
a)) 2 Rmax
8
264 Rmax log
125 II.
(sN)
(8,
(1 -1-)447 7 (8,
a)
Ek
(1
8
Applying Lemma B.8 by Metelli al. 2021 we get that
256 R2 Rax log
128 R2
12 II. |A'
(g(s, <
(1 [
(1 - (1-7)
8
33

---

At each iteration we are allocating the samples uniformly over S x A and recalling that Ts,a III [ a) therefore we get
256 1 R maax log T
128 R2 (1 (1->)
12
Now we only have to achieve that we have seen each state at least once, to correctly estimate the policies for every agent. Therefore, we force that Ns)s) 1. As here need to allocate samples uniformly over the state space only but for every agent separately and recalling that T. = (s), we get
Ts I n||1
With Ta.a + Ta we get total
128 S II: 1
R
64a7² 2 R22 imax
S2 11: |A
max log
+ n|S]..
7)
This is exactly of order
2 R2
||] -|IT 1A4
max
(1 -2)
D Hardness result
In this section, want quantify the non-expressiveness of the recovered feasible reward set under a single NE observation. Therefore, we give the following hardness result. The idea is that the observed NE only covers a part of the environment and the definition of NE only ensures robustness against single agent deviations.
Theorem D.1. Let us consider any IRL algorithm Algin that chooses R RGG that is not constant reward, i.e. R + C for C I-aaxx Rmax]. Furthermore consider a forward MARL algorithm AlgMARL that guarantees learning policy it E I[Nahh Then, there exists Markov game, such that even if tे IINahh and R. Rx holds true that E(Tx) is of order (1-7)) (1-7)-1.
Proof. We consider the following 2-player general-sum Markov game G U R. Let S {so, 81, 82, $3, 83,84) 84) with A A = ={a1, a2). Furthermore, let the transition dynamics be given
81 if (a141),
P(. So. a)
82 a {(a10)), (aza:)}.
=
if (az, 02).
In states $1, $2, $3 the transition is defined to stay in the respective state with probability 1. Further- more, let the true reward of the Markov game be given by
if a a1)a1).
2 if (aja)),
R (s0, a)
a E (a1az), (a2a1)), if a (a2, 0z).
R2 a)
0 if a E {(1122), (aza1)},
3 if 02).
For the other states we have that R(81, a) = R(*3. a) = 1 E A and R(s2, a) 0'va E A. This indicates that the Markov game has two pure NE strategies nt Nashi with (a, su) = Tz(a1 88) =
1 and Nash, 2 with क (a2 so) = =2 8o)
and any distribution in states 81, 82, 83. Note that this game can be seen as Markov game extension of the Normal Form Game Battle of the Saxes that
rewards the NE strategies in subsequent states. An illustration of this game can be found Fig. 2
Let us assume that the observed Nash equilibrium is π Nash, 1. Next, apply any AlgiRI that returns
34

---

R E R Nawa Note, that the Nash equilibrium for the state So and will be recovered perfectly and potential is given by
if (d1a1),
2
if a (α1a1).
1 if (0102),
2 if a (0102),
R! (so, a)
(S a)
if (Q2a1),
if (0201).
2 if a = (22, 02).
2 if a (02, a2),
Additionally, the rewards R(s1, a) 1, RR,,R(s3, a) - A and R(s2, a) 1 Va A. Then, note that indeed NE under ft and also in the underlying environment R.
However, in the recovered Markov game & U R there exists another pure equilibrium solutions π Nash π Nash, & Nash. where for π Nashi 3 we have TiJ (a1 sq) = and Tī(a2 sn) and Nash, 4 is given by (a so) and π (a) 80) = 1.
If one now applies forward MARL algorithm that guarantees convergence any (pure) NE defined by n,, i.c. satisfying
&
max V カ-) V = 0.
(E(1.2) eill
Then, assuming that ग in the true Markov game it holds true that
EALMMARI [En(F)] (1 P( Nash 1)
This holds true because for म Nash 1. have that EirrNasl) original Markov game. However for л Nash, and Nash 4 which both go state 82 Best response would either be to go $1 or 83 resulting in a exploitability for for all future states. Assuming that the algorithm returns NE uniformly across the set of NE, get
0 as this is also NE in the
1
BAlEMARI [En(#)]
P( + Nash 1)
(1 7)
3(1 - 7)
This is exactly of the order (1 - 7) and completes the proof.
Next, we want to provide further intuition on this phenomenon by giving the Normal Form Game that is the origin the considered Markov game instance.
Example D.I. We consider the general form of coordination game as a Normal Form Game (NFG):
Player 2: Stag
Player 2: Hare
Player 1: Stag
(A,
(C, B)
Player 1: Hare
(B,C)
(D,
In general coordination games, we have that D > B and D - < A+ observe the pure Nash equilibrium strategy (Stag, Stag). The feasible reward set R then contains all rewards that satisfy:
C. Assume we
R' (Stag, Stag) 2 R' Stag) ^ R² RStag, Stag) 2 R2 R²t(attg, Hare),
while for all other reward values, any rewards are feasible, i.c., At (Stag, Hare), R² (Hare, Hare) e BA A2
This flexibility in reward specification allows for undesirable scenarios (see Example D.I such as:
Changing the nature of the game: The game can transform into an anti-coordination variant with additional pure Nash equilibria not present in the original game.
Losing equilibria: Rewards can be defined so that "Stag" becomes the unique dominant strategy for player 1.
The following two examples of feasible rewards if observing the NE expert (Stag, Stag):
35

---

Player 2: Stag
Player 2: Hare
Player I: Stag
(2, 2)
(0.0) 0)
Player 1: Hare
(0.0)
(-1,- -1)
Player 2: Stag
Player 2: Hare
Player 1: Stag
(2
12
Player 1: Hare
(2, 11)
10, 10)
This example highlights that even in simple NFGs, the feasible reward set encompasses too many reward functions, including those that significantly alter the game's equilibria. This contrasts with the single-agent IRL setting, where the feasible reward set contains degenerate rewards like constant oncs, but due to the fact that all equilibria obtain the same value, preserving the mcaning of the environment. In the multi-agent setting, this second source of ambiguity allows for strategic behavior entirely absent in the original game, which is highly undesirable the goal is to recover meaningful reward functions for transfer to new environments.
E Proofs of Section 3.2
In this section, we will give the missing proofs of Section 3.2 We start by giving again the definition of feasible reward function for an observed pair of expert policies. In particular, if the observed expert policy is a QRE equilibrium.
Definition E.1 (Feasible Reward Set (regularized)). A reward function R is feasible for an MAIRL problem (9, (j²", (p=,ve) v*)) if and only the observed policy pair forms an equilibrium in G U R.
Additionally, we will restate Definition 3.3 in terms of regularized games.
Definition E.2 (Regularized Optimality Criterion). Let R ((G.(u","*") be the exact feasible set and R := (G(((_.00)) the recovered feasible set after observing N 2 0 samples from the underlying MAIRL problem (
π Nashi). We consider an algorithm to be (s, N) coorrec after observing N samples if with probability of at least 1 - ô it holds:
sup inf max (max (1, 8) V2 (i, D), max (2 v) - (2 8)) S
RER ReR
sup inf max(max V (v. 2) (2, (2, D), V2(A,0 min v)( se RER RER
where we used μxx Mi to denote entropy regularized policies.
This optimality criterion can be seen as the soft version of the Nash Imitation Gap(Definition 3.2 Next, note that a policy is considered optimal, i.c. QRE equilibrium, if the policies satisfy
exp ( EwER v* (6' |s) (s,aa
(a () Ewed exp (1 EvEE (b s)Q; (s, (s.
(9)
exp (1 Eaveati (s,;,
n" (b 8) Eveaexp exp Enren (s) (s, 1b)
(10)
Similarly to the analysis done in the single-agen setting the goal to derive an explicit characteriza- tion of the reward function [Metelli et al.) 2023 Lindner et al.) 2022, Metelli et al. 2023 Zhao et al.) 2024 Cao et al. 2021]. The idea is to rewrite the formulation of the optimal policy terms of the reward function by using the definition of the value function and the Q-function. We will present the analysis only for player superscript for the player.
holds analogously for player 2. For a better readability we drop the
Lemma E.3 (Feasible Explicit (regularized)). A reward function R for the regularized Markov game i feusible if and only if there exists V E R and [B] - many functions R'' E I [mRmax Rmax) S B
such that for all (s, a, b) it holds that
R(s,a. b)
(Xlog(u"(e (a s)) V(s) ~iP Ever (1 [))((/ (.).V)V(())) -o {))((,
36

---

Proof. First, assume that the reward function R is feasible. By definition, this implies that μ is an optimal policy for agent under when agent 2 plays v². Let (s) be the corresponding unique regropy-re optimal value function for agent 1. The optimal policy f (a s) (see Eq. (9) is given by
cxp ( EvEB v (V s)Q2(s,
p² (a (a Ed'EA exp (1 Eves v' (b' (s)
Recognizing that the denominator relates to the soft value function Vi((s) Alog Eaed exp ( Eveg (
write
(
Σ WBEB
v' s){{(s, -)0
(" s) exp
Using the definition of the Q-function, Q7 a, b) = R(s, a, + Eves P(d' 7 we substitute this into the expression for μ p" {1| s))
(8,0,))((()))
(a (s)
-cxp (2 (X
( R)) +7 1v'(b's)) P(s (1
WEB
MEB
s'ES
Taking the logarithm and rearranging terms yields
EMeB 2" s)),(s, a, Alog(u"(a 8)) (s) - EveR (8)
Evcs P(s') (V
Let Kv; (s, a) denote the right-hand side the equation above. Then, for any specific action such that (b > we can express R(s, a, b) as
R(s, a) (0(bl
1
Kv; Kv, (s
E v2(b' (()(1s)((s,.bb)) VEBI(D)
This matches the form specified in the lemma, where V(s) is taken as (s), and the [B|-1 functions R' correspond to the components R(s, a, b') for b' & b from the original feasible reward R.
For the opposing direction, assume there exists an arbitrary function V E RR and reward function R (composed of [B] 1 given functions (s. a, b') for 8' * that are within [-Rmax: Rmax], and the remaining component R(s, a, b) defined by the formula) such that for all (s, a, b) it holds that
R(s, b) v*bb(s)
1
Alog(a 8)) V(()) - Σ
Σ 8'ES DEEB
Σ 00 1 R(s,0))))
(b)
This structural definition implics that the expected reward for agent 1, R² (s,a) = EVER (B' R(s, a, b'), satisfies
R" (s,a) = Alog(H I 5)) + V(8) -
Σ> (0' s) s,,,))
(11)
SESUEB
Let p (s' s, = VV' s))((s agent I's perspective. Then (11) becomes R" (s, a) Alog(p" s)) V(s) 1 Eves P p (s'). We now show that R is feasible by demonstrating that V(s) is the value function of policy jº" for agent (given agent plays v²) and that μr" is the optimal policy.
s, b)) be the expected transition probability from
First, let Vu" (s) be the value function for agent when it follows policy μ¹ and agent 2 follows v*, with rewards R(s, a, b). The Bellman equation for Vu (s) given by
V# (s) = Σ (al(s)) (s. +y Σ pd (s'ls,a)V* (5') -A μ¹ (als))
aEA
#'ES
37

---

Substituting the expression for R (s, a) from (II:
([ [Alostata +))+ + V(s) - Σ
Va (s)= = Σ (als)
pm
(s' (s'I (111)))((s))
aEA
rES
Σ p (515s,a)V (d)g=llgx""dh)
+y
YES
Σ (als) aEA
E (s' +7 Σ p" (611)))))))
s'ES
s'ES
Since EoEa 1 (a|s) = 1, we have
vc (s) = V(s) + (alss)) (5 ( (8)--((s)).
REA
s'ES
Eves P (8' s, s,))g(s)) This equation, g YPuu' p , 9. where Par - is the Bellman operator for policy evaluation, implies that g()) 0 is the unique solution since 7 E [0, 1) ensures Prr.u- is a contraction. Thus, VF (s) Vss) for all s E S.
getg(s) = Vu (s) (s)- Then
ECEA (als)
Next, we show that μ² (als) is the entropy regulai-re optimal policy for agent 1. The optimal policy, where E (s, a) is the expected Q-value =g((s,))
r (als), is given by x (als) exp (x F (s.a)).
using the optimal value function V(s):
Fe (0, = R²
R" (s. +7 Σ
p" (1)s,)a)
e'ES
Substituting the expression for R² (s, a) from III:
E Alog(u [ (s) + Vs)) - Σ pd (o +7 s'ES
Pd
.'ES
Rewriting this expression gives exactly the form of an optimal policy in the entropy regularized Markov game. Since je" (a|s) is the optimal policy for agent under the reward R (when agent plays v²), the reward function R is feasible. This completes the proof.
In the following, we want to investigate how an error in estimating the expert policy pair and the transition function translates to the recovered reward function. Note that compared the single-agem agent case it is required to estimate the policy of opponent accurately as well.
The next lemma is of great importance, derive the error propagation. It states how estimating the induced transition probability is related to the joint transition probability.
Lemma E.4. Let V S ++ R be a function. Furthermore, let Pa be the induced transition probability and Pu the estimated one of an underlying Markov game with transition dynamic P. With out loss of generality, assume that we are fixing the policy of agent 2, i.e. Then it holds true, that
( (8,88((())) - IPO 1 as))
max Ev(s') (P(s s, P(s' 1 (s,a,b))
(P(6))((())))))
38

---

Proof.
Σ (' as)) - P s.a)V(s))
ubbl ()))))(( (,,,
ΣΣ ulb 8) P('
BEB
BEB
max(v(b] s), s)) Σ P(s' (s,,,)V((s))
Σ P(s (,,(ls,a.))V(ss))
BEB
Σ P(s'|s,..b)V(() Σ P(s' I s.a,b)(((s)
max
( (s,,b) P(s' P(s'1s,a,b) ss,,,b))
max
With the introduced Lemma, we can now introduce an error propagation theorem. The idea that we use the explicit reward function from Lemma E.3 and bound the individual terms of the true underlying MAIRL problem and the estimated one.
Theorem E.5 (Error propagation). Let the MAIRL problem be given by (G, (,", ,²)) for Markov game and let (G, (fr, 80) be another MAIRL problem. Then, we have that
2
[[(s, a. b)
A| Al (a (s log ůi (a s)]
(* (b) s)
+ 7 max
v(s))(ss s, P(s' b)l + RmaxTTV( D)
Proof. In the first step, we use the derived explicit form of the reward derived in Lemma E.3
1 a(s,a,b) [ (bl s) [Alog(i (a s)) + (s)
Σ Σ (b' P) ssa,)))((s'' - [)'((1s)))s
1s))((
As pointed out in Metelli et al. 2023), the rewards i(ss, a, b) do not have to be bounded by the same Rmux as R(s, a, b)... To fix this issue the authors point out, that the reward needs to be rescaled such that the recovered feasible reward set is bounded by the same value. In our case we have to be bit more careful with the choice of the scaling, as we did not assume that the reward is bounded by 1. As proof the existence of such reward function, R(s, a, b') R(s, a, b' + for every (s, a, S x Ax B, which results in rewards R(s,a, a, = Alog(A (a + - (* | P) s,a, - Evses (6 s)R(s, a,
choose V(s) V(s) for every S and
(b s)
Now we need to rescale the reward with Rmax + lee (s, a, b) respectively,
E(s, a, b)
Alog(a s) + ((s) - Ev Eveg s) s,a,) - (R), a,
(²(b] 8)
s)) (19) 2' (b s) s,0, Ev 10 5) s) (+bb(s) s)
such that it remains bounded by Rmaxx we receive R(s, b) R((, b) Rmaae Manns+lee [66
Rmaa
39

---

It then follows that:
Ranax R(s, 0,
R[ss, a. a(s, |R(s, b)
Rmax + (e(s,,,b))
Rmax
Rmax
+ beb( R(s, a, b) - R(s, ( a,
- Rmax + +I((s, a,
Rmax
Rmax
[R( R(s, (a..a,)l= c(s,a, b) R(s, a(s.a,b))
$ Rmax + +E(ss, a, b)
Rmax
Rmax
1 Rmax + +|E(s,a, a. b)l (lE(s, a, b) + al((s,,,b))
Raaxx (1s(s,a,b)] b)] (s(s,a,b))
Rmax
= 2) a, b)l
In the next step, we bound the (e(s, b)]
18(8, b)]
Alog(a 18)+ + ((s) -E Ever " (K) 8, Eves v (V) R))
(*(b] S)
- (l)) D' (V P(s (8, Ev 00 | {
(*bb)s) s)
(bl s)0*(bl s) (Al (al | 8) log (a s)
(u(b' s)P(s' s, D' 106b' (3))((..,))))((
Σ R(s, b') -) (0(b)] -b)))( (b((b))))) 8))
1 (b(b) (b)()
(A 8) log (a s)
Σ
-Ps/aaa,)))-ss.,,) +
(6 s))
+7
max
WEB
(88)
(A 8) - log log (a s)]
"*(b (b)= 8)
+7 max
Σ
P(s' ss,,,') P(s,a, Rmax
Σ (1=(6'1 (6) s))1
MEB
8/40
v² (b (b)* s) (Al (Allog (a| 8) (a |s]
E (, - P(s, (3) + Rmax ΣTV(E" 83)
+y
max
WEB
brbbb
where we used Lemma E.4 for (i), then the assumption that R(s, a, b) is bounded by Rmax in (ii)
and last, we added |r* s) (b s)] to obtain the definition of the total variation with the triangle inequality.
We now again, want to use the empirical estimators do a sample complexity analysis. The part of the transition probability can be obtained similar to the case of the pure NE, while for the policy
40

---

need to bound with high probability
[og(HH (a s)) log(A" s))l, log(v"(a s)) log(E" (a (s)]
Let us first introduce the assumption, also common in single-agent IRL, that the lowest probability of an action taken from the expert is bounded away from zero by some constant.
Assumption E.6. Let μt, v² be the QRE equilibrium expert policies. Then assume that
min (4' ac A
2 A min-
Now we are introducing the empirical estimators, used for recovering the MAIRL problem.
For both estimation tasks, the expert policies and the transition probability, we employ empirical estimators. For each iteration & [K] let ne a, b, s') E dr.e)) denote the count of visits to the triplet (s, a, b, s') ) S (Ax B) x S, and let (s, E Ese M b, s') denote the count of visits to the state-action pair (s, a). Additionally, we introduce ms(s,a) Σ (=s.a) and n b) Dt= (x.,6))((s.)) the count of times action and respectively b was sampled in state S for each agent and ny (s) EmEA (s a) as the count of visits to state s for any agent.
It is important to note the distinction here: the count of actions must be done separately for each agent, whereas the count state visits needs to be done for both of the agents.
The cumulative count of actions for each agent and the cumulative state visit count are given by:
(s)
Σ a) N(s) jE(K]
Σ (s).
JE(K]
After introducing the empirical counts, we can now state the empirical estimators for the transition model and the expert's policy:
Na(x.a.b.'
if (a
Pa (8,,,)
N2(a,a,b]
(12)
otherwise
Na(a.))
if (s(s)>
imc(a
8)
Ne(e)
(13)
otherwise.
[AT
Ne(a.b)
if Na(s)
D& |s)
Nx(s)
(14)
otherwise.
[B]
Next, we state the lemma that derives the good event. Note that here we prove something stronger regarding the transition model, i.c. that the good event holds for all s, a, b, therefore also for maxses
Lemma E.7 (Good Event Regularized Games). Let k be the number of iterations and (p") v²) be
the QRE expert policies. Furthermore let (js, 0) and P be the empirical extimates of the Nash expert and the transition probability after io iterations as defined Eq. {13) and Eq. (12) respectively. Then for 8 e (0, 1), define the good event & as the event such that the following inequalities hold
41

---

simultaneousl for all (s) E SSx x B and k 2 1, which holds with probability at least 8:
2 (og(10)S||AA (s))2/8)
[lo](u(a s)) log(A(() |s)]] -
min
Ng (s)
Σ (P(s bs,, |, s,a,,))VV((' 1-> V
Rmax
81x(s, a,
No (s,
max
(l, a, b)
Σ (P(s') ss, - Pa(s') a b)))((())))
- 1 7
No (s, a, b)
2|13| log 10 ( (8))) (8))3/8)
[b () 0b6
N (s)
BEB
log (10 BB] [N (s))2/5
D(b s)v(b]
A
N (s)
min
where we introduced (e(8, a, == log [0|S||A|| BI,N, (s.a,81)²
Proof. We start the proof by defining the good event for the transition model, which proceeds in similar way as already seen in Lemma We start with bound of the transition dynamics. Note that here we prove something stronger, that the good event holds for all s, a, therefore also for
m. Therefore we define as, a, b) == log [3]|S|||||B][ (s.aa))))) (sa.,))² )
and additionally denote
(Na(s,a,))
RBmax I-7
2la(s,a.b) Now we define the set NJ. (a,a)))
gtrans = ExAxx -1P( V('') S (n.,))
Then we get for V with probability of 1 5:
PP (( (E)rams))) (c)
= (3k 2 1, E)
Σ (P(S | s, - Pa(s' s,a, b)) v(s') > (Niinas)(ssa.66
Σ
P
3k 2 1: Σ (((s s) - Pals' s, v(s'} > Srataams
(xx
IA3
Σ
P
3m 2 0: Σ
(P(s (s,,,b) Pa (,, v(s') > (Na(maa))
( AxB
In
32 (Alaaaa)) m2 7)2
Σ
Σ
2exp
4m 2 R2
(s.a.))SSx xx.eEExAAR AB m20
8
Σ
15|S||AA|| (m
8
n2
<
1
15
5'
where (a) uses a union bound over the state and joint-action space, (b) uses that we only consider
the m-times, where we updated the estimated transition model and (c) uses an union bound over the update times and an application of Hoeffding's 's inequality combined with the fact that we
can bound the value function, i.c. V'(s') < RBaas for every s' S. Next, will consider the
42

---

first equation regarding estimating the log probability of the expert policy, In a first step we define
(2(3) | (+))%// the following set
2NT (+)
glog = [vk E N. v(s,a) E x A: [log(u(a | s)) log(ā(a s) S 82(s))
P (( P3 1, 3 (8, a) A: [log(u(a 8)) log(Ax |+)]| > Ba(+)
(0)
P P log(u(a s)) - log(Ax(a s))l > B2(s))
(s,))SxAA
Σ
P (3m > 0: [log(a(a (s) log(ūm(( 8))] > B2(6))
(s.0)ESXA
5
Σ
Σ
10/5||A|m2
(8,0)ESxAA
m20
8
VA
5
where (a) uses a union bound over the state and action space player 1, (b) uses that we only consider the m-times, where updated the estimated transition model and (c) we can applied Lemma H.3 To be precise, (c) only holds N large enough, however, we will late only consider this case, therefore use directly.
For the second last step we define the good event for the total variation
{ ((s
TV = Vk VK
B log (10|S]IBI(N (s))2/8)
e TV(, S
(s)
We will the bound the probability of the complement of this event by and can then take the intersection of both events to get the total result. We will skip some intermediate steps, they similar to the ones obtained above.
B log(10|S|188 (N (s))2/8)
P((ETV)C) = P 3k E N.
TV(,,D) >
N (s)
B log (B] mn2///
Σ
P TV(,,0)
(s.0)ESxAA m20
5'
where (a") uses union bound over the state and action space, (b") uses Lemma H.5 Also here to be precise, (b") only holds N is large enough, however, we will late only consider this case, therefore we use it directly. To bound the second last event, we can apply Lemma H.4 To complete this proof,
log (]](()) (1)22/8) and once again apply the same argument for
we first define Ba(s) == the good event,
N₂ (9)
clnvprop
Vk (( v(b s)ū(b s) - Bs(5))
now combined with Lemma
H.4 As all the good events holds with probability 8/5, we get that P (ETVV n glog n gtrane n ginvprop) > ~18 8.
Following, we present the reward uncertainty metric, which allows to demonstrate that the difference between the recovered reward function and the true reward function bounded.
43

---

Definition E.8 (Reward Uncertainty). Let l be the number of iterations. Then the reward uncertainty after & iterations for any (s.a, a, b) E A x B defined
4 max
(v
8 log (10}S [ (8))2/6)
b)) = (1 7 min
N (s)
log log (10) (NE (s))²/0)
(s, a, No (8,
No (8)
Theorem E.9. Let the reward uncertainty be defined in C.9
Under the good event it holds for any
b) E x A that:
as, - (',ss, a, b) & Cs(s,,,b).
Proof. The theorem is an application of the error propagation Theorem E.. followed by Lemma E.7
(8(s, a, b) - (s,,,),)))))
$ (b(b (b) s)
(A] Aolog (a s) log log s)]
+7 max
Σ V(8)P(8
8, 8,0, b) P(6 8, 8,a, b)] + Ruax TV(,, (i)
4mmax
1
(I (5))
2/ (gg(0 (N) (8))2/8)
+
7
A 2
N+((5) (8)
No
1
2 20og 10 (N (4))2/0)
(s, a,
A Amin
N (s)
N (s. a,
47 R Bmax
8| log
(5))2/8)
2 log S| (s))2/8)
<
(1 A min
(s)
N
24, b)
No (s, a,
CC(ss,,b)) b).
Before stating the correctness of the algorithm, we want mention that the derivations Lemma C.6 also hold for the regularized case. Therefore, we can continue with the the correctness result for the regularized case.
Corollary E.10. Let k be the number of iterations for any allocation of the samples over the state- action space S x A. Furthermore, let Re be the true feasible set and R (G the recovered one. Then the optimality criterion 3.3 holds true, if
max Ca a. (s.a.b)
Proof. We complete the proof for the first case of the optimality criterion, the second follows analogously.
sup
inf
max{max (2 Vil 0), (2( min (2,
RER (E, Nob RER Noob))
XX
22
max b) 1 (s,a.))
where we applied C.6 we used the fact that + b < max (a, by followed by the error propagation Theorem E.5 and then used|C.10
44

---

We can combine the derived results to now state the main theorem regarding the sample complexity of the Uniform Sampling
Theorem E.11. Let Assumption 3.8 hold true. Then, allocating the samples uniformly over S x xAX B and using the empirical estimators introduced in Eq. (13) and Eq. (12), we can stop the sampling procedure with a probability of at least 1 5 after iteration T and satisfy the optimality criterion where the sample complexity is of order
Definition E.2
| |
2 min
Proof. We know from
C.11 that we need
Ek 2
max Ca(s, S 7 (e,0,))
By the definition of Cs(s,a, this is satisfied if
4yRmmax
2/ 21, a)
Ek
> 2 min
N as,
4- Rmax
(5)))/)) log(10 ( (5))2/0)
EK
(1 7)2 A min
N
6
B log (I (5))
Ek
(1 7 min
(x)
6
To achieve the first condition, we get
R² R
2
Na(8,
224 a, b)
(1 7) min
&
121152 mnxx
[2 (s, (s)
log
(1 A min $
Applying Lemma B.8 by Metelli et al. [202] we get that
4608 R
R 2304 max
12 12
Nu a. <
log
7)= min
(1 2
At each iteration we are allocating the samples uniformly over S x A x B and recalling that Ts.a.b N a, b) therefore we get
4608>2|S|E | max log
2304> R (1 A min
B
Ta
(1 (1-7)'A* min of
Now we have to achieve the second condition,
24 R2 Raax
log(10|S]||A (N+ (s))2/8)
(x(s) 2 (1 A mii
2 (og(10))]]44(N) (8))
7:2 2576R2 maxx
(1 7)4ERA A min
22 2576R2 max
= (log(10{$){AA/o) 2 (NV (s)))
If we additionally force that Nx(x) 2 1 and apply Lemma 15 of Kaufmann et al. 2021 with 2337612
1/A2 (1->) a (1)(11))))A/))),b c 0, d = 1, we get that
2276R max
No(s) 51 (1- (1 log(10/S](A1/0)
((1 (1- min
(-7576/f2 max
(log(10)S\(A1/b) - -2)) )
2 log
45

---

As we here need to allocate samples uniformly over the state space only but for every agent separately and recalling that Ts (s), we get
55175566 log(10//|IAA/0)
Ta S |8| +
71-7) min
((1- 2776R max 7) A
(log(10[$11A41/) +2) ))
2
Lastly, we can proceed in similar way compared to the last step,
R max
22 8| log [ (N (5))2/0)
N&(6)= 2 (1
A
26060 R max
B
log(10/S]]B[(} (
45 min
If we additionally force that (x(ss) 2 and again apply Lemma 15 of Kaufmann et al. [202] with
|8)> 280724608.72
1/A²
T = log( 10 S|| (1)) 2, = 0, we get that
(1-7)=={A A min
1B124608 max
(s) 11 (1 - 7 A4
log(10/S|1B1/6)
min
B602 max - min
(log(10)5118)/6) + (2))))++)))))) 22))
2log
As we here need to allocate samples uniformly over the state space only but for every agent separately and recalling again that Ts2 (N)( get
B| 24688/66FFF R R
Tea S |S|
(1 76
min
(
(1B3
[B 4608 R2
(log(10)S]188/0) + +2) )
+ 2og
(1- min
Finally, as Ts.a + Top + Top we get that this is exactly of order
B 2 R2
max
7 A2
One can see that the problem scales with [A which is due to the used union bound. Scaling this up to n-player games the union bound implies that the bound will scale exponentially in the number of players. Additionally, bound. sufficiently large Amin can c.g. be obtained the regularization parameter Á is small.
have to bound the inverse probability the term Amin appears on the
F Identifiability in multi-agent games?
This appendix provides supplementary details and proofs for the identifiability results discussed in Section 4 We follow the notation established in the main text, where applicable, using R (x, a, to denote Player I's reward, (". a) Eveg v(b' | (s. a, b') for the average reward received by Player when Player uses policy v, and Prr for the induced transition matrix for Player under v. X denotes Player I's entropy regularization parameter.
Average identifiability. We start with the case, where we try to identify the average reward function (up constants) for any player. The theorem is direct consequence of Theorem 3 by Rolland et al.
2022
46

---

Theorem F.1. Let Markov game be given with two different opponents v1, that induce different dynamics pi, tnd and discount factors Y/. Suppose that in both Games we observe QRE equilibrium policy pairs (M,, v1) and a different V2 with best responding policy #tl such that they have same average reward functions R R Additionally, define P RRSx the induced transition matrix of expert i E {1,2}. Then, the average reward player receives can be recovered up to constant if and only if
71 Pu
- T-72Pa
P2
rank
2|S| 1.
1
PM M
1 72 RÍAl
PIAl
Analogously this holds for player 2.
Theorem F.2 (Sample Complexity for Induced Transitions). To estimate the induced transition model P for Player (where v" is Player 2's true policy) such that the maximum L1 ervor over all (s, a) rows is bounded by i.e., max,,a || (,),a)- ( s, 3,a)llı S s, with probability at least 1 - 8.
the total number of samples is of the order:
O Bog( /)/5)
g²
where pi (,))) EvEr (()l)) b) uses empirical estimates i of v² and P of the true dynamics P.
Proof. The estimated induced transition is (- a) = Es ((kss b). The true induced transition is p" (+Is,a) En "" (bls) a, 6). We want to bound the Li enror. We use the triangle inequality and properties of the L1 norm:
|| pp (-18, a) (11(,1 (-1s,a)ll a)ll
Σ ((1ss)
Σ b(bss) P(-s,a)
Ev ((1s.)) + b)
< Σ 10" (b|s) - p(11s)] ||P(11,,, blll + ((bss)lP((lssaa P(-1s, b)]l
Since ||P(-|s, a, b)ll and (bbss) 1:
- 80 (-|s, a)ll - 1 (-1s) - 0111s)]l1 + max [||(|) | 0, P(- a, 8
VeB
To ensure || (-Is, a) - PO (-|s, a) a)l < E with high probability, we need to ensure both terms on the right are sufficiently small, e.g.. - e/2.
Estimating the multinomial distribution D² (-1s) over [B] actions requires Ns(s) samples of Player
2's actions at state s. Applying Lemma H.5 gives us that to achieve [|x*((|s) (+11)]] S e/2 with probability
requires that (s) is of the order O
samples.
Similarly, we can bound the transition dynamics. In particular, if we apply Lemma H.5
then we get
that the amount of samples required to minimize with high probability is of the order [SS|IA As the part of the transition dynamics dominates, the total number of samples is then of the order is then given by
S||A|| g2
With this result we recover Theorem 8 by Rolland et 2022 for every player. For completeness we restate the result here.
47

---

Theorem F.3. Suppose that we estimate the transition dynamics P and P by P and Pa such Va A. Assume that the estimated transition dynamics satisfy Eq. 33 then the true transition dynamics satisfy Eq. 3 if for the second smallest eigenvalue a of the following matrix
that || -Pa l1 and 2 1 S
1 71 Pai
1 - --22Pa
1 Vi péj
I 722 RiAI
it holds true that
e/2 max (nax(1;771)
Reward identification in linear separable Markov games. As the so far discussed theorems only work for the average reward case, want identify conditions that allow to identify the rewards in the multi-agent case. As discussed in Section potential solution to achieve this is to assume linear separable rewards that naturally disentangle the rewards into part that only depends on action a and a part that only depends on action b.
We can immediately see that R" as = Eber v (b 8) R) a, b) RA(s, EbER v R) b). This means, that the average reward equation Eq. ( can be rewritten. In particular, we get for every (s,a) E S x A
Ra(s,a) Alog(u" (a 6)) V88) -7 Exr (11,,,)))V())
Evr(b ())(s)))B(ssb)) BEB
Next, we again consider the case, where we have Markov games where we have the same reward function for player 1, in particular for action a. Using the explicit formulation of the reward, we get the following:
Rs Alog(ui s)) Vi(() - Σ PT (.s.0)Vss)))))
Σ vi [ R)RBss
BEB
= Allog(aāaa s)) + V2((s) - (1.
(,s,a)V2(())
1 8) RB b) bE
Let us consider two cases. The first case is that in both environments the opponent policy is the same, meaning that we have vf = 1/.. Then, we see immediately that EbEr Va (6 RB, and we get
(s, b) cancels out
Alog(wi(a s)) Vi(s) - E. Pr (s' (s)) Alog(us(a s)) + Va(8) - E. Ps (s' V2(s5))
Therefore, reconstruct the single-agent case, as obtain for every (s, E S A:
Vi(s) V((() >., Pf (s' a))) + - PT (s' ())())) A(log(Hi(a $)) log(ui s)))-
Therefore, can again write this system of equations but this time for the same v². We can summarize these findings in the following result.
Proposition F.4. Let a Markov game with QRE equilibrium policy pair (pā ) be given. Addi- tionally, let another Markov game with the same V but different transition Model Pz and discount factor 7/ and therefore also different best response p2 be given such that R2, is the same for both environments. Then, R2 is identifiable if and only if
pej 7i 1.a
I- 72 pKg
2,a1
rank
2||S|] - 1.
1 m
Pid
1 - 72 Dot
T.caal
2.a.al
Analogously this holds for player 2.
48

---

For the second case, we assume that the opponent policies are different in the two Markov games, meaning that of * v/. In this case we need an additional assumption, namely R bo) 0. his constraint fixes the baseline for Rn(s,b) b). allowing us to determine how much player 2's different actions contribute to player I's reward, relative to this baseline.
(i( (v((s)
EPtiGs (s' (.s,a)V(((s) + Σ
Ps (s' (,,a))
+
Σ () (/(bb $)) = Alog(/ 8)) - Alog(1i(a s)). bo
This now again express system of equations as the above holds for every (s. 8 A' and we get:
Mng
m PM
1 - 722 Par
2(1og(u2(: an)) log(un (a))))
RB Vi
MR
I-
I
P
n Al
I 7/ AjA
V/2
A(log(A2(- (A1)) - log(uz( (()i)))
where Rg is the reward vector for every E S and E B {bo} and each Mng is an |S] x |S||8] block diagonal matrix with the following structure
v(s)) 0
82
0
MR
0
0
((sss)
where each (s::) for 8; E is (1B) 1) row vector where every element is the difference of the policies for the actions (2 8) (b 8) for E B {bo}-
This means that the matrix on the left has shape SA||S| x | + 1). As require identification
up to constants we need that the matrix has rank [ + 1) - 1. We can conclude our findings in the following proposition.
Proposition F.5. Let us assume that we have two-player general-sum Markov games with different transition functions Pt, P2 and Y1, 72 be given. Additionally, assume that the rewards for player I are the same under the QRE (ni, v1) and the other observed best responding policy μiz to v/z Additionally, suppose player 1 ''s reward function is linearly separable: Rí b) RA(s, a) + Rp(s, b). To ensure unique decomposition between RA and Rg, the normalization Rg bu) for some fixed by E B and for all E S. Then, player I's reward function [s,s, b) (and its components Ra a) and Rg(s, under the given normalization) can be recovered up to a single additive constant if and only if:
imposed
MRg
I- 71 PM
I 7/ Pvz
rank
=| + 1)
MRn
"n Pri
I - 7/2
Pin
PiAl
G Experimental evaluation
In this section, we first give the details for the figures in Fig. 2 and Fig. Then, we aim to demonstrate the advantages of IRL in the multi-agent setting compared Behavior Cloning.
It is important emphasize that the primary goal of this paper is address the IRL problem from theoretical perspective by defining a new objective and presenting the first algorithm to characterize the feasible of rewards. particular, we will demonstrate the case of pure NE strategies in simple environment. Although, we have shown that in the general case one needs to observe multiple equilibria to infer a meaningful reward function, we will demonstrate that one can still obtain good performance in simpler environments. We motivate this simple example given that calculating the NE is PPAD-hard. The idea emphasize the need for MAIRL framework and motivate future research computationally more feasible equilibrium solutions.
49

---

G.1 Numerical verifications for Nash and QRE equilibrium observations.
In this section, we give the details for the numerical examples provided in Fig. and Fig. B respec- tively. The idea of both experiments is the same. The considered environment is the used in Proposition 3.4 and illustrated in Fig. 2
Expert observations. In the case of Nash equilibrium experts, equilibrium solver to calculate the equilibrium for state $p- This holds true because in the following states the Nash equilibrium actions of the Normal Form Game in 8o are rewarded (s1 and 83), while the other actions are not 82. Regarding the equilibrium observations for the QRE, we again only consider state so and run simple algorithm that iteratively computes the expected reward of player keeping the other players strategy fixed and then updates the policy. This is repeated until the changing anymore.
simply take any Nash
strategies of both players
Calculating new equilibria and exploitability. For both expert observations, we then use any IRL. algorithm that picks reward function, such that the observed equilibrium is feasible under this reward. Then, we compute again the new equilbria and compare the list original Nash equilibria with the ones under the recovered reward function. From this list, then randomly select equilibrium and calculate the exploitability of the picked strategy in the original Markov game. This we repeat for 10000 iterations and compute the average exploitability and the average correlations.
G.2 MAIRL Behavior Cloning.
In this section, we empirically evaluate the benefits of MAIRL compared to BC and describe the details on the environments in the following paragraphs. One of the advantages IRL over BC lies in its ability to transfer the recovered reward function to new environments with different transition probabilities. This particularly significant in multi-agent setting, where even minor changes in transition probabilities can alter not only the individual behavior of agents but also the interactions between them.
For our experiments, we utilize the 3 3 Gridworld example, also considered in Hu and Wellman 20033. To recover the feasible reward set and learn the expert policy with BC, we consider scenario where the transition probabilities are deterministic. The Nash experts are learned via NashQ- Learning as proposed Hu and Wellman 2003). The resulting Nash Experts and more details on the environments can be found in G.2
1.
0.0
Uniforza Sazopling
40
BD
50
Noch
40
401
Samples
Samples
Samples
Figure 4: Nash Gap in Grid Games for different transition probabilities.
Using the Uniform Sampling algorithm to recover the entire feasible set, we then apply a Random Max Gap MAIRL algorithm to extract reward function from the feasible set, similar to the ap- proach introduced in Appendix C of Metelli et al. [202T]. A detailed description can be found in Appendix G.2 To test the transferability of the recovered reward function, we alter the transition probabilities so that in states (0, any) and (any, 2). taking action "up" is only successful with probability of 0.5; otherwise, the agent remains in the same state (as in Grid Game 2 in Hu and Wellman 2000)). ). In a second scenario, we introduce an obstacle into the environment, that prohibits the agent from passing through. While in the first scenario, the BC strategy still performs reasonably, the second altered environment leads failure to reach the goal state for agent 1, resulting in the maximal Nash Gap.
50

---

Figure 5: Multi-agent grid world environments with different transition probabilities and learned NE path
We observe that while BC may perform better in the original environment, for the first iterations, the Uniform Sampling Algorithm proves superior when transferring the reward function, especially as the number of samples increases and the environment changes.
Multi-agent Gridworld. In this section, describe the environments used for the experiments. The environments are similar to the ones used in Hu and Wellman [203). We adjust them in such that for the random transition probabilities in the states (0, any) and (2, any) the environment still has different goals for each agent. Additionally, we introduce the scenario, where an obstacle is added in the middle of the environment, that bounces the agent back with probability This results in failure of reaching the goal for agent in the BC case.
In the left column, we draw the learned Nash path for both agents in the deterministic environment,
when applying the NashQ Learning algorithm to retrieve an expert policy.
Max Gap MAIRL. this section, we describe the Max Gap MAIRL algorithm, an extension
of the approach presented by Metelli al. [2021] (see Appendix C in Metelli al. [202T) I) to the multi-agent setting. This algorithm is chosen due to the limited number of existing works that
address the selection of feasible reward functions in general-sum Markov games with Nash expert, particularly without imposing additional assumptions on the reward structure. Given the simplicity of the chosen environments, the Max Gap MAIRL procedure suitable choice.
The algorithm operates as follows: for each agent E [n]. random reward function it' is selected such that ||||| Rmaxx The next step involves finding reward function R' that minimizes the squared 2-norm distance the randomly chosen reward R'' subject
constraints: (1) R6 must belong to the recovered feasible set, and (2) it must maximize the maximal reward gap, thereby enforcing the feasible reward condition introduced in C.4 This results in the following constrained quadratic optimization problem:
Ai
max REER ,
s.l. (π Nash +) - 7T P > A N0) 1 iNooh 503 1sxA,
(
|R loc S Rmaxx
H Technical Results
In this section, we present results that were used throughout this work.
Theorem H.1 (compare Theorem in Cao et al. [2021]). For fixed policy ā (a]s) > 0, discount factor 7 E j0, 1), and an arbitrary choice of function S - R. there is a unique corresponding reward function
r(s, a) = Alog - Σ P(s)(s,a)u(d))+ v((s
S'ES
such that the MDP with reward r yields a value function V v and retraiy-regularizee optimal policy T n.
51

---

Proof. Fix r as in the statement of the theorem. Then the corresponding value function is given by
Vi(() log Σ
r(8,a)+ +
Σ
P(s'ls -((6)).))Vi(()))
exp
BEA
N'ES
v(s) Alog Σ
((aas)exp
P(s'ls, P(63,00)))))) -0(1))
aEA
e'ES
which rearranges give
exp(g(s)) = Σ
7(als) 7 Σ P(s(s,,))(()))
(15)
aEA
SES
with g(s) = (Vi(s) v(s))/A Applying Jensen's inequality, we can see that, for E
arg minles
exp min g(i)g(s)) exp (g(x)) 2 exp
E (sl,))(('ls,a))(
aEA,'ES
However, the sum on the right is weighted average of the values of g. so
Σ {(als) ())((s))))))( 2 min g(s).
aEA.SES
Combining these inequalities, along with the fact 1, we conclude that g(s) 2 0 for all 8 E S. Again applying Jensen's inequality Eq. 15). for 8 E arg argmax,es ((8) have
max (exp (g(s)) exp (9(3)) S Σ
(s (1g(s'))
aEA.S'S
As the sum on the right is a weighted average, we know
Σ
((x (1g(()))))) s max fexp (11(s)))
AEA
Hence, y 1, we conclude that g(s) for all e
Combining these results, we conclude that g = 0, that is, V = v. Finally, we substitute the definition of and the value function into (6) to see that the rntropy-regullrizzd optimal policy is πī क.
The next lemma an extension of Lemma from Zanette et al. [2019] for the multi-agent setting, accounting that different Nash equilibria can have different values.
Lemma H.2 (Simulation Lemma). Let [n] be any agent. Then it holds true that Fimm (s) - ViT (s)
Σ TT (((ssaa) (((s +7
Σ(
Σ (P(s' (s,a) P(s') s.))) virt(s')
6.0
Proof. Let the starting distribution dirac measure on some s E S. It then holds that
(i) (s)
f( (), +7 P(s'
P(s' 8, (16'|8,a)))
a)) P(s' a.
;s, (s, +, (P(s') s,a) P(s' a)) (s)
Σ P(s' a)
(s)))
The proof follows by induction.
52

---

Lemma H.3. Let 1,, 1/" be the QRE equilibrium expert policies, such that Assumption E.6 holds true and fi, 8r the respective empirical estimators with samples N. Then for E (0, 1) it holds tree with probability 1 8 if
log(2/5) Amin that for E A, b
2NT (6)
log(2/8)
log(u" (a 8)) - log(ū" (a 8))1 -
min
2N
2
log(2/6)
log(u"(( (a s)) - log(U" (a s))
A
min
2N
Proof. The difference in logarithms be bounded using the inequality:
|u[a s) p( s)
[lg[[(( s)) log(ū(a |s)]| S
minn((( 8), Íd(a [s)
This follows from the fact that the derivative of log(x) is 1/z, so the difference in logarithms is controlled by the relative difference in probabilities.
By Hoeffding's inequality, for any (s, a) S A, with probability at least 1 8/(SA), we have:
log(2/0)
In(a s) id(a s)1
V
2N (s)
Since uaaa 8) Amin, and assuming i=(a
s) is close to pa(a 8), we have:
log(2/0) 2N (s)
log(2SA/0)
ila 8) p(a
A min
2N (s)
To ensure Úa(a s) > 0, require:
log(2/0)
min-
2N (s)
Under this condition, the denominator satisfies:
log(2/8)
min(u(a s), 8)) 2 Amin
V 2N (s))
Substitute the bounds for [u(a s) - fa(a s) and min(a(a s), jaaa s)) into the inequality for the
difference logarithms:
log (2/()/8) 2N (+)
llo((u(a| s)) log(A(( s))1 <
A
Amin
log(2/8) 2N (s)
log(2/6)
2N (s) < Amin, then:
2
log(2/8)
2,
2N (s)
[log(u(a s)) - log(ā(a 8))1 <
Amin
Lemma H.4. Let pt be a probability such that 2 Amin > 0, and let Ps be the empirical estimate of Pi based independent samples. Then, for any E (0, 1), with probability least ō, the following bound holds:
Ing (2/8)
2n
<
Pt
Ps
A Amin
A
min
log(2/8) 2n.
53

---

Furthermore, if V /log(2/6) _
Amin the bound simplifies to:
2v
log(2/6)
2m
2
Ps
min
Proof. The difference can be rewritten as:
1
D:
Pr
Pi
P:
P:P
By Hoeffding's inequality, for any 8 E (0, 1), with probability at least 1 8, have:
log(2/6)
p. p S
2n
Let 1og(2/8)
Then, with high probability:
1b p:l S E.
Since Pi 2 Amin and p0: Pil I e, we have:
pi 2 ps -
Amin
To ensure P; O, we require E < A min
Using ps 2 Amin and P. 2 Amiu E, the denominator satisfies:
peps Amin (Amin e).
Substitute the bounds for 1p: Pil and p:p into the expression for the difference:
1
16. Pol
P: p.
P.P.
Amin (Amin E)
This gives the first part of the lemma.
If e < Amin then Amin
Amin and the bound simplifies to: 2
1
2x
<
Ps
pi
A
Amin
Amnn 2
A
tin
Substituting
V
(2g(2/6) 2n
we obtain:
2
log(2/8)
2n
P:
P
2
min
This completes the proof of the lemma.
Lemma H.5 (Concentration Inequality for Total Variation Distance, e.g. Thm 2.1 by Berend ........
and Kontorovich (2012)). Ler 21. .|X be a finite set. Let P be a distribution on X. Furthermore, let P be the empirical distribution given i.i.d. samples T2,""" In from P, i.e.,
P()
n M Mas = 5}.
Then, with probability at least we have that
2 2 (1/0
|P P
Σ
((x))
P(0)
n
54

---

Proof. Define the function f(z1..... Rn) = ExEx P(x) - P(z)1, where P is the empirical dis- tribution. Replacing one sample 2j 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 's inequality, we have for any E >
ns 2
Pr(
e) S exp
Berend and Kontorovich (2013) show that E[f] solve
X
Setting the failure probability to 6,
nE²
2 (10((1
exp
6
n
Therefore, with probability at least 1 - 6.
x S V
log((1/))
X' log(1/6)
|
PI1
+
55


Reviews:
[{"review_id": "ZJA46qpn7o", "reviewer": "Reviewer_qBYJ", "summary": "The paper explores the problem of inverse reinforcement learning (IRL) in Markov games (MG). They start with defining a feasible reward set for a given MG as the set of reward functions under which a single observed Nash equilibrium (NE) policy has higher value than the policies that can be obtained by unilateral deviations. The authors observe the existence of degenerate MGs for which a NE policies of a non-constant reward function in the feasible reward set might have Nash Imitation Gap of order $(1 - \\gamma)^{-1}$. This stems from the fact that the feasible reward set captures many reward functions, some of which allows undesirable scenarios where the nature of the game is changed. The authors argue that, although one can address this issue by requiring a feasible reward function to align with every NE of the original game, this would lead to tractability issues. In order to mitigate these issues, they investigate the entropy-regularized 2-player MGs. In this setting, they show that the sample complexity of the problem is of order $\\mathcal{O}\\left(\\gamma^2 (1 - \\gamma)^{-4} |\\mathcal{S}| |\\mathcal{A}| |\\mathcal{B}| \\Delta_{\\min}^{-4} \\right)$, where $\\mathcal{A}$ and $\\mathcal{B}$ are the action spaces of agents, $\\mathcal{S}$ is the state space and $\\gamma$ is the discount factor, and $\\Delta_{\\min}$ is a lower bound on the lowest probability of an action. While this shows an exponential dependence on the number of players, the authors point out that this matches the complexity of learning an NE, which is known to have such exponential dependence in the worst case. Finally, the authors focus on the identifiability problem and note that when the other agent's policy is fixed, the 2-agent game reduces to an MDP, which allows the single-agent IRL theory to be used. The authors thus provide a condition under which the average reward can be identified up to a constant. Finally, the authors show that reward identification is possible in linearly separable Markov games.", "questions": "1. As of Section 3.2, the authors focuses two-player MGs for better readability (line 234). Is it possible to straightforwardly extend the analysis to n-agent case?\n2. Theorem 3.7 provides an upper-bound on the estimated rewards for two MAIRL problems. This allows the quantification of the difference between the original and recovered MAIRL problems. Could your analysis lead to a lower bound on the difference of estimated rewards as well to understand the fundamental limitations of the problem?\n3. Does your results require knowing $\\lambda$ for entropy-regularized Markov games? If so, could you discuss how restrictive is this assumption? Is it possible to obtain a bound similar to Theorem 3.7 for when there is a mismatch between the true $\\lambda$ and the one used for solving the MAIRL problem?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "**Quality and Clarity:** The paper presents a strong and methodologically sound contribution. The results and the ideas are clearly explained. Some experimental results were presented; as an addition, it would be nice to see an experiment designed to observe how identifiability differs in general games and linearly separable games.\n\n**Significance and Originality:** This paper extends the theoretical line of work on multi-agent inverse reinforcement learning (MAIRL) under varied game-structure assumptions. It demonstrates the inherent reward ambiguity that arises when only a single equilibrium is observed, and analyses the identifiability of reward functions in entropy-regularized games, both with and without the assumption of linearly separable rewards.\n\n**Minor issues:**\n1. typo in Definition 3.1: equilirbium\n2. the dependence of $\\mathcal{E}$ on $R$ is rather unclear at first sight, e.g. in the inequalities in Definition 3.3. I would consider making the dependence explicit.\n3. There are some related works that were not cited in the work, including: [1], [2]\n\n[1] X. Lin, S. C. Adams, and P. A. Beling, ‘Multi-agent Inverse Reinforcement Learning for Certain General-sum Stochastic Games’, _Journal of Artificial Intelligence Research_, vol. 66, pp. 473–502, Oct. 2019.  \n[2] J. Liao, Z. Zhu, E. X. Fang, Z. Yang, and V. Tarokh, ‘Decoding Rewards in Competitive Games: Inverse Game Theory with Entropy Regularization’, in _Forty-second International Conference on Machine Learning_, 2025.", "was_revised": true, "final_justification": "The authors identify the core aspects of the problem and elaborate on their methodology with relevant discussions. The paper is well-written and is enjoyable to read. The authors' rebuttal addressed the concerns. They will add further improvements on clarity that will enhance readability.", "rebuttal": "We thank the reviewer for their time to read our paper, providing this kind and insightful review that helps us to improve it. In particular, we are grateful that the reviewer acknowledges that our paper makes a  *“strong and methodologically sound contribution.”*\n\nBelow, we would like to address the concerns raised by the reviewer and answer the questions.\n\n### Experiment on Identifiability\n\nWe thank the reviewer for the excellent suggestion to include an experiment validating our claims on identifiability. We will add the following to the appendix.\n\n**Experimental Setup**: We test identifiability by observing the QRE policies from two environments with different, randomly generated transition dynamics satisfying the identifiability. The Markov Game has 15 states, and both agents have 5 actions for both setups. We only consider the results for the reward of the first player; it follows analogously for the second one. \n- *Averagel Case*: We first use a ground-truth reward $R\\_1​(s,a\\_1​,a\\_2​)$. The algorithm perfectly identifies the *average reward* (max difference: 0.000000). However, the full reward is not identifiable, achieving a correlation of only 0.9097 with the ground truth.\n- Linearly Separable Case: We repeat the experiment with a linearly separable reward. Then, the algorithm perfectly recovers the full reward component R\\_1​ (max difference: 0.000000), meaning the full reward is successfully identified.\nWe summarize the results of the correlation in the following table\n\n| Game Structure           | Correlation with True Full Reward |\n|--------------------------|:---------------------------------:|\n| Average Case             | 0.9097                        |\n| Linearly Separable Case  | 1.0000                  |\n\n### Minor issues\n\nWe thank the reviewer for pointing out these minor issues, and we have addressed them separately to improve the quality of our paper:\n\n- Fixed typo, changed equilirbium to equilibrium\n- To clarify the dependence on $R$, we addressed the dependency directly in Definition 3.2 and changed it to $\\mathcal{E}(\\hat{\\boldsymbol{\\pi}};R) := \\max\\_{i \\in [n]} \\max\\_{\\pi^i \\in \\Pi^i} V\\_{\\mathcal{G}\\cup R}^{i}(\\pi^i,\\hat{\\pi}^{-i}) - V\\_{\\mathcal{G}\\cup R}^{i}(\\boldsymbol{\\hat{\\pi}}).$ Then, we can include $\\mathcal{E}(\\hat{\\boldsymbol{\\pi}};R)$ also in Definition 3.3 to emphasize the dependence.\n- We thank the reviewer for pointing out the missing citations. We have already cited [1] in our related work section (line 984). Regarding [2] we are happy to include the concurrent work(it was released after the NeurIPS submission deadline), in our related work section of the camera-ready version. In particular, we note that [2] introduces identifiability in the context of linear payoff functions, where the essential goal is to estimate the parameter $\\theta$ if the experts are playing a QRE. Next, the authors extend their results to Zero-Sum Markov Games with a linear reward function. In contrast, we consider the general-sum Markov Game case, and additionally, we provide insights on the ambiguity of the feasible reward set.\n\n### Extension to n-player case\n\n- We would like to affirm this question from the reviewer. The results can easily be generalized to the n-person case:\n       - If we denote the policy of the other player as $\\pi\\_{-i}$, all policies but the policy of agent i, we can simply replace $\\nu$ by this joint policy. \n       - In Theorem 3.8 we would then have the sum of the total variations of the other players' policies.\n       - In Theorem 3.9, as stated below the theorem, we would get an exponential dependency in the number of agents $\\mathcal{A}^n$. \nWe will add these comments as a footnote in the camera-ready version.\n\n### Lower bound\n\nThis is an interesting question raised by the reviewer, and it remains an open question for future works. Constructing a lower bound is, in general, not easy and as we have shown in this work, MAIRL is hard, and therefore it is unclear if techniques used in the single-agent case [3] also apply to the multi-agent setting. Next, we lay out our conjectures:\n \n- In the single-agent case, it was shown that Inverse RL suffers from the same lower bound as RL, except for an additional $(1-\\gamma)$ factor, when given access to a generative model [3]. This could indicate that, also in Multi-agent Inverse RL, the lower bound will be of the same order as learning equilibria in the first place. This would mean that a lower bound would also suffer from the curse of multi-agents.\n- In [5] the authors provide a lower bound for Zero-Sum Games for the reward agnostic case, meaning that the learner has no access to the reward function during learning. The lower bound here scales with $\\vert \\mathcal{A} \\vert \\vert \\mathcal{B}\\vert$, which is worse than the reward-aware case in zero-sum games, scaling linearly in the number of players.\n\nTo summarize, we conjecture that Multi-Agent Inverse RL will probably suffer from the curse of multi-agents, meaning a bound that will scale exponentially in the number of players. We will add a comment about this future direction in the appendix.\n\n### Knowledge of entropy coefficient\n\nWe thank the reviewer for this relevant question. We answer it below:\n\n- The knowledge of the entropy coefficient is also required in the single-agent case [4].\n- To check the identifiability conditions, knowledge of $\\lambda$ is not required.\n- If the goal is to recover a specific reward function, it is necessary to know the coefficient, as this scales the recovered reward. Therefore, a mismatch in this coefficient would also result in a mismatch of this difference for the recovered reward and true identifiablity would not be possible. \n- Regarding the feasibility, one can see this as input given by the expert, as the entropy coefficient reflects the bounded rationality of the agent in a multi-agent setting. This means how much the expert believes in the rationality of the other agents. \n\nWe are happy to include a discussion regarding this in the camera-ready version of the paper.\n\n[3] Metelli, Alberto Maria, Filippo Lazzati, and Marcello Restelli. \"Towards theoretical understanding of inverse reinforcement learning.\" International Conference on Machine Learning. PMLR, 2023.\n\n[4] Rolland, Paul, et al. \"Identifiability and generalizability from multiple experts in inverse reinforcement learning.\" Advances in Neural Information Processing Systems 35 (2022): 550-564.\n\n[5] Zhang, Kaiqing, et al. \"Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity.\" Advances in Neural Information Processing Systems 33 (2020): 1166-1178."}, {"review_id": "lu3mCfWP1a", "reviewer": "Reviewer_7b2B", "summary": "The paper studies feasible‐reward sets in Multi‐Agent Inverse Reinforcement Learning (MAIRL), showing that inferring rewards from a single observed Nash equilibrium is fundamentally ambiguous, different reward assignments can admit novel, exploitable equilibria. To address this, the authors first define a multi‐equilibrium feasible‐reward set (intractable in general) and then introduce an entropy‐regularized framework yielding a unique quantal‐response equilibrium (QRE). They propose a new optimality criterion, the Nash Imitation Gap, to mirror the value‐gap objective in single‐agent IRL, and under the QRE they derive an explicit characterization of all reward functions consistent with the expert policy. For linearly decomposable rewards, identification is possible up to additive constants (as in single‐agent IRL), and they prove polynomial sample‐complexity bounds for recovering these rewards from finite data. Finally, they also establish a negative result: without entropy regularization, reward identifiability is not possible in the general MAIRL setting.", "questions": "### Remarks and Questions \n1. Content-Sensitive Typos\n\t- In the \"Mathematical Background\" paragraph, the definition of the Hausdorff (pre)metric contains two $\\inf_{\\sup_{y\\in\\mathcal{Y}}}$ which are supposed to be $\\inf_{y\\in\\mathcal{Y}}$.\n\t- In line 180 \"...player 2 plays action $a_{2}$ ...\" should be \"action $b$\" instead to align with the following expressions.\n\t- In lines 109 and 181 the $\\mathcal{A}_{i}$ should be $\\mathcal{A}^{i}$ to be consistent with the notation introduced in the Preliminaries/Markov Games paragraph.\n\t- In line 110 the expectation is missing the condition on the initial state $s$.\n\t- In line 192 the closing parenthesis on the superscript of the last $V$ is aligned with the $Nash$ instead of the $\\pi$. \n\t- In line 362 the cross-reference to \"Section 4\"  should refer to the appendix?\n2. Some elements would benefit from some notational clarity. To give some examples:\n\t - On line 88, the probability $\\mathbb{P}$ should include a time index (e.g. $\\mathbb{P}^t$) to indicate that it transitions from the initial state to $(s,\\mathbf{a})$ by executing the policy for $t$ steps.\n\t - E.g. in lines 98 and 110 it would increase clarity to add a time index to variables where applicable ($s$, $a$, $b$, etc.) or a separate notation for random variables and realizations.\n\t - The paragraph \"Entropy Regularized Markov Games\" would benefit from adding that it is described in the setting of a two-player game.\n\t - The action set of player 2 is sometimes referred to as $\\mathcal{A}^{2}$ and sometimes as $\\mathcal{B}$, while both refer to the same set, I would suggest using the same notation as synonyms might spark a first thought of -- something is different here? -- when its in fact the same object.\n\t While most of these issues can be understood in the context and it is mostly clear from the context what is meant by the expressions or symbols, I think that it would improve clarity and ease of access.\n3. Figure 2 needs a more thorough description to give context to the values shown as well as the \"Stag Hunt MG\". Another option would be to move this figure to E.1.\n4. There are some consistency related issues. The two things that stand out the most are the mixed usage of \"Markov Games\" (capitalized) and \"Markov games\" (lowercase) as well as the inconsistent capitalization in section and paragraph titles. Lastly, the use of acronyms versus their expanded counterparts is inconsistent. Fixing these little issues would further improve the otherwise well written text.\n5. In Theorem 3.7, is $TV(\\nu, \\hat{\\nu})$ the total variation distance?\n6. The insights from the future-work and limitations sections should be integrated into Section 5 of the main paper, as they offer valuable and relevant information on the topic. \n\n##### Typos:\n- Description of Figure 1: Plural \"..sets of Nash equilibira...\"\n- Line 120: considers -> consider\n- Line 128: Typo in equilibrium\n- Line 309: agent' 1 -> agent 1's ?\n- Line 367: showed -> shown", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Besides some room for improved clarity, as noted above, the paper is well written and pleasant to read. The authors explain the topic with attention to detail and make room to elaborate on the underlying intuition. They do a great job capturing the essence of the MAIRL problem and explaining if, when, and how feasible-reward identification is possible -- delivering what a reader would expect from a paper with this title. They also introduce valuable tools, such as their optimality criterion, that future work can build upon. I believe this work makes a valuable contribution by strengthening the foundations of MAIRL and will be a relevant read for anyone entering the field. That is why I have emphasized clarity and the placement of key information in the main text: clear, unambiguous presentation is particularly important when building a theoretic foundation, and especially helpful for newcomers. However, few of the issues I have raised detract from the paper’s contributions; if the content-sensitive typos are corrected or clarified, I consider this work a valuable contribution.", "was_revised": true, "final_justification": "My concerns centered on notation, clarity, and consistency, as I worried that the interesting contribution might not be as accessible as befits the importance of the topic; the authors agree with these points and intend to improve the paper accordingly. I have read the other reviews and their rebuttals and do not see any major points that would contradict my decision. Because these changes are easily done within the scope of producing the camera-ready version, I propose to accept this work.", "rebuttal": "We thank the reviewer for their detailed and constructive feedback. We are pleased that the reviewer found the paper *”the paper is well written and pleasant to read”* and *”makes a valuable contribution by strengthening the foundations of MAIRL and will be a relevant read for anyone entering the field.”* Below, we address all comments and suggestions in detail.\n\n**Content-Sensitive Typos**\n\n- We corrected the definition of the Hausdorff metric to properly reflect the intended subscript and structure: \n\n$\\mathcal{H}\\_d(\\mathcal{Y}, \\mathcal{Y}') := \\max\\left\\\\{ \\sup\\_{y \\in \\mathcal{Y}} \\inf\\_{y' \\in \\mathcal{Y}'} d(y,y'), \\sup\\_{y' \\in \\mathcal{Y}'} \\inf\\_{y \\in \\mathcal{Y}} d(y,y')\\right\\\\}$\n\n- Changed action $a_2$ to action $b$.\n- We changed the subscript in the action space to a super script  $\\mathcal{A}^i$ to be consistent.\n- Added the missing condition $s \\sim \\rho$ in the expectation on Line 110.\n- We changed the alignment in line 192: $V^{i, (\\pi^{\\mathrm{Nash}}\\_i, \\pi\\_{-i}^{\\mathrm{Nash}}) }\\_{\\mathcal{G} \\cup R}(s) $.\n- We changed the reference in line 362 to Appendix G.\n\n**Clarity**\n\n- We added time indices where appropriate.\n- Adopted a convention where random variables are capitalized and their realizations use lowercase (e.g., $S_t$, $s_t$).\n- In the paragraph on entropy-regularized Markov games, we now clarify that the exposition focuses on the two-player setting, but the framework generalizes to $n$-player games.\n- While we defined $\\mathcal{A}^2 := \\mathcal{B}$ on Line 109, we acknowledge the potential confusion and now consistently use one notation throughout the paper for clarity.\n\n**Figure 2**\n\nWe move the illustration of the Markov Game to section E.1 and refer in the main text to this section for a detailed description of the setup. \n\n**Consistency and Terminology**\n\n- To align with common usage in the literature, we now consistently use *Markov game*\n- We standardized capitalization across section and paragraph titles.\n- We ensured consistent usage of acronyms and their expanded forms throughout the paper.\n\n**Total Variation**\n\nYes, the reviewer is correct. We now introduce this explicitly in the Preliminaries (Mathematical background).\n\n**Limitations and future work section**\n\nAs the camera-ready version allows us to include an additional page, we are happy to extend section 5 by including the future work and limitation setting which used to be in Appendix C.\n\n**Typos**\n\nWe thank the reviewer for pointing out these typos, we have fixed them in the current version of the paper (equilibira -> equilibria, considers -> consider, agent’1 -> agent 1’s, showed -> “shown”).\n\n\nOnce again,we would like to thank the reviewer for their careful reading and valuable suggestions. We believe these revisions improve the clarity and quality of the paper, and we hope it now better reflects the significance of the contributions."}, {"review_id": "IrMGQ1YCas", "reviewer": "Reviewer_14AJ", "summary": "The paper investigates the Inverse RL problem in the multi-agent setting (MAS) where they formalize the problem of learning the joint reward function (feasible reward set) from the expert demonstrations (at some equilibrium). They formalize the added complexities that arise due to the multi-agent setting, in particularly, they present an important result that states a observations from a singe Nash equilibrium can be insufficient for a identifying feasible reward set. This is due to the nature of multi-agent settings where there can be multiple Nash-equilibria and it can result in a Nash of order $(1-\\gamma)^-1$ (Prop 3.4). \n\nThe paper then presents a method to mitigate this issue via building on the recent work in single-agent entropy-regularized IRL in the multi-agent IRL setting and Quantile Response Equilibria (QRE). For the QRE, they provide the analysis in terms of error and sample-complexity bounds for finding feasible rewards (Theorem 3.7, Thm 3.9). \n\nThen the authors ask if the reward identifiability even feasible in MAS and propose that for general-sum Markov Games, it is only possible for the average reward case where the reward structure has a particular form, i.e. when they are linearly separable (Prop 4.3).", "questions": "- My suggestion will be to bringing the QRE and average reward definitions in technical background, and then work with consistent setting throughout the paper. If that seems quite a big delta from the current version, a more detailed section describe the need of switching the setting will help the reader and make paper more accessible.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "# Strengths \n- The paper is clearly written and does the important task of characterizing the MAIRL problem which is important given the agentic trends. \n- The paper is rigorous - assumptions are laid clearly, and the results and analysis does a good job of characterizing the findings. \n- The main result shows the hardness of the MAIRL problem and lays open the ground for future opportunities and problems in this domain. \n\n# Weakness\n- The main weakness of the paper is Sec 3.2 where the paper switches the setting to Entropy-regularized MGs and QRE. While the authors provide some motivation of working with QRE, it is unclear why wasn't this introduced in the beginning (instead of NE). That would make the paper more consistent. For instance, how does QRE changes the optimality gape (Definition 3.3) that was defined earlier? \n- A similar concern also lies with switching from regular rewards to average rewards based criterions (Eq 2). Why we need this? How does it impact the general setting? Any other implications?", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful and encouraging feedback. We are glad that the reviewer found the paper  *” is clearly written”* and *”rigorous”*. \n\nBelow we address the reviewer’s questions and suggestions in detail.\n\n**Introduction of QRE**\n\nWe appreciate the reviewer’s suggestion to introduce QRE earlier in the paper. Our current presentation begins with NE because it is the most commonly studied solution concept in game-theoretic analysis. This allows us to clearly highlight the limitations of single-equilibrium inference. That said, we agree that introducing QRE earlier would provide a more consistent conceptual framework throughout. In the camera-ready version, we make the following adjustments:\n\n- Introduce QRE in the Preliminaries (in the Entropy Regularized Game section).\n- Clarify the transition from NE to QRE in Section 3.2, emphasizing the practical and analytical motivations for using QRE.\n\n**Average reward**\n\nWe introduced the average-reward setting (Equation 2) in the context of our second research question, on when rewards are identifiable in multi-agent games. This was not necessary before, as we were mainly considering the feasible reward set, meaning all reward functions that are feasible under an observed expert equilibrium. To clarify this, we are happy to explicitly state this transition when Equation 2 is introduced.\n\nOnce again, we thank the reviewer for their constructive and positive feedback, helpful suggestions, and we hope that we have clarified the reviewer's concerns."}, {"review_id": "mR9TPJeb6e", "reviewer": "Reviewer_4wfF", "summary": "This paper presents a theoretical analysis of reward recovery feasibility in multi-agent inverse reinforcement learning (MAIRL) within Markov games, using two behavioral game theory equilibrium concepts: (i) Nash equilibrium and (ii) Quantal Response Equilibrium (QRE). It demonstrates that under the Nash setting, access to a single equilibrium policy may be insufficient for accurate reward recovery, as the resulting policy can exhibit a large optimality gap (Proposition 3.4). In contrast, under the QRE setting, the paper establishes sample complexity bounds for estimating transition dynamics and agents' QRE policies, ensuring reward recovery meets optimality guarantees (Theorem 3.9). Additionally, Theorem 4.1 identifies conditions under which a player’s average reward can be recovered from observations of two distinct opponent policies.", "questions": "1. Can you please justify the assumption of the same average reward function in Theorem 4.1?\n\n2. Can you elaborate on how your analysis on QRE can be extended to more than 2 players?", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n+ The paper offers a thorough theoretical analysis of the feasibility, ambiguity, and complexity of reward recovery in Markov games. The analysis is grounded in well-established equilibrium concepts—Nash and Quantal Response Equilibrium (QRE)—from competitive game theory.\n+ The writing is clear and well-organized.\n\nWeaknesses:\n− The connection between the Nash and QRE analyses lacks consistency. While the Nash analysis applies to general Markov games with two or more players, the QRE results are restricted to the two-player setting.\n\n− In Theorem 4.1, it is unclear under what conditions the assumption—that two distinct opponent policies yield the same average reward for the player—can be realistically satisfied.\n\n− In Theorem 3.9, all equations and definitions referred should be included in the main paper, not in the appendix.", "was_revised": true, "final_justification": "Based on our post-rebuttal discussion, I will keep my rating. Thanks!", "rebuttal": "We thank the reviewer for their careful reading and valuable feedback. We are glad the reviewer found the paper *“clear and well-organized”* and appreciated its *”thorough theoretical analysis”*. \n\nBelow, we address the reviewer’s concerns in a detailed way.\n\n**Extension to n-player setting**\n\nWhile our QRE-based analysis is presented in the two-player setting for clarity, the framework can be naturally extended to the general $n$-player case. Specifically:\n\n\n- In Theorem 3.8 we would then have the sum of the total variation of the variations of the other players' policies.\n- In Theorem 3.9, as stated below the theorem, we would get an exponential dependency in the number of agents $\\mathcal{A}^n$. \n\nWe will clearly state in the introduction that we focus on the two-player case for readability, but the framework extends to $n$ players.\n\n**Average reward assumption**\n\n- The assumption that two distinct opponent policies yield the same average reward for a player can hold in various realistic settings. One example is a symmetric zero-sum game where the agent’s reward depends only on the final outcome (e.g., win/loss).\n- This assumption is also consistent with identifiability conditions in the single-agent inverse RL literature (e.g., [1]), where one needs to observe the same reward function across two MDPs. \n\n- Compared to the single-agent case, this assumption can be less restrictive as in the single-agent case, it is required to observe two different MDPs with different transition functions as well. On the other hand, in the multi-agent case, a different transition function can be induced by a different expert in the same Markov Game. Coming back to the example, one can consider a Tic-Tac-Toe game where one faces two different winning strategies; then the average reward function is the same, and the transition dynamics can be altered for the same Tic-Tac-Toe game. \n\n\n**Notations in the appendix**\n\nWe thank the reviewer for noting this and agree with the reviewer that all the notations should be included in the main paper instead of the appendix. As the final version allows an additional page, we include the necessary notation in the main section of the camera-ready version.\n\nOnce again,  we would like to thank the reviewer for their valuable feedback that helps us to improve the paper, and we are happy to answer any further questions that the reviewer might have.\n\n[1] Rolland, Paul, et al. \"Identifiability and generalizability from multiple experts in inverse reinforcement learning.\" Advances in Neural Information Processing Systems 35 (2022): 550-564."}]

Author rebuttal:

Meta-review: This paper makes nice progress on core challenges of understanding the theoretical underpinnings of MAIRL. At this stage I don't see any major outstanding concerns.  There was a lingering concern that the assumption in Theorem 4.1 may be on the strong side, but I am satisfied with the author's justification.  There are a number of constructive comments regarding the presentation that I encourage the authors to incorporate.
Decision: Accept (spotlight)