Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the convergence of simple bandit learning algorithm in weighted zero-sum games, to the Quantal Response Equilibria. I have several major questions regarding the problem setup, motivation and conclusion.
main_review: This paper studies the convergence of a simple bandit learning algorithm in weighted zero-sum games, to Quantal Response Equilibria. I have several major questions regarding the problem setup and conclusions.

1) Problem setup: The "Q-learning" algorithm defined in Eq (5) is actually a bandit learning algorithm, as it does not consider the transition dynamics (simple repeated game). However, the authors didn't clearly state this is a bandit setup, and mentioned MDP in line 111, which confused the readers a lot.

2) Main result: For the main convergence result part (Section 4), in line 222, the author mentioned the bandit learning will converge to QRE, and will approximate a NE. The first claim is proved, but why this QRE can approximate a NE? QRE and NE are two different solution concepts in games, and one does not imply the other. The authors should theoretically explain the latter statement. 

3) Motivation of this work: the author mentioned equilibrium selection is mostly discussed in cooperative game setting, and this is the first work studies these concepts in multi-agent competitive setting. Equilibrium selection in cooperative games make sense, as all agents are collaborative and can coordinate to maximize certain central utility. But it seems equilibrium selection in competitive games doesn't make much sense? Agents are self-interested and the outcome of the game cannot be selected - it's determined by agent's self-interested actions.

4) Experiment: Similar to my question (2), the authors mentioned the learning dynamics converge to Nash equilibrium in all simulated game. But the main convergence result is about the Quantal Response Equilibria  - not the Nash equilibrium. The author should either show results about the convergence to QRE, or clearly explain why convergence to QRE implies convergence to NE in these example games.
limitations_and_societal_impact: Not apply
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper investigates the convergence of a smooth variant of Q-learning dynamics in multiplayer network games called weighted zero-sum polymatrix games. The authors suggest interpreting the exploration rate of Q-learning as the inverse of the lambda parameter of the quantal response model, determining the degree of the agent’s rationality. The main result of this work claims that in weighted zero-sum polymatrix games, the Q-learning dynamics will always converge to the unique quantal response equilibrium associated with strictly positive exploration rates exponentially fast, irrespective of the initial profile of strictly mixed strategies (i.e., no agent adopts a pure strategy). The manuscript is concluded by empirical analysis of convergence of Q-learning in two-player and multiplayer weighted zero-sum games. The results show that with strictly positive exploration rates, the dynamic will indeed converge to the associated quantal response equilibrium and approximate Nash equilibrium as exploration rates approach zero. In the case of the two-player setting, the authors observe the quantal response equilibrium is reached even when only one of the players explore (and the dynamic is cyclic when no one explores), which is turned into a formal proposition in appendix C for two-player games with two actions per each player. For multiplayer games, exploration by only a subset of players will not guarantee to reach equilibrium.
main_review: The results the authors present in this work are indeed interesting; the inverse of the lambda parameter was interpreted previously as the intensity of noise, and it is compelling to see the interpretation based on exploration. In the limited time allocated for reviewing, I went through the proofs presented in the appendix (and partially also in the main text), and as far as I can tell, they seem correct to me. I am convinced the quality of results meets the standards of NeurIPS, and analyzing the convergence of different variants of Q-learning is definitely worth investigating. The manuscript is well written in terms of prose, the relevant concepts are well described, and the notation is clear. I suggest the authors allocate some space in the introduction to motivate the class of games they study with some real-world examples. I also have a few notes and questions relating mainly to the experimental part of the paper.

What I am missing in the experimental part is some comparison to traditional methods for computing quantal response equilibrium in terms of practical scalability in the number of players and their actions. Even seeing how the convergence is affected by the number of players and sizes of their action spaces for the smooth Q-learning with fixed exploration rates alone would be interesting. Moreover, limiting the exploration rates to zero, as described in the manuscript, closely resembles the tracing procedure introduced by McKelvey and Palfrey in their 1995 paper, for which Turocy presents a practical algorithm in his paper “A dynamic homotopy interpretation of the logistic quantal response equilibrium correspondence”. The algorithm is implemented in the Gambit library. I believe that comparing Turocy’s method to smooth Q-learning with ELE or CLR-1 strategy would also provide insight into how smooth Q-learning performs in solving the equilibrium selection problem in practice.

McKelvey and Palfrey call the selected Nash equilibrium when lambda approaches infinity (or equivalently, the exploration rates go to zero) the limiting logit equilibrium. Turocy claims that in 2x2 games, the limiting logit equilibrium is risk-dominant (and a similar result is also achieved by Anderson, Goeree, and Holt in minimum-effort coordination games), but Zhang and Hofbauer later disputed this. Do the authors have some intuition which equilibrium would be selected, e.g., in the ZSPG game with many players, besides what is described in part C.5 of the appendix?

What do the authors consider to be the main takeaway from the experiments? Is it the fact that strictly positive rates are indeed necessary for multiplayer games to guarantee convergence? Is the convergence lost in the ZSPG game even when all but one player explore?

### After rebuttal

I would like to thank the authors for their detailed response to my questions, and for pointing me to the work of Leonardos and Piliouras. The assumption that the limiting equilibrium will exhibit a higher entropy than other Nash equilibria is intriguing yet natural and I hope there will be some results in this direction in the future. 

limitations_and_societal_impact: I can not think of any limitation not addressed by the authors.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the convergence of Boltzmann Q-learning to the unique quantal-response equilibrium (QRE),   in weighted zero-sum polymatrix games, assuming all agents using positive exploration rates. 
main_review: Strengths:

This paper provides a solid contribution to the literature on selecting Nash equilibria in multi-agent systems, not only in cooperative settings but also in competitive settings. Considering the complexity of multi-agent systems and the minor assumptions needed in this paper,  the present paper serves as a good start to understanding the effectiveness of exploration in the convergence of Q-learning in multi-agent systems. The experiments on some zero-sum games show the convergence of the algorithm and the necessity of exploration.

Questions:
- In the experiment ''Two-agent Weighted Zero-Sum Games'', what's the performance if both of the agents use ETE? I wonder whether both of the agents doing exploration at the beginning stage would affect the convergence. 
- Can the convergence be observed in larger games and would it be robust? Currently, the simulation is in a 7-agent game. What's the potential difficulty of simulating the proposed method in larger games?

limitations_and_societal_impact: No visible negative societal impact.
review_title: null

Meta-review: This paper shows that for a class of multi-agent competitive games -- weighted zero-sum polymatrix games, a variant of Q-learning can provably converge to the unique quantal response equilibrium.
(+) The paper presents a set of new theoretical results regarding convergence guarantees of learning rules in multi-agent games, an area that is understudied so far despite the popularity of learning algorithms used for multi-agent settings. The theoretical analysis is solid.
(+) The numerical experiments show the learning dynamics in some example games, which confirms the theoretical results.
(-) There are some minor presentation issues, for example, the term “network competition” is used without explanation in the introduction, and the use of “.” instead of “,” in line 67.
(-) The reviewers also made a number of suggestions to further strengthen the paper, including adding additional motivations, connections between QRE and NE, additional experiments regarding the scalability.

Overall, the reviewer team has a positive view of the paper. We suggest the authors make changes they promised in the responses to improve the paper.
Decision: Accept (Spotlight)