Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors analyze the zero-sum stochastic Stackelberg game. They proved the existence of an optimal solution in zero-sum games and showed how to compute a recursive Stackelberg equilibrium via value iteration. Then they provide some applications of stochastic Stackelberg games.
strengths_and_weaknesses: Strengths
1. The paper studies an interesting problem: a leader-follower game where the follower's actions depend on the leader's actions. 

2. The authors propose (as far as I know) a novel solution concept recSE and study when this equilibrium exists in stochastic games.

3. The authors propose a value-iteration algorithm to converge to the equilibrium solution.


Weaknesses
1. The related work does not mention the works on Stochastic Stackelberg Games and Leader-follower stochastic Stackelberg games as [1,2,3,4,5]. What is the relation between the considered setting and these other ones? Maybe the name stochastic Stackelberg game is not the most appropriate.

2. Line 129, 140, 264 have formatting problems. $\alpha$ is an unusual way to bound the rewards I suggest putting 1 or $R_\max$.

3. I have some questions which I listed below. 

[1] Vorobeychik, Y., & Singh, S. (2012). Computing stackelberg equilibria in discounted stochastic games. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 26, No. 1, pp. 1478-1484).

[2] Chang, Yanling, Alan L. Erera, and Chelsea C. White. "A leader–follower partially observed, multiobjective Markov game." Annals of Operations Research 235.1 (2015): 103-128.

[3] Sengupta, S., & Kambhampati, S. (2020). Multi-agent reinforcement learning in bayesian stackelberg markov games for adaptive moving target defense. arXiv preprint arXiv:2007.10457.

[4] Ramponi, G., & Restelli, M. (2022, February). Learning in Markov Games: can we exploit a general-sum opponent?. In The 38th Conference on Uncertainty in Artificial Intelligence.

[5] Vu, Q. L., Alumbaugh, Z., Ching, R., Ding, Q., Mahajan, A., Chasnov, B., ... & Ratliff, L. J. (2022, March). Stackelberg Policy Gradient: Evaluating the Performance of Leaders and Followers. In ICLR 2022 Workshop on Gamification and Multiagent Solutions.


questions: 1. Could Lemma 2.1 be written only from the "equivalently" part? The first part seems redundant.

2. It would be useful to add citations on how to solve the min-max constrained problem defined by the contraction operator.

3. How does the proposed method differ from the min-max algorithm from [1]?

4. Remark 2.6 said that the payoff function can also be non-convex-non-concave. How can we solve the optimization problem given by the contraction operator if the payoff function is non-convex-non-concave?

5. How can the algorithm be independent of the initial-state distribution? If we start from a state $s$ which is disconnected from the other states we are achieving a different recSE... or am I missing something (maybe connected to Assumption 1)?

6. I find section 3 quite interesting but not well commented. I suggest explaining better what the implications of the proposed theorem are.

7. Although less interesting, it would be useful to add experiments with finite state-action spaces, where the authors can use the value-iteration method. Is it possible to use [2] as a baseline?

8. Are there other applications of the game considered?

[1] Littman, M. L. (1994). Markov games as a framework for multi-agent reinforcement learning. In Machine learning proceedings 1994 (pp. 157-163). Morgan Kaufmann.

[2] Fiez, T., Chasnov, B., & Ratliff, L. (2020, November). Implicit learning dynamics in stackelberg games: Equilibria characterization, convergence analysis, and empirical study. In International Conference on Machine Learning (pp. 3133-3144). PMLR.
limitations: Since there is space the authors could add a section analyzing the limitation and the potential negative societal impact of their work. However, since the work is more theoretical, I don't think it has an immediate negative societal impact.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies zero-sum Stackelberg games. First, this paper proves the existence of the recursive Stackelberg equilibrium. Furthermore, the authors provide necessary and sufficient conditions for identifying the Stackelberg equilibrium and show that a recursive Stackelberg equilibrium can be computed in polynomial time via value iteration. Finally, the authors show that the stochastic Fisher market can be modeled by the stochastic Stackelberg games.
strengths_and_weaknesses: This paper studies the zero-sum Stackelberg game and provides a complete set of results for this problem. The authors also show that the zero-sum Stackelberg game can model the Fisher market. This is interesting. But I still have some concerns (see the questions below).
questions: 1. 	It seems that some results (e.g. value iteration) are straightforward. I hope the authors point out the non-trivial part if I miss something. I also encourage the authors to highlight the technique novelties in the paper.
2. 	This paper only considers planning problems where the model is known. Recently, some papers considers learning problems in Stackelberg games [1] [2]. Can these methods (with some modifications) be applied to finding recursive Stackelberg equilibria in online zero-sum Stackelberg games? I hope the authors make some comments on this.
 
[1] Y. Bai, C. Jin, H. Wang, and C. Xiong. Sample-efficient learning of Stackelberg equilibria in general-sum games. In NeurIPS, 2021.
 
[2] H. Zhong, Z. Yang, Z. Wang, and M. I. Jordan. Can reinforcement learning find Stackelberg-Nash equilibria in general-sum Markov games with myopic followers? 2021. arXiv:2112.13521.
 

limitations: Yes
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: The paper introduces a novel variant of the stochastic game model, where the available strategies of one player may be constrained by strategy choice of the other player. The paper establishes the existence of a corresponding solution concept and shows that a variant of value iteration approaches it. The paper shows the relevance of the proposed model by using it to model a realistic variant of Fisher market. Finally, the paper demonstrates that the algorithm converges very close to the solution in some games and a little further in more complex games.
strengths_and_weaknesses: I enjoyed reading the paper. The paper is not very well motivated in the introduction, but the separate Section 4 already nicely demonstrates the usefulness of the model. The results in the paper are not very surprising, but still important to establish for a new game model. The content is quite technical, but notation is intuitive and definitions sufficiently thorough to make the paper reasonably easy to follow. 

I have only smaller suggestions for improvements:

I understand the motivation by the Stackelberg setting.and I like the name of the model. However, referring to the distinction from the standard model as static vs. dynamic is very confusing for me. Stochastic games are fundamentally dynamic and referring to the games as static/dynamic based on what happens in individual states makes the claims, e.g. in the abstract, sound just wrong.

Lines 49-51: It was completely unclear to me how the mentioned games could benefit from being modeled as Stackelberg games.

Line 65-66: The line of 22 references without giving any context is useless and makes it look like an artificial inflation of the number of citations. What is the reader supposed to learn from that? Since this paper is about the Slackelberg setting, these papers do not seem relevant at all.

Lines 69-78: Similar as above, I am not sure what is the relation of these papers to the current work. Few lines of explanation would be very appreciated.

Line 243: I guess you mean equations (1)-(5).

I would appreciate a plain text explanation of equation (6) to make it faster to understand.

questions: What is the intuitive reason why the solution does not depend on the initial distribution?

limitations: The limitations are discussed and I do not think there is a significant societal impact.
review_title: null

Meta-review: metareview: There was a positive consensus amongst the reviewers about this paper. It examines an interesting setting and makes worthwhile contributions. I believe that it that would make a nice contribution to NeurIPS and that it is likely to lead to more follow-up work. At the same time the authors should take care to improve the discussion of the related work and improve readability at the points that the reviewers have identified.
confidence: Certain
Decision: Accept