Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper studies the Q-learning algorithm in the multi-agent setting, under the assumption that each agent observes its action and reward only while being completely unaware of the other agent's actions and rewards (decentralized setting). The asymptotic convergence of the proposed algorithm is proved under two different sets of assumptions regarding the algorithm hyperparameters. An illustrative experiment is presented.
main_review: ***Major***
- My main concern is about the novelty of the work compared with the recent work [1]. Both the present paper and [1] consider the Q-learning algorithm in the multi-agent decentralized setting, with no communication between the agents. Besides the fact that [1] considers a single-timescale rule and the present paper a two-timescale rule, it seems to me that the results of [1] are more general/stronger. In particular:
1) The present paper limits to the finite state case, whereas [1] uses function approximation and, therefore, can be applied to continuous state spaces (although the theoretical results are provided under the assumption that the function approximator allows representing the Q-function)
2) The present paper provides an asymptotic convergence guarantee, while [1] manages to derive a finite-sample guarantee.

Compared to [1], the present paper proves that the proposed algorithm is "rational", which seems a not too demanding requirement. Indeed, if the opponent is playing a stationary strategy, the problem reduces to single-agent RL.

- Assumption 2-ii. The value of the temperature converges to \epsilon in this assumption. This means that the agent will never play a deterministic policy. Instead, a small exploration will always be preserved. Does this imply that the algorithm will converge to an \epsilon-Nash equilibrium rather than a Nash equilibrium?

- Experiment. The experiment seems a little sacrificed there. The explanation is very synthetic, and nothing about the employed environment is reported in the main paper. I suggest considering moving the experiment to the supplementary material.


***Minor***
- Line 185: the subscript k is introduced here, but its meaning is explained only later
- Table 1: shouldn't this be considered an "Algorithm" rather than a "Table"? Missing full stop at the end of the caption.
- Is there any relation between the requirements of Assumption 1 and the classical Robbins-Monro conditions?

***Overall***
The paper is written in good English, and the presentation is overall clear. My main concern, as reported above, is about the novelty of the work compared with [1]. I would greatly appreciate it if the authors could elaborate on the substantial differences between their work and [1]. For this reason, at present, I opt for a borderline score.

[1] Guo, Hongyi, Zuyue Fu, Zhuoran Yang, and Zhaoran Wang. "Decentralized Single-Timescale Actor-Critic on Zero-Sum Two-Player Stochastic Games." In International Conference on Machine Learning, pp. 3899-3909. PMLR, 2021.
limitations_and_societal_impact: This is a mainly theoretical paper. I do not foresee any societal impact.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The authors propose an independent Q-learning algorithm for two-player zero-sum Markov games. Asymptotic convergence results are obtained for the cases where both (or only one) players both follow the proposed algorithm.
main_review: Writing quality and clarity are okay. It's nice to have figures to illustrate the Q-functions. I do have some questions and concerns regarding the theoretical results.

1. Asymptotic convergence: Having asymptotic convergence is not a strong enough result. Given the works [1, 2], can the authors get a rate of convergence? If not, what are the algorithmic/technical barriers that make getting convergence rates fundamentally harder?

2. Rationality property: I think the authors are trying to argue  in ​"rationality property" (Corollary 1) that a player would learn good response even if the opponent does not follow the proposed algorithm. But my concern here is that, 

(1) When considering asymptotic convergence, letting the opponent using a stationary strategy almost surely actually means you are fixing the opponent's strategy throughout the learning process. How does this differ from learning optimal policy in the single-agent setting

(2) Do we not allow the opponent to choose whatever strategy he wants in each iteration? If that's the case, aren't we still asking the two players to collaborate in a sense that the opponent should either follow the algorithm or keep using the same strategy "almost surely"?

(3) Is best-in-hindsight response to arbitrary strategy sequence possible?

In my opinion, the above concerns make the convergence results in this paper less appealing that the typical convergence results with rates, and weaken the claim that the algorithm is fully "decentralized".

[1] https://arxiv.org/pdf/2011.01868.pdf

[2] https://arxiv.org/pdf/2010.15020.pdf
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents a fully decentralized Q-learning algorithm for Markov games.  The individual ("local") Q-function is tracked separately from a state-value function, with updates to the Q-function taken according to a TD-error computed using the state-value function (of the next state).  Crucially, these two function are learned at differing timescales, making the action-reward value for each state "appear" stationary.  The algorithm is demonstrated to converge to Nash equilibrium (or the neighborhood of a Nash equilibrium, depending on the strength of assumptions made) in zero-sum Markov games when both players use it, both theoretically and numerically.
main_review: This paper gives a very elegant solution to a persistently vexing problem in MARL.  The solution has the potential to extend beyond the simple setting initially studied by the paper, and could have a substantial impact.  The paper is very well structured, and gives a clear motivation and intuition for each aspect of its results.

#### Additional comments ####

* It seems like Theorem 1 is a consequence of Corollary 1 more than the reverse.  In particular, Corollary 1's statement does not appear to depend upon the zero-sum property of the game at all, whereas Theorem 1 is a straightforward consequence of Corollary 1 given that the game has the zero-sum property.  This could point toward extensions beyond the zero-sum case.  E.g., stochastic games in which each stage game is a potential game seems like a natural next step, since better-response dynamics are guaranteed to converge to an equilibrium, and corollary 1 seems to point to a strong connection with better-response dynamics.

* All of the statements of Theorem 1 and related results refer to global learning rates $\{\alpha_c\}$ and $\{\beta_c\}$ rather than agent-specific sequences.  Is this without loss of generality, or does the result of Theorem 1 rely upon both agents using common learning rates?  If yes, then this is still more uncoupled than a case where agents must agree on who is the "fast" learner and who is the "slow" one, but it still requires some coordination to agree on the learning schedule.

* On a related note, is this algorithm more vulnerable than standard independent Q-learning approaches to exploitation by a sophisticated opponent who knows the learning algorithm being used?  I.e., if I know the opponent is using a particular learning schedule, can I exploit their value-estimates' being out of date by a particular non-stationary strategy?

* I found the convergence described in Figure 2 to be somewhat surprising; it appears that one or the other agent always converges to a stage-game-suboptimal strategy in each stage game, rather than a "natural" equilibrium in which each player plays some equilibrium of the stage game at each stage.  (This latter equilibrium is guaranteed to exist, even when the players have different discount factors; it would give every state a discounted value of 0).  Is this a consequence of the requirement to play each action with a softmax probability (i.e., when there is a tie in expected continuation value between two actions, they must be played with equal probability if they also have the same expected reward)?  Or is there something deeper going on here?  Or is this just happenstance of which equilibrium was selected?


limitations_and_societal_impact: Limitations are directly and adequately addressed, including societal impact.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper introduces a two-timescale variant of decentralised Q-learning for two-player zero-sum Markov games (without terminal states). Convergence of the algorithm is shown under several assumptions, and example experiments are provided to illustrate this convergence in practice.
main_review: I thank the authors for their detailed response to my queries, and maintain my rating. I'm glad the authors will add more detail around the experiment to the main paper. Interesting points were raised in other reviews regarding e.g. degree of decentralisation that algorithm achieves given the need for similar time-scale updates between the players - further discussion of these points in a later version of  the paper would be useful.

---

This is a strong paper with an important central contribution. The paper is also generally very clearly written, and in my opinion the authors have achieved an excellent balance in the main paper between describing the algorithm, required assumptions, proof sketch, and illustrative experimental results. In addition, the work is well contrasted against a variety of different approaches to MARL in zero-sum Markov games.

I have not had time to check all proofs in the appendix line-by-line, but have checked Propositions 1-3 and found these to be correct.

Some minor comments are given below:

Statement of Proposition 3: I don't think "Assumption 2" or "Assumption 2'" are defined as terms in the paper - does Assumption 2 mean 2-i and 2-ii together?

Section 4: I appreciated the inclusion of a proof-of-concept implementation and experiment here. However, at present there is not really enough detail provided in the main paper to take much from the diagrams, and the reader is essentially required to consult the appendix to understand the significance of what is illustrated. If space allows, I think this section could be improved by including sketch details of the environment (and algorithm settings), perhaps at the cost of not illustrating convergence for both assumption sets in the main paper. As a very minor point, the last x-axis tick label in Fig 2a seems to have been cut off.

Questions for the authors:
 * Regarding the clipped learning in Line 2 of the Table 1, presumably any choice of upper-bound (in the range (0,1]) to clip at would yield a convergent algorithm (i.e. with Prop. 2 still holding for this modified algorithm, and the remainder of the argument then going through). Is there any particular reason to select 1 as the upper-bound here, other than the largest value that still guarantees boundedness of the iterates?
 * Do the authors have a sense of how important is the choice of entropy regulariser in Table 1? I.e. could a convergence proof hold for other classes of regulariser with the properties of strong concavity, unbounded gradients at simplex boundary etc.

Minor notational comments:
There are a few minor notational issues in the main paper:
 * I found #s quite odd notation, in contrast to something like N(s). Potentially the notation used should also be something like N_k(s_k) rather than N(s_k) (or #_k s_k rather than # s_k in current notation), to make clear the dependence on k of the visit count. Without this, statements such as Proposition 3 look odd, since in "# s -> infty as k -> infty", the dependence of # s on k is not clear. This notation is used to some extent (e.g. proof of Prop 3), but would be clearer if used throughout.
 * The notation is a little imprecise in places: Eqn (1): expectation written over actions, but not states?
 * There are also some typos to be corrected in the main paper and appendix e.g. "ith" -> "with" Line 607.
limitations_and_societal_impact: These aspects are addressed in Section 5.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper studies the convergence of decentralized q-learning in two-player zero-sum games. The theoretical conclusion of the paper is sound. My main concern is regarding the originality and significance of this paper in comparison to a recent ICML 2021 paper.
main_review: * The paper studies the convergence of decentralized q-learning in two-player zero-sum games. There seems a recent ICML 2021 paper studies the same learning in games setting and reaches almost the same result: http://proceedings.mlr.press/v139/guo21a/guo21a.pdf. So one concern is about the originality and significance of this paper. 

* In addition, one of the key assumptions in deriving the convergence results is that every state is visited infinitely many times --> so that the global value function estimation \hat{v} can be an unbiased estimator. But the appearance of the state seen by agent 1 is affected by the action/stratedgies of agent 2. What if agent 2 is a dummy player that takes the same action or an adversarial player? Actually, the state is not visited infinitely many times (and many states may not be visited) is a key challenge in actually training MARL. The other paper ICML 2021 didn't make this assumption - and this may be one of the reasons that they only have a stochastic convergence guarantee instead of the prob 1 results achieved in this paper.

* The author may want to explain the experiment setup in further details. In Figure 2(a, b) There are 5 lines for each agent in each sub-plot, are they corresponding to 5 different zero-sum games? what are the game setup and parameters?

* Figure 1 is confusing - it might be helpful to add more explanations or adjust the presentation to be more clear, and link the definition of global and local Q-functions to the corresponding equations.
limitations_and_societal_impact: Not apply
review_title: null

Meta-review: Almost all the Reviewers agree that this paper is worth being published. The potential overlap with the ICML 21 paper raised initially serious concerns by the Reviewers. However, all the Reviewers agree that this paper and the ICML 21 paper are concurrent. I also believe that these two papers present several differences and the authors clearly discuss these differences in the rebuttals. I invite the authors to add a section in their paper in which the differences with ICML 21 are discussed. I also invite the authors to take into seriously consideration the following concerns raised by Reviewer KoGL and to clarify these issues in the paper:

*The "fully" decentralized claim is still questionable to me after reading the response. To some extent, it does make sense for agents to follow "myopic" best-response dynamics. But still, assuming every one of them being at the same level of "myopia" is sort of collaborating. And the Corollary 1 does not really tell any meaningful thing in terms of the algorithm's ability to exploit opponents that do not follows such dynamics.*

Frankly, I don't think that *assuming every one of them being at the same level of "myopia" is sort of collaborating*, but it could be useful that the authors clarify better this point in their paper.

Decision: Accept (Poster)