Decoding Rewards in Competitive Games: Inverse Game Theory with Entropy Regularization
Authors: Junyi Liao
Zihan Zhu
Ethan X Fang
Zhuoran Yang
Vahid Tarokh
Venue: ICML 2025 poster (2025)
Keywords: Inverse game; Quantal Response Equilibrium; Reward recovery; confidence sets
Primary area: reinforcement_learning->inverse
TL;DR: his paper introduces a unified framework for reward function recovery in two-player zero-sum matrix games and Markov games with entropy regularization.

Abstract: Estimating the unknown reward functions driving agents' behavior is a central challenge in inverse games and reinforcement learning. This paper introduces a unified framework for reward function recovery in two-player zero-sum matrix games and Markov games with entropy regularization. Given observed player strategies and actions, we aim to reconstruct the underlying reward functions. This task is challenging due to the inherent ambiguity of inverse problems, the non-uniqueness of feasible rewards, and limited observational data coverage. To address these challenges, we establish reward function identifiability using the quantal response equilibrium (QRE) under linear assumptions. Building on this theoretical foundation, we propose an algorithm to learn reward from observed actions, designed to capture all plausible reward parameters by constructing confidence sets. Our algorithm works in both static and dynamic settings and is adaptable to incorporate other methods, such as Maximum Likelihood Estimation (MLE). We provide strong theoretical guarantees for the reliability and sample-efficiency of our algorithm. Empirical results demonstrate the framework’s effectiveness in accurately recovering reward functions across various scenarios, offering new insights into decision-making in competitive environments.

Decoding Rewards in Competitive Games: Inverse Game Theory with Entropy Regularization
Junyi Liao' Zihan Zhu 2
Ethan X. Fang'
Zhuoran Yang²
Vahid Tarokh
|
Abstract
ment learning (IRL) (Ng & Russell, 2000; Arora & Doshi, 2020). While traditional reinforcement learning (RL) (Szepesvári, 2010; Sutton & Barto, 2018) focuses on solv- ing policies based on a known reward function, IRL inverts this process, aiming to infer the reward function from ob- served behavior. In competitive settings, such as two-player zero-sum games, this problem becomes even more compli- cated, as the agents' strategies depend not only on their own rewards but also their opponents' strategies (Wang & Klabjan, 2018; Savas et al., 2019; Wei et al., 2021). These challenges motivate the study of inverse game theory (Lin et al., 2014; Yu et al., 2019), which seeks to recover reward functions from observed strategies in competitive games.
Estimating the unknown reward functions driv- ing agents' behavior is a central challenge in in- verse games and reinforcement learning. This paper introduces a unified framework for reward function recovery in two-player zero-sum matrix games and Markov games with entropy regular- ization. Given observed player strategies and ac- tions, we aim to reconstruct the underlying re- ward functions. This task is challenging due to the inherent ambiguity of inverse problems, the uon-uniqueness of feasible rewards, and limited observational data coverage. To address these challenges, establish reward function identi- fiability using the quantal response equilibrium (QRE) under linear assumptions. Building on this theoretical foundation, we propose an algorithm to learn reward from observed actions, designed to capture all plausible reward parameters by con- structing confidence sets. Our algorithm works in both static and dynamic settings and is adapt- able to incorporate other methods, such as Maxi- mum Likelihood Estimation (MLE). We provide strong theoretical guarantees for the reliability and sample-efficiency of our algorithm. Empirical re- sults demonstrate the framework's s effectiveness accurately recovering reward functions across var- ious scenarios, offering new insights into decision- making in competitive environments.
From practical perspective, inferring the reward functions in competitive games has wide-ranging applications in eco- nomies, cyber security, robotics, and autonomous systems (Ng & Russell, 2000; Ziebart et al., 2008). Understand- ing the motivations behind players' actions in adversarial settings help optimize resource allocation cyber security (Michling et al., 2018), model strategic interactions in eco- nomic markets (Chow & Djavadian, 2015), or design better AI systems for competitive tasks (Huang et al., 2019).
Meanwhile, recovering reward functions in competitive games involves several key challenges: (i) Inverse problems are inherently ill-posed (Ahuja & Orlin, 2001; Yu et al., 2019), as multiple reward functions can lead the same optimal strategy and equilibrium solutions. A well-designed algorithm should not merely recover single reward func- tion but instead identify the entire set of feasible reward functions (Metelli et al., 2021; Lindner et al., 2022; Metelli et al., 2023). (ii) In an offline setting (Jarboui & Perchet, 2021), insufficient dataset coverage is also significant chal- lenge. Observed strategies often fail to comprehensively cover the state-action space, making difficult to ensure ro- bust reward function recovery. These challenges are further amplified in Markov games (Littman, 1994), where agents' strategies evolve dynamically over time, introducing addi- tional complexity in reward identification and estimation.
1. Introduction
Understanding the underlying reward functions that drive agents' behavior is a central problem in inverse reinforce-
'Department of Electrical and Computer Engincering, Duke University, Durham NC, USA 'Department of Statistics and Data Science, University of Pennsylvania, Philadelphia PA, USA 'Department of Statistics and Data Science, Yale Uni- versity, New Haven CT, USA. Correspondence to: Junyi Liao <junyi.liao@ www.liiaoduk..cuu>>.>
1.1. Major Contributions
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
We propose a unified framework for inverse game theory that addresses the identification and estimation of reward

---

Inverse Game Theory with Entropy Regularization
functions in competitive games in both static and dynamic settings. Our contribution is four-fold:
and machine learning (Konstantakopoullos al., 2017; Dong et al., 2018; Tan al., 2019).
Inverse reinforcement learning (Ng & Russell, 2000; Ziebart et al., 2008; Herman et al., 2016; Wulfmeier et al., 2016; Arora & Doshi, 2020) focuses on inferring the reward func- tion based on the observed behavior or strategy of agents and experts, which is crucial for understanding various decision- making processes, from single-agent processes (Boularias et al., 2011; I; Herman et al., 2016; Fu et al., 2018) to compet- itive or cooperative games (Vorobeychik et al., 2007; Ling et al., 2018; Wang & Klabjan, 2018; Wu et al., 2024). A popular approach within the field of IRL. is the Maximum Entropy IRL (Ziebart et al., 2008; Ziebart, 2018; Wulfmeier et al., 2016; Snoswell et al., 2020), which is based on the principle of maximum entropy and is provably efficient in handling uncertainty of agent behaviors (Snoswell et al., 2020; Gleave & Toyer, 2022) and high-dimensional obser- vations (Wulfmeier et al., 2016; Snoswell et al., 2020; Song et al., 2022).
Identification of Reward Functions: We study the iden- tification problem using the quantal response equilib- rium (QRE) under a linear assumption. We formally define the conditions for reward parameter identifiabi-- ity and characterize the feasible set when parameters are not uniquely identifiable.
Algorithm for Reward Estimation: Building on the identification results, we propose an algorithm that estimates reward functions by constructing confidence sets to capture all feasible reward parameters.
Extension to Markov Games: We extend our frame- work to entropy-regularized Markov games, combining reward recovery with transition kernel estimation to handle dynamic settings. This approach is designed to be sample-efficient and adaptable, incorporating meth- ods like Maximum Likelihood Estimation (MLE).
We provide rig- orous theoretical guarantees to establish the reliability and efficiency of our algorithm. Additionally, numeri- cal experiments demonstrate the effectiveness of our framework in accurately recovering reward functions across various competitive scenarios.
Theoretical and Empirical Validation:
Entropy Regularization in RL and Games. We use the entropy regularization in our framework, which has be- come a widely used techmique in reinforcement learning (Szepesvári, 2010; Ziebart, 2018) and game theory (Savas et al., 2019; Guan et al., 2021; Cen et al., 2023). Entropy regularization is provably effective in addressing challenges like exploration-expleee peplorationeeplliiatioon exploitationn tradeoff (Haarnoja et al., 2018: 18; Wang al., 2019; Ahmed et al., 2019; Neu et al., 2017), algorithm robustness (Zhao et al., 2020; Guo et al., 2021) and convergence acceleration (Cen et al., 2021; Cen et al., 2023; Zhan et al., 2023). Importantly, entropy regularization has also been shown to improve identifiability in inverse reinforcement learning (IRL.) problems. Recent works in single-agent IRL, such as Cao al. (2021) and Rolland et al. (2022), leverage entropy-reeullriized policies to transform ill posedd IRL problems into identifiable ones under mild assumptions. Our work builds on this insight by extending it to competitive multi-agent settings, where identifiability becomes even more subtle due to strategic interactions.
1.2. Related Work
Zero-sum Markov Games. The zero-sum Markov game (Shapley, 1953; Xie et al., 2020; Cen et al., 2023; Kalogian- nis & Panageas, 2023) models the competitive interactions between two players in dynamic environments. The solution typically focuses on finding equilibrium strategies (Nash Jr, 1951; McKelvey & Palfrey, 1995; Xie et al., 2020) where neither player can unilaterally improve their outcome. With a primary focus on learning in a sample-efficient manner, learning algorithms are proposed, including policy-bassi based methods (Cen al., 2021; Wei et al., 2021: Zhao et al., 2022; Cen al., 2023) and value-based methods (Xie et al., 2020; Chen et al., 2022; Kalogiannis & Panageas, 2023).
Paper Organization. In $2, we develop the framework of inverse game theory for entropy-regularized zero-sum games. In $3, we extend the framework introduced in $2 to sequential recision-making setting, focusing entropy- regularized zero-sum Markov games. We provide numerical experiments to validate the theoretical findings in $4, and conclude the paper in $5.
Inverse Optimization and Inverse Reinforcement Learn- ing (IRL). Inverse optimization (Ahuja & Orlin, 2001; Chan et al., 2022; Ahmadi et al., 2023) reverses the tradi- tional optimization process by taking observed decisions as input to infer an objective function (Ahuja & Orlin, 2001; Nourollahi & Ghate, 2018) and constraints (Chan & Kaw, 2019; Ghobadi& & Mahmoudzadeh, 2021) that make these decisions approximately
exactly optimal. In practice, inverse optimization offers a powerful framework for un- derstanding and modeling decision-making in complex sys- tems across fields like marketing (Chow& & Djavadian, 2015; Vatandoust et al., 2023), operations research (Brotcorne et al., 2005; Agarwal & Özlem Ergun, 2010; Yu et al., 2021),
Notations. We introduce some useful notation before proceeding. Throughout this paper, we denote the set 1, 2, ....... n by [n] for any positive integer n. For two posi- tive sequences (a and (b,)) we write a, = (b,,) or an S b, if there exists a positive constant C' such that an S C bb. For any integer d, we denote the d-
2

---

Inverse Game Theory with Entropy Regularization
dimensional Euclidean space by R4, with inner product (rr xTy y and the induced norm |>||| vx, For any matrix A = (a:s), the Frobenius norm of A is ||A||e 1E,, f. 2/3)1/2 and the operator norm (or spec- tral norm) of A is |Alpop 01 (A), where (A) stands for the largest singular value of A. For any square ma- trix = (aiz), denote its trace by tr(A) = Σ; az.. For nonempty set X, we denote by ( the space of all probability distributions on X.
(McKelvey & Palfrey, 1995). which satisfies the following fixed point equations:
enQ(a))
1r (a
for all a E A,
EncA enQla.)
(²)b) e ==
EBEB e=nQ(. for all b E B.
This non-linear system is equivalent the following +
2 linear constraints: for all A and 6 e B.
2. Retropy-Regularizeed Zero-Sum Matrix Games
{ ((0(a.)-00..))) -0.-)))QQ11,))))) Q(1, = =log(1' (a) (1))/n,
(I)
(00(,))-((.1)))) =-==' (b)/v/ (1))/n
We derive the inverse game theory for entropy-regularizee two-player zero-sum matrix games. We consider the iden- tification problem of payoff matrices under the linear para- metric assumption and derive a necessary and sufficient condition for strong identification. Furthermore, we pro- pose methods to recover identified sets and payoff matrices.
We study the inverse game theory for this entropy- regularized zero-sum game. To elaborate, we observe strat- egy pairs (a", bb) id (p", ,v*) follows the QRE, and we aim to recover all the feasible payoff functions Q(:,)).
Goal.
Identification of payoff matrices. To derive inverse game theory, it is important to study the identifiability of the pay- off matrix, i.e. there exists a unique payoff matrix that satisfies the QRE constraint. In this paper, we study the identification problem under the linear structure assump- tion ($2.2) and further generalize the analysis to the partial identification case ($2.3).
2.1. Preliminary and Problem Formulation
We consider a two-player zero-sum matrix game, which is specified by a triple (A, B, Q), where A = 21,2. m) and B- 21,2,-... n are finite sets of actions that players i E [1,2] can take, and (), is the payoff function. The zero-sum game can be formulated as the following min-max optimization problem
2.2. Strong Identification
T Qv, max min J
are the QRE for two players and use the observed data to obtain an estimation denoted by (f, D)) Next, we are going to estimate the payoff matrix from this estimated QRE To ensure the game is identifiable, we lever- age the following linear parametric assumption.
Suppose
where E A(A) and v E A(B) are policies for each player, and Q (Q(a, A,) E mR denotes the payoff matrix. The solution of this optimization problem is also known as the Nash equilibrium (Nash Jr, 1951), where both agents play the best response against the other agent.
Assumption 2.1 (Linear payoff functions). Suppose that there exists vector- vector-valued kernel A x B - Rd and vector 0" E Rdd such that ||0*|| < M for some M > 0, and
Two-Player Zero-Sum Matrix Game We study the entropy-regularized matrix game. Formally, this amounts to solving the following matrix game with entropy regularization (Mertikopoulos & Sandholm, 2016):
Q(a, b) (0(a, b),0")
for all (a, AX
To estimate the payoff matrix Q from the observed data, our essential goal is to estimate H* Under Assumption 2.1, the linear system (1) can be rewritten as follows: for all a E A and b B.
max min p T Qu + 1f H(()) - -1 HHv),, R
where 1) > 0 the regluarization parameter, and
-((1, v-, 9) = log(H" log(u"(a)/re) (a)/n((1))/n ((o(-.)) 1)) p², p²,0)
log(v>(b///) (b)/2* (1))/n
H(T) Σ m. log(T:))
where (o(a,.) - Φ(1, 1) vt, ( - ((,)))(1111) 1))_ 1² e Rd.
To simplify the notation, we define matrices
denotes the Shannon entropy (Shannon, 1948) of π. Accord- ing to the von-Neumann minimax theorem (von Neumann, 1928), there exists a unique solution (1*,,²") to this min- max problem, denoted as the quantal response equilibrium
A(v) = ((ó(a, - o(1. v))))))) E (m)-))xd
B(x) (()(:))- o), M)bEB/(1) ((
3

---

Inverse Game Theory with Entropy Regularization
and define vectors
Now we present the finite sample result of the sample com- plexity. In the two-step method, given dataset of agent actions following the true QRE, we first use consistent estimator to approximate the true QRE and obtain p., 17, then we use the estimated QRE to conduct the least square (5). Therefore, the sample complexity would be dependent on the convergence rate of the QRE estimator. A natural choice for QRE estimation is the frequency estimator.
c(p) = (log(ula)//())))/)ecc) E ER"11,
d(v) = (- (o-looovv00//(())/)))eeeee)) ER"
Then the linear constraints would be
A(er)] B(x²) [((x))
Td(ut)
Theorem 2.4 (Finite sample error bound). Given N sam- ples {(a (a,,,")) KEEN following the true QRE (u" v²), we obtain P. v by the frequency estimator. For any 5 E (0. 1). the estimation error bound of the payoff matrix holds with probability at least 1-
Since the linear system has m + n -2 constraints and the dimension of is d. Intuitively, if d S m + n 2 and the linear constraints are full rank, there most one solution of the above linear equations.
Proposition 2.2 (Necessary and sufficient condition for strong identification). Under Assumption 2.1, there is unique 0 E Rdd such that ((a,b) (øaa, b), 0) (i.e. 0 = 0*) for all (a, b) E A x B if and only if the QRE satisfies the rank condition
m² n² + (m + n) log(1/6)
I1 - 50
N
Theorem 2.4 provides a probabilistic guarantee for the accu- racy of the reconstructed payoff matrix Q in finite-sample setting. The bound explicitly depends on the sample size N, the action space dimensions m, n, and the confidence parameter 8, The estimation error decreases at a rate of ( (1)),, which is consistent with the standard empirical result of the frequency estimator (van der Vaart, 1998). As the sample size N increases, the errors of ğ and decrease, leading to more accurate reconstruction of the reward Q' On the other hand, the bound grows with the action space size in terms of m² + nē² indicating that larger action spaces require more samples to achieve the same estimation accuracy.
rank (A(r))) d.
(3)
Let the rank condition (3) hold, so that the game is strongly identifiable. In an offline setting, we propose a two-step method to estimate 0"
1. Estimate the QRE (H", 2²*) from the observed data and obtain (7z D).
2. Leverge (2) to estimate 0. To be specific, we conduct the least-square estimation and obtain 0:
2.3. Partial Identification
0 = arg min
AA())
0- - B(A)
[(() ((D))
(4)
If the rank condition (3) does not hold, there are infinitely many 0 E RRd that satisfy the QRE constraint (2). Under Assumption 2.1, the feasible set θ C Rd is
BER"
If the sample size is sufficiently large and TV x²) and TV (D, v*) are close to zero, the coefficient matrix in (4) is of full column rank, and can derive closed form for 0:
θ = 0
00 B(x²) [ 0 ==
A(v*)]
[e(p²) (d(")) : 1101 S M].
Since the true parameter 0" is partially identified, we con- struct a confidence set that contains the identified set with high probability. Given N strategy pairs following the true QRE, we first estimate the QRE from the observed data by frequency estimators p and D. Next, we select a threshold KN 0 and construct the confidence set as follows:
θ= = (( [A0] B())
A B())
1
AA() B
(5)
d())
Next, we derive the estimation error of the two-step method. Namely, given a finite sample bound for TV and (V v*), we aim to derive ||0 -0-0" 1-
Theorem 2.3 (Parameter estimation error). Let e and 62 be two small numbers satisfying 61 < minaa(m) 1º (a) and 22 < minsein] v²(b), (b). Under Assumption 2.1 and the rank condition in (3), suppose (f. i)) satisfies TV(p, 4²)= S e1/ and TV(P, v*) < e2/2, then 0 constructed by (4) satisfies
θN {0
0:
AA()) B())
0
[e(A) d(D)
I KN.
101
S
M
To recover the feasible payoff functions, we simply compute
Q(a. b) = aaa b) 9 for all Ø ê according to the linear assumption.
11 $ 2 m ( 11+ (1 n (G +1)

---

Inverse Game Theory with Entropy Regularization
We demonstrate the effectiveness of our Algorithm by es- tablishing its ability to construct accurate confidence sets. To be specific, we show that the confidence set θ is close to the identified set ( when the sample size N is large. The
Now we derive the estimation error bound ||0 10--0 0*1|- Theorem 2.6 (Convergence of the optimal QRE solution). Assume that the matrix
A(u*) B(ur) E RR (2(
key to approximating feasible set θ is to identify a suitable threshold Ky that makes the confidence set @ "similar" to
X =
O. The following theorem formalizes this intuition.
is ofll row rank, and its smallest singular value is bounded from below, that is, mm+n-2 (X) 2 To for some σG > O. Given N samples {(a bt) [NEIN) following the true QRE (1²x ,,),, we obtain (p. 2) by the frequency estimator. For any 5 E (0, 1), when N is sufficiently large, the sollowing estimation error bound of the optimal QRE solution holds with probability at least 1 5:
Theorem 2.5 (Convergence of confidence set), Let Assump- tion 2.1 hold. For each N E N. suppose we observe N samples {(a*, ( ]<EN] following the true QRE (n", ,,"), and calculate (7t, D) by the frequency estimator. Set the confidence set θr as in (6), where KN = O(N-1). Then 5,
with probability at least
@ ON) m + n +
(m- + n) log (1/6)
||0 - 10-1-11 1 m + V (m + n) log(1/6)
(7)
VN
VN
where dæ is the Hausdorff distance corresponding to the Euclidean distance in Rd.
In practice, selecting the minimum-norm solution helps avoid overfitting and promotes stability (Hastie et al., 2009). The convergence rate ((N-1/2) matches standard results in statistical estimation, showing the reliability and efficiency of our method in practical settings.
Theorem 2.5 establishes the asymptotic consistency of our confidence set nN in the finite-sample setting, showing that it converges the true feasible set O as the number of observed samples increases. The finite-sample bound (7) demonstrates that the estimation error decreases at the rate of O(N-1/2), which matches the standard concentration rate for empirical frequency estimators. The dependence on m and n highlights that larger action spaces require more samples for the same level of confidence. This result con- firms that our method provides both statistical consistency and well-characterizee finite-sample error bound, making it a robust approach for inverse game- game-theoretic inference.
3. Entropy-Regullrizee Zero-Sum Markov Games
In this section, we follow the same methodology in $2 and derive the inverse game theory for entropy-regularized two- player zero-sum Markov games.
3.1. Preliminary and Problem Formulation
We briefly review the setting of a two-player zero-sum Markov game (Littman, 1994), which is a framework that extends Markov decision processes (MDPs) to multi-agent settings, where two players with opposing objectives in- teract in a shared environment. A two-player zero-sum simultancous-moot episodic Markov game is defined by sextuple (S, A, B,r H), where
2.4. Selection in Confidence Sets
As discussed in $2.3, the true parameter 0* is partially iden- tifiable when the rank condition (3) does not hold, and there are infinitely many parameters that lead to the same QRE. To avoid unnecessary large coefficients that might overfit or lead to instability, we define the optimal solution 0* as the vector that satisfies the QRE constraints and has the minimum Euclidean norm, i.e.,
is the state space, with =s
A(x*)] subject to B(p²)) 8= To(pe)] ddv"))
A and B are two finite sets of actions that players
8* argmii||@@] 6
i {1,2} can take,
H E N is the number of time steps.
When the system is not full column rank, the minimum- norm solution of least square is uniquely determined by the PooreePenrose inverse (Ben-Israel & Greville, 2006):
. r (ra]eejz) is a collection of reward functions, and
. P = (Paheej is collection of transition kernels.
[A(*)] Te(p-)
g= =
At each time step h E [M], the players and simul- taneously take actions a E A and b E B respectively upon observing the state E S, and then player 1 receives the reward (s a, b), while player 2 receives -r) (s, a, b). Namely, the gain of one player equals the loss of the other. The system then transitions to a new state s' ~ Pa a, according to the transition kernel P,,.
[(xr)
d(v-)
Therefore, estimate the optimal parameter 0*, we propose the following plug-in estimator:
A(D)
(
ē
[(
d
5

---

Inverse Game Theory with Entropy Regularization
Entropy-regulartzee two-player zero-sum Markov game. We study the two-player zero-sum Markov game with tropy regularization. We use (u,v) to denote the policy of two players, where {ur Junthe and y f At step h, the entropy-regulariied V-function is
Goal. We study the inverse game theory for this entropy- regularized two-player zero-sum Markov game, where both the rewards (rx) and the transition kernels (IPr) are un- known. To elaborate, we observe i.i.d. trajectories
a(s..a) 6f), (s d'g 6ff herr)
(5)
= E
7 - [rr(ses az, bz) - 1 log ue (arlss)
following the QRE (n",, v²), and we aim to recover all the feasible reward functions r defined as follows.
+ n -o ui (b [s]] 8/
Definition 3.2 (Identified reward sets). Given state and ac- tion space x A B and quantal response equilibrium (1² ,,",, reward function S A x B - R is iden- tified if pa. Un. is the solution of the minimax problem (10)
where E
[0 is the discount factor and 7) > 0 is the parameter of regularization. Meanwhile,, we define the entropy-regularized Q-function that
induced by the reward function Th for all h E [H].
(s, b) = ra(s, a, b) + (BPx(-)saa)) [VFT))) (8)
3.2. Learning Reward Functions from Actions
For notation simplicity, we denote by (s) E mxxx the collection of Q-functions at the state s, which is the matrix [Qth" (8, a, (a,))exx With this notation, we may write
In this section, we propose algorithm to find all the feasible reward functions that lead to the QRE. We assume that both the reward function and transition kernel have a linear structure (Bradtke & Barto, 2004; Jin et al., 2020).
(s) = (s)s 11 (s) + (() - "Mpp)sss (s))
Assumption 3.3 (Linear MDP). For the underlying MDP, we assume that for every reward function ra S AxAxL B + [0, 1] and every transition kernel IP,, S x A B - A(S), there exist w/ Rd and (+) S - Rd such that
The equations (8) and (9) are also known as Bellman equa- tions for Markov games. In zero-sum game, one player seeks maximize the value function while the other player wants to minimize it:
rh a, b) = o(s, a, b) T) wh. Pa(-18, b) = lbs (.)))
(s) max min V. (s) min max VINi(s)) 1
1
Definition 3.1 (Quantal response equilibrium). For each time step h, there is a unique pair of optimal policies (ph P/)) of the entropy-regularizzed Markov game, i.e. the quantal response equílibrium (QRE), characterized by the following minimax problem:
for all (s, a) E A x B. In addition, the Q function is linear with respect to 6. Namely, for any QRE (H, v) and h E [H], there exists a vector 0n IRd such that
Qn(s, ((5, On.
Via
max min Va (s) Ph
min max VIL (8). Ph
We assume [ I 1, |0, S R. and || s Va for all h E [H] and s E S.
PB
which is equivalent to
Remark 3.4. In Assumption 3.3, since the reward functions Th are normalized to the unit interval [o, 1] and the number of time steps [H] is finite, every Q-function Qa must be bounded by some constant, and the constant R > H + log m log n) exists. Since (wx) can be recovered by (0x), we prefer to make an assumption on (0)) instead of (w)) for the convenience of subsequent analysis.
Vi max min (s) ( (s)pn())(s)
Ph
(10)
(s(pn(s)) - 17 (H(pnsss)
where ph S + ((A) is the policy followed by player and V/2 S > ABB is the policy followed by player 2, and H(TT) == - Σ, F, log(T,)) (T;) denotes the Shannon entropy of a distribution æ. Also, it is known that the unique solution of this minimax problem (QRE) satisfies the following fixed point equations:
We are going to find all the feasible wn. for all h E [H] under Assumption 3.3. Analogous to matrix games, first consider the identification problem of the Q-function. Namely, whether there is a unique 0₁ corresponding to the QRE. Given the equilibrium constraint (11), we propose the following theorem for strong identification.
pi(a|s) E (10066))))) Va E A,
Proposition 3.5 (Strong identification of Q-function). Un- der Assumption 3.3, for each h E [H], the Q-function (8 a, b) = Φ(8, a, b) 0r, is feasible for all (8, a, b)
(b]s)))) Edere (1 vb B.
(11)
6

---

Inverse Game Theory with Entropy Regularization
8 A x Bi 15 satisfies the following linear system:
3.3. Theoretical Guarantees
On = [en(8,14)) 14)
In this section, we present the theoretical results for our Algorithm. To begin with, we define the base metric to measure the distance between rewards.
for all s E S, (12)
(a
[n(s, 15)
where
(n(s, (10(s, a) (n) (a( ((0(8,;1) ((,,,,,) b)) pn (n (+1)))EBB\(1)
Definition 3.6 (Uniform metric for rewards). We define the metric d between any pair of rewards r' as
and
sup D(r,r))= (hssa
[( - (1,
(n() 11 log Ph (als)
E RR--!
Hun (1[s) REA((1)
We aim to recover the feasible reward set defined below. Definition 3.7 (Feasible reward set). We say reward func- tion r = (r1, ,TH) is feasible with respect to a quantal response equilibrium μ and v if the Q function Q = (Q1. Q2. Qu) satisfies the identifability condi- tion (11) and the norm constraint [|0]]] S R. We denote R as the feasible reward set corresponding to the quantal response equilibrium μ and v, namely,
(b|s)
vn) log Vn (1[s) BEB((1)
E RR-1
Moreover, there exists a unique On E Rdd if only if the QRE satisfies the rank condition
rank ([An(P))
(L(A)) d.
(13)
where
A1,1,
Bi, (1,
(2,
(2,
R r- (21, ,TH): is identified and
(vk)
Ba(mn)= =
:
(l))
(I(()),
|wn + +7 Σ Th (s) s R for all h e [M]
Following the Bellman equation (8), rh a feasible reward function iff there exists feasible Q function Qn and V function Va+1 such that
SES
Also, we denote Q as the feasible Q function set:
@ = (QO)) Q is identified and ||0^]| S R, vh [H]]
(s, a. b) = Qu. a, b) - -Ep,(-1.,0))) (V)+1 (14)
Next, we propose algorithm to recover the feasible reward functions. For all h [H], the algorithm performs the following four steps:
Our formulation provides a principled way to handle partial identifiability in Markov games. Instead of foreing single estimated reward function, we construct a structured set of feasible rewards, which offers more robust approach to analyzing decision-making in complex multi-step strategic settings. Intuitively, the norm constraint ||0,]| < R plays a key role in ensuring that the estimated reward functions remain well-conditioned, and do not include arbitrarily large coefficients. Additionally, by linking the feasible reward set to the recursive Bellman equations (8)-(9), our defini- tion ensures that every element of R maintains temporal consistency. In other words, the inferred rewards lead to equilibrium strategies that are valid over multiple decision- making steps.
Recover the feasible set by solving the least square problem associated with the linear system (12):
|101|= S R:
|10||
[ 0
(AN
Te (Pa) di (Pr)
|
S Kh
(15)
Calculate the feasible Q and V functions (Qn, and Vi,) for all 0, ①
Estimate the transition kernel PA from the observed data. Since the transition kernel has linear structure, we employ ridge regression for estimation:
For the sake of clarity, we fix the initial state distribu- tion in the Markov game Pl E A(S), and define the marginal state visitation distributions associated with poli- cies μu, at each time step h [H] as ds) = P(s slpi, n4, v). Also, write the state-action visitation distri- butions as (s, blp,, V)
An Σ Shs ah ()) 6T) ALd,
PA Vht1 a, b) = Ø(s, a, b) A,1
8, ah = a, ba PP(sh
Msh of, bl) V (sh
To control the uniform metric in Definition 3.6, we require an estimator of the QRE that performs uniformly well across
Recover feasible set R₂ by the Bellman equation (14).
7

---

Inverse Game Theory with Entropy Regularization
all states 8 E S. When using frequency estimators to ap- proximate the policies 1 (-Is) and vz (ss),, the estimation at each state is conducted independently. As result, it is essential that the dataset sufficiently covers all states in S to obtain reliable estimates. To ensure this, we impose the following assumption, which guarantees that every state is visited with a minimum frequency throughout the horizon. Assumption 3.8 (C-well-posedness)). There exists a con- stant C > 0 such that
statistically reliable and sample-efficient. The explicit de- pendence on problem parameters offers insights into how exploration, feature representations, and action space size affect the difficulty of inverse reward learning in Markov games.
We also note that the condition that Vn, is nonsingular en- sures that the feature representation provides sufficient in- formation for parameter recovery (Tu & Recht, 2017; Min et al., 2022). The norm || | appears in the sample complexity bound, indicating that ill-conditioned feature matrices lead to larger estimation errors and require more samples to achieve the same level of accuracy.
(s) 2
for all 8 E 8 and h E [M]
In addition, instead of relying solely on frequency estima- tors for QRE estimation, we can extend our framework to integrate Maximum Likelihood Estimation (MLE) into our method and establish convergence result with the same 7-1/2 rate.
Now are ready present the theoretical results for the proposed algorithm.
Theorem 3.9 (Sample complexity of constructing feasible reward set). Under Assumptions 3.3 and 3.8, let Ph = d' be the stationary distribution associated with optimal policies ke and v", where h E [H]. We assume that the following x d matrix
4. Numerical Experiments
In this section, we implement our reward-learning algo- rithm and conduct numerical experiments in both entropy- regularized zero-sum matrix games and Markov games. All experiments are conducted in Google Colab, In this section we consider only two-player entropy regullazee entropy- regularized zero-sum Markov games.
Vn= = Epn. [o(s, On, ba) an. bn)
is nonsingular for all h E [H] Let R be the feasi- ble reward set given in Definition 3.7. Given dataset we set X =
D = +{Da)hein = [((s), aiy, ((1), Kr. = (T- and let R be the outpul of our Algo- rithm.. Let =
ae {uz (als), vf (b)s)). For any 5 10, let T > O be sufficiently large,
Setup. We define the kernel function é : A x B + Rd with dimension d' = 2, and set the true parameter W/. that specifying reward functions to be
1
2HS
16(m Vn)
4HS
T 2 max
C
log
C
log
8
w = -0.8, 006)
512 | 1 12
log
2Hd
4 llop
for all steps h E [H]. We set the sizes of action spaces to be m = and n = 5, the size of state space = 4, and the horizon H 6. The entropy regularization term is r) = 0.5.
Then the following inequality holds with probability at least 1 35:
We implement the algorithm proposed in $3.2. In each experiment, our algorithm outputs parameter 0n in the confidence set 2₁. We set the bound of feasible parameters Og to be R 10, and set the threshold K; = 10 10 where N is the sample size. The regularization term in ridge regression is = 0.01.
1
(Vs(mm + n) log
HS log
D(R. R) S
T
vT
5
+ (m + nil log HS
+ +VSdd+ v T) log(mm)
where D is the Hausdorff distance corresponding the uniform metric in Definition 3.6.
Metrics. We evaluate the performance of our algorithm using two metrics: (1) the error in the estimated reward function (fr). which measures how accurately the recon- structed payoff function matches the true reward function; and (2) the error in the estimated QRE, which quantifies the discrepancy between the QRE (Ti D) derived from the estimated payoff function and the true QRE (μ², (H²,""). We are particularly interested in the error in the estimated QRE, which validates whether the reconstructed reward functions interpret the observed strategy.
Theorem 3.9 provides a strong guarantee on the accuracy of reward recovery algorithm in Markov games. Our bound shows that the distance (R,, R. diminishes at the rate of 0(2-1/2), which matches the optimal statistical rate for empirical risk minimization problems. This demonstrates that with sufficient data, the estimated reward functions remain close to the true feasible set, making our method
8

---

Inverse Game Theory with Entropy Regularization
Results. As shown in Figures 1, 2 and Table I, the overall error of our algorithm's output decreases the sample size N increases from 10s to 10s, demonstrating the improved accuracy of our approach with more data. While the esti- mation error of reward functions (Fr)h=2 can be relatively large, the corresponding QRE (āt, Pa) remains well-aligned with the true QRE (ui (1)). Although some fluctuations are observed across time steps, the error remains small, espe- cially for larger sample sizes. These results confirm that our method for reward estimation in Markov games is both statistically consistent and sample-efficient.
Estimated Reward Error with 95% CI
3.0
2.5
Estimated Reward
2.0
1.5
N 10000
1.0
N 50000
N 100000
0.5
5
6
Time Step
5. Conclusion
Figure I. The reconstruction error of the reward functions (Fr )==1- The X-axis represents the time step lt from 1 to 6, while the Y-axis represents the error | rill> of the reward function P.
To conclude, we explore the challenge of recovering re- ward functions that explain agents' behavior in competitive games, with focus the catropy-regularizer zero-sum setting. We propose framework of inverse game theory concerning the underlying reward mechanisms driving ob- served behaviors, which applies to both the static setting ($2) and the dynamic setting ($3).
QRE Error with 95% CI
Under a linear assumption, we develop a novel approach for the identifiability of the parameter specifying the current- time payoff. To move forward, we develop offline algo- rithm unifying QRE estimation, confidence set construction, transition kernel estimation, and reward recovery, and es- tablish its convergence properties under regular conditions. Additionally, we adapt this algorithm to incorporate a MLE approach and provide theoretical guarantees for the adapted version. Our algorithms are reliable and effective in both static and dynamic settings, even in the presence of high- dimensional parameter spaces or rank deficiencies.
0.005
QHE Error (log
N 10000
= 20000
0.001
N 100000
4
5
Timr Slep
Figure 2. The discrepancy between the QRE (7, D) correspond- ing the estimated reward functions (Fr) and the true QRE ("',")) The X-axis represents the time step h from 1 to 6, while the Y-axis represents the errors TV (Th, ph) + (V
Future directions include exploring more complicated game settings, such as partially observable games and non-linear payoff functions, and extending the framework to online learning setting. Mcanwhile, this research contributes to the broader effort to make competitive systems more inter- pretable, offering valuable insights at the intersection of game theory and reinforcement learning.
Reward Error
Sample Size
Mean
95% CI
10,000
2.4611
= 0.1559
20,000
1.9031
0.1008
Impact Statement
50,000
1.5609
= 0.0663
100,000
1.4398
+ 0.0499
This work advances the field of inverse reinforcement learn- ing and game theory by introducing a unified framework for reward function identification and estimation in competitive multi-agent settings. Our findings contribute understanding of deeiisionmmaingg in strategic environments, with potential applications in economics, automated negoti- ation, and multi multi-agent AI systems.
QRE Error
Sample Size
Mean
95% CI
deeper
10,000
7.08 x 10-3
#466 x 10
20,000
5.11 x 10-3
#3111 x 10-4
50,000
3.28 x 10-3
1.70 X 10-4
100,000
2.41 x 10-3
1.41 X 10-4
While our research provides theoretical and methodological advancements, we acknowledge potential ethical considera- tions. The ability to infer reward functions from observed
Table 1. Mean error and 95% confidence intervals for reward and QRE estimation over repetitions the Markov game setting. across all time steps.

---

Inverse Game Theory with Entropy Regularization
behavior could be used both positively-to enhance trans- parency in Al decision-making and improve algorithmic fairness-and negatively, if applied to manipulate exploit agents in competitive settings. Ensuring the responsible application of this work will require careful consideration of ethical safeguards and alignment with societal values.
Bradtke, S. J. and Barto, A. G. Linear least-squares al- gorithms for temporal difference learning. Machine Learning, 22:33-57, 2004. URL https:/ /api. http:/orrpSID:113110
semanticscholat
Brotcome,, L., Marcotte, P., Savard, G., and WIART, M. Joint pricing and network capacity setting problem. 01 2005.
Overall, this paper aims advance Machine Learning and Game Theory research, and we do not foresce immediate societal risks. However, encourage further discussion the ethical implications of inverse game theory in real-world applications.
Cao, H., Cohen, S., and Szpruch, L. Identifiability in inverse reinforcement learning. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, W. (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 12362-12373, Curran Associates, Inc.. 2021. URL https: http:////cccceeeegeeeeeoe neuripp cc/ feaper_filaee Seeperr_fileesppppe//2/////// 6 7 pdf.
References
Agarwal, R. and Özlem Ergun. Network Design and Allocation Mechanisms for Carrier Alliances in Liner Shipping. Operations Research, 58(6):1726 1742, December 2010. doi: 10.1287/opre. 1100.
Paper.
0848. http:t crop2ee/y552201016117---7778
rwwpeeereeeeeeeeeeeeeeeeoeopeeee waagg///iini a/inm/
Cen, S., Cheng, C., Chen, Y., Wei, Y., and Chi, Y. Fast global convergence of natural policy gradient methods with en- tropy regularization, 2021. URL https://arxiv:
Ahmadi, F., Ganjkhanloo, F., and Ghobadi, K. Inverse learn- ing: Solving partially known models using inverse op- timization, 2023. URL https:://axxiei org/ abs/ 2011.03033
org/ abs / 2007 100000.000 06558.
Cen, S., Wei, Y., and Chi, Y. Fast policy extragradient methods for competitive games with entropy regulariza- tion, 2023. URL https:: /ttpaaaxiivvv./////v//e/e/eaaava org/ abs 21055 15186.
Ahmed, Z., Le Roux, N., Norouzi, M., and Schuurmans, D. Understanding the impact of entropy on policy opti- mization. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Conference on Ma- chine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 151-160. PMLR, 09-15 15 Jun 2019. URL https: httpp:://ppotttoo http:////occeeeneeeeeeeee mlr http:///w...........ee...eeee press/v97/ ahmed1 9a. html.
Chan, T. C. Y. and Kaw, N. Inverse optimization for the recovery of constraint parameters, 2019. URL https: //arxiv. www.abgg////....o..o.........o.o wwtpx//.ogg/bb//1111.... 00726.
Chan, T. C. Y., Mahmood, R., and Zhu, I. Y. Inverse optimization: Theory and applications, 2022. URL https: httpss//axxivvv.voo
Ahuja, R. and Orlin, J. Inverse optimization. Operations Re- search, 49, 06 2001. doi: 10. 10.1287/opr.49...7771.0000
Chen, Z., Ma. S., and Zhou, Y. Sample efficient stochas- tie policy extragradient algorithm for zero-sum markov game. In International Conference on Learning Represen- tations, 2022. URL https: openrevieeeeeeeeeeeeeeeeeeeeeeee nnt// forum dieendddIIIvvxxeeeee
Arora, S. and Doshi, P. A survey of inverse reinforcement learning: Challenges, methods and progress, 2020. URL https://arxiss //t.x/ixvvvrr./.. org/ ats///////////a//////g////aaaera 1106.068777 06877.
Ben-Israel, A. and Greville, T. Generalized In- verses: Theory and Applications. CMS Books in Mathematics. Springer New York, 2006. ISBN 9780387216348. URL https:///////. boocks.google. comm/books71t-=abEPPAAAa.
Chow, Y. and Djavadian, Activity- market equilib- rium for capacitated multimodal transport systems. Trans- portation Research Procedia, 7:2-23, 2015, ISSN 2352- 1465. doi:
com/ 21 International Symposium on Transportation and Traffic Theory Kobe, Japan, 5-7 August, 2015.
URL science/artiiiiooc sitiene//rrtccee///////222222210
Boularias, A., Kober, J., and Peters, J. Relative entropy inverse reinforcement learning. In Gordon, G., Dunson, D., and Dudík, M. (eds.), Proceedings of the Fourteenth International Conference Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pp. 182-189, Fort Lauderdale, FL, USA, 11- 13 Apr 2011. PMLR. URL hitps: StRLutttts//rccccciiioo /ptpceeeiggg..... ml r. press /v15 wwt.///bolllrrr
Dong, C., Chen, Y., and Zeng. B. Generalized inverse optimization through online learning. In Bengio. S., Wal- lach, H., Larochelle, H., Grauman, K., Resa-Bianchi N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc.,
html.
10

---

Inverse Game Theory with Entropy Regularization
2018. URL httpss//prcceeeenn....rrree
Jin, C., Yang. Z., Wang, Z., and Jordan, M. Prov- ably efficient reinforcement learning with linear func- tion approximation. In Abernethy, J. and Agarwal, S. (eds.), Proceedings of Thirty Third Conference on Learn- ing Theory, volume 125 of Proceedings of Machine Learning Research, pp. 2137-2143. PMLR, 09-12 Jul 2020. URL https: ptatttss:/proceeeeeeeee http///eoooeeeneeeeeeeeee/e ml press/ v125/jin22 html.
cc/ppppe__ffleesspperr////////1 B pdf.
Paper.
Fu, J., Luo, K., and Levine, S. Learning robust rewards with adversarial inverse reinforcement learning, 2018. URL. https:/ http:////aaiio.o.aa/////////
11248.
Ghobadi, K. and Mahmoudzadch, H. Inferring linear feasi- ble regions using inverse optimization. European Journal of Operational Research, 290(3):829-843, 2021. ISSN 0377-2217. doi: https://bbiiagg/llolol1l....:222
Kalogiannis, F. and Panageas, I. Zero-sum polymatrix markov games: Equilibrium collapse and efficient com- Oh, A., Naumann, T., putation nash equilibria.
Globerson, A., Saenko, K.. Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Sys- tems, volume 36, pp. 59996-60020. Curran Associates, Inc., 2023.
048. URL htt.LL/LLtttt////ee/eeeeeeedeeed com/ osieenee//rttcee//////7777722322
Gleave, A. and Toyer, S. A primer maximum causal entropy inverse reinforcement learning, 2022. URL pettps:/arrxinn http:/aawwi.ggaaaaaaa//aaa wwtg/agg////oooooooo/....t....re htrgg/bb/2223333 2203.222..222 11409.
Konstantakopoulos, I., Ratliff, L., Jin, M., Sastry, S., and Spanos, C. A robust utility learning framework via in- verse optimization. IEEE Transactions on Control Sys- tems Technology, PP, 04 2017. doi: 10.1109/TCST.217. 2699163.
Guan, Y. Zhang, Q. and Tsiotras, P. Learning nash equilibria in zero-sum stochastic games via entropy- regularized policy approximation, 2021. URL https: //arxiv. wrw. /2t. 00162.
Langley, Crafting papers on machine learning. In Langley, P. (ed.), Proceedings of the 17th International Conference Machine Learning (ICML 2000), pp. 1207-1216, Stan- ford, CA, 2000. Morgan Kaufmann.
Guo, X., Xu, R., and Zariphopoulou, T. Entropy regular- ization for mean field games with learning, 2021. URL https:/ //tp///xvvvv/////////////////avv wwt.aiiww./....aaaa.......oooere abs 2010 0 000455
Lin, X., Beling, P., and Cogill, R. Multi-agen, inverse reinforcement learning for zero-sum games. IEEE Trans- actions Computational Intelligence and AI in Games, PP, 03 2014. doi: 10. 20.119///II
Haarnoja, T., Zhou, A., Abbeel, P., and Levine, S. Soft actor- critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor, 2018. URL https: // //arxiv. org/ abs/ /wt../11...000 01290.
Lindner, D., Krause, A., and Ramponi, G. Active ex- ploration for inverse reinforcement learning. In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K. (eds.), Advances in Neural Information Processing Systems, 2022. URL https: http:///ppeeeeeeeeeeeeeeeeeeeeee net forum? id=TPOJzwY2pc.
Hastie, T., Tibshirani, R., and Friedman, The Elements of Statistical Learning: Data Mining, Inference, and Predic- tion. Springer series in statisties. Springer, 2009. ISBN 9780387848846. URL ht:ps: /wwoks..../// google.
Herman, M., Gindele, T., Wagner, J., Schmitt, F., and Bur- gard, W. Inverse reinforcement learning with simultane- ous estimation of rewards and dynamics. Gretton, A. and Robert, C. C. (eds.), Proceedings of the 19th Interna- tional Conference Artificial Intelligence and Statistics, volume 51 of Proceedings of Machine Learning Research, pp. 102-110, Cadiz, Spain, 09-11 May 2016. PMLR. URL https: /proceedingss mlr. www..prress.... wwwps/rsssss1. herman16 html.
Ling, C. K., Fang, F., and Kolter, J. Z. What game we playing? end-to-end learning in normal and exten- sive form games, 2018. URL httttps://axxi..rrt
02777.
Littman, M. L. Markov games framework for multi-agent reinforeement learning. In Cohen, W. W. and Hirsh, H. (eds.), Machine Learning Proceedings 1994, pp. 157-163. Morgan Kaufmann, San Francisco (CA), doi: https://doi.or//
1994. ISBN 978-1-55860-33-
Huang, S., Held, D., Abbeel, P., and Dragan, A. Enabling robots to communicate their objectives. Autonomous Robots, 43, 02 2019. doi: 10. 10.10077/105114-11--7777
1- w/wp:./ciennedirreetccccoocceeee URL https: arriclle/pi1/9911115883333333
Jarboui, F. and Perchet, V. Offline inverse reinforcement learning, 2021. URL https:://// / //t////rxia /atxiv.vvvv./////////a////aaaava org/ abs/ 1..06.00 05068.
McKelvey, R. D. and Palfrey, T. R. Quantal re- sponse equilibria for normal form games. Games and Economic Behavior, 10(1):6-38, 1995. ISSN

---

Inverse Game Theory with Entropy Regularization
0899-8256. doi: http:///di...o./0..0000000//aaa
Rolland, P., Viano, L.,, Schürhoff, N., Nikolov, B., and Cevher, V. Identifiability and generalizability from multi- ple experts in inverse reinforcement learning. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Process- ing Systems, volume 35, pp. 550-564. Curran Associates, Inc., 2022.
1023. wtt.httpss//www.ccccc..... rect. com/ sccbaccc/arricee///////392223993
Mertikopoulos, P. and Sandholm, H. Learning in games via reinforcement and regularization. Math. Oper. Res., 41(4):1297-1324, November 2016. ISSN 0364-765X.
Metelli, A. M., Ramponi, G., Concetti, A., and Restelli, M. Provably efficient learning of transferable re- wards. In Meila, M. and Zhang, T. (eds.), Pro- ceedings of the 38th International Conference on Ma- chine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 7665-7676. PMLR, 18-24 Jul 2021.
Savas, Y., Ahmadi, M., Tanaka, T., and Topcu, U. Entropy- regularized stochastic games. In 2019 IEEE 58th Con- ference on Decision and Control (CDC), pp. 5955-5962, 2019. doi: 10.1 (.LL09/CDDCA00022209999999999999
Shannon, C. E. A mathematical theory of communication.
http://pocceeeeneeeeeeeeeeeeesee mwr. press/ v139 (339/mmteeli2200 html.
The Bell System Technical Journal, 27(3):379-422) 1948. doi: 10. 15300 1308.1948.tbbl... 19...............
Shapley, L. S. Stochastic games*. Proceedings of the National Academy of Sciences, 39:1095 1100, 1953, URL https: www.:esssmaaiiscoo....oo o arg/CorpusTD::6333 4073.
Metelli, A. M., Lazzati, F., and Restelli, M. Towards the- oretical understanding of inverse reinforcement learn- ing. In Krause, A., Brunskill, E., Cho, K., Engel- hardt, B., Sabato, S., and Scarlett, J. (eds.), Proceed- ings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learn- ing Research, pp. 24555-24591. PMLR, 23-29 Jul 2023. URL http///pcceeeig....cem mlr mr.sspress/ 0202/mete// 00002meteeli23a.lii htmi.
Snoswell, J., Singh, N., and Ye, N. Revisiting maximum entropy inverse reinforcement learning: New perspectives and algorithms. In 2020 IEEE Symposiuun Se- ries Computational Intelligence (SSCI), pp. 241-249. IEEE, December 2020. doi: 10. 00.119//sc447808.22000 9308391. URL http: / dx doi. www.d/oooor.....0//0.000 SSCI47803 2020. 001220..33880 9308391.
Miehling, E., Rasouli, M., and Teneketzis, D. A pomdp approach to the dynamic defense of large-scale cyber networks. IEEE Transactions on Information Forensics and Security, 13(10):2490-2555, 2018. doi: 10.1109/ TIFS.2018.281999
Song, I.., Li, D., Wang, X., and Xu, X. Ad- aboost maximum entropy deep inverse reinforce- ment learning with truncated gradient. Informa- tion Sciences, 602:328-350, 2022. ISSN 00200 0255. doi: https://oo.orp//.000//......0..0 017. URL setennee/arriccee//////222333330
Min, Y., Wang, T., Zhou, D., and Gu, Q. Variance-aware off-policy evaluation with linear function approxima- tion, 2022. URL https:/ orgbass/////////// /2106 11 119
Sutton, R. S. and Barto, A. G. Reinforcement Learning: An Introduction. A Bradford Book, Cambridge, MA, USA, 2018. ISBN 0262039249.
Nash Jr, Non-cooperative games. Annals of Mathematics, 54(2):286-255, 1951. ISSN 0003486X, 19398980. URL http://wwa. jstor. httpe//or///ttabeeebeeeeeeeeeee
Szepesvári, C. Algorithmss for Reinforcement Learn- ing, volume 4. 01 2010. doi: 10.2200/ S00268EDIV01 Y20100011000000
Neu, G., Jonsson, A., and Gómez, V. unified view of entropy-regularrized markov decision processes, 2017. URL htRp:t/:::/ /aariv..///iv////a wttpg//gg//...////ooooo 07798.
Tan, Y., Delong, A., and Terekhov, D. Deep inverse op- timization. In Rousseau, L.-M. and Stergiou, K. (eds.), Integration of Constraint Programmingg Artificial Intel- ligence, and Operations Research, pp. 540-556, Cham, 2019. Springer International Publishing. ISBN 978-3- 030-19212-9.
Ng, A. Y. and Russell, S. J. Algorithms for inverse rein- forcement learning. Proceedings of the Seventeenth International Conference on Machine Learning, ICML 00. pp. 663-670. San Francisco, CA. USA, 2000. Mor- gan Kaufmann Publishers Inc. ISBN 1558607072.
Nourollahi, S. and Ghate, A. Inverse optimization mini- mum cost flow problems on countably infinite networks. Networks, 73, 11 2018, doi: 10.1002//et.21862.
Tu, S. and Recht, B. Least-squares temporal difference learning for the linear quadratic regulator, 2017. URL https:/ https///axxw..oo/ab///o///s 08642.
12

---

Inverse Game Theory with Entropy Regularization
van der Vaart, A. W. Asymptotic Statistics. Cambridge Series in Statistical and Probabilistic Mathematics. Cam- bridge University Press, 1998.
of Machine Learning Research, pp. 3674-3682. PMLR, 09-12 Jul 2020. URL https: httpas:///occoeoeeeeeee mir. wttpppssss/..iiie2e/000
Vatandoust, B., 7ad, B. B., Vallée, F., Toubeau, J.-F. and Bruninx, K. Integrated forecasting and scheduling of im- plicit demand response in balancing markets using inverse optimization. In 2023 19th International Conference on the European Energy Market (EEM), pp. 1-6, 2023. doi: 10.1 10.10099EM55333.22222. 10161818.
Yu, L., Song, J., and Ermon, S. Multi-agent adversarial inverse reinforcement learning, 2019. URL https://
a arxiv.org/ai abs 9977 13220.
Yu, S., Wang, H., and Dong, C. Learning risk prefer- ences from investment portfolios using inverse optimiza- tion, 2021. URL https: aaaaaaxiivv.... org/ httpiv..rrgbbbs/11111 abs/2010. 01 016.7
von Neumann, J. Zur theorie der gesellschaftsspiele. Math- ematische Annalen, 100:295-320, 1928. URL https: //api. www.sseeaannccchceeeeeee org/CorpusID: 122961988.
Zhan, W., Cen, S., Huang, B., Chen, Y., Lee, J. D., and Chi, Y. Policy mirror descent for regularized reinforce- ment learning: A generalized framework with linear con- vergence, 2023, URL pettps://arten orgg /abs/ 2105.11065.
Vorobeychik, Y., Wellman, M. P., and Singh, Learning payoff functions in infinite games. Mach. Learn., 67(1-2): 145-168, May 2007. ISSN 0885-6125. doi: 10.1007/
110994-007--7115-8. URL httt::::/doo..org///// 000--100009900007-5-5-----
Zhao, L., Liu, T., Peng, X., and Metaxas, D. Maximum- entropy adversarial data augmentation for improved generalization and robustness. In Larochelle, H. Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 14435-14447, Curran Associates, Inc., 2020. URL httt::::/prooeeedngggeeeeeee cc fc/ppape__files/pppppeeeeeee /c//appee_f.lee//pppe///////// a 350rcc80776446ddee95554333333333 pdf.
Wang, H., Zariphopoulou, T., and Zhou, X. Exploration versus exploitation in reinforcement learning: stochastic control approach, 2019. URL https: /ttpxvx.xvv.g/////..... abs/1812 01552.
Wang. X. and Klabjan, D. Competitive multi-agent in- verse reinforcement learning with sub-optimal demon- strations. In Dy, J. and Krause, A. (eds.), Proceed- ings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learn- ing Research, pp. 5143-5151, PMLR, 10-15 Jul 2018. https:::: http:///po/ed/ggeeeeeee mlr. press/v80/ mangl8ddhtm...
Zhao, Y. Tian, Y., Lee, J., and Du, S. Provably ef- ficient policy optimization for two-player zero-sum markov games. In Camps-Valls, G., Ruiz, F. R., and Valera, I. (eds.), Proceedings of The 25th Interna- tional Conference Artificial Intelligence and Statis- tics, volume 151 of Proceedings of Machine Learn- ing Research, pp. 2736-2761 PMLR, 28-30 Mar 2022. URL https: wtwptttss///ppoeeeteeee v151 2ha.22b....bb..... html.
Wei, C.-Y., Lee, C.-W., Zhang, M., and Luo, H. Last- iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive markov games, 2021. URL htttt::/aaaatti //tp///aavvv//////////ee//aaa/ org/o//g//oooo /bs/ 2102. 04540.
Ziebart, B. D. Modeling Purposeful Adaptive Behavior with the Principle of Maximum Causal Entropy. 7 2018. doi: 10. N0.118//116720692.1
Wu, J., Shen, W., Fang, F., and Xu, H. Inverse game theory for stackelberg games: the blessing bounded rationality. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS '22, Red Hook, NY, USA, 2024, Curran Associates Inc ISBN 9781713871088.
Ziebart, B. D., Maas, A. I.., Bagnell, J. A., and Dey, A. K. Maximum entropy inverse reinforcement learn- ing. In AAAI Conference on Artificial Intelligence, 2008. URL https: / //ppp/app...a/aa semant icscholar. org org/Corpp axg/CorrpssD:333219
Wulfmeier, M., Ondruska, P., and Posner, I. Maximum entropy deep inverse reinforcement learning, 2016. URL ht https: http:://axxivv /aaaaiiiiiv//// org abs//b/1/ 04888.
Xie, Q., Chen, Y., Wang, 7.,, and Yang, Z. Learning zero- sum simultancous- markov games using function ap- proximation and correlated equilibrium. In Abernethy, and Agarwal, S. c.ds.). Proceedings of Thirty Third Con- ference on Learning Theory, volume 125 of Proceedings
13


Reviews:
[{"review_id": "cpEmCsp0JJ", "reviewer": "Reviewer_Jg64", "summary": "The submission considers inverse reinforcement learning in games. Specifically, the authors first study the conditions for the problem to identifiable, and the propose a methodology to estimate the reward function. Both theoretical analysis and empirical results are provided to justify the proposed method.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nThank you for your valuable feedback and for recognizing the relevance and significance of our contributions. Below, we address your concerns regarding the necessity of the rank condition (Proposition 2.2), comparisons with related works, and competing methods in experiments.\n\n#### Necessity of the Rank Condition (Proposition 2.2)\nWe apologize for our unclear statement in Proposition. The submitted version of the paper may not clarify the necessary conditions and their assumptions. In fact, the reward parameter is uniquely solvable **if and only if** the rank condition holds, and the logic is derived in previous contents.\n\n- $(\\mu^*,\\nu^*)$ is the quantal response equilibrium (QRE) corresponding to $Q$ if and only if the following QRE constraint is satisfied:\n$$\n\\mu^*(a)= \\frac{e^{\\eta Q(a,\\cdot)\\nu^*}}{\\sum_{a\\in\\mathcal{A}}e^{\\eta Q(a,\\cdot)\\nu^*}}\\ \\text{for all}\\ a\\in\\mathcal{A},\\quad\n\\nu^*(b)= \\frac{e^{-\\eta  Q(\\cdot,b)^\\top\\mu^*}}{\\sum_{b\\in\\mathcal{B}}e^{-\\eta  Q(\\cdot,b)^\\top\\mu^*}}\\ \\text{for all}\\ b\\in\\mathcal{B}.\n$$\n- Under the linear assumption, the above non-linear system is equivalent to the linear system (2).\n- According to our model assumption, this linear system has at least one solution $\\theta=\\theta^*$. The solution is unique if and only if the rank condition (3) is satisfied.\n\nWe will correct our statement in a later version. We hope this clarification solves your confusion.\n\n#### Comparisons with Prior Works\nWe understand your concern regarding related works that do not impose a linear condition. The works [1,2,3] you listed explore nonlinear settings and adopt different **model assumptions**. In particular:\n\n[1] (Reward Identification in Inverse Reinforcement Learning) studies the problem of reward identifiability in IRL from a **graph** perspective, focusing on single-agent MDPs. It primarily addresses identifiability conditions **without discussing the problem of reward estimation in identifiable cases.**\n\n[2] (Reward-Consistent Dynamics Models for Offline Reinforcement Learning) focuses on **model-based offline RL**, where the goal is to learn a dynamics model that generalizes well to unseen transitions. It is applied to single-agent settings, and **the problem of reward identification is not addressed.**\n\n[3] (Deep PQR: Solving Inverse Reinforcement Learning using Anchor Actions) works on inverse reinforcement learning (IRL) with **deep energy-based policies**. The key innovation is the introduction of an anchor action, which is a known, zero-reward action (e.g., doing nothing), to facilitate reward identification. Compared with our linear assumption, this method is based on an Anchor-Action Assumption (See Assumption 1), which helps to uniquely determine the reward function.\n\nThese works differ significantly from our approach and share limited similarities with our problem setting. In our work, the linearity assumption is crucial to transform the non-linear QRE constraint into a tractable linear problem. This enables us to derive rigorous theoretical guarantees on both identification and estimation of reward functions. Moreover, we provide a thorough theoretical analysis including convergence guarantees and confidence set construction, which is not covered in above works. We will include a more detailed discussion of these related works in the final version. Thank you for pointing out these references and helping us improve the clarity of our presentation.\n\n#### Lack of Competing Methods\nWe would like to clarify that our paper introduces a **totally novel framework** for inverse game theory, covering both identification and estimation of reward functions in competitive game settings.\nTo the best of our knowledge, **there are no existing methods specifically designed for inverse reinforcement learning (IRL) in two-player zero-sum Markov games that are directly comparable to our approach**. Most prior works in IRL focus on single-agent settings or non-competitive scenarios. Furthermore, the entropy-regularized QRE setting that we address is particularly unique, as it requires handling the complexity of equilibrium strategies and partial identifiability.\n\nWhile there are some works that address inverse RL with deep policies or anchor actions (e.g., [3]) or model-based RL for offline settings (e.g., [2]), these methods do not address the competitive, game-theoretic setting we focus on. Our approach leverages linear parametrization and QRE modeling, which makes it fundamentally different from existing IRL techniques that do not incorporate game-theoretic interactions or entropy regularization.\n\nWe would greatly appreciate it if the reviewer could suggest any closely related methods that might have been overlooked or not covered in our paper. We are committed to enhancing our work by incorporating relevant comparisons, if available, and we value your input in guiding us toward potential improvements.", "claims_and_evidence": "The claim that that the proposed condition is necessary is not well discussed (proposition 2.2). First of all, proposition 2.2 does not explicitly claim the condition to be necessary. This itself is contradictory the previous claims and the subtitle of the proposition. Second, to my understanding, the proposed condition is necessary only under some assumptions like the model setup. Specifically, there are similar works (IRL while not in the game setting) that does not take a linear condition like [1,2,3]. \n\nThe discussions regarding why the condition is necessary and on the comparisons with the mentioned works are missing. \n\n[1] Reward Identification in Inverse Reinforcement Learning\n[2] Reward-Consistent Dynamics Models are Strongly Generalizable for Offline Reinforcement Learning\n[3] Deep PQR: Solving Inverse Reinforcement Learning using Anchor Actions", "methods_and_evaluation_criteria": "I am not farmiliar enough to the direction of IRL for games to suggest any competing methods in this line. But the submission does not consider any competing methods in the experiment section. As a result, the the advantage of the proposed method is not well justified.", "theoretical_claims": "I did not check the proof of the results. I tried to find the proof for proposition 2.2 especially on why the proposed condition is necessary, but did not find the proof. \n\nIn general the proof makes sense to me: by posing the linear assumption, the reward identification is indeed an MLE problem, whose theoretical guarantees are well established even given not perfectly IID data.", "experimental_designs_or_analyses": "I did not pay very much attention to this. The design makes sense to me but lacks competing methods.", "relation_to_broader_scientific_literature": "The submission contributes to the area of inverse reinforcement learning for games. For such problems, a key challenge is identifiablity. The submission uses a linear-like condition to solve this issue.", "essential_references_not_discussed": "Already mentioned above.", "other_strengths_and_weaknesses": "NA", "other_comments_or_suggestions": "NA", "questions_for_authors": "Already mentioned above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XnLTOLN9Op", "reviewer": "Reviewer_h55M", "summary": "The paper analyzes the problem of identifying the utility in a zero-sum game from observations of a quantal response equilibrium policy. The authors provide an algorithm and theoretical guarantees on the recovered utilities. Moreover, they extend their analysis to zero-sum Markov games under a linear MDP assumption and provide experimental validation in a tabular setting.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nThank you for your thoughtful and constructive feedback! We greatly appreciate your positive assessment of the theoretical soundness and methodological consistency of our work. Below, we address your specific concerns and suggestions.\n\n### Relation to Single-Agent IRL Identification\nWe appreciate the suggestion to connect our results with identifiability in single-agent IRL. In particular, works such as Cao et al. [1], Rolland et al. [2], and Schlaginhaufen & Kamgarpour [3] explore how observing behavior under varying transition dynamics or discount factors can lead to identifiability, typically through rank or subspace conditions. These insights align with our own setting, where we identify necessary and sufficient rank conditions on linear systems derived from QRE constraints in zero-sum Markov games.\n\nUnlike the single-agent case, we address multi-agent, strategic interactions where agents follow a quantal response equilibrium. Nevertheless, the underlying intuition is similar: entropy regularization and structured assumptions (e.g., linear parameterization) enable us to derive strong identifiability and sample-efficient estimation. We will incorporate this discussion in the Related Work section to better position our contributions.\n\n### Experimental Design\nWe have now conducted additional experiments in the Markov game setting with 100 replications per sample size and computed 95% confidence intervals. These results align closely with our theoretical rates. Below are some results on the QRE error $\\mathrm{TV}(\\widehat{\\mu},\\mu)+\\mathrm{TV}(\\widehat{\\nu},\\nu)$:\n\n|Sample Size (T)|Mean Error and 95% Confidence Interval $(10^{-3})$|\n|-|-|\n|10,000|$7.55\\pm 2.71$|\n|20,000|$5.36\\pm 2.11$|\n|50,000|$3.40\\pm 1.86$|\n|100,000|$2.27\\pm 1.22$|\nWe will update our paper to include these results and clearly explain the statistical significance of the results.\n\n### (Q1) Theoretical Insights on When the Rank Condition (12) Is Satisfied\nThe rank condition (12) ensures the linear system (11) has a unique solution, which is the strongly identifiable case. Here the matrices $A_h(s,\\nu_h^*)$ and $B_h(s,\\mu_h^*)$ are derived from differences between feature vectors weighted by the corresponding equilibrium strategies, which means that distinct action pairs should lead to linearly independent differences. The rank condition also implicitly requires that the QRE policies $(\\mu_h^*,\\nu_h^*)$ do not degenerate and effectively captures the difference between different action pairs.\n\nIn the tabular case, where $\\phi$ is the canonical map and $d=Smn$, this condition does not hold in general, since the system (11) has only $S(m+n-2)$ equations. Nevertheless, our theory for the partially identifiable case ensures that we can still learn an acceptable estimate for the reward function even when the rank condition is not satisfied.\n\nIn practice, we recommend using low-dimensional, non-redundant feature maps and applying tools like PCA to remove collinearity, which helps maintain full rank and improves sample efficiency.\n\n### (Q2) QREs Corresponding to the Recovered Reward\nTheoretically, our algorithm aims to recover a confidence set of feasible reward functions rather than a single one, due to the partial identifiability inherent in inverse game learning. In practice, our focus is on behavioral consistency rather than exact reward matching.\n\nIn the entropy-regularized setting, small variations in rewards result in proportionally small variations in QRE, according to the Lipschitzness of softmax. Consequently, when the error between the recovered reward and the true reward is small, the QRE induced by the recovered reward function is guaranteed to be close to the true QRE.\n\nOur experimental results consistently show that even when the recovered reward function differs from the assigned one (due to partial identifiability), the QRE derived from the recovered reward still closely matches the observed QRE. This indicates that **the estimated reward is close to another feasible reward**.\n\n### Other Strengths And Weaknesses\nThank you for your positive feedback on the theoretical results and for suggesting ways to build more intuition. Below, we address the specific point you raised.\n\nThe distance measure quantifies the Hausdorff distance between the estimated feasible set $\\widehat{\\mathcal{R}}$ and the true feasible set $\\mathcal{R}$. In practice, when it is sufficiently small, we know that\n\n- The estimated reward set $\\widehat{\\mathcal{R}}$ almost captures all feasible rewards $r\\in\\mathcal{R}$;\n- For any estimated reward $\\widehat{r}$, there exists a feasible reward $r$ close to it, so the confidence set $\\widehat{\\mathcal{R}}$ is not too conservative.\n\nIf the rank condition (12) holds, our confidence set $\\widehat{\\mathcal{R}}$ converges to a single point, which is the uniquely feasible reward $r$. Indeed, even if the rank condition does not hold, our algorithm still efficiently recovers all feasible reward functions.", "claims_and_evidence": "The theoretical results seem sound, and they are presented clearly and convincingly.", "methods_and_evaluation_criteria": "The paper proposes first estimating the expert policies, followed by estimating a confidence set for the payoff or Q function parameter via least-squares. Additionally, in the linear MDP setting, the transition kernel is estimated, and a confidence set for the reward is recovered via the Bellman equation. This methodology is sound and consistent with approaches from prior work in the single-agent setting.", "theoretical_claims": "While I didn't have the time to check all the proofs, the claims made seem reasonable and in line with what we would expect from the single-agent theory.", "experimental_designs_or_analyses": "The authors provide an experimental validation in the tabular case. They show that both rewards and the corresponding QRE are close to the expert's reward and QRE. I have the following suggestions:\n1) Clarify whether the rank condition (12) is satisfied in the current experimental setup, as only then could we expect reward identifiability.\n2) Discuss whether closeness of QREs is theoretically expected. Although your current analysis seems to lack a formal continuity argument, I'd expect that it would hold in the entropy-regularized setting.\n3) Repeat experiments and add confidence bars to your plots.", "relation_to_broader_scientific_literature": "The paper builds on ideas from both single-agent reinforcement learning and inverse game theory. In single-agent IRL, similar identifiability conditions have been established for learning from multiple experts with the same objective but different transition kernels (see references below).", "essential_references_not_discussed": "While the authors briefly discuss single-agent IRL, they don't discuss the very much related results on identifiability in single-agent IRL. For instance, [1,2,3] discusses identifiability when learning from multiple experts with the same reward but individual transition laws. In particular, [1,2] frame reward identifiability problems as a subspace intersection problem and establish rank conditions similar to (12). Moreover, [3] establishes finite sample guarantees for both the feasible reward set and the suboptimality of $\\pi_{\\hat r}^*$ under the ground truth reward $r^*$. Given the similarities between your zero-sum formulation and learning from two distinct transition dynamics, providing a more detailed discussion that explicitly connects your findings to existing single-agent IRL results would enhance the theoretical clarity and positioning of your work.\n\n1) Cao, Haoyang, Samuel Cohen, and Lukasz Szpruch. \"Identifiability in inverse reinforcement learning.\" Advances in Neural Information Processing Systems 34 (2021)\n2) Rolland, Paul, et al. \"Identifiability and generalizability from multiple experts in inverse reinforcement learning.\" Advances in Neural Information Processing Systems 35 (2022)\n3) Schlaginhaufen, Andreas, and Maryam Kamgarpour. \"Towards the transferability of rewards recovered via regularized inverse reinforcement learning.\" Advances in Neural Information Processing Systems 35 (2024)", "other_strengths_and_weaknesses": "The theoretical results are interesting, sound, and clearly presented. However, the paper would benefit from some more explanations of these theoretical results to help build intuition, e.g. when is the rank condition satisfied, what does $D(\\mathcal{R},\\hat{\\mathcal{R}})<\\varepsilon$ imply in practice?", "other_comments_or_suggestions": "Minor issues & typos: \n- line 27, right column: \", as and multiple ...\"\n- line 192, right column: \"approximating feasible set...\"\n- line 207, left column: \"frequency estimator\" not defined explicitly.\n- line 330 & 343, left column: \"estimating the transition kernel\" is mentioned twice.", "questions_for_authors": "1. Can you give any theoretical insights on when the rank condition (12) is satisfied? Say in a tabular setting.\n2. Can you say something about the QREs corresponding to your recovered reward?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "F0HyOdjx5z", "reviewer": "Reviewer_PH73", "summary": "Under the assumption that agents are playing a QRE (a relaxation of Nash equilibrium that includes an entropy regularization term), this paper presents a method for learning the rewards of each agent based on a dataset of interactions in a finite-horizon zero-sum Markov game (or the special case of a single normal form game).  In the general case, the transition kernel must be learned in addition to the agent rewards.\n\nThe proposed method exploits a linearity assumption: that every action profile can be mapped to a finite-dimensional feature vector whose inner product with a weight vector yields the payoff of the maximizer agent. Based on this assumption and an empirical estimate of the agents' strategies from the observed interaction data, it produces an estimate of the weight vector $\\theta$.\n\n## Update after rebuttal\nThanks for your response!  In light of the rebuttal my opinion of the paper remains positive.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nThank you for thoroughly evaluating our work and for your valuable comments. We hope our reply will address your concerns and questions.\n\n### (Q1) Substantive Implications of the Non-singularity Assumption\nThe non-singularity assumption on the feature covariance matrix $\\Psi_h$ ensures that the feature vectors are linearly independent, meaning that no feature can be expressed as a linear combination of others, so we have sufficient information for parameter recovery. This is a standard assumption of coverage in many related literatures [1, Corollary 4.2; 2, Assumption 2.3]. One practical way for users to check this assumption is to examine the condition number of the matrix $\\Psi_h$. If the condition number is extremely large, it indicates that the matrix is nearly singular. Additionally, principal component analysis (PCA) can help detect high collinearity among features. \n\nIf the assumption does not hold, the problem becomes ill-posed, meaning that there exist multiple solutions for the estimated reward function. In such cases, our method may produce arbitrarily large or unstable estimates, as the problem becomes underdetermined. Nevertheless, in parctice,we can take proactive measures to avoid rank deficiency:\n- Reducing feature dimension to avoid over-parameterization.\n- Removing redundant features to ensure numerical stability and identifiability.\n\n### (Q2) Parameter Choice\nWe chose $m=n=5$, $H=6$ to strike a balance between model complexity and computational feasibility. The setup provides sufficient structure to validate both static and dynamic cases. We will add this explanation in the revised version.\n\n### (Q3) Number of Replications and Confidence Bounds\nIn the revised version, we repeat experiments 100 times and report 95% confidence intervals. Below we list the results on the QRE error:\n\n|Sample Size (T)|Mean Error and 95% Confidence Interval $(10^{-3})$|\n|-|-|\n|10,000|$7.55\\pm 2.71$|\n|20,000|$5.36\\pm 2.11$|\n|50,000|$3.40\\pm 1.86$|\n|100,000|$2.27\\pm 1.22$|\nWe will include more result in our revised paper. This will ensure that the results are statistically robust and interpretable.\n\nIn Figure 1, we compare reconstructed and assigned rewards. Since the true reward is not uniquely identifiable, different reward functions may induce the same QRE. Thus, even with large $N$, we may observe limited improvement in raw reward error. Our true goal is behavioral consistency, which we assess in Figure 2 via the QRE induced by the recovered reward. This metric better reflects algorithm performance and convergence.\n\n### (Q4) Quantitative Differences and Theoretical Validation:\nThank you for raising this important point. We acknowledge that the empirical results presented in the main text may not fully demonstrate consistency with the theoretical convergence rates.\n\nIn fact, we did compare the empirical convergence rate with the theoretical result in the matrix game setting and verified their consistency (both $\\mathcal{O}(N^{-1/2})$). This comparison and analysis are detailed in **Appendix E**. While we had limited Markov game replication before submission, we have since conducted 100-run experiments and observed consistent convergence rates. These additional results with confidence intervals will be added to the revision to strengthen empirical validation. We will update the revised version of the paper to include these new experimental results and confidence intervals, and explicitly discuss the consistency between empirical and theoretical results.\n\nThank you once again for pointing out this important aspect. We believe that this additional empirical evidence will significantly strengthen the experimental validation of our theoretical findings.\n\n### About Undiscussed Essential References\nThank you for pointing out the recent work. While Chui et al. (2023) also explore preference estimation in games, their focus is fundamentally different from ours. They investigate non-strategic or **imperfectly rational players**, proposing models that better fit human behavior by relaxing equilibrium assumptions like Nash equilibrium and QRE. In contrast, our work assumes strategic agents playing QRE and studies the identification and estimation of reward functions under this equilibrium assumption. Moreover, Chui et al. do not address the identifiability or sample complexity of their estimation procedure, while a key contribution of our work lies in formally characterizing when the reward function is identifiable and how to estimate it reliably from finite data. Finally, their analysis is limited to static games, whereas our framework extends to finite-horizon Markov games. \n\nWe will include a discussion of this work in the Related Work section. \n\n### References\n[1] Tu, S. and Recht, B. (2017). Least-Squares Temporal Difference Learning for the Linear Quadratic Regulator.\n\n[2] Min, Y., Wang, T., Zhou, D. and Gu, Q. (2022). Variance-aware off-policy evaluation with linear function approximation.", "claims_and_evidence": "The theoretical claims appear well supported.  I do not find the empirical evaluation convincing.", "methods_and_evaluation_criteria": "The empirical evaluations are on a single seemingly-arbitrary scenario, do not include checks of statistical significance, and do not appear to check the theoretical claims.  Answers to my \"questions to authors\" will provide insight into how serious these issues are.", "theoretical_claims": "No", "experimental_designs_or_analyses": "See \"Methods\"", "relation_to_broader_scientific_literature": "The related work is a solid survey of relevant literature.  I'm aware of work that aims to estimate payoffs in Stackelberg settings using the assumption of quantal response (some of which is cited).", "essential_references_not_discussed": "[Chui et al. AAMAS 2023] perform empirical estimation of payoffs under a QRE assumption in the normal form setting.  I am not aware of any work which performs similar estimation in the Markov game setting.", "other_strengths_and_weaknesses": "See \"Questions\"", "other_comments_or_suggestions": "* p.2 \"with inner produce\": inner product\n* p.3: $d \\le m + n - 2$ will not be true in general (in general there will be up to $mn$ unique utility pairs).  This is actually a pretty restrictive assumption.  The traveller's dilemma is a very structured game, and yet it has $3m$ unique utility profiles.  (It's not zero-sum though)\n* p.4 \"Let Assumption 2.1 and the rank condition (4) hold.\": Do you mean the rank condition (3)?\n* p.7 def.3.6 \"between any pair of rewards $r,r' \\in \\mathcal{R}$\": later on you define $\\mathcal{R}$ as the set of feasible rewards corresponding to the QRE $\\mu,\\nu$; this is probably not what you mean here, because in Theorem 3.9 you want to bound distance away from $\\mathcal{R}$, which doesn't make sense if the metric is only defined on $\\mathcal{R}$.", "questions_for_authors": "1. Theorem 3.9 \"We assume that the following $d \\times d$ matrix is nonsingular\": What are the substantive implications of this assumption?  One is presumably that no feature is a linear transformation of another feature, is that sufficient, or does more need to be true?  What happens if this assumption fails to hold, does your whole method fail?  Can a user tell in advance that it fails to hold?\n\n\n2. How did you choose the parameters of your test environment ($m=n=5$, $H=6$, etc.).\n\n3. How many replications do the figures represent?  What are the confidence bounds on your plots?  Are the differences between $N=30000,N=100000,N=300000$ significant? (Especially in Figure 1)\n\n4. Beyond the bare fact that more data means lower error, what should I take away from figures 1 and 2?  Are the quantitative differences in error in line with the theoretical bounds?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JsKNip09AY", "reviewer": "Reviewer_TbpT", "summary": "This paper studies inverse game theory for two-player zero-sum Markov games under entropy regularization (quantal response equilibrium): instead of best responding, each player plays a mixed strategy with softmax probability $\\frac{e^{\\eta u(a)}}{\\sum_{a\\in\\mathcal A} e^{\\eta u(a)}}$.  Given observed actions sampled from the quantal response equilibrium, this paper aims to estimate the utility function of the two players.  The paper derives the sample complexity of this problem, using a Maximum Likelihood Estimation approach.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nThank you for your valuable feedback and for carefully checking the proofs of our theorems.\n## Concerns about the Asymptotic Notation\nWe appreciate your observation regarding the use of asymptotic notation in Theorems 2.3, 2.4, and 2.5. To streamline presentation, we omitted terms that implicitly depend on the problem size—specifically, action space sizes $m,n$, feature dimension $d$, and the regularization parameter $\\eta$. We agree that these quantities affect the sample complexity and convergence rates and are not truly constant. In the revised version, we will explicitly include these dependencies in the theorem statements and discuss their implications.\n\n## Questions\n### (Q1) Contribution to the Broader Litterature\n```\nThe idea of inverse reinforcement learning under entropy regularization is well known and dates back to Ziebart et al.\n``` \nZiebart et al., 2008 focuses on imitation learning in **single-agent Markov Decision Processes**. In comparison, our work addresses IRL in two-player zero-sum Markov games, where the objective is to recover the reward functions given observed equilibrium strategies (QRE). Additionally, we deal with both strong and partial identifiability, which introduces new theoretical challenges not covered in Ziebart et al.\n``` \nMore recent works about inverse game theory under entropy regularization include, for example, Wu et al and Chen et al. \n```\nThese studies focus on inverse game theory for **Stackelberg games** and **quantal Stackelberg equilibrium** (QSE). These methods primarily deal with leader-follower interactions, where one player commits to a strategy first, and the follower responds optimally. The difference between QRE and QSE is crucial:\n- QRE models simultaneous decision-making under entropy regularization, where both players make noisy best responses.\n- QSE models sequential decision-making, where the leader’s strategy is announced, and the follower best responds.\n\nOur theoretical framework leverages QRE constraint, which fundamentally differs from the QSE setting explored by Wu et al. and Chen et al. \n```\nThe idea of using MLE to estimate the unknown reward functions for such problems is also standard. \n```\nWe are sorry about causing the confusion. To clarify, we do not directly apply MLE for reward estimation. Instead, the key to our identification method is using the linear assumption to transform the QRE constraints into linear systems like (2), (11). We then employ least square to construct confidence sets. MLE is only used to estimate QRE from data (e.g., Appendix E), not to estimate rewards directly.\n\nTo summarize, our contribution includes:\n- We introduce a **complete framework** that addresses reward identification and estimation in two-player zero-sum games and Markov games. To the best of our knowledge, no existing work addresses these specific problems.\n- We establish necessary and sufficient conditions for strong and partial identification under linear parameterization.\n- We provide theoretical guarantees for the sample complexity and convergence of the constructed confidence sets.\n- Through experiments, we verify the behavioral consistency between the recovered reward functions and the observed QRE.\n\n\n### (Q2) Zero-Sum Game Restriction\nOur framework is currently specific to zero-sum games because of their **minimax structure**, which enables QRE to yield tractable linear constraints on the reward parameter. General-sum games lack this structure and may admit **multiple equilibria**, complicating both identification and estimation.\n\nThough extending our methods to general-sum settings is nontrivial, we view this as an exciting direction for future work and appreciate your suggestion to explore this aspect.\n\n### (Q3) Assumption of Known Regularization Parameter $\\eta$\nWe acknowledge that our method assumes a known entropy regularization parameter $\\eta$, which reflects our modeling of agents . In practice, agents may use different or unknown $\\eta$'s. We address this in two parts:\n- If players use different $\\eta_1$ and $\\eta_2$, our linear formulation and results still hold by adjusting the vectors $c(\\mu)$ and $d(\\nu)$ accordingly.\n- If $\\eta$ is unknown, one could treat it as a hyperparameter and select it via cross-validation. In estimation, the choice of $\\eta$ is not a problem since we can scale the reward functions, so the identifiability and consistency of strategies remain unaffected.\n\nWe will discuss this in the revised version as an important direction for future research.\n\n### (Q4) Derivation in the Proof of Theorem 2.3 \nThank you for pointing out this issue. We apologize for the confusion caused by the notation. There was a minor typo in the proof where the inequality sign $\\leq$ should have been $\\lesssim$, which absorbs a constant factor of $2$. The estimate is a consequence of Cauchy-Schwartz inequality. We appreciate your careful attention to detail, and we will correct this in the final version of the paper.", "claims_and_evidence": "All the theoretical and empirical results are solid as far as I can tell.", "methods_and_evaluation_criteria": "Using Maximum Likelihood Estimation to recover the utility functions in inverse reinforcement learning / inverse game theory under entropy regularization is a standard technique in the literature.  It makes sense for the problem at hand.", "theoretical_claims": "I checked the proofs for the theorems in Section 2, which I believe are correct.\n\n\n\nHowever, I have some concerns about the presentation of the theoretical results:  in particular, the asymptotic notation $\\lesssim$ hides some important quantities that are not necessarily constants: \n\n(1) The $\\lesssim$ notatioin in Theorem 2.3 hide quantities $\\eta, \\epsilon_1, \\epsilon_2$.  In particular, the $\\frac{1}{\\eta^2 (\\min_{i\\in[m]} \\mu_i - \\epsilon_1)^2}$ terms in equation (25) (Page 15) is hidden.  These quantities are important to the sample complexity when they are close to $0$.  They are not necessarily constants and should not be hidden by the $\\lesssim$ notation in my opinion.  \n\n(2) Similarly, a quantity of $\\sum_{a, b \\in \\mathcal A \\times \\mathcal B} \\| \\phi(a, b) \\|^2$ is hidden by the $\\lesssim$ notation in Theorem 2.4.  This quantity depends on the sizes of $\\mathcal A$ and  $\\mathcal B$, $m$ and $n$, which are not constants, and depends on $d$ which is not a constant, either. \n\n (3) Similarly, the $\\lesssim$ notation in Theorem 2.5 hides $|| \\Phi_1 ||$ and  $|| \\Phi_2 ||$, which seem to depend on $m, n, d$, which are not constants. \n\nHiding too many such important quantities hurts the clarity and soundness of the theoretical results in my opinion.", "experimental_designs_or_analyses": "I don't see any issues with the experimental results.", "relation_to_broader_scientific_literature": "The key contribution of the paper to the broader literature is unclear.  The idea of inverse reinforcement learning under entropy regularization is well known and dates back to [Ziebart et al 2008](https://cdn.aaai.org/AAAI/2008/AAAI08-227.pdf).  More recent works about inverse game theory under entropy regularization include, for example, [Wu et al, 2024](https://arxiv.org/abs/2210.01380) and [Chen et al, 2023](https://arxiv.org/abs/2307.14085). The idea of using MLE to estimate the unknown reward functions for such problems is also standard.  The authors mentioned several related works in Section 1.2, but didn't mention the main difference between previous works and their work.  This makes it difficult to judge the contribution of this work.", "essential_references_not_discussed": "No in my knowledge.", "other_strengths_and_weaknesses": "### Strength:\n\n(S1) Considering two-player games is a strength of this paper.  As far as I know, previous works on inverse reinforcement learning under entropy regularization mostly focus on single-agent problems.  \n\n\n\n### Weakness:\n\n(W1) However, the two-player games considered by this paper are restricted to zero-sum games only.  Are there fundamental reasons that the approach in this work can only be applied to zero-sum games, or it can actually be applied to general-sum games? \n\n(W2) Another big weakness is that the entropy-regularization parameter $\\eta$ is assumed to be known by the learner.  In practice, different agents may use different regularization parameters and the parameters can be unknown.  When $\\eta$ is known, as shown by the authors, the problem of estimating the utility function becomes a simple linear regression problem, which can be solved by standard MLE technique.  This technique doesn't seem to be applicable to unknown $\\eta$.", "other_comments_or_suggestions": "(1) The $\\|\\theta\\| \\le M$ in Assumption 2.1 should be $\\|\\theta^*\\|\\le M$. \n\n(2) I would suggest not hiding essential parameters using the $\\lesssim$ notation in the theorem statements (see \"Theoretical Claims\").", "questions_for_authors": "(Q1) What's the main difference between this work and previous works in IRL and inverse game theory with entropy regularization?  See \"Relation to Broader Scientific Literature\".\n\n(Q2) Are there fundamental reasons that the approach in this work can only be applied to zero-sum games, or it can actually be applied to general-sum games?  (See Weakness 1)\n\n(Q3) What if $\\eta$ is unknown?  (See Weakness 2.)\n\n(Q4) How do you derive the first equation in the proof of Theorem 2.3 (Line 665 - 670)?  In particular, how do you get $(A(\\hat \\mu)^\\top A(\\hat \\mu) + B(\\hat \\mu)^\\top B(\\hat \\mu))^{-1}$ from equation (5) ?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of inverse reinforcement learning in games by observing demonstrations of the quantal response equilibrium in two-player zero-sum normal form games as well as Markov games. All the reviewers were enthusiastic about the technical contribution of this paper, and so I am recommending acceptance. Multiple reviewers mention that contextualization of the result with related work (e.g. in single-agent IRL) could be much improved. I recommend the authors pay close attention to the many helpful suggestions made by the reviewers to improve their related-work exposition for the camera-ready version, as well as better justify their assumptions.
Decision: Accept (poster)