Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper provides sample complexity results and analysis of algorithms that learn Stackelberg equilibria for three types of games: general bandit games, bandit-RL games, and linear bandit games. The novelty of this paper lies in the fact that it studies a different solution concept, Stackelberg game, in general-sum games without assumptions regarding the convexity or concavity of the reward functions. To the best of my knowledge, this is the first paper that studies the sample complexity for learning Stackelberg equilibria under such games.
main_review: 1. This paper focus on learning with bandit feedback for Stackelberg equilibria in static general-sum games, instead of general-sum stochastic (Markov) games. As the authors remarked, bandit games and bandit-RL games can be considered special cases of general-sum stochastic games (line 108). The significance of the paper is confined since only static games are considered (the bandit-RL is similar to a static game considering that the value functions are pre-computed using a reward-free learning algorithm.) It would be better if the authors can shed more light on (discuss related works about) learning Stackelberg equilibria for dynamic games (stochastic Stackelberg game and Stackelberg differential game) in which the leader and the follower make their decisions sequentially.


2. There exists literature that studies Stackelberg equilibria for stochastic games which the authors want to include in ‘related works’.
        *  Vasal, Deepanshu. "Stochastic Stackelberg games." arXiv preprint arXiv:2005.01997 (2020). .

3.The real-world application of the proposed algorithms is not well demonstrated. The authors did mention the optimal taxation problem by learning the Stackelberg equilibrium studied by another work [48], which is a problem that often times be formed as a Stackelberg game problem (Wang, You-Qiang. "Commodity taxes under fiscal competition: Stackelberg equilibrium and optimality." American Economic Review 89.4 (1999): 974-981.). This application is discussed at a problem formulation level. It is not clear how the results (sample complexity results) can offer insights for the potential applications. Hence, the current draft seems somewhat dry, overloaded with complexity metrics and math equations. Discussions in "Implications; Overview of Algorithms" does not offer two much practical interpretation. It requires effort for the reader on interpreting their practical meaning. It would be better if the authors can explain the results in the context of a practical application.

4. I did not thoroughly check all the proofs due to time constraint. I took a quick a look and no mistakes were identified.
limitations_and_societal_impact: Not applicable.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper considers the problem of online learning the Stackelberg Equilibrium in general-sum games. The authors identify a fundamental gap between the exact and the estimated version of the Stackelberg value. Then they consider three general-sum games setting: bandit games, bandit-RL games, and linear bandit games, designing algorithms for these settings and providing sample complexity results.
main_review: The paper studies an important problem in the online learning literature, analyzing the problem of learning Stackelberg Equilibrium in general-sum games. Although many works study this problem in the exact setting, the authors show that the problem becomes informationally-theoretically hard when we cannot observe the exact estimates of the rewards but only noisy samples. Moreover, the authors study the problem of learning epsilon-Stackelberg equilibrium in three settings: bandit games, bandit RL games, and linear bandit games. In my opinion, this paper shows important results for the game theory and online learning communities. 
Moreover, these results leave out interesting future directions for the considered setting (for example, studying the optimal sample-complexity for bandit-RL games) and other settings as Leader-Follower MDPs, or Turn-based Markov Games.


 
limitations_and_societal_impact: In my opinion, this paper has not particular limitations.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper considers learning Stackelberg equilibria in unknown games with noisy bandit feedback of the rewards obtained by leader and follower, respectively. The authors prove an information theoretic gap between the value of the true Stackelberg equilibrium and the one learned from finitely many data points. However, they show that approximate Stackelberg equilibria (defined according to a $\epsilon$-best response of the follower) can be learned efficiently using empirical reward estimates. Upper and matching lower bounds are provided on the number of required samples. Results are instantiated for bandit games, bandit reinforcement learning games, and linear bandit games.
main_review: The problem considered is relevant and I believe the contributions are novel, as previous work has mostly considered learning Nash equilibria. Moreover, the paper is well written and organized. Hence, my accept score.
However, I think that the authors should not claim (in Conclusions): "This paper provides the first line of sample complexity results for learning Stackelberg equilibria in general-sum game", since previous work has already considered learning Stackelberg equilibria under different assumptions (as discussed in related work section). Moreover, I believe some related works have been overlooked. 
For instance, the StackelUCB algorithm by [Sessa et at., Learning to Play Sequential Games versus Unknown Opponents, NeurIPS 2020] also computes the optimal strategy for the leader, under noisy (albeit different) bandit feedback, by building an approximate best-response set. 
limitations_and_societal_impact: How do the obtained upper bounds compare with previous works, e.g. [26,33] which consider learning Stackelberg equilibria from best-response oracle? It is not clear which feedback model is less restrictive (since in practice we may not have access to the follower's reward and we could only observe the actions played), so I believe the obtained bounds deserve a fair comparison with these works. 

Moreover, it would be nice to see some experimental results which can illustrate whether the derived bounds hold in practice.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors study the problem of learning Stackelberg equilibria from random samples in general sum games. The work will be of interest to both theoreticians of Stackelberg games and those who work on applications. The main contributions are:
- In bandit games, which are two-step Markov games where the leader and follower only observe their own rewards, the authors show that there is a constant gap between the optimal and the best strategy the leader can attain with a finite number of samples. This gap is a central feature of the paper—it exists in all settings that are analyzed by the authors, and the sample complexity results give you performance that approaches the best possible up to the gap. The authors give a tight bound on the number of samples required which is linear in the size of the action sets of the leader and follower and quadratic in the approximation ratio relative to the gap. The algorithm queries each leader action a fixed number of times (which is the same across all actions) to construct an estimate of the follower's best response function that has the desired properties.
- For bandit-RL games, where the leader selects an action that induces an MDP for the follower, the authors show that a quite similar algorithm can be applied. The main challenge is that the follower has to learn the optimal policy for each MDP (this is an RL setting with bandit feedback to the follower), and this requires an application of some recent work to yield appropriate estimates. The bandit-RL game setting reduces to bandit games when the horizon is of length 1. The derived sample complexity matches that of the bandit game for the horizon = 1 subcase, showing that the dependence on these parameters is tight. However, the scaling in horizon length is extreme—more than quintic. There is no known lower bound for the dependence on horizon.
- In linear bandit games, which are bandit games, but where the rewards are a linear function of the features of each action. The algorithm the authors state for this setting scales quadratically in the dimension of the feature space and quadratically in the approximation ratio. There is a factor of the dimension between this and the lower bound they derive.
main_review: I found the paper to be clear and well-written throughout, even in the supplemental material. The authors relate their work to prior work well and explain these connections extensively. The sample complexity results are original and useful to other researchers in this area. Bandit-RL games look like the most challenging of the settings and the most significant open questions come from this setting (the required dependence on states and horizon).

I don't have a firm basis for this, but I suspect the result about the constant gap for the bandit game setting was "known" in the Stackelberg general sum setting—it might be a consequence of other results or not stated directly. I suspect there is some kind of explanation in terms of the standard literature that could be added, but I don't have a citation. Even if this is the case, I don't think this is a major issue for the paper—I see the main contributions as analyzing the sample complexity "up to the gap."

The magnitude of the gap diminishes the interest of the authors' results to some extent—you would want some kind of guarantee that the gap would not be too large for a class of problems of interest.

Post-response edit:
- To clarify, I did not deduct any points for my suspicion that the constant gap result is "known" (more likely, a consequence of a known result). I do not have a specific reference for this and no reference was raised by the other reviewers either.
- The papers specific novelty are suspect. Specifically, 1. "To the best of our knowledge, this is the first result for sample-efficient learning of Stackelberg equilibrium in general-sum games with bandit feedbacks." (top of page 6) and 2. "This paper provides the first line of sample complexity results for learning Stackelberg equilibria in general-sum games." (conclusion, bottom of page 9). The pg. 9 claim is clearly false—the authors acknowledge other work in their related work section. The pg. 6 claim—I believe the authors intend to say that they are the first to provide results in their specific bandit feedback model, which is true to the best of my knowledge. Nevertheless, there are other bandit-style feedback models in the literature—for example, the learning model that assumes best responses by the adversary _is_ a bandit feedback model—it is just a different one from the authors'. These claims need to be revised.
- I still find the central claims of the paper to merit acceptance. The paper would benefit from integrating a stronger motivation about what kinds of games have a small gap—the point the authors made in their response.


limitations_and_societal_impact: The authors don't spend a lot of time on limitations, but I found their treatment adequate—they identify gaps in knowledge (e.g., between upper and lower bounds) as well as fundamental limitations in the learning process.

Negative societal impact is not a concern for this theoretical paper.
review_title: null

Meta-review: The discussion mainly centered on the authors' claims of novelty.  While (to our knowledge) the technical contributions are indeed novel, there was consensus that the informal claims need to be significantly toned down -- there are too many variants of "initiates the theoretical study of sample-efficient learning of the Stackelberg equilibrium" and everything being "vastly open" which is simply not true given the references cited by the authors themselves.  (There is sometimes a qualifier about samples / a bandit model, but prior work could also be considered to involve samples and a bandit model -- this isn't exactly what sets this paper apart, though maybe the noise does, which is sometimes, but not always, mentioned in the qualifier.  As pointed out by one of the reviewers, there are also places where there isn't even any qualifier at all.)  The fact that this is claimed again and again, and the fact that this issue was apparently already raised in the ICML submission of an earlier version of this paper and apparently wasn't fully addressed (I wasn't involved in reviewing that version so I do not know the details), do honestly leave us a bit worried about just accepting the paper.  That seems unfortunate because it really wasn't necessary.  Still I think acceptance is the right decision, but the authors should appreciate that this really involves trusting them that they will truly fix this this time.  The same goes for any talk/poster about the material of course.

I wonder if the line of work on empirical game theory by Wellman and others should be cited here somewhere.
Decision: Accept (Poster)