Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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.
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.

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


__Minor issues__
- 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.
- 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?
- p.6 L251: "the strategy $x^{j^*}$": Shouldn't this be $x^{\tilde{j^*}}$?
- also L251: "for all $j' \ne j$": Should this be $j' \ne j^*$?
- 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?
- 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.
- 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?
- 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.
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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.

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

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. 

Otherwise, 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.

For some of this work’s (possible) weakness, please see the next section.

Overall, I believe this is a nice work that may profit from some more detailed discussion regarding its limitations, but is worth publishing.

Nits:
Line 10: this work relax -> relaxes
Line 243: the equation in Def2 is missing a period at the end of the sentence
Line 259: we defer to the full statement -> we defer the full statement

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?

The 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?

I 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?

Could 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?

Could 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?

Do 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?

Could the authors state if or when is the mathematical program from Theorem 2 solvable/approximable in polynomial time?

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?)?
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: 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.
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.

First, 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.

Proposition 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].

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

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

Overall, I find the paper lacking sufficient novelty over prior work and also a lack of in-depth comparison with prior work.

Some citations are missing venue: e.g., [20].
Some citations seem irrelevant for Stackelberg games such as [24,25]


[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

[9] Avrim Blum, Nika Haghtalab, and Ariel D Procaccia. Learning optimal commitment to overcome insecurity. Advances in Neural Information Processing Systems, 27, 2014.

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

[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
questions: I have none, but authors can respond to my comments above.
limitations: Not really applicable here.
review_title: null

Meta-review: metareview: High-level view: this paper presents some interesting observations around
learning against a Stackelberg follower that corresponds to a quantal response model.
The learning seemingly relies strongly on the follower being a quantal responder with a logit regularizer, but this is an interesting setting to study, and one that seems to have been overlooked in the literature.
Thus I am broadly in favor of the paper.


Now, on a more detailed level, I do disagree with some claims made in the paper regarding bounded rationality. I would expect the authors to handle bounded rationality versus logit QRE more carefully in the camera ready. Personally, I would say that even the title of the paper ought to be changed. The short of it is that the authors conflate bounded rationality and quantal response behavior, but these are not the same thing. In fact, both the AC and other reviewers feel that the results are *not* likely to extend to most other models of bounded rationality. They may extend to other models of quantal response behavior, though.

Now, in more detail:
The authors state

> We remark that in general, even without such extreme case of dominated actions, the extra payoff information are now available on how much worse (or better) using the empirical frequency of actions from the boundedly rational responses, which has been overlooked due to the assumption of perfectly rational follower

But this can't be true: a special case of bounded rationality is that the
boundedly-rational player is rational enough to rule out the dominant action in
the example; in that case bounded rationality does not let us learn anything
from that action! The reason the authors can learn here is because they study a
very specific type of bounded rationality: quantal follower response.
Learnability then becomes doable specifically because the follower plays all
actions with non-zero probability. 


A second thing is that the authors call it "perhaps surprising" etc that bounded
rationality helps. However, again, the authors are looking specifically at
quantal response behavior under the logit response model, which is well-known to be easier to handle. In
particular, adding the logit quantal response assumption corresponds to adding a
strongly-convex regularizer to the follower's best response problem. Regularizing
a nonsmooth function is known to lead to much nicer behavior in many settings,
e.g. in optimization, learning, etc. Moreover, the logit model specifically leads to a form of regularization that plays every action with non-zero probability, again a very useful fact for learning the follower model.

Finally, the authors say 

> While our quantitative results do rely on the form of this model, we believe
53 the insight revealed from our model generalizes to most problems of learning from boundedly rational
54 agent behaviors.

This seems very unlikely, given what I stated above. Quantal response is a very
special type of bounded rationality. The results should probably only be
expected to extend to other problems that share some of these characteristics,
e.g. playing every action with non-zero probability, and possibly also corresponding to strongly
convex regularization.

Let me finish by reiterating that this is not a huge issue for the paper: the logit QRE setting is definitely important and of interest in its own right. But it's important to better delineate where we may hope for these results to generalize or not generalize.
confidence: Certain
Decision: Accept