Efficient Inverse Multiagent Learning
Authors: Denizalp Goktas
Amy Greenwald
Sadie Zhao
Alec Koppel
Sumitra Ganesh
Venue: ICLR 2024 spotlight (2024)
Keywords: Inverse Game Theory
Inverse Multiagent Reinforcement Learning
Primary area: reinforcement learning
TL;DR: We provide an efficient generative adversarial characterization for the inference of parameters of a game in inverse game theory and inverse multiagent (reinforcement) learning settings.

Abstract: In this paper, we study inverse game theory (resp. inverse multiagent learning) in
which the goal is to find parameters of a game’s payoff functions for which the
expected (resp. sampled) behavior is an equilibrium. We formulate these problems
as generative-adversarial (i.e., min-max) optimization problems, which we develop
polynomial-time algorithms to solve, the former of which relies on an exact first-
order oracle, and the latter, a stochastic one. We extend our approach to solve
inverse multiagent simulacral learning in polynomial time and number of samples.
In these problems, we seek a simulacrum, meaning parameters and an associated
equilibrium that replicate the given observations in expectation. We find that our
approach outperforms the widely-used ARIMA method in predicting prices in
Spanish electricity markets based on time-series data.

Published as a conference paper at ICLR 2024
EFFICIENT INVERSE MULTIAGENT LEARNING
Denizalp Goktas" & Amy Greenwald Brown University, Computer Science den zaz haallp__otttbbbbrnno
Sadie Zhao Harvard University, Computer Science
Alex Koppel & Sumitra Ganesh JP Morgan Chase & Co
ABSTRACT
In this paper, we study inverse game theory (resp. inverse multiagent learning) in which the goal is to find parameters of a game's payoff functions for which the expected (resp. sampled) behavior is an equilibrium. We formulate these problems as generative-adversaria (i.e., max- optimization problems, which we develop polynomial-tin algorithms solve, the former of which relies on an exact first- order oracle, and the latter, a stochastic one. We extend our approach to solve inverse multiagent simulacral learning in polynomial time and number of samples. In these problems, we seek simulacrum, meaning parameters and an associated cquilibrium that replicate the given observations in expectation. We find that our approach outperforms the widely-used ARIMA method in predicting prices in Spanish electricity markets based on time-series data.
INTRODUCTION
Game theory provides a mathematical framework, called games, which is used to predict the outcome of the interaction of cefferencemmxxmmize agents called players. Each player in game chooses strategy from its strategy space according to its preference relation, often represented by payoff' function over possible outcomes, implied by a strategy profile (i.e., a collection of strategies, one- per-player). The canonical outcome, or solution concept, prescribed by game theory is the Nash equilibrium (NE) (Nash, 1950): a strategy profile such that each player's strategy, fixing the equilib- rium strategies of its opponents, is payoff- maxooffmxiiizzigggg (or more generally, neeferece-maximizzng))
In many applications of interest, such as contract design (Holmström, 1979; Grossman & Hart, 1992) and counterfactual prediction (Peysakhovich et al., 2019), the payoff functions (or more generally, preference relations) of the players are not available, but the players' strategies are. In such cases, we concerned with estimating payoff functions for which these observed strategies are an equilibrium. This estimation task serves to rationalize the players' strategies (i.e., we can interpret the observed problems). Estimation problems of this nature
strategies as solutions characterize inverse game theory (Waugh et al., 2013; Bestick et al., 2013).
cefffrence-maximizattee
The primary object of study of inverse game theory is the inverse game, which comprises game with the payoff functions omitted, and an observed strategy profile. The canonical solution concept prescribed for an inverse game is the inverse Nash equilibrium, i.e., payoff functions for which the observed strategy profile corresponds to a Nash equilibrium. If the set of payoff functions in an inverse game is unrestricted, the set of inverse Nash equilibria can contain a wide variety of spurious solutions, e.g., in all inverse games, the payoff function that assigns zero payoffs to all outcomes is an inverse Nash equilibrium, because any strategy profile is a Nash equilibrium of a constant game: i.e. one whose payoffs are constant across strategies. To meaningfully restrict the class of payoff functions over which to search for an inverse Nash equilibrium, one common approach (Kuleshov & Schrijvers, 2015; Syrgkanis et al., 2017) is to assume that the inverse game includes in addition to all the aforementioned objects, a parameter- dependeet payoff function for each player, in which case an inverse Nash equilibrium is simply defined as parameter values such that the observed strategy profile is a Nash equilibrium the parameter-dependee payoff functions evaluated at those values.
Research conducted while the author was an intern Morgan Chase & Co.

---

Published as a conference paper at ICLR 2024
If one assumes exact oracle access to the payoff's of the game (i.e., if there exists function which, pypptooft
for any strategy profile, returns the players' payoffs'), ) the problem of computing an inverse Nash equilibrium is one of inverse multiagent planning. In many games, however, a more appropriate assumption is stochastic oracle access, because of inherent stochasticity in the game (Shapley, 1953) or because players employ randomized strategies Nash (1950). The problem of computing an inverse Nash equilibrium assuming stochastic oracle access is one of inverse multiagent learning.
One important class of inverse games is that of inverse Markov games, in which the underlying game is a Markov game (Shapley, 1953; Fink, 1964; Takahashi, 1964), i.e., the game unfolds over an infinite time horizon: at each time period, players observe a state, take an action (simultaneously), receive a reward, and transition onto a new state. In such games, each player's strategy," also called a policy, is a mapping from states to actions describing the action the player takes at each state, with any strategy profile inducing a history distribution over histories of play i.e., sequences of (state, action profile) tuples. The payoff for any strategy profiee is then given by its expected cumulative reward over histories of play drawn from the history distribution associated with the strategy profile. Excluding rare instances," the payoff function in Markov games is only accessible via a stochastic oracle, typically implemented via a game simulator that returns estimates of the value of the game's 'ss rewards and transition probabilities. As such, the computation of an inverse Nash equilibrium in an inverse Markov game is inverse multiagent learning problem, which is often called inverse multiagent reinforcement learning (inverse MARL) (Natarajan et al., 2010).
In many real-world applications of inverse Markov games, such as robotics control (Coates et al., 2009), one does not directly observe Nash equilibrium strategies but rather histories of play, which we assume are sampled from the history distribution associated with some Nash equilibrium. In these applications, we are given an inverse simulation-an inverse Markov game together with sample histories of play-based based on which we seek parameter values which induce payoff functions that rationalize the observed histories. As a Nash equilibrium itself is not directly observed in this setting, we aim to compute parameter values that induce Nash equilibrium that replicates the observed histories in expectation. We call the solution of such an inverse simulation (i.e., parameter values together with an associated Nash equilibrium) a simulacrum. Not only does a simulacrum serve to explain (i.c., rationalize) observations, additionally, it can provide predictions of unobserved behavior.
We study two simulacral learning problems, a first-order version in which samples histories of play faithful, and second-order version in which they are not-a a (possibly stochastic) function of each history of play is observed rather than the history itself. Here, the use of the term "first-order" refers to the fact that the simulacrum does not necessarily imitate the actual equilibrium that generated the histories of play, since multiple equilibria can generate the same histories of play (Baudrillard, 1994). More generally, if the simulacrum is "second-order," it is nonfaithful, meaning some information about the sample histories of play is lost. We refer to the problems of computing first-order (resp. second-order) simulacra as first-order (resp. second-order) simulacral learning: i.c., build first-order (resp. second-order) simulacrum from faithful (resp. fai-ffithful; e.g., aggregate agent behavior) sample histories of play. We summarize the problems characterizing inverse game theory in Table la.
Contributions
The algorithms introduced in this paper extend the class of games for which an inverse Nash equilibrium can computed efficiently (i.e., in polynomial-time) to the class of normal- form concave games (which includes normal-form finite action games), finite state and action Markov games, and a large class of continuous state and action Markov games. While our focus is on Markov games in this paper, the results apply to normal-form (Nash, 1950), Bayesian (Harsanyi, 1967; 1968), and extensive- beyond Nash, such as (coarse) correlated Aumann (1974); Moulin & Vial (1978), and more generally, D-equilibrium (Greenwald & Jafari, 2003) mutatis mutandis.
games (Zermelo, 1913). The results also extend to other equilibrium concepts,
First, regarding inverse multiagent planning, we provide min-max characterization of the set of inverse Nash equilibria of any inverse game for which the set of inverse Nash equilibria is non-empty, assuming an exact oracle (Theorem 3.1). We then show that for any inverse concave game, when the
'Throughout this work, we assume that the oracle evaluations are constant time and measure computational complexity in terms of the number of oracle calls.
Throughout this paper, strategy refers to the complete description of players' hehavior at any state or time of the game, while an action refers to a specific realization of strategy at a given state and time. Forr simple enough games, one can express the expected cumulative reward in closed form, and then solve the inverse (stochastic) game assuming exact oracle access.
2

---

Published as a conference paper at ICLR 2024
Metoraae
Lirr Wape
Solanee Coeeept
Pistmne
Ph 2011)
Finil Marece
Nust
Fine Mirac
(taral Roparee
Eqpiliiiir Access
FAR Daale
Sinlestc Oode
Yillg
Frai Mirioe
Ouural Resporos
DESt
Bronn Malleaar Famigg
Brane Melrage Loning
15 Aiilee 2017
Fintr Hoyrear
ToyreNuh
Fankin Narpes
Fii anr Verdban Pammy
HeNooeer Meri Lomin
Kkacsson & Sclagsess 30.3)
Fuil Numaa
Cindael
Natrzanl Stmples
Separdende Sindaaal Harning
Sears--onde Namibeml Laaming
Wuzgi 11. 2013
Fint Name Fart
Cindzed
(a) Taxonomy of inverse game theory problems. First- order simulacral learning more commonly known multiagent apprenticeship learning (Abbeel Ng. 2004; (b) A comparison of our work and prior work inverse Yang et al., 2020).
Timir Miratr
Exqparane
Thi nock
Fimis Cmaos Marker
UoiisUCnnae Noo
Uner
game theory and inverse MARL.
regret of each player is convex in the parameters of the inverse game, an assumption satisfied by a large class of inverse games such as inverse normal-form games, this min-max optimization problem is convex-concane methods. This characterization also shows that the set of inverse Nash equilibria can be convex, even when the set of Nash equilibria is not.
and can thus be solved in polynomial time (Theorem 3.2) via standard first-order
Second, we generalize our min-max characterization inverse multiagent learning, in particular inverse MARL., where we are given an inverse Markov game, and correspondingly, a stochastic oracle, and we seek first-order simulacrum (Corollary 1). We show that under standard assumptions, which are satisfied by a large class of inverse Markov games (e.g., all finite state and action Markov games and class of continuous state and action Markov games), the ensuing min-max optimization problem is convex-grade -raddeett dominated, and thus an inverse Nash equilibrium can be computed once again via standard first-order methods in polynomial time (Theorem 4.1).
Third, we provide an extension of our min-max max characterization to (second- -rder)) simulacral learning (Theorem 5. We once again characterize the problem as a solution to min-max optimization problem, for which standard first-order methods compute first-order stationary (Lin et al., 2020) solution in polynomial-time play) that is polynomial in the size of the inverse simulation (Theorem 5.2).
using a number of observations (i.e., unfaithful samples of histories of
Finally, we include two sets of experiments. In the first, we show that our method effective in synthetic economic settings where the goal is to recover buyers' valuations from observed competitive equilibria (which, in this market, coincide with Nash equilibria). Second, using real- real-world time-scries data, we apply method to predict prices in Spanish electricity markets, and find that it outperforms the widely-used ARIMA method in predicting prices on this real-world data set.
2 PRELIMINARIES
Notation. All notation for variable types, e.g., vectors, should be clear from context; if any confusion arises, see Section 7.1. We denote by [m] the set of integers nI. Let X' be any set and (X, F) any associated measurable space, where the o-algebra F unless otherwise noted assumed to be the o-algebra of countable sets, i.c. F {E S X E is countable }. We write A (X) = {u+ F) > [0, 1}} to denote the set of probability measures on (X,F), Additionally, we denote the orthogonal projection operator onto set X' by IIxxx) = arg oigmingex x ||x - y |
Mathematical Concepts. Consider any normed space (X, II-I]) where X C Rm and any function w.r.t. norm (typically, Euclidean) ||-|| iff Væ 22 E < & ||= æ2|l- If the gradient of f is Ss,-Lipschizz-coniinonn
f X + I.. f is E--Lipshhit--ooninuann - [[lf(())-f(zs) to f as lu -i--ipcchttz--moothh Furthermore, given μ > 0, f is said to be p-gradient w-gradient-dominated if mingex f'(x)= 2 f(x)) + p.. min (x' x., V fxx)) (Bhandari Russo, 2019).
we refer
Normal-form Games. A (parametric) game G = (n, m, d, X, θ 0, u) comprises n E N players, each i E [n] of whom chooses a strategy x; E X, from an strategy space X, S R simultaneously. We refer to any vector of per-player strategies = (æI...., ) E X as strategy profile, where X x= ==X X, C Ram denotes the space of all strategy profiles. After the players choose their strategies x E X, each receives payoff u, ux(:;; 0) given by payoff function u; X θ I parameterized by a vector 0 in a parameter space θ C Rdd We define the payaff profile function u ( 0) = (u,(x; (x;; 0)) the cumulative regret vp XxXXO + R across all players, between two strategy profiles x. y E X, given 0 E O, as (xx y: 0) Σ Eiejn| u, (,,,,, x_ O) (x; 0): and the exploitability (or Nikaido-Isoda potential (Nikaido & Isoda, 1955)) (x 0) = max,ex dh y; 0)
3

---

Published as a conference paper at ICLR 2024
A game is said to be concave if for all parameters 0 ② and players i [n], 1. X, is non- empty, compact, and convex, 2. U; is continuous, and 3. D, + u [T x_ ;: 0) is concave. Given 0 E O an e-Nash equilibrium (s (s-NE) of a game G is a strategy profile x* E s.t. u, (2()00)) 2 maxæ, ex, u,(x,, 0) E, for all players E [n]. A O-Nash equilibrium simply called Nash equilibrium, and is guaranteed to exist in concave games (Nash, 1950; Arrow & Debreu, 1954).
Dynamic Games, An (infinite-horizon discounted, parametrie) Markov game (Shapley, 1953; Fink, 1964; Takahashi, 1964) .M = (n, S, A, O rr..r.P..... P.P.y (4 is dynamic game played over an infinite time horizon. The game initiates at time t = -0 in some state S ~ drawn from an initial state distribution ja E (S)) At each time period
0, I.... each player i E [n] plays an action a E A, from an action space A, C R We define the space of action profiles A = Xie(n] A.. After the players choose their action profile (!)) (a ...,.....
E A, each 9) according to a parameterized reward profile function r : S x A θ + IR.. The game then either ends with probability 1-1, 7, where E (0, 1) is called the discount factor, or transitions to a new state S(++1) ~ p(. s((), aa()) according to (Markov) probability transition kernel p whereby for all (s, E x A, p(- 8,a) E (SS),
)
player i receives a reward r, (s("",, (t)
and p(s((+1) 8 aa())) = PP(S((+1) = g(++1) s(t) = , A(0) = (!)) is the probability of transitioning to state s(++1) from state s(t) when the players' take action profile a!))
A (stationary Markov) policy (Maskin & Tirole, 2001) for player i E [n] is a mapping म; S + A from states to actions so that न. (8) E A, denotes the action that player takes at state 8. For each player i E [n), we define the space of all (measurable) policies P, = { S + Ai). As usual, т = I TT) E P - senn P, denotes policy profile. A history (of play) h E (S x A) of length TE N is a sequence of state-action tuples h = (s(*) T-1 For any policy profile π E P, , (s(t))) as the probability of observing history h of length T. Throughout, denote by H = (s(t), A())) Va any randomly sampled history from n*
(T=)
define the discounted history distribution vTa (h) = (()( I ('p(s((+)) s(t), π
P and player i. In our analysis of Markov games, we rely on the following terminology. The expected cumulative payoff is given by u,(T;) 0) = Ex- r, (S()) (0] The state- and action-value functions are defined, re- spectively, as v." 0) = EETEE ", (1)))) A()) (()) s] and qf (s, a; A) = En E, A(0); (0;00) | = 8, A = a]. The state occupancy distribution of E (S)) denotes the probability that a state is reached under a policy æ, given initial state distribution Jt, ie.. 67 (s) _H Er 1 |s0 Finally, as usual, an e-Nash equilibrium (s-NE) of a game
Fix policy profile
MM is a policy profile πt E P such that for all E [m]. u(==;;)) 2 max EP, Uy (A T=;; 0) E; and Nash equilibrium ensues when 0.
3 INVERSE MULTIAGENT PLANNING
The goal of inverse multiagent planning is invert an equilibrium: i.e., estimate a game's parameters, given observed behavior. In this section, we present our main idea, namely a zero-sum game (i.e., min-max optimization) characterization of inverse multiagent planning, where one player called
*For notational convenience, we assume the probability transition function is independent of the parameters, but we note that our min-max characterizations apply more broadly without any additional assumptions, while our polmnomial-time computation results apply when, in addition to Assumption 4, one assumes the probability transition function stochastically convex (see, for instance, Atakan (2003a)) in the parameters of the game.
'Let (S, Fs). FA) and (S x A, be the measurable spaces associated with the state, action profile, and stale-action profile (S x A) spaces, respectively. Further, let ((O, 11, Bj.,)). (R", Bgr.) ) be measurable do not explicitly represent the reward profile function, transition probability kernel, initial state distribution, or policies as measures or measurable functions. We note, however, that for the expectations we define to be well-posed, they all must be assumed to be measurable functions. We simply write : S x A + I2". S x (S x A) + [0, 11, : S - [0, 1J. and π S + A to mean, respectively, r (8 x F.xA)) + (R" Bg p: (S, Fs) x (S x A.Fsx ([0, 1], Bp..) p. FS)Fs) + (f0, 1]. p).1), and π Fs) + (A,
spaces on [0, 1] and R" defined by the Borel o-algebra. For simplicity,
4

---

Published as a conference paper at ICLR 2024
the stabilizer picks parameters, while the other called the destabilizer picks per-player deviations. This game is zero-sum) because the stabilizer seeks parameters that rationalize (i.e., minimize the exploitability of) the observed equilibrium, while the destabilizer aims to rebut the rationality of the observed equilibrium (i.e., seeks deviations that maximize cumulative regret). We use this characterization to develop gradient descent ascent algorithm that finds inverse NE in polynomial time, assuming access to an exact first-order oracle: specifically, a pair of functions that return the value and gradient of the payoff profile function.
An inverse game g-1 = =Go' (0i, x)) comprises a game form (i.c., a parametric game sans its parameter) go \ Ot together with an observed strategy profile xi, which we assume is a Nash equilibrium. Crucially, we do not observe the parameters 0f of the payoff functions. Given an inverse game G our goal is to compute an e-inverse Nash equilibrium, meaning parameter values 0" E Q s.t. xr is an e-NE of go As usual, a O-inverse NE is simply called an inverse NE. Note that this definition does not require that we identify the true parameters 0t, as identifying ot is impossible unless there exists bijection between the set of parameters and the set of Nash equilibria, a highly restrictive assumption that not even satisfied in games with a unique Nash equilibrium. To compute an inverse NE is to find parameter values that minimize the exploitability of the observed equilibrium. This problem is min-max max optimization problem, as the parameter values that minimize exploitability those that maximize the players' cumulative regrets. More precisely:
Theorem 3.1. The set of inverse NE of G-1 is the set of parameter profiles O E @ that solve the optimization problem mingee @p ((x: (a::0) O), or equivalently, this min-max optimization problem:
min max OEG yEX
y0 = v (x) 0: = Σ
[, x1, - u, u,(xx;;; 0)]
(I)
iEIm]
This min-max optimization problem can be seen as generalization of the dual of Waugh et al.'s (2013) maximum entropy likelihood maximization method for games with possibly continuous strategy spaces, taking Nash equilibrium rather than maximum entropy correlated equilibrium as the inverse equilibrium. In contrast to Waugh et al.'s dual, our min-max optimization problem characterizes the set of all inverse NE, and not only a subset of the inverse correlated equilibria, in particular those that maximize entropy. This formulation also generalizes Swamy et al (2021) moment matching game from a single-agent a multiagent setting.
Algorithm 1 Adversarial Inverse Multiagent Planning
Without further assumptions, the objective function f in Equation (1) is non-convex non- concave; however, under suitable assump- tions (Assumption 1) satisfied by finite action normal-form games, for example, it becomes convex-concave.
Inputs: O.X. f, no. 7y T, (()) (0) xt
Outputs: (0(t), y (t) ) 1=0
1: for 6= ......77 T do
2: @(++1) < Ile O(())
(1) V vo f(()) y0)
10
Assumption 1. Given an inverse game G-1, assume 1. (Concave game) for all parame- ters O E O, 9 is concave; and 2. (Con- vex parametrization) @ is non-empty, com- puct, and convex; and for all Vi E [m], y E X, and ae E X, euch player i's regret is convex.
3: ((++)) +- xxx (0)) + ml
y ((())) y0))
4: return (0it), y (1) o
- u.
Remark 1. Perhaps surprisingly, the set of inverse NE can be convex even when the set of NE is not, since the set of solutions to a convex-concave (or even comvex-non-concave) min-max optimization problem is convex. This observation should alleviate any worries about the computational in- tractability of inverse game theory that might have been suggested by the computational intractability of game theory üseef ( (Daskalakis et al., 2009; Chen & Deng, 2006).
If additionally, we assume the players' payoffs are Lipschitz-smooth (Assumption 2), Equation (1) can then be solved to precision in O (1/=2) via gradient descent ascent (Algorithm 1). That is, as Theorem 3.2 shows, an inverse E-NE can be computed in O (1/22) iterations." 6 We note that this convergence complexity can be further reduced to O (1/2) (even without decreasing step-sizes) if one instead applies an extragradient descent ascent method (Golowich et al., 2020) or optimistic GDA (Gorbunov et al., 2022).
'ee include detailed theorem statements and proofs Section 7.2.
5

---

Published as a conference paper at ICLR 2024
Assumption 2 LLipschiz--Smoote Game), For all players E [n]], u, is : Lipschitzz-smotth.
Theorem 3.2 (Inverse NE Complexity). Under Assumptions 1-2, for e 2 0, if Algorithm I is run (t) with imputs that satisfy TE 2()(s) and for all E [7], v/y) = f = 1/e, then the time-uverage of all parameters ((T)
1 T+1 Ei=o ((+) is E-inverse NE.
4 INVERSE MULTIAGENT REINFORCEMENT LEARNING
In this section, we build inverse game theory to tackle inverse MARL in an analogous fashion. As it is unreasonable to assume exact oracle access to the players' (cumulative) payoft's in inverse MARL, relax this assumption in favor of a stochastic oracle model. More specifically, we assume access to a differentiable game simulator (Suh et al., 2022), which simulates histories of play h n" according vx given any policy profile ग,, and returns the rewards r and transition probabilities p, encountered along the way, together with their gradients.
zero-sum game (i.e., min-max optimization) characterization of
Formally, an inverse Markov game M (Mo) (i) is an inverse game that comprises a Markov game form (i.e., parametric Markov game sans its parameter) MM \ 07 together with an observed policy profile π², which we assume is Nash equilibrium. Crucially, we do not observe the parameters 0f of the payoff functions. Since Markov game is normal-form game with payoffs given by u (T; 0) = Ex~ Ei= r ((S((),,())) 0)], the usual definitions of inverse NE and cumulative regret apply, and the following result, which characterizes the set of inverse NE as the minimizers of a stochastic min-max optimization problem, is corollary of Theorem 3.1.
Corollary 1. The set of inverse NE of M is characterized by solutions to the following problem:
min max f(0, T) 0 TEP
Σ
E
Σ rr((S)) AA,00) 1=
r((stt)) ,
(2)
(E(n) H Haw Li H' x
t=
As is usual in reinforcement learning, use policy gradient to solve the destabilizer's problem in Equation (2). To do so, we restrict the destabilizer's action space to policy class p parameterized by X C R.. Redefining f(0, x) = f(0, πh for x P we aim to solve the stochastic min-max optimization problem minøge m /(0, x)) Solutions this problem are superset of the solutions to Equation (2), unless it so happens that all best responses can be represented by policies in P because restricting the expressivity of the policy class decreases the power of the destabilizer. As in Section 3, without any additional assumptions, is in general non-convex, non-concave, and non- smooth. While we can ensure convexity and smoothness of 0 ~ f(0,a) xx) under suitable assumptions on the game parameterizatton, namely by assuming the regret at each state is convex in O, concavity in æ is not satisfied even by finite state and action Markov games. Under the following conditions, however, we can guarantee that f is Lipschitz-smooth, convex in O, and gradient dominated in æ.
Game), Given an inverse Markov game M- assume S and A are non-empty, and compact; (Convex parameter spaces) X, O are non-empty, compuct, and convex; 3. (Smooth Game) Vr, Vp. and V n² for all policies Doadieent-Dmmnatedd Game) for all players i [n], states E S, action profiles E A, and policies πh E SDx, + q (s, {s); 0) is p-gradient- dominated for some > O; and (Closure under Policy Improvement) for all states 8 S, players [ri,, and policy profiles π E P, there exists NO EP. s.t. 9. (s, n. (s), π (s)) max EP, q," T((s), (s)))
Assumption 3 -Lipschitz-Smoott
nh E EPX are continuously differentiable;
Part of Assumption 3 implies that the game's cumulative payoff function is Lipschitz-smooth in the policy parameters æ. We note that a large class of Markov games satisfy Part 4, including linear quadratic games (Bhandari & Russo, 2019), finite state and action games, and continuous state and action games whose rewards (resp. transition probabilities) are concave (resp. stochastically
We note that in inverse reinforcement learning, as opposed to reinforcement learning, is typical to assume that the transition model known (see, for instance (Abheel & Ng. 2004), Footmote 8).

---

Published as a conference paper at ICLR 2024
concave) in each player's action (Atakan, 2003b). Finally, Part is standard assumption (see, for instance, Section of Bhandari & Russo (2019)), which guarantees that the policy parameterization is expressive enough to represent best responses.
Assumption 4 (Convex Parameterization), Given an inverse Markov game M assume that for all players E [n). states s E S, and action profiles a, b A. the per-state regret + 0) a r,(s, a. 0) is convex.
r, r,,s,, a
With these assumptions in hand, we face convex gradient-dominate optimization problem, i.e., + f(0,20 x) is convex, for all æ X. and æ + f(0, x) gradient-dominater for all E G. As for normal-form games (see Remark 1), the set of inverse NE in Markov games is convex under Assumptions and 4. Consequently, we can obtain polynomial-tin convergence of stochastic gradient descent ascent (Algorithm 2) by slightly modifying known results (Daskalakis et al., 2020).
Algorithm 2 requires an estimate of VJ f w.r.t. both 0 and Under Part 3 of Assumption 3, the gradient of f w.r.t. æ can be obtained by the deter- ministic policy gradient theorem (Sil- ver al., 2014), while the gradient of f w.r.t. O can be obtained by the lin- earity of the gradient and expectation operators. However, both of these gradients involve an expectation- over H (+.)), and H n²² As such, we estimate them using sim- ulated trajectories from the deviation history distribution H (h²,...,,h") hm)² ~ ig|n) (m. and the equilibrium history distribu-
Algorithm 2 Adversarial Inverse MARL
Inputs: O,P, Ja, 110, Tm, T, ( (0)
Outputs: (0(t), (())) ()) 1==
1: for 0..... 1 do
2:
H X |E|n] p(
# ht Dt!
3: (1++1) Ille o0())
(1) V volo (0(t), ,0 H h!)
11
4: (+-+)) f nI
x(t) 1/e
(t) V a (0 ;) H. hT)
5: return (010), (0()))
1==
tion ht ~ y² respectively. For given such pair (H, ht), the cumulative regret gradient estimators fe and fa correspond to the gradients of the cumulative regrets between each deviation history h' in H and h and can be computed directly using the chain rule for derivatives, as we assume access to differentiable game simulator."
Finally, define the equilibrium distribution mismatch coefficient ||067' /aulloo the Radon- Nikodym derivative the state occupancy distribution of the NE π w.rt. the initial state distribution μ.. This coefficient, which measures the inherent difficulty of reaching states under πt, is closely related to other distribution mismatch coefficients introduced in the analysis of policy gradient methods (Agarwal al., 2020). With this definition in hand, we can finally show polynomial-time convergence of stochastic GDA (Algorithm 2) under Assumptions 3-4.
Theorem 4.1. Under Assumptions for all e E (0, 1), Algorituu 2 is run with inputs that satisfy TED Ω E -100|106"' /0o and for all t E (T]. Ml > ea and (1) = E8, then the time-average of all parameters ((T) T+1 El ((t) is an E-inverse NE.
5 SIMULACRAL LEARNING
In this section, we consider the more realistic setting in which we do not observe an equilibrium, but observe only sample histories (h(*),, } = {s((..)), alt.A)),) ) y² associated with an unobserved equilibrium .,. The problem of interest then becomes one of not only inferring parameter values from observed behavior, but of additionally finding equilibrium policies that generate the observed first-order simulacrum. A first-order simulacrum can be
behavior, a solution which we refer seen as a generalization of an inverse equilibrium, as it not only comprises parameters that rationalize
For completeness, we show how to compute fa and fe Section 7.5. In our experiments, however. as has become common practice in the literature (Mora et al., 2021), we compute these gradients by simply autodifferentiating the cumulative regret of any history w.r.t. the policy parameters using library like Jax (Bradbury al., 2018). We also show that under Assumption 3, (fo, fe unbiased estimate of (Vof. V.f) whose variance is bounded.
7

---

Published as a conference paper at ICLR 2024
the observed histories, but also policies that mimic them in expectation. First-order simulacral learning is also known as multiagent apprenticeship learning (Abbeel & Ng. 2004; Yang et al., 2020).
Even more generally, we might not have access to samples (
Algorithm 3 Adversarial Simulacral Learning
nz from an equilibrium history distribu- tion, but rather lossy func- tion of those histories accord- ing to some function p that produces observations {ol(k) ]ee[d] - {o (ht(W) ) E dis- tributed according to some (pushforward) observation dis- tribution = E AOO), parame- terized by policy profile π P. where O is the observation space. This more general framework is very useful in applications where there are limitations on the data collection process: e.g.. if there are game states at which some the players' actions are unobservable, or when only an unfaithful function of them is available. Here, we seek to learn the more general notion of a second-order simulacrum.
Inputs: e, P, (go, Sa:-wagg By)y Outputs: (0it), (()), (t)) 1=
J. no. 7a fl T, ( (0)) y00) {ot(h)}
1: for 0, ,.... T do
~ X [n| ( (1)
v(1)
h ~ vinell))
2:
3: 0++11) t ll ((1) 1
(1) V 0:0 (10), x0(1 (1) H, h)
+
4: x ((-+)) t Ip x(1) T V x. Iu (0()) y (0) H.h)
5: ((++)) t lp
(()) + fy
V y By (0()
x (1, ( H.h)
6: return (0i (t), (
Formally, an inverse simulation I-1 = (M'' (tt, O,E, ) is a tuple consisting of a Markov game form MM0 \ gi with unknown parameters 0i, an observation distribution E P A AO) mapping policies to distributions over the observation space O, and an observation distribution = for the unobserved behavioral policy π which we assume is Nash equilibrium. Our goal is to find an (s, 6)- Nash simulacrum, meaning a tuple of parameters and policies (0","') E θ x P that (e. 8) simuulate the observations a Nash equilibrium: i.e., (,(T;; 0*) 2 max EP, (T nT 0*) and
( (o xg* |1lo - ot S Theorem 5.1, which analogous Corollary characterizes the set of Nash simulacra of an inverse simulation.
Theorem 5.1. Given an inverse simulation I- ' for any a, B > O, the set of Nash simulacra of M is equal to the set of minimizers of the the following stochastic min-max optimization problem:
[11o-o1] o']]²] + (,; (3)
min (00 π) min max g(, π. 608
p) p) a
E (0.0')=""
GE PEp TEP
TEP
To tackle simulacral learning, we approximate via realized observation samples (ot(k)
_x", based which we compute the empirical learning loss @(0, π, p) = 1/ - -ooo)(() |²] + (, O).) Additionally, as in the previous section, we once again restrict policies to lie within parametric class of policies pt, redefine g(0, x, y) = g(0, ,.. ") and @(0, x. y) = @(,, ,.= ,"",,,, and solve the ensuing optimization problem over the empirical learning loss min eexx maxyex @ x, y).
In general, this stochastic min-max optimization is non-convex non-concave. By Assumption 3, however, the function y - ( x, y) is gradient dominated, for all 0 E θ and E X. Nevertheless, is not possible to guarantee that (0, + g0, x, yy is convex or gradient dominated, for all y E Vi without overly restrictive assumptions. This claim is intuitive, since the computation of an inverse simulacrum involves computing a Nash equilibrium policy, which in general is a PPAD- complete problem (Daskalakis al., 2009; Foster al., 2023). Finally, defining gradient estimators as we did in Section 4, to obtain gradient estimators (ge. Iw Py (0, x, y; H,h" h²m from samples histories H X (e(n) (T,"" " and h ~ ,T² we can use Algorithm 3 to compute a local solution of Equation (3) from polynomially-many observations.
Theorem 5.2. Suppose that Assumption 3 holds, and that for all क E PX =x" is twice con- tinuousty differentiable in x. For any E (0.1), 1), if Algorithm 3 is run with inputs that satisfy
(t) T E Ω (1066"0106) /8ulloo) and for all L E [T], Yly x 5a and no x 58, then the best iterate
8

---

Published as a conference paper at ICLR 2024
(0 best: 2. best) converges e-stationary point of ip (defined in Section 7.2). Additionally, for any
5. 2 O, it holds with probability 1 1- ( that Gp (T) (T" sample observations 22(Ve² log(/<))-
(T) hest (0 2 best) S & if the number of best 2
6 EXPERIMENTS
We run two sets of experiments with the aim of answering two questions, Our first goal is to understand the extent to which our algorithms are able to compute inverse Nash equilibria, if any, beyond our theoretical guarantees. Our second goal is understand the ability of game-theoretic models to make predictions about the future." "
Electricty (Rteal Predicted)
Asimo MEGE: o.00e6
In first set of experiments, of economic games whose equilibria and payoff's have different properties. The first three are Fisher market (FM) games, which are zero-sum, between sellers and buyers engaged in trading goods. These games can be
consider five types
10
Our MSF no0
AFIMAA
20
Pric cleppoyy
0.8
categorized based on the buyers' utility functions as lin-
ear, Soub-DD or Leontief (Cheung et al., 2013). We then consider two general-sum economic games, which model competition between two firms, namely Cournot competition and Bertrand oligopoly. When budgets are the only parameters we seek to recover, our min-max for- mulation is convex-concave, because the players' payoffs are concave in their actions, and affine in their budgets, and hence the regret of players is also affine in the players' budgets. In addition, in both the Cournot competition and Bertrand oligopoly games, regret is again convex in the parameters of the game. Finally, all the games we study are concave, with the exception of the Bertrand oligopoly Cobb-Douglas FM, Cournot competition, and Bertrand oligopoly games. In each experiment, we generate 500 synthetic game instances, for which the true parameters are known, and use Algorithm I (which does not rely on this knowledge) to compute algorithm recovers the true parameters of the market and whether it finds an inverse NE (i.e., average exploitability). We summarize recovers the true parameters more often when budgets are the only parameters we seek to recover, as opposed to both budgets and types; but even in non-convex-coneave case, our algorithm is still able to approximate inverse NE over 80% of the time. In settings where the equilibria are unique we recover true parameters most often, while the worst performance is on Leontief FM games, where payoffs are not differentiable.
80
5000
20000
25000
55300 40000
1el
Figure 1: Hourly prices in the Spanish electricity market from January 2015 to December 2020. The Nash simulacrum achieves a MSE that is twice as low as that of the ARIMA method.
game, and the equilibria are unique in the
inverse NE for each. We record whether our
findings for the FM games in Table 2. We find that our algorithm
Game Parmmeters
Hudgets
Types
Budgets
Fisher Market Type
Linear
Lennter
(3>
Linear
Loonier
Cournot
Berirand
7% l'aruncterss Recovered
100%
36.8%
100%
12%
1%
99.6%
% Parameters Recovered
95.2%
78%
Average Exploitability
0.0018
0.2240
0.0004
0.0119
0.1949
0.0004
Average Exploitability
0,0000
0.0011
The percentage of games for which we recovered the true parameters and the average exploitabilities of the observed equilibrium evaluated w.r.t the computed inverse Nash equilibrium. In our second set of experiments, we model the Spanish electricity market as a stochastic Fisher market game between electricity re-sellers and consumers. In this game, the state comprises the supply of each good and the consumers' budgets, while the re-sellers' actions are to set prices in today's 's spot market and tomorrow's 's day ahead market, and the consumers' actions are their electricity demands. We assume the consumers utilities are linear; this choice is suited to modeling the substitution effect between electricity today and electricity tomorrow. Using publicly available hourly Spanish electricity prices and aggregate demand data from Kaggle, we compute simulacrum of the game that seeks to replicate these observations from January 2015 to December 2016. We also train an ARIMA model on the same data, and run hyperparameter search for both algorithms using data from January 2017 to December 2018. After pieking hyperparameters, we then retrain both models on the data between January 2015 to December 2018. and predict prices up to December 2018. We also compute the mean squared error (MSE) of both methods using January 2018 to December 2020 as a test set. We show the predictions of both methods in Figure 1. To summarize, we find that the simulacrum makes predictions whose MSE is twice as low.
Table 2:
Our code can be found here.
9

---

Published as a conference paper at ICLR 2024
REFERENCES
Pieter Abbeel and Andrew Y Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the twenty-first international conference Machine learning, pp. 1, 2004. 3, 6, 20
Sydney N Afriat. The construction of utility functions from expenditure data. International economic review, 8(1):67-77, 1967. 20
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. Optimality and approximation with policy gradient methods in markov decision processes. In Conference on Learning Theory. pp. 64-66. PMLR, 2020. 7
Kenneth Arrow and Gerard Debreu. Existence of equilibrium for a competitive economy. Econe- metrica: Journal of the Econometric Society, pp. 265-290, 1954. 4, 22
Alp E Atakan. Stochastic convexity in dynamic programming. Economic Theory, 22:447-455, 2003a.
4
Alp Atakan. Stochastic convexity in dynamic programming. Economic Theory: 22(2):447-455 2003b. ISSN 09382259, 14320479. URL http: http://ww...o....//aaaaoaaaaaaaa httpg////taeeeee/5555533 25055693.
Robert Aumann. Subjectivity and correlation in randomized strategies. Journal of mathematical Economics, 1(1):67-96 1974.
Monica Babes, Vukosi Marivate, Kaushik Subramanian, and Michael L Littman. Apprenticeship learning about multiple intentions. In Proceedings of the 28th international conference on machine learning (ICML-I1), I), pp. 897-904, 2011. 20
Patrick Bajari, Han Hong, and Stephen P Ryan. Identification and estimation discrete game of complete information. Econometrica, 78(5):1529-1566) 2010. 20
Jean Baudrillard. Simulacra and simulation. University of Michigan press, 1994. 2
Richard Bellman. On the theory of dynamic programming. Proceedings of the National Academy of Sciences of the United States of America, 38(8):716, 1952. 20
Aaron Bestick, Lillian Ratliff, Posu Yan, Ruzena Bajesy, and S Shankar Sastry. An inverse correlated equilibrium framework for utility learning in multiplayer, noncooperative settings. In Proceedings of the 2nd ACM international conference on High confidence networked systems, pp. 9-16, 2013. 3, 21
Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods. arXiv preprint arXiv:1906.00 01786, 2019. 3, 6, 7, 16, 18
Abdeslam Boularias, Jens Kober, and Jan Peters. Relative entropy inverse reinforcement learning. In Proceedings of the fourteenth international conference artificial intelligence and statistics, pp. 182-189. JMLR Workshop and Conference Proceedings, 2011. 20
Abdeslam Boularias, Oliver Krömer, and Jan Peters. Structured apprenticeship learning. In Machine Learning and Knowledge Discovery Databases: European Conference, ECML PKDD 2012, Bristol, UK, September 24-28, 2012. Proceedings, Part 11 23, pp. 227-242. Springer, 2012. 20
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne. and JAX: composable transformations of Python+NumPP programs, 2018. URL
Qiao Zhang.
http:/ / ggithub......gggggg com/ hamm///ool////////ooooooooo jax.
William C Brainard, Herbert E. Scarf, et al. How to compute equilibrium prices in 1891. Citeseer, 2000. 22, 24
Timothy F Bresnahan and Peter C Reiss. Empirical models of discrete games. Journal of Economet- rics, 4811-2):57-81 1991. 20
10

---

Published as a conference paper at ICLR 2024
Daniel Brown, Wonjoon Goo, Prabhat Nagarajan, and Scott Nickum. Extrapolating beyond sub- optimal demonstrations via inverse reinforcement learning from observations. In International conference on machine learning, pp. 783-792. PMLR, 2019. 20
Timothy C. Y. Chan, Rafid Mahmood, and Ian Yihang Zhu, Inverse optimization: Theory and applications, 2022. 20
Timothy CY Chan, Rafid Mahmood, and Ian Yihang Zhu. Inverse optimization: Theory and applications. arXiv preprint arXiv:2109.08:: 0..900 2021. 20
Xi Chen and Xiaotie Deng. Settling the complexity of two-player nash equilibrium. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS (FOCS)06), pp. 261-272. IEEE, 2006. 5
Yun Kuen Cheung, Richard Cole, and Nikhil Devanur. Tatonnement beyond gross substitutes? gradient descent the rescue. In Proceedings of the Forty-Fifth Annual ACM Symposium
Theorr of Computing, STOC '13, pp. 191-200, New York, NY, USA, 2013. Association for Computing Machinery. ISBN 9781450320290. doi: 10.1145/2488608 24886333,, URL https:
//doi.org/100 / 248///488860 208.//4488800.248838.38 2488633.
Jaedeug Choi and Kee-Fung Kim. Map inference for bayesian inverse reinforcement learning.
Advances in neural information processing systems, 24, 2011. 20
Adam Coates, Pieter Abbeel, and Andrew Ng. Apprenticeship learning for helicopter control. Communications the ACM, 52(7):97-105, 2009. 2
John M. Danskin. The theory of max-min, with applications. SIAM Journal Applied Mathematics, 14(4):641-664, 1966. ISSN 00361399. URL www.hhttp//tt 17
//t:://wwwwwww jstor. org/ wtt.://oootoottaaa/////eee///// httr///aaaeee29422....3
Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. The complexity of computing a nash equilibrium. SIAM Journal on Computing, 39(1):195-25) 2009. 5,
Constantinos Daskalakis, Dylan Foster, and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. Advances in neural information processing systems, 33: 5527-5540, 2020. 7, 16, 18, 19
Arlington M Fink. Equilibrium in stochastic n-person game. Journal of science of the hiroshima university, series ai (mathematics), 28(1):89-93, 1964. 2, 4
Dylan Foster, Noah Golowich, and Sham M Kakade. Hardness of independent learning and sparse
equilibrium computation markov games. arXiv preprint arXiv:2303. 12287, 2023. 8
Justin Fu, Andrea Tacchetti, Julien Perolat, and Yoram Bachrach. Evaluating strategic structures in multi-agent inverse reinforcement learning. Journal of Artificial Intelligence Research, 71: 925-951, 2021. 3,
David Gale. The theory of linear economic models. University Chicago press, 1989. 22
Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, and Asuman Ozdaglar. Last iter- ate is slower than averaged iterate in smooth convex-concave saddle point problems. CoRR, abs/2002.00057, 2020. URL https:://asdvv.orr////a//
00057. 5
Eduard Gorbunov, Adrien Taylor, and Gauthier Gidel. Last-iterate convergence of optimistic gradient method for monotone variational inequalities. Advances in neural information processing systems, 35:21858-21870) 2022. 5
Amy Greenwald and Amir Jafari. A general class of no-regret learning algorithms and game-theoretic equilibria. Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLI/Kernel 2003, Washington, DC, USA, August 24-27, 2003. Proceedings, pp. 2-12. Springer, 2003.
Sanford J Grossman and Oliver Hart. An analysis the principal problem. In Foundations of Insurance Economics: Readings in Economics and Finance, pp. 302-340. Springer, 1992. 1

---

Published as a conference paper at ICLR 2024
Dylan Mladiild-Menede Stuart Russell, Pieter Abbeel, and Anca Dragan. Cooperative inverse reinforcement learning. Advances in neural information processing systems, 29, 2016. 21
John C Harsanyi. Games with incomplete information played by "bayesian" players, i-iii part i. the basic model. Management science, 14(3):159-18,, 1967.
John C. Harsanyi. Games with incomplete information played by "bayesian" players, i-iii. part iii. the basic probability distribution of the game. Management Science, 14(7):486-502 1968. ISSN 0025 I 52265501. URL http: www. jstor. org/ http///abbeeeeee22eee/
Clemens Heuberger. Inverse combinatorial optimization: A survey on problems, methods, and results. Journal of combinatorial optimization, 0,329-361, 2004. 20
Bengt Holmström. Moral hazard and observability. The Bell journal of economics, pp. 74-91, 1979.
Kamal Jain, Vijay V Vazirani, and Yinyu Ye. Market equilibria for homothetic, quasi-coneave utilities and economies of scale in production. In SODA, volume 5, pp. 63-71, 2005. 22
Shankar Kalyanaraman and Christopher Umans. The complexity of rationalizing matchings. In Algorithms and Computation: 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008. Proceedings 19, pp. 171-182. Springer, 2008. 20
Shankar Kalyanaraman and Christopher Umans. The complexity of rationalizing network formation. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pp. 485-494. IEEE, 2009. 20
Edouard Klein, Matthieu Geist, Bilal Piot, and Olivier Pietquin. Inverse reinforcement learning through structured classification. Advances in neural information processing systems, 25, 2012. 20
Edouard Klein, Bilal Piot, Matthieu Geist, and Olivier Pietquin. A cascaded supervised learning approach to inverse reinforcement learning. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2013, Prague, Czech Republic, September 23-27, 2013, Proceedings, Part I 13, pp. 1-16. Springer, 2013. 20
Volodymyr Kuleshov and Okke Schrijvers. Inverse game theory: Learning utilities in succinct games. In Web and Internet Economics: 11th International Conference, WINE 2015, Amsterdam, The Netherlands, December 9-12, 2015, Proceedings 11, pp. 413-427. Springer, 2015. 1,3, 20, 21
Sergey Levine, Zoran Popovic, and Vladlen Koltun. Nonlinear inverse reinforcement learning with gaussian processes, Advances in neural information processing systems, 24, 2011. 20
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-comeave minimax problems. In International Conference on Machine Learning, pp. 6083-6093, PMLR, 2020. 3, 18
Xiaomin Lin, Peter A Beling, and Randy Cogill. Multiagent inverse reinforcement learning for two-person zero-sum games. IEEE Transactions on Games, 10(1):56-68, 2017. 21
Xiaomin Lin, Stephen C Adams, and Peter A Beling. Multi-agent inverse reinforcement learning for certain general-sum stochastic games. Journal of Artificial Intelligence Research, 66:473-502, 2019. 3, 21
Wietze Lise. Estimating a game theoretic model. Computational Economics, 18:141-157, 2001. 20
Manuel Lopes, Francisco Melo, and Luis Montesano. Active learning for reward estimation in inverse reinforcement learning. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 31-46. Springer, 2009. 20
Andreu Mas-Colell, Michael D. Whinston, and Jerry R. Green. Microeconomic Theory. Number 9780195102680 in OUP Catalogue. Oxford University Press, 1995. ISBN ARRAY URL https::///// //iea//..////////////////aa/aa www.deaasseeee..eeeeeeeeeeeeee.. org /b/gg//// http://///p///////////////// httpp//boook///// 9900019011111 95102680. .tml.. 20
Eric Maskin and Jean Tirole. Markov perfect equilibrium: I. observable actions. Journal of Economic
Theory, 191 2001. 4
12

---

Published as a conference paper at ICLR 2024
Miguel Angel Zamora Mora, Momchil Peychev, Schoon Ha, Martin Vechev, and Stelian Coros. Pods: Policy optimization via differentiable simulation. In International Conference on Machine Learning, pp. 7805-7817. PMLR, 2021.
Hervé Moulin and J P Vial. Strategically zero-sum games: the class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory, 1210, 1978.
John F. Nash. Equilibrium points in lron</i>-person games. Proceedings of the National Academy of Sciences, 36(1):48 49, 1950. doi: 10. 10.1073/pnas.56.1444 URL httpt: www. pnas org/ doi/abs/ 10. 1073/pnas 36. 88. 1, 2,
Sriraam Natarajan, Gautam Kunapuli, Kshitij Judah, Prasad Tadepalli, Kristian Kersting, and Jude Shavlik. Multi-agent inverse reinforcement learning. In 2010 ninth international conference on machine learning and applications, pp. 395 400. IEEE, 2010. 2, 3, 21
Denis Nekipelov, Vasilis Syrgkanis, and Eva Tardos. Econometrics for learning agents. In Proceedings of the sixteenth acm conference on economics and computation, pp. 1-18, 2015. 20
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic
approximation approach stochastic programming. SIAM Journal on oplimization, 19(4):1574- 1609, 2009. 16
Andrew Ng, Stuart Russell, et al. Algorithms for inverse reinforcement learning. In lcml, volume 1, pp. 2, 2000. 20
Hukukane Nikaido and Kazuo Isoda. Note non-cooperative convex games. Pacific Journal of Mathematics, 5($1):807-815, 1955.
Alexander Peysakhovich, Christian Kroer, and Adam Lerer. Robust multi-agent counterfactual prediction. Advances in Neural Information Processing Systems, 32, 2019. 1
Deepak Ramachandran and Eyal Amir. Bayesian inverse reinforcement learning. In ISCAI, volume 7,
pp. 2586-2591, 2007. 20
Nathan D Ratliff, Andrew Bagnell, and Martin A Zinkevich. Maximum margin planning. In
Proceedings of the 23rd international conference on Machine learning, pp. 729-736, 2006. 20
Paul A Samuelson. Consumption theory in terms of revealed preference. Economica, 15(60):243-22 253,,
1948. 20
Lloyd S Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10): 1095-1100, 1953. 2,4
David Silver, James Bagnell, and Anthony Stentz. High performance outdoor navigation from overhead data using imitation learning. Robotics: Science and Systems IV, Zurich, Switzerland, 1, 2008. 20
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In International conference on machine learning, pp- 387-395. Pmlr, 2014.
Jaming Song, Hongyu Ren, Dorsa Sadigh, and Stefano Ermon. Multi-agent generative adversarial imitation learning. Advances in neural information processing systems, 31, 2018. 3
Hyung Ju Suh, Max Simchowitz, Kaiqing Zhang, and Russ Tedrake. Do differentiable simulators give better policy gradients? In International Conference Machine Learning, pp. 20668 20696. PMLR, 2022. 6, 25
Gokul Swamy, Sanjiban Choudhury, Andrew Bagnell, and Steven Wu. Of moments and matching: A game-theoretic framework for closing the imitation gap. In International Conference on Machine Learning, pp. 10022-10032. PMLR, 2021.
Umar Syed and Robert E Schapire. A thme-theoretic approach to apprenticeship learning. Advances in neural information processing systems, 20, 2007. 20
13

---

Published as a conference paper at ICLR 2024
Vasilis Syrgkanis, Elie Tamer, and Juba Ziani. Inference auctions with weak assumptions information. arXiv preprint arXiv:/710.038300, 2017. 1, 20
Masayuki Takahashi. Equilibrium points of stochastic non-cooperative n-person games. Journal of Science of the Hiroshima University, Series Al (Mathematics), 28(1):95-99, 1964. 2, 4
Ben Taskar, Vassil Chatalbashev, Daphne Koller, and Carlos Guestrin. Learning structured prediction models: A large margin approach. In Proceedings of the 22nd international conference on Machine learning, pp. 896 903,900,,200 2005. 20
Evangelos Theodorou, Jonas Buchli, and Stefan Schaal. A generalized path integral control approach to reinforcement learning. The Journal of Machine Learning Research, 11:3137-3181, 2010. 20
Hal R Varian. The nonparametric approach demand analysis. Econometrica: Journal of the Econometric Society, pp. 945-973, 1982. 20
Hal R Varian. Revealed preference. Samuelsonian economics and the twenty-first century, pp. 99-119,
2006. 20
Leon Walras. Elements de l'economie politique pure, ou, Theorie de richesse sociale. Rouge, 1896. 22
Kevin Waugh, Brian D Ziebart, and J Andrew Bagnell. Computational rationalization: The inverse equilibrium problem. arXiv preprint 1308. 2013. 5,
Markus Wulfmeier, Peter Ondruska, and Ingmar Posner. Maximum entropy deep inverse reinforce- ment learning. arXiv preprint arXiv: (507004480 2015. 20
Mingzhou Yang. Yanhua Li, Xun Zhou, Hui Lu, Zhihong Tian, and Jun Luo. Inferring passengers' interactive choices on public transits via ma-al: Multi-agent apprenticeship learning. In Proceedings of The Web Conference 2020, pp. 1637-1647, 2020. 3,
Lantao Yu, Jiaming Song, and Stefano Ermon. Multi-agent adversarial inverse reinforcement learning. In International Conference on Machine Learning, pp. 7194-7201, PMLR, 2019. 3, 21
Ernst Zermelo. Über eine anwendung der mengenlehre auf die theorie des schachspiels. In Proceed- ings of the fifth international congress of mathematicians, volume 2, pp. 501-504. Cambridge University Press Cambridge, 1913.
Brian Ziebart, Andrew L Maas, J Andrew Bagnell, Anind K Dey, et al. Maximum entropy inverse reinforcement learning. In Aaai, volume 8, pp.
Chicago, IL, USA, 2008. 20
14


Reviews:
[{"review_id": "qIFr0OtbT3", "reviewer": "Reviewer_WrBZ", "summary": "The paper introduces a generative-adversarial (or min-max) characterization of the inverse game theory problem where a generator provides payoff parameters that minimize total regret, and a discriminator looks for action-profiles that maximize it. A min-max objective mimicking this two-player game is optimized to estimate the inverse equilibrium using gradient descent ascent algorithm (and other variations of it). It is further proposed that for games that satisfy certain assumptions guaranteeing convex-concavity of the objective, the algorithm converges in a number of iterations that are polynomial in the precision of the obtained inverse equilibrium. This formulation is further extended to give algorithms for multi-agent inverse reinforcement learning and multi-agent apprenticeship learning, accompanied by polynomial time (and space) convergence guarantees under appropriate assumptions. Experiments are conducted to identify categories of games for which the method is effective, and whether its usefulness goes beyond provided theoretical limits.", "questions": "What does the term $\\psi(\\pi, \\rho; \\theta)$ in the \"Multiagent Apprenticeship Learning\" section expand to? Cannot seem to find a definition anywhere.\n\nAssuming that Algorithm 3 was used on the spanish electricity market data, how was the observation distribution specified?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "* An inverse game theoretic perspective to multi-agent inverse reinforcement learning is certainly a novel direction to approach the problem with. Backed by results in inverse game theory, this approach leads to algorithms with desirable convergence guarantees that prior work in multi-agent imitation learning does not provide.\n\n* The low restrictiveness of the assumptions made allow for the framework to be effective on a vast majority of markov games, leading to useful and efficient solutions on a wide variety of multi-agent problems.\n\n* While the paper focuses on the inverse nash equilibrium, the simplicity of the objective allows for easy extensions of the framework to alternative game theory solution concepts.\n\n* All presented algorithms are succinct and easy to understand. Sufficient mathematical background is provided as and when necessary.", "weaknesses": "* It would be helpful to expand on the proofs of theorems 6.1, 6.2, and 6.3 in the supplementary material. I know that a reference has been provided, but a slight explanation of the cited result and how it relates to the theorem in question would be nice.\n\n* Although a comparison of the method has been shown with the ARIMA model on the spanish electricity market data, it would be beneficial to have a comparison with prior methods in inverse multi-agent reinforcement learning. Especially in terms of efficiency since it's one of the main points of the paper. The abstract says that the method outperforms other widely-used methods (plural), and we only get to see it being compared with one other model which is specific to time-series data. \n\n* Some comparison/contextualization with prior work in multiagent inverse reinforcement learning would also be helpful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TYtLCNVLDj", "reviewer": "Reviewer_Wrco", "summary": "This paper studied inverse game theory to find parameters of the payoff functions of the game. Polynomial time and sample efficient algorithms are provided and claimed.", "questions": "1. See weaknesses.\n\n2. Can you further polish the paper? Some typos: for example, in the fifth line of the abstract, should it be \"to solve them\"?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "1. This paper formulate the inverse game as an generative-adversarial optimization problem and provide polynomial time algorithms.", "weaknesses": "1. The proofs are not completed, e.g., I cannot find the proofs for Theorem 4.1 and Theorem 5.2.\n\n2. The presentation can be further improved, e.g., more intuitions about the assumptions and theorems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wgF4Csqwyj", "reviewer": "Reviewer_F6LX", "summary": "This paper formalizes the problem of inverse game-theory (determining\nequilibrium strategies and associated game structure from historical play) as a\nnovel min-max optimization problem and solves it using a primal-dual gradient\nmethod. This technique is deployed on a practical and interesting application\ndomain of market pricing dynamics.", "questions": "Remark 1 is indeed interesting, but it is not obvious. Did I miss an associated\nproof or example?\n\nWhy was the proof of Theorem 3.2 omitted? Was it rephrased to appear as Theorem\n6.1 in the supplementary material?  Establishing the convergence rates of\nvarious algorithms is not my expertise, but the results seem reasonable,\nespecially given assumptions of convexity and Lipshitz smoothness.", "limitations": "", "rating": 10, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The simple formulation of the set of inverse Nash equilibria (NE) as a min-max\ngame is elegant and appears to be original. If it is indeed original, for this\nalone, the paper merits publication and should be highlighted.\n\nThe paper overall is well written and showcases immediate applications of the\nproposed solution to an important and practical domain as a proof-of-concept. I\nbelieve these results are significant and will be impactful.", "weaknesses": "As an easily rectified issue, Figure 1 could have been better represented by\nplotting residuals over time or, by subsampling the data, plotting mean\nresiduals with error bars.\n\nAs a minor complaint, I do not prefer the language of \"generative-adversarial\"\n(especially not in terms of a \"discriminator\"), even if this is the closest\nanalogy familiar to machine learning practitioners: This is a standard min-max\noptimization problem that need not be wed to the ML setting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9uG83ji1iD", "reviewer": "Reviewer_zp62", "summary": "Game theory provides a structured approach to predicting outcomes of interactions between rational agents. Inverse game theory deals with situations where the players' behavioral models are unknown and aims to deduce the payoff functions that explain observed actions as equilibria. This paper presents a new approach for solving inverse equilibrium problems in a range of games, using generative adversarial optimization to match game-theoretic models to observed data and make predictions, as exemplified by modeling the Spanish electricity market.", "questions": "Minor remark/question: what is the meaning of that weird symbol in Theorems 3.2, 4.1, 5.2? I assume it means of the same order as (but I don't think this is standard notation.)\nIn Theorem 3.2, it is a little bit surprising that the optimal is obtained by averaging prior solutions instead of the last one. What is the intuition behind averaging (which includes initial solutions that can be of very low quality)? I assume the proof is correct.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The authors study an interesting and challenging problem of inverse MARL. The theoretical results are nice; they are simple yet relevant and impactful. \nThe experiments on an electricity market are well thought and designed.", "weaknesses": "The readability can be improved. I think Section 3 never mentions that it is for the one-shot game setting. \nThere is no methodological contributions. All presented algorithms are simple extension of known algorithms. (On the other hand we should not invent/propose algorithms just for the sake of proposing them).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)