Inverse Game Theory for Stackelberg Games: the Blessing of Bounded Rationality
Authors: Jibang Wu
Weiran Shen
Fei Fang
Haifeng Xu
Venue: NeurIPS 2022 Accept (2022)
Keywords: Stackelberg game
inverse game theory
quantal response
bounded rationality

Abstract: Optimizing strategic decisions (a.k.a. computing equilibrium) is key to the success of many non-cooperative multi-agent applications. However, in many real-world situations, we may face the exact opposite of this game-theoretic problem --- instead of prescribing equilibrium of a given game, we may directly observe the agents' equilibrium behaviors but want to infer the underlying parameters of an unknown game. This research question, also known as inverse game theory, has been studied in multiple recent works in the context of Stackelberg games. Unfortunately, existing works exhibit quite negative results, showing statistical hardness and computational hardness, assuming follower's perfectly rational behaviors. Our work relaxes the perfect rationality agent assumption to the classic quantal response model, a more realistic behavior model of bounded rationality. Interestingly, we show that the smooth property brought by such bounded rationality model actually leads to provably more efficient learning of the follower utility parameters in general Stackelberg games. Systematic empirical experiments on synthesized games confirm our theoretical results and further suggest its robustness beyond the strict quantal response model.

Inverse Game Theory for Stackelberg Games: the Blessing of Bounded Rationality
Jibang Wu
Weiran Shen
Department of Computer Science University of Chicago wujiabang@uchiccom cage..c.aaco.ooooooo go. edu
Gaoling School of Artificial Intelligence Renmin University China
shenweirane ruc.run....rrrrre.ee edu.
Fei Fang Institute for Software Research
Haifeng Xu
Department of Computer Science
Carnegie Mellon University fei f cmu. edu
University of Chicago hai haifengxuuuchiiaag edu
Abstract
Optimizing strategic decisions (a.k.a. computing equilibrium) is key the success of many non-cooperative multi-agent applications. However, in many real-world situations, we may face the exact opposite of this game-theoretic problem instead of prescribing equilibrium of given game, we may directly observe the agents' equilibrium behaviors but want to infer the underlying parameters of unknown game. This research question, also known as inverse game theory, has been studied in multiple recent works the context
Stackelberg games. Unfortunately, existing works exhibit quite negative results, showing statistical hardness [27 37 and computational hardness [24] 25 26), assuming follower's perfectly rational behaviors. Our work relaxes the perfect rationality agent assumption the classic quantal response model, a more realistic behavior model of bounded rationality. Interestingly, we show that the smooth property brought by such bounded rationality model actually leads to provably more efficient learning the follower utility parameters in general Stackelberg games. Systematic empirical experiments on synthesized games confirm our theoretical results and further suggest its robustness beyond the strict quantal response model.
Introduction
One primary objective of game theory is to predict the behaviors of agents through equilibrium concepts in a given game. In practice, however, we may observe some equilibrium behaviors of agents, but the game itself turns out to be unknown. For example, can observe the shoppers' purchase decisions on different sale prices, but the platform has limited knowledge of the exact utilities of the shoppers. Similarly, while the policymaker could observe the market reactions to its policy announcement, the exact motives behind traders' reactions are usually unclear. In various security domains, the defender may want understand the intentions incentives of the attackers from their responses to different defense strategies so as to improve her future defense strategy. As such, recovering the underlying game parameters would not only lead us to better strategic decisions, but also improve our explications of the motives and rationale in the dark.
online shopping platform
These potentials and prospects motivate a class of research problems known as the inverse game theory [261: given the agents' equilibrium behaviors, what possible utilities that induce these behaviors? In this paper, we specifically target the sequential game setting from the perspective the
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

first-moving agent (e.g., Internet platform, policymaker, or defender) whose different strategies (e.g.. price, regulation, or defense scheme) would induce different equilibrium behaviors of the following agent (e.g., Internet users, traders, or attacker). Studies of such game settings have seen broad impacts and extensive applications ranging from the principal-agent problems in contract design [2 19]. the AI Economist
+ to security games modeled for social good [T6]. We formalize our problem
under the normal form Stackelberg game, where a leader has the commitment power of a randomized strategy, and a follower accordingly decides his response. It is known that the optimal commitment of the leader can be efficiently computed in a single linear program, given full knowledge of the game [4] However, the inverse learning problem to determine the underlying game from the follower's responses is more challenging: Letchford et al. (27]), Peng et al. [B7] show that learning optimal leader strategy from the follower's ' best responses requires number of samples that is high-degree polynomial in the game size and may be exponential in the worst cases. This significantly limits the practicality of these algorithms, the leader usually cannot afford the time cost gather feedback from so many interactions.
More concerning is the inconvenient reality that we can hardly expect the agents' optimal equilibrium responses assumed in existing work. In fact, these shoppers, traders, or attackers themselves hardly know their exact utilities and are naturally unable to determine the expected-utility maximizing strat- egy. Extensive studies of behavioral economics and psychology [23 51 32 ITI ITC have pinpointed the cognitive limitations that make human decisions prone to the noisy perception of their utilities. Among various models for quantifying irrational agent behaviors, one of the most popular ones is perhaps the quantal response (QR) model [22, which adopts the well- logit choice model to capture agents' probabilistic selection of actions. This will also be the bounded rationality model of our focus in this paper.
The Blessing of Bounded Rationality. The key insight revealed from this paper is that the extra layer of behavioral complexity due to bounded rationality, while complicating the modeling and computation, provides a more informative source for us to learn the underlying utility of agents. To understand the intuitions and motivations behind our results, consider case where the follower has dominated action J1 as shown in Table I where the leader's ' and follower's 's utility of action profile (i,j) is specified by ui_j. U4 respectively. Conventionally, such instance is treated as degenerated instance, because the leader could ignore the action ji that a perfectly rational follower would never play. Then, the optimal leader strategy is clearly to always play the action i2. However, when facing
Ug.jj Ut.j
j1
j2
21
100, 0.9
0.9, 1
12
99, 0.9 1.1,
Table 1: An example of dangerously "degenerated" Stackelberg game.
boundedly rational follower, it becomes possible to observe the response j1 and estimate the utilities regarding this dominated action. For example, if the follower plays his action ji and ja at almost the same frequency, the follower's 's expected utility on the two actions should be close. Although such dominated action has no effect on the leader's 's optimal strategy against a perfectly rational follower, it could be a potentially damaging (or beneficial) action that leader want to avoid (or encourage) a bounded rational follower to play. That is, in the above game instance, if somewhat irrational follower plays action j1, would be dangerous for the leader to play action ég yet rewarding to play action i therefore, a more robust leader strategy should randomize by assigning some probability to play action i, We remark that general, even without such extreme case of dominated actions, the extra payoff information is now available on how much worse (or better) it is to use the empirical frequency of the boundedly rational action responses (as long as some smoothness propertics are exhibited), which are overlooked under the assumption of perfectly rational followers.
Our Results. We present a set of tight analysis on the number of strategies and sample complexity sufficient and necessary to learn the follower's 's utility, for both situations in which the leader can observe the follower's s full mixed strategies or only the follower's sampled pure strategies. In the former situation of observing follower's mixed strategies, our algorithm can recover the follower utility parameters using m follower mixed strategy responses in any general Stackelberg game where m is the number of leader actions. Surprisingly, the required number of queries is independent of follower actions! This is due to the fact that the randomness introduced by bounded rationality carries much more information about follower payoffs, compared to the perfect best response. In the later
2

---

(more realistic) situation of only observing follower's 's sampled pure strategy, our algorithm learns the follower utility parameters within precision with probability at least 6 using O m ( /8) pe²
carefully chosen queries, where n is the number of follower actions and p depends on agent's bounded rationality level and is of order (1/nn) for typical boundedly rational agents. Interestingly, the additional challenge of only observing sampled actions only deteriorates the sample complexity by factor of log( (mn))// These sample completexity results should be compared with that of B7 27. which study similar learning questions but from perfectly rational follower responses. The m log /m))/p order in our sample complexity is in sharp contrast to their complexity with exponential dependence in m or n in the worst case. Our experimental results empirically confirm the tightness of our sample complexity analysis.
At the conceptual level, our work illustrates that noises due to bounded rational behaviors could be leveraged as additional information sources to learn the follower utility. This intuition also drives the design of our analytical tools to explain how efficient and effective learning of the follower's utility is possible in real situations, in complementing the previous negative results developed under the idealized perfect rational behavior models 2
2 Related Work
Learning in Stackelberg Game The learning problem in sequential games has been studied in several different setups. Marecki et al. [0,, Balcan et al. 7 consider the online learning problem in the Stackelberg security game with adversarially chosen follower types. Bai et al. [6 consider bandit learning setting where one could query any entry of the followers' utility under noise and use the estimation of utility to approximate the optimal leader strategy; however, this learning process assumes centralization, that is, the learner can control both leader's and follower's 's actions. More similar to ours is the strategic learning setup in Stackelberg games studied by 2 37 y. where the leader adaptively chooses her strategies based on the observation of the follower's 's best response and eventually recovers the follower's utility up some precision level.
Bounded Rationality. McKelvey and Palfrey 32 introduced the quantal response equilibrium (QR)) by adopting the logit choice model 15
QRE serves as strict generalization of Nash cquilibrium (NE)- - when the agents become perfectly rational, QRE converges to the NE, The modeling success of QR model attributes to the nice mathematical and statistical properties of the logit function that can capture a variety of boundedly rational behaviors under different parameter A. QRE is widely adopted especially in Stackelberg (security) games [42 35
31
20 12] and zero-sum games (29) and notably has been deployed in various real world application [2] 17]. Moreover, the model structure of QR has been also used in various other contexts, such the softmax activation in neural network [8. multinomial logistic regression [ and the multiplicative weight update
39
16.
algorithm for no-regret learning
As an initial attempt to our general learning problem, we also adopt the QR model to capture our agent's 's bounded rational behavior, for its modeling success in practice and being the most common choice of prior work 42
17 We acknowledge that there exist other models of bounded rational behaviors beyond the QR model. For example, Kahneman 23 introduced the prospect theory to model the bounded rationality of agents in games under risk; Camerer et al. proposed the cognitive hierarchy theory that classifies the agents according to their degree of reasoning in forming expectations of others. We anticipate that the message of our paper - i.e., the observation of suboptimal responses could provide additional information to learn the follower's preferences - would apply to many of these bounded rationality models.
3
16 20
Inverse Game Theory. Vorobeychik et al. 40 considered the payoff function learning problem using the strategy profiles and the corresponding utilitics through regression. Kuleshov and Schrijvers 26 introduced the concept of inverse game theory, and the authors showed that the problem of computing the agents' utilities from a set of correlated equilibrium is NP-Hard, unless the game is known to have special structures. More recently, the inverse game theory problem is studied under the QR model and leads to a few positive results: Sinha et al. [39 considers the offline PAC-Iearning setup where the follower responses can be predicted with small error for fixed leader strategy
Note that the (8)(&) follower actions) have randomness.
22 term comes from concentration bound and is natural when observations (i.e., observed
3

---

distribution; Haghtalab et al. 20
proves only three strategies are sufficient to recover linear follower payoff functions in security games: Ling et al. 29 presents an end-to-end learning framework that learns the zero-sum game payoff from its QRE. Following their success, our paper is the first work that provides theoretical guarantee of payoff recovery general Stackelberg game. Finally, inverse problems have received significantly more attention in single-agent decision making problems; The most notable problem is the inverse reinforcement learning pioneered by Ng et al. [4] Abbeel and Ng (T.
3 Problem Formulation
Game Setup We consider the Stackelberg game between a single leader (she) and follower (he). We let U E mmx (resp. V E R ) be the leader (resp. follower's) utility matrix, where m, the number of actions for the leader (resp. follower). We use GU, V) to denote the game instance. Each entry Ui (resp. Bi.5) of the utility matrix denotes the leader's utility (resp. follower's utility) when leader plays action and follower plays action j. Without loss of generality, let u4ys Vi,j E [0, 1]. Let V33 E RT be the jth column of the matrix V. We denote the set of the leader's (resp. follower's) s) action set by [m]] == (1,...,m) m (resp. [n] == (1,...,n)).
In this sequential game, the leader moves first by committing to a (possibly randomized) strategy, x = (I1, Fmm E Am. where the simplex Am = {x Lie(m] I2 = 1 and 0 S 24 S 1] and each 24 represents the probability the leader playing action i. Similarly, let An denote the follower's strategy space. Under perfect rationality, given the leader's s committed strategy, the follower would in turns chooses the best response action j that maximizes his utility, i..., = argmaxje(w fx Vý}. In our problem, we use the QR model instead to capture the follower's bounded rational behavior. That is, the follower would respond to the leader's s committed strategy by choosing strategy y" that maximizes his utility up to a Gibbs entropic regularizer, i.c., y" = argmax y {Ax' Vy y In y). This is shown to be equivalent to the setting where the follower is best responding according to the payoff perturbed by noises from a Gumbel distribution [22]. And we know the close form solution of follower's 's optimal strategy for this convex optimization program is exactly the logit choice model on
the true payoff, i.e., for each E [n). D4 Exejal exp(Ax V2.)
exp(A= V,)
33
We refer to À as the bounded rationality constant that is given in each specific problem, as several existing work have already determined its empirical value in practice: the human behavior experiments in compute = 7.6; the experiments 36 32
show is in the range of 4 to 16
Learning Problem We consider the inverse game theory problem in sequential game with unknown follower utility and seek to quantify how much the leader can learn about bounded rational follower's utility. We frame this problem under active and strategic learning setup, where the leader can interactively choose a randomized strategy and observe follower's strategic responses. Specifically, at each round t E [T'. the leader commits to a strategy and responds based on the QR strategy (t). Below we will consider both feedback settings based on whether the leader is able to observe the exact distribution ytt) or merely its samples.
x (t). The follower observes the committed (()
We set our primary learning objective as to recover a full characterization of the follower's utility; our results below shall explain how it is unnecessary and almost unrealistic to expect an exact recovery of the follower's utility. And we show in Observation | |nnn Theorem | that such utility characterization can be used to compute the optimal leader strategy under both perfect rationality, known as the strong Stackelberg equilibrium (SSE), and bounded rationality, known as the quantal Stackelberg equilibrium (QSE). And besides developing the optimal (or robust) leader strategies, we believe the recovered utilities are generally useful for our better understanding and reasoning of the followers' motives. However, given the limited scope of the paper, focus on the inverse game theory problems and defer the problems regarding how to strategize using the knowledge of game (i.c., the typical game-theoree theoretical problems) to related and future work.
Such learning problem has been considered in 20 specifically for Stackelberg security games, where the payoff is strictly simplified single-dimensions linear utility function. Our paper overcomes the curse of dimensionality and answers the open question in recovering payoffs in the general Stackelberg game. On the other hand, Sinha et al. B39 showed case of learning the nonparametric
'The À estimations are normalized the utility scale in |0. 1].

---

Lipschitz function (which includes the payoff function in the general Stackelberg game as a special case) in PAC-learning setup and they obtained a sample complexity exponential to the number of actions. Notably, the PAC-learning problem is fundamentally different from our active learning problem, as its learning guarantee tied to the given data distribution and is not guaranteed to recover the follower's payoff.
4 Theoretical Results
4.1 Warm-up: Learning from Mixed Strategies
As warm-up, we first consider rather ideal case where the leader can directly observe the follower's mixed strategy yt)). In this case, it turns out that the leader would be able to perfectly recover the follower's s payoff' matrix from his responses to different strategies and thereby determine the her optimal strategy. Despite a seemingly intuitive result, its underlying rationale is actually not as straightforward Specifically, many would raise the following doubt: the logit transformation is not bijective and thus its inverse mapping is not injective; in particular, it only gives us a system of at most 1 different linear equations w.r.t. the follower's 's utility; one can check that if we add constant to all entries of the utility matrix, the resulting probability distribution stays the same after the logit transformation. Thus, it should require more than such linear equation systems to recover a utility matrix with m x n unknown parameters. However, thanks to Observation [T] it happens that the follower's utility matrix can be fully characterized by x (n 1) parameters that is essentially the difference of each column in the utility matrix. This somewhat coincidentally compensates the missing information on follower utility due to the logit transformation.
Knowing that m strategies is the lower bound of this learning problem in general, below we will explicitly construct learning algorithm that have the matching upper bound. To begin, useful game-theoretic property of Stackelberg games is the following observation about the class of follower utilities that will induce the same leader and follower policies. While similar observation has been made in
20 39].
we also provide a formal proof in Appendix A for completeness.
Observation 1 (Equilibrium Invariance under Payoff Transformation). For any V {V +V+c& In l/lc RT'", }. i.e. a row-wise shifted matrix of V, the follower's 's quantal response (resp. best response) policy to leader's committed strategy remains the same, and thus the optimal leader strategy in SSE QSE remains the same.
Observation suggests that the row-wise shifted payoff matrix is just as good the ground-truth payoff matrix in our setting. This essentially means that only the difference between action payoffs matters for the follower's policy. As such, we introduce a row-wise distance metric that accommodates such policy-invariant transformation to empirically measure the quality of the recovered follower utility.
Definition 1 (Logit Distance). We define logit distance between the ground truth follower utility V and the recovered follower utility V E Rmxn, ΦVV = mn Eiejm min; V V; 2
Whenever the distance 4 (V, V) = O, we say that the recovered follower utility is perfect.
We next present a result that generalizes the well-known result, three strategies to success in security games, by Haghtalab et al. 20). Notably, we identify a simple but fundamental condition (in terms of rank) necessary to recover the game payoffs, rather than the special distance conditions tailored to the structure of the security game as in (20). The notion of rank has a clear physical meaning and we would later follow this theoretical insights to design learning algorithm to actively select leader strategies to query.
Proposition 1 (m Strategies Success). There exists learning algorithm that can always perfectly recover the follower strategy from m queries of the follower's mixed strategies.
Proof Sketch. We pick m linearly independent basis vectors for each x=()) in rounds and argue that the following optimization program can perfectly recover the follower's utility matrix V.
minimize
Exe(mi =(1) = (xx VV,
[lo E exp (t) y(t) x(1)
(4.1)
for t E [m].
5

---

We can see that the objective of the optimization program is log-sum-ens exp function w.r.t variables (x(t) which is convex. This means we can determine its minimizer set of (z(t))ee(m) Meanwhile, the constraints of the optimization program gives system of linear equation between {z(t), (t)) and the variable V. But the solution of V is not unique, the minimizer set of (=(())e(m) contains infinitely many elements. But it turns out that when {a((1) he(()) forms an linearly independent basis of R", any solution V to the linear system given by any minimizer (=(())ee(m) are guaranteed to have ((V V) O. We defer the full proof to Appendix B
4.2 More Realistic Situations: Learning from Realized Actions
In this section, we consider the more challenging yet realistic scenario, where the leader is able to observe a single action from follower at each round, i.e., the best response w.r.t. his perceived utility under the Gumbel noise, equivalently the realized action of the follower's quantal response strategy. It turns out that the intuitions from Section 4.1 still apply, and we are able to prove strict generalization of these results. In particular, Theorem strengthens Observation iin that learning the follower's 's utility up to some logit distance could also lead to an approximation of the optimal leader strategy under some mild condition given by Definition 2 in general Stackelberg games. Theorem 2 generalizes Proposition 1 as we showcase the sample complexity of our learning framework to recover the follower's 's utility in face of the follower's stochastic responses.
Definition 2 (Inducibility Gap). For any follower utility V, we define its inducibility gap as min max min x: V[e, -ey]- jE[n] wEAm #1
(V)
That is, the maximum constant (V) such that for any follower actions j E [n], there exists leader strategy x² that makes j dominate any other action j' by margin of at least oVV), i.e. x Ve, 2 x Vey +VV. Vj' $ E (n].
If a game has small inducibility gap a, then there must exsit two follower actions j. such that the follower's utility for action can never be 5 better than his utility for action j'. regardless of what strategies the leader play. In such cases, action j is essentially dominated by j' (up to at most 8). It is not difficult to that in such case with small 5 it will be difficult recover all the payoffs in such cases since action j is expected to be played very rarely. This intuition is also reflected in our following two results.
Theorem 1. Given a follower utility V with inducibility gap o(V) > 5E, we can construct an ((c/o(V)) ) optimal leader strategy for any game GUU,V) V) with logit distance ((V, (V) < mn
Proof Sketch. We prove through an explicit construction. That is, given the estimate of the follower's utility V. we construct a e-robust strategy x = (1
) o(V xJ based on the SSE (σ", ."*) of (U, V) and the strategy 2²" such that (ax VVe. 2 (~) Te, + (V), J We show this strategy is guaranteed be an ((VV) -SSE of the Stackelberg game G(U, V). The proof
3e a(V)
First, given that 4(V. V) < and a (VV) > 3e, the best response of robust strategy x in game G(U, V) remains the same as that of a game (UU V), and so is the leader utility. This means x gets at least (1 3e
then relies on two key observations stated in Lemma 1.1 and 1.2
o(V) portion of SSE utility in GUU V). Second, the difference between the SSE utility in G(U, and GU, V) are bounded by 3x Meanwhile, even though V is unknown us, Lemma 1.3 shows that we can bound
[(V].
(VV)= 2 (V) 2c, so we can use (V) 2x to substitute a (V). And this requires o (V) 2 5c. N
Due to the space limit, we defer the full statement of the lemmas and proofs to the Appendix C After restoring the connections between the logit distance and the leader's 's optimal equilibrium utillity, we now show the relationship between the logit distance and sample complexity in the learning problem. We remark that by satisfying our full rank condition, this sample complexity result does not depend on any additional parameter on the distance of queried leader strategies, such as X, in (20), both of which are only guaranteed to affect the sample complexity by polynomial (not necessarily linear) factors w.r.t. the number of targets.

---

It takes @ logfmm//))) queries of the follower's quantal response to recover the Theorem 2.
pea
follower's s utility V within the logit distance ΦVV = & with probubility at least 1 --, ô, where p is the least non-zero measure among all of the follower's 's mixed strategies induced by leader's strategy queries during learning.
This theorem is a strict generalization of Proposition I and we defer the full proof to Appendix
D due to space limit. The high level intuition comes from the fact that (1 e)-muttiplicative approximation guarantee is translated additive error after the logarithmic transformation using the approximation that for small positive close to zero, we have In( 1 O(e). And to obtain such (1 e)- -multiplicative approximation of an mixed strategy, we use standard concentration results for a tight sample complexity bound. We formalize these statements and proofs in Lemma 2. 2.2
Lemma 2.1. There exists learning algorithm that can recover the follower's 's utility V within the logit distance @V, V) O(5,) from m queries of the (1 - mullipiicca approximation of the follower's mixed strategies.
Lemma 2.2. For any discrete distribution with support size n. and the least non-zero measure jin 2 p. with 0 ( samples, the corresponding empirical distribution is e) -multipplicatiie approximation to y, with probability at least 8.
4.3 A Learning Framework of Practicality
PURE, Less is More The above results lead to a simple but provably effective method, PURE; the name comes from the fact that it only uses the m different pure strategies in Am. [ar())) As specified in the proof of Theorem - it gathers the follower's sampled quantal responses of these pure strategies to estimate the corresponding empirical distributions {ū(t) [xe(m) and solves for the V through the optimization program
While is seemingly naive learning algorithm, we would like to make a few crucial points on its unique advantages from both theoretical and practical perspectives.
Theoretically, we know PURE is guaranteed to perfectly recover the follower utility in the setting of Section I More importantly, when randomness is present, PURE guarantees that the estimation error measured by the logit distance is always bounded as ():: the Equation (D.I) in the proof of Theorem 2
suggests that the inverse of a general row-stochastic matrix X and the error matrix | could otherwise lead to possibly unbounded estimation error.
Meanwhile, we anticipate that the simplicity of PURE would be especially valuable to its applicability in practice. First, the randomized leader strategies in many applications are difficult to be implemented precisely, because the followers may not have the perfect estimation of the leader's distributions of randomization. This means that observing the follower's 's responses to randomized leader strategies could be more noisy in nature. Second, it might be inappropriate and possibly forbidden for the learner (e.g.. an Internet platform or policy marker) to frequently change its strategies (c-g.. prices or policies). Instead, the deployment of PURE only requires the learner to observe the responses of only a small number of pure strategies at the population level.
We remark that the learning framework of PURE could be tailored to the special structures in Stackelberg game. For example, let us consider a celebrated variant, known as the Stackelberg security game F Namely, a leader (defender) commits to a randomized allocation of security resource defend set of n(= m) targets from follower (attacker). In turn, the follower observes this randomized allocation and picks a target to attack. Both the leader and the follower receive payoffs depending on the target that was attacked and the probability that was defended. So in this case the follower utility can be expressed as linear functions, where each entry in vector w. E R. denotes, respectively, the attacker's 's cost and reward on each target. When the leader defends each target with the randomized strategy x A,, if the follower attacks the target j. he receives utility based on the cost w.r.t. the chance target j is defended, and the reward for the attack, i.e., Viz,j) wyz + by. Then, we can use the learning framework of PURE that only solves for the linear utility function parameters using the optimization program 4.2 This not only reduces the
PURE for Structured Games
For simplicity, we here present standard simplification of Stackelberg security game, where the resources allocation and scheduling constraints are ignored and the defender's strategy space is simply the simplex A.. Our method can be extended to security games under the general definition by carefully picking strategies on the vertices of the constrained strategy space.
7

---

number of parameters to be learnt but also directly gives the reward and cost parameters of each targets. Our empirical experiments below suggest a significantly faster error convergence rate once the structure insights is brought into the learning framework.
minimize
EiE(a] log E exp 2))) - 7({) x(0] 2, (1 (() bb),
(4.2)
for j E [nt] [T].
PURE-Exp for the Worst Cases In certain situations, however, the followers could be more rational and the parameter is larger than the standard estimation. Then, the follower's stochastic quantal response becomes rather deterministic, and the least non-zero measure p decreases. Lemma 2.2 suggests that querying through simple pure strategies could become much less inefficient in obtaining the (1 - mulliiiplliaative approximation of the actual strategy. Nevertheless, it turns out that we can introduce the "exploration and exploitation" principle here for the remedy, and we thus name such variant of PURE algorithm as -xx. Specifically, we introduce an exploration procedure to search for better strategies if an empirical estimation of the follower strategy tends to concentrate on single action. We knew such strategy would contain more noise than information, as the error introduced by its multiplicative approximation ratio can be significant; reversing a one-hot distribution from logit transformation provides no information about the follower utility. In this case, we carefully replace it by a perturbed strategy from the original strategy. This ensures that the resulting strategy set after replacement still forms a full-rank matrix that ensures the invertibility necessary for provably more effective recovery of V in Theorem 2 Otherwise, the algorithm would continue to exploit the leader strategies to better estimate the follower responses. Our empirical experiments show substantial performance improvement by PURE Exp in those extreme cases.
Algorithm 1 PURE-Exx
1: Input: Game parameters m, A, QR oracle O: Am + [r]] and optimization program Q based on the game structure.
2: Initialization: X' a list of leader strategies where the i-th strategy (1) + [ea]ee(m] V, list of
empirical estimation of follower strategies w.r.t. e(1); set i + 0.
3: for / 0, 0, 1,, do
4: Use leader strategy (8) from X' to query for follower response j + (z)())).
5: Update empirical estimation ( of the follower's QR strategy to (1)
6: if Probability mass of ( concentrates on a single action then
7: Sample random perturbation æ from simplex Am-
8: Replace (+1) in list X' by the new strategy x+)) 2 22
9: Reset the empirical estimator ( in V.
10: end if
Update i + (i 1) mod m.
12: end for
13: Solve the optimization program Q for the best game parameters using X,Y.
5 Experiment
In this section, we seek to further understand the empirical implications of our learnability results. major challenge when evaluating the learning performance is that the measures rely on the underlying ground truth utility. While there are several real world data collected in particular to understand the human behaviors and QR model [2 38
they are sensitive, proprietary datasets in security domains that we are unfortunately unable to access. Moreover, these offline dataset only offer limited number of offline samples that can hardly be used in our active learning setup. Therefore, our experiments have to rely on synthesized game instances, from which we can construct oracles to respond to the active learning queries and accurately evaluate for the learning performance. As motivated in the previous section, we will use the logit distance in Definition | to empirically measure the quality of recovered follower utilities We start by investigating the empirical performance of PURE in games sy synthesized using several sets of different parameters below.
41 35
'Except the varying parameters, we control the parameters as m = n 10, a 0.2, A 8 by default, and plot their average performance across 5 different randomly generated instances with the standard deviation illustrated in the error bars or the lightly shaded regions.
8

---

VVV. V
61v.
KV V
0.004
m=10
0.05
A=0.5
0.020
#=20
0.04
A=1
e-02
0.003
n=100
2-0.6
a^0.4
0.03
1-8
0-0.8
0.002
1=16
0.010
0.01
0.000
100 8.0
0.2
0.4
0.6
0.8
1.0
0.008.0
0.4
0.8
*Sample
lc7
<Sample
1e7
Figure 1: Recovering payoffs under varying parameters m x n (left), À (middle), (right)
The number of leader and follower actions m, no: We compare the learning performance in game of varying sizes, while fixing the number of query T 10". In the left plot of Figure [ the first trend notice is that the error grows almost linear to m, exactly as Theorem preddictss Meanwhile, the eтror also grows as n increases, as the enror bound depends on 1/p n. In Appendix, we shows that 1/p average among those randomized generated game instances grows linearly with which justifies the almost linear relation between the logit distance and n.
The level of bounded rationality A: We consider different À ranging from 0.5 to 16 estimated prior human behavior experiments 33 41 In the middle plot Figure [ we display the convergence trend of logit distance in the number of queries. The PURE algorithm shows consistently good performance among these different On one hand, in games with the smaller the eπror tends converge slower, as bounded by the XVi convergence rate implied by Theorem On the other hand, the variance of error increases especially in the initial half of the timeline games with larger A. This is explained by the fact that sample complexity of learning distribution up (1 multiipplicatiie factor increases as the distribution concentrates when À increase.
The payoff' margin a: We generate the follower's utility matrix, V al + (1 ai)., convex combination of diagonal matrix / E R and Gaussian random noise E normalized to [0, _| such that the larger a, the follower are likely to have higher margin for his best response against each of the leader's ss action. In the right plot of Figure | we can see consistent trend of improving estimation of the follower's utility as query number increases across different level of Interestingly, as the utility matrix becomes closer to the simple diagonal matrix, and the follower easily becomes less irrational, the convergence rate slows down; this again suggests our message on the blessing of bounded rationality that provides the stochasticity in follower's responses used as our additional information source.
We also compare the performance of PURE and its variants introduced in Section and the results closely match with our theoretical insights. In the left plot of Figure _ we compare PURE using only 10 leader strategies with the standard offline learning setup using 10 10x 10 leader strategies with less samples in average and less accurate estimation of follower response for each leader strategy, We can see that the PURE significantly outperforms these offline learning setups, especially when À is smaller such that the response of follower tends to be more irrational and thus "noisy". In the middle plot of Figure g without using the optumization program specialized for the game structure (in dotted or straight lines). The result suggests that the structure insights can be used for fast recovery of follower utility. the right plot of Figure we found that PURE-Exp, with the principle of exploration and exploitation, are able improve the learning performance the case when the follower appears to be more rational. However, its performance also degrades as À further increases and the problem becomes almost the perfect rationality setting that are proved to statistically hard to learn p 37 In the limit of space, please check out Appendix for more descriptions and analysis of our experiments.
we study the learning performance PURE in various security games with or
Conclusion
Two common assumptions of typical game theory problem are: (1) the agents know the game parameters; (2) the agents are perfectly rational. Though these assumptions have enabled elegant mathematical models and fundamental theoretical insights, they could be limiting in some real- world scenarios. Our paper tackles the particular problem in sequential game-theorrtic interactions without these two common assumptions. While similar inverse game theory problems under perfect rationality

---

V1V.
etv.
0.175
2.0.5
0.025
sec-20
0.10
Pure
A-1
sec-20
Pure-Exp
0.020
0.125
88c-50
0.100
A=
0.015
sec-100
sec-100
0.06
0.04
0.050
0.025
0.000
10a
10
101
0.00 16
64
80
+Strategics
Figure 2: Comparision PURE v.s. offline data (left), PURE with or without structure insights (middle), PURE PURE-Exp (right).
are shown to be statistically or computationally intractable, we made an intriguing finding in which relaxing from these idealistic settings in turns lead provably efficient learning guarantee. Therefore, we proposed the learning framework of PURE intended for fewer usage restrictions in real-world applications. In future work, we wish extend our analysis and insights more general game settings and other models of bounded rationality.
Acknowledgement
We thank all the anonymous reviewers for their helpful comments. Co-author Haifeng Xu is supported in part by an ARO award W91 INF-23-1121 IN Fei Fang was supported in part by NSF CAREER grant IIS-2046640. Weiran Shen gratefully acknowledges financial support from the National Natural Science Foundation of China (No. 62106273), the Fundamental Research Funds for the Central Universities, and the Research Funds of Renmin University of China.
References
[1] Pieter Abbeel and Andrew Y Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the twenty-first international conference on Machine learning, page 1, 2004.
[2] Bo An, Fernando Ordóñez, Milind Tambe, Eric Shieh, Rong Yang. Craig Baldwin, Joseph DiRenzo III, Kathryn Moretti, Ben Maule, and Garrett Meyer. A deployed quantal response- based patrol planning system for the coast guard. Interfaces, 43(5):400-43) 2013.
[3] Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: meta-algorithm and applications. Theory of computing, 8(1):121-164, 2012.
[4] Patrice Assouad. Deux remarques sur l'estimation. Comptes rendus des séances de l'Académie des sciences. Série Mathématique, 296(23):1021-100 1983.
[5] Robert J Aumann. Rationality and bounded rationality. In Cooperation: Came-Theorettc Approaches, pages 219-231. Springer, 1997.
[6] Yu Bai, Chi Jin, Huan Wang, and Caiming Xiong. Sample-efficient learning of stackelberg equilibria in general-sum games. Advances in Neural Information Processing Systems, 34, 2021.
[7] Maria-Florine Balcan, Avrim Blum, Nika Haghtalab, and Ariel D Procaccia. Commitment without regrets: Online learning in stackelberg security games. In Proceedings of the sixteenth ACM conference economics and computation, pages 61-78. 2015.
[8] Christopher M Bishop and Nasser M Nasrabadi. Pattern recognition and machine learning. volume 4. Springer, 2006.
[9] Avrim Blum, Nika Haghtalab, and Ariel D Procaccia. Learning optimal commitment to overcome insecurity. Advances Neural Information Processing Systems, 27, 2014.
[10] Colin Camerer. Behavioral game theory: Experiments strategic interaction. Princeton university press, 2011.
10

---

[11] Colin F Camerer, Teck-Hua Ho, and Chong. A cognitive hierarchy model of games. The Quarterly Journal of Economics, 119(3)861--98, 2004.
[12] Jakub Cerný, Viliam Lisý, Branislav Bošanský, and Bo An. Computing quantal stackelberg equilibrium in extensive-form games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 2260-5268 2021.
[13] Herman Chernoff. A measure of asymptotic efficiency for tests of hypothesis based on the sum of observations. The Annals of Muthematical Statistics, pages 493-507, 1952.
[14] Vincent Conitzer. On stackelberg mixed strategies. Synthese, 193(3):68-703,, 2016.
[15] Gerard Debreu. Individual choice behavior: A theoretical analysis, 1960.
[16] Fei Fang, Peter Stone, and Milind Tambe. When security games go green: Designing defender strategies to prevent poaching and illegal fishing. In Twenty-fourth international joint conference on artificial intelligence, 2015.
[17] Fei Fang, Thanh H Nguyen, Rob Pickles, Wai Y Lam, Gopalasamy R Clements, Bo An, Amandeep Singh, Brian C Schwedock, Milin Tambe, and Andrew Lemieux. Paws-a deployed game-theoretic application to combat poaching. Al Magazine, 38(1):23-36 2017.
[18] Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
[19] Sanford J Grossman and Oliver D Hart. An analysis of the principal-agent problem. In Foundations of insurance economicx, pages 302-340. Springer, 1992.
[20] Nika Haghtalab, Fei Fang, Thanh Hong Nguyen, Arunesh Sinha, Ariel Procaccia, and Milind Tambe. Three strategies success: Learning adversary models in security games. 2016.
[21] Bengt Holmström. Moral hazard and observability. The Bell journal of economics, pages 74-91, 1979.
[22] Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. arXiv preprint arXiv: 161.011144 2016.
[23] Daniel Kahneman. Econ ometrica ci. Econometrica, 47(2):263-291, 1979.
[24] Shankar Kalyanaraman and Christopher Umans. The complexity of rationalizing matchings. In International Symposium on Algorithms and Computation, pages 171-182. Springer, 2008.
[25] Shankar Kalyanaraman and Christopher Umans. The complexity of rationalizing network formation. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 485-494. IEEE, 2009.
[26] Volodymyr Kuleshov and Okke Schrijvers. Inverse game theory: Learning utilities in succinet games. In International Conference on Web and Internet Economics, pages 413-427. Springer, 2015.
[27] Joshua Letchford, Vincent Conitzer, and Kamesh Munagala. Learning and approximating the optimal strategy to commit to. In International symposium on algorithmic game theory, pages 260- Springer, 2009.
[28] Bernhardt Lieberman. Human behavior in strictly determined 3x matrix game. Behavioral Science, 5(4):317-322, 1960.
[29] Chun Kai Ling, Fei Fang, and Zico Kolter. What game are we playing? end-to-end learning in normal and extensive form games. arXiv preprint arXiv:1805.02777. 2018.
[30] Janusz Marecki, Gerry Tesauro, and Richard Segal. Playing repeated stackelberg games with unknown opponents. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems- Volume 2, pages 821-828, 2012.
[31] Daniel I. McFadden. Quantal choice analaysis: survey. Annals of economic and social measurement, volume 5, number 4, pages 363-390, 1976.

---

[32] Richard D McKelvey and Thomas R Palfrey. Quantal response equilibria for normal form games. Games and economic behavior, 10(1):6-38, 1995.
[33] Panayotis Mertikopoulos and William Sandholm. Learning in games via reinforcement and regularization. Mathematics of Operations Research, 41(4):1297-1322 2016.
[34] Andrew Y Ng, Stuart Russell, al. Algorithms for inverse reinforcement learning. In Ieml, volume 1, page 2, 2000.
[35] Thanh Nguyen, Rong Yang, Amos Azaria, Sarit Kraus, and Milind Tambe. Analyzing the effectiveness of adversary modeling in security games. Proceedings of the AAAI Conference on Artificial Intelligence, volume 27, pages 718-724, 2013.
[36] Barry O'Neill. Nonmetric test of the minimax theory of two-person zerosum games. Proceedings of the national academy of sciences, 14(7):2106-2109 1987.
[37] Binghui Peng. Weiran Shen, Pingzhong Tang, and Song Zuo. Learning optimal strategies to commit to. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 2019.
[38] James Pita. Manish Jain, Milind Tambe, Fernando Ordónez, and Sarit Kraus. Robust solutions to stackelberg games: Addressing bounded rationality and limited observations in human cognition. Artificial Intelligence, 174(15): 142-112227111 1171, 2010.
[39] Arunesh Sinha, Debarun Kar, and Milind Tambe. Learning adversary behavior in security games: A pac model perspective. arXiv preprint arXiv: 1500:004330 2015.
[40] Yevgenly Vorobeychik, Michael Wellman, and Satinder Singh. Learning payoff functions in infinite games. Machine Learning, 67(1):145-16) 2007.
[41] Rong Yang, Christopher Kiekintveld, Fernando Ordonez, Milind Tambe, and Richard John. Improving resource allocation strategy against human adversaries in security games. In Twenty- Second International Joint Conference Artificial Intelligence, 2011.
[42] Rong Yang. Fermando Ordonez, and Milind Tambe. Computing optimal strategy against quantal response in security games. In AAMAS, pages 847-854, 2012.
[43] Stephan Zheng, Alexander Trott, Sunil Srinivasa, Nikhil Naik, Melvin Gruesbeck, David C Parkes, and Richard Socher. The ai economist: Improving equality and productivity with ai-driven tax policies. arXiv preprint 2:X44 2020.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] [Yes], [No], or [N/A]. . You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section ??.
Did you include the license to the code and datasets? [No] The code and the data are proprietary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questionss/nssers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
12

---

(b) Did you describe the limitations of your work? [Yes] See Section !!
(c) Did you discuss any potential negative societal impacts of your work? [No] There is no foresceable negative societal impacts of this work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofss of all theoretical results? [Yes] Most of them in Appendix due to space limits
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed reproduce the main perimental results (either in the supplemental material or as URL)? [Yes] In the supplemental material
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix P
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix E
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "lgZIwkuGZrK", "reviewer": "Reviewer_AWq9", "summary": "This paper analyzes the problem of identifying follower utility in Stackelberg games, under the assumption that the follower *quantally* responds via softmax rather than playing a strict best response.  Remarkably, this turns out to be an easier problem.  The paper analyzes the sample and query complexity of identifying follower utility first under the toy assumption that the follower's full mixed strategy is observable, and then under the more realistic assumption that only actions realized from this strategy will be observed.  A specific algorithm is specified and used to validate the theoretical results empirically in experiments.", "questions": "1. p.8 L355: \"We generate the follower's utility matrix $V=\\alpha I + (1-\\alpha)\\Xi$\": This seems like a very special kind of structure for the utility; should I be worried that the empirical results depend upon it?", "limitations": "I don't forsee any serious negative impact from this work.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The Stackelberg setup is commonly used in security work, including with the assumption of quantal follower response, but it typically makes the assumption that follower utilities are known.  This paper studies the extension of this well-studied setting to a more realistic setting in which follower utilities must be inferred from their behavior.  These results are both novel, and likely to have significant impact on the security games literature.\n\nThe paper is well-written; the motivation, results, and proofs are all very clearly stated.  There are a few notational inconsistencies that I have noted below, but overall the paper was a pleasure to read, and did an excellent job of expressing some subtle distinctions.\n\n\n__Minor issues__\n- p.4: \"And we know the close form of follower's optimal strategy... [33]\": [Luce 1959] \"Individual Choice Behavior\" or [Train 2009] \"Discrete Choice Methods with Simulation\" would be more standard references for this equivalence.\n- eqn (4.1): Why does the optimization use $\\hat{y}$ instead of $y$?  This section assumes that we are able to observe the full mixed strategy, no?\n- p.6 L251: \"the strategy $x^{j^*}$\": Shouldn't this be $x^{\\tilde{j^*}}$?\n- also L251: \"for all $j' \\ne j$\": Should this be $j' \\ne j^*$?\n- p.7 L281: The empirical distributions are introduced as $\\tilde{y}(t)$, but the program in equation (4.2) seems to use $\\hat{y}(t)$, are these the same thing?\n- The empirical distributions $\\tilde{y}(t)$ (and/or perhaps $\\hat{y}(t)$) in this section will all be deterministic/one-hot distributions, right?  Might not hurt to say so explicitly.\n- Alg.1 line 7: \"Sample a random perturbation $\\tilde{x}$  from simplex $\\Delta_m$\": Does the sampling distribution matter here?  Should I just imagine a uniform sample?\n- Alg.1: The description (lines 2--5) of how the $\\mathcal{X}$ and $\\mathcal{Y}$ lists are generated is kind of confusing; the initialization section makes it seem like they are generated up front, but it looks like $\\mathcal{Y}$ at least is generated \"on the fly\" on line 5.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OqgxvONleaY", "reviewer": "Reviewer_osrx", "summary": "Leader-follower games are among the most studied classes in the field of algorithmic game theory. The reason is simple: the corresponding solution concept – the strong Stackelberg equilibrium – proved to have many real-world applications. One of the central issues of Stackelberg equilibrium is its lack of robustness with respect to utilities. More specifically, it is imperative to correctly estimate the players’ priorities, represented through their utilities, otherwise the solution may force the leader to commit to a strategy that will eventually harm them.\n\nIn this paper, the authors present an approach that guarantees to uncover the follower’s true utilities in two-player leader-follower games through repeated interaction with the follower. The key appears to be the assumption of the follower’s bounded rationality. More precisely, the follower’s behavior needs to comply with the logit quantal response model of subrationality, playing each action with non-zero probability. Using this property, the authors are able to determine the number of interactions needed to estimate the follower’s utilities to a sufficient precision. Such characterization is possible not just when the leader observes the follower’s entire quantal-response strategy, but also in a more realistic setting, when they observe only samples from the strategy. Once the observations are collected, the follower’s utility is calculated as a solution of a particular mathematical program. The authors further show how to tailor their method to specific utility structures or when the follower’s quantal responses begin to approach best responses. The last part of the paper is dedicated to empirical analysis, depicting differences between true and estimated utilities over games with diverse sizes, players with different degrees of rationality, and utility matrices with varying levels of randomness.\n", "questions": "The authors of the original Quantal Response paper later introduced also other possible quantal-response models besides the logit one, e.g., probit, Luce, etc. Would this approach generalize to those models as well?\n\nThe definition of SSGs in section 4.3 appears to be a bit simplified for the sake of arriving at linear utilities. If I am not wrong, it is much more common to define defender strategies in SSGs using limited resources allocated to a subset of possible targets, expressing utilities using marginal coverage probabilities of the targets. Would this definition of SSGs lead to a similar result?\n\nI liked how explicitly the experimental section compares PURE and PURE-EXP algorithms. Still, I am missing some intuition on when exactly it becomes beneficial to resort to PURE-EXP. Could the authors construct some explicit example when it is to? For example, on some fixed 2x2 game, what would be the follower’s rationality parameter (and the corresponding expected utilities of actions and quantal-response strategies) when the quantal responses approach best responses too closely to use PURE efficiently?\n\nCould the authors comment on how do the computational times scale with the game size, i.e., how large games and datasets are solvable within some reasonable time limit?\n\nCould the authors mention some possible applications of this exact learning method they propose? In which settings could the leader afford to practically iterate over their own strategies, when some could arguably lead to terrible outcomes?\n\nDo the authors foresee how difficult it would be to generalize their approach into sequential games? More specifically, do they see some way how to deal with the problems associated with sequential reasoning, e.g., the existence of non-credible threats, in their learning framework?\n\nCould the authors state if or when is the mathematical program from Theorem 2 solvable/approximable in polynomial time?\n", "limitations": "The authors did not include an explicit section about limitations, but they do mention some shortcomings in the introduction. Still, there are some limitations which most readers recognize when reading the text the authors may consider discussing. For example, how realistic is it to assume the follower’s model is fully known and what to do when it is not (perhaps something akin to playing a game with known utilities?)? \n", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I enjoyed reading the paper. Its motivation is clear and the authors describe well how their work fits into the literature on the topic. The results appear to be original and novel. The notation is not excessively complex and all notions are sufficiently well described. The arguments presented throughout the paper seem reasonable, facilitating the understanding of the exposition. I went through some of the proofs in the appendix and even though I did not go into all the details, as far as I can tell, they give an impression to be correct to me. Moreover, the results the authors present in the experimental section seem to corroborate the authors’ theoretical claims, even though at times the error bars happen to be rather larger (e.g., in the right graph of Fig. 3, for pure-exp and larger lambda), which would suggest averaging over more seeds might be a good idea. \n\nOtherwise, I found it a bit confusing to refer to this setting as to a “sequential game”, which is a term commonly reserved for non-trivial extensive-form games, rather than a repeated Stackelberg (or leader-follower) normal-form game, which seems to be the case studied by the authors here.\n\nFor some of this work’s (possible) weakness, please see the next section.\n\nOverall, I believe this is a nice work that may profit from some more detailed discussion regarding its limitations, but is worth publishing.\n\nNits:\nLine 10: this work relax -> relaxes\nLine 243: the equation in Def2 is missing a period at the end of the sentence\nLine 259: we defer to the full statement -> we defer the full statement\n", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Hs-fDAiHLi0", "reviewer": "Reviewer_uvLt", "summary": "This paper studies learnability of approximate Stackelberg games in rational and quantal response follower setting. Results are mostly positive relying of ceratin properties of the utilities. The result explores sample complexities and performs experiments in simulation.", "questions": "I have none, but authors can respond to my comments above.", "limitations": "Not really applicable here.", "rating": 3, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This content of this paper is incremental and to some extent covered in few related works, one of which[A] the authors do not include in references. The writing should provide more explanation and comparison to prior results.\n\nFirst, the m strategies proof (Prop 2) is a minor extension of the work in the paper [20], same style of proof also except the utility function is slightly different.\n\nProposition 1 really does not deserve the importance given in the paper; it is a well-known fact for rational player games and for quantal response (stated in text in [A],[20]). That invariance can actually be easily handled by fixing one utility parameter to be 0, again as in [A], [20].\n\nThe paper [9, 37] gives an explicit best response sample complexity for computing approximate SSE in security games (with one resource, a security games is essentially a standard Stackelberg game with m=n). So, I do not understand how Thm 1 compares to this, I do not understand why Thm 1 assumes a given learned tilde(V) with a certain property? How can this be learned from best response samples? Thm 1 also refers to leader optimal strategy - should it be explicitly called SSE as written in the proof - this is important as the paper deals with both SSE and QSE.\n\nIn the same vein, [A] gives an explicit sample complexity for the quantal response case in achieving the same (m log m) term. How does this compare to Thm 2? In fact, that paper [A] present a more general result in terms of the capacity of the function class used in the exponent, making those result more applicable than the result here for bimatrix games.\n\nOverall, I find the paper lacking sufficient novelty over prior work and also a lack of in-depth comparison with prior work.\n\nSome citations are missing venue: e.g., [20].\nSome citations seem irrelevant for Stackelberg games such as [24,25]\n\n\n[A] Arunesh Sinha, Debarun Kar, Milind Tambe. Learning Adversary Behavior in Security Games: A PAC Model Perspective, in International Conference on Autonomous Agents and Multiagent Systems (AAMAS), May 2016\n\n[9] Avrim Blum, Nika Haghtalab, and Ariel D Procaccia. Learning optimal commitment to overcome insecurity. Advances in Neural Information Processing Systems, 27, 2014.\n\n[20] Nika Haghtalab, Fei Fang, Thanh Hong Nguyen, Arunesh Sinha, Ariel D Procaccia, and Milind Tambe. Three strategies to success: Learning adversary models in security games. 2016.\n\n[37] Binghui Peng, Weiran Shen, Pingzhong Tang, and Song Zuo. Learning optimal strategies to commit to. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 2149–2156, 2019", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept