Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback

Summary

The paper studies the problem of designing uncoupled learning dynamics that provably converge to Nash equilibria in two-player zero-sum Markov games. As a preliminary result, the paper introduces the first dynamics that converge last iterate in self play in matrix games with bandit feedback. Then, the paper shows how to extend such last-iterate-convergent learning dynamics to the case of irreducible Markov games. Finally, the paper studies the case of general Markov games, proving that a variation of the previously-introduced learning dynamics achieve convergence according to a newly introduced definition of convergence (called path convergence).

Strengths

The problem studied in the paper is interesting and it has received considerable attention over the last years. The paper is well written and easy to follow.

Weaknesses

A major weakness that I see is that the results presented in the paper seem minor adaptations and different analysis of already known techniques/tools. The authors should focus more on discussing the novelty of their approach.

Questions

Please resolve my concerns in the weaknesses part.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

None.

Summary

The paper introduces a new algorithm for learning in two-player zero-sum Markov games based on prior work that is uncoupled (agents only need their own reward as feedback), convergent (to NE) and rational. The result is an algorithm that is similar in concept to a single agent RL algorithm, but guarantees convergence if both players use the same algorithm. For their initial algorithm, there is an additional assumption of irreducibility on the Markov games, and it achieves last iterate convergence to the Nash with rate O(t^{-1/9+eps}). Meanwhile, for general 2 player zero sum Markov games without additional assumptions, a modification of the algorithm that applies optimism achieves O(t^{-1/10}) path convergence rate.

Strengths

The algorithm proposed takes inspiration from prior works and makes useful modifications that give practical and theoretical advantages. The structure of the results and explanation of analysis also flows well and is easy to read despite the technical complexity. The authors are also very clear in their motivation and I find the literature review to be quite comprehensive.

Weaknesses

The paper does a good job of setting up motivation and prior ideas, but in my opinion the key takeaway from this work is that there is now a truly uncoupled and convergent algorithm for general Markov games, which is in my opinion the paper's most significant contribution. However, there is too much space dedicated to matrix and irreducible Markov games, when in my view, the section on general Markov games should be greatly expanded. In addition to the overview of the analysis, I am interested to know how optimism can be leveraged in this type of algorithm, and the thought process behind the modifications to Algorithm 3 compared to Algorithm 2. As a suggestion, perhaps part of the analysis overview for Thm 3 can be repurposed and moved forward to add to the explanation about Alg 3, which would improve the flow of the section in my opinion. Finally, there is a lack of experimental results which would make help frame the results better in comparison to prior work.

Questions

Have any experiments been run using Algorithms 1, 2 and 3 to compare them to current SOTA methods? If so, how does the empirical performance compare? It seems that your algorithms would scale well with larger games since players only use local information, how does this compare to existing methods?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors have adequately addressed the paper's limitations.

Summary

The paper studies the last iteration convergence of uncoupled learning in two player zero-sum markov game, with bandit feedback. The paper provide the first finite last-iterate convergence guarantee under the bandit feedback. The paper studies the problem of two-player zero-sum Markov game and designs a new uncoupled learning algorithm that enjoys last iteration convergence, under bandit feedback. Along the way, the paper derive a couple of results, summarized below: (1) Even for the standard matrix game (where there is no Markov transition), the paper provides an algorithm with $O(T^{-1/8})$ convergence rate (2) For irreducible Markov game, the paper provides an algorithm with $O(T^{-1/9})$ convergence rate (3) For general irreducible Markov game, the paper provides an algorithm with $O(T^{-1/10})$ convergence rate, but only under the notion of path convergence. It is worth noting that there is a large body of literature, but previous work [WLZL21] are either not uncoupled, or [BJY'20 ] not last iterate convergent. The technical part seems novel, from a high level, the results are obtained by adding an entropy regularizer, but there are many subtle details to make it really work and the analysis is involved. ------------------ I have read the author response and want to keep my positive evaluation.

Strengths

The paper studies a fairly popular topic and provide the first finite last-iterate convergence guarantee for Markov game (two-player, zero-sum). The technical contribution seems to be novel. The paper is also well-written and the technical part is well explained.

Weaknesses

No.

Questions

I have a few minor questions: (1) Can you provide some intuition on the number of $T^{-1/8}$ or $T^{-1/9}$, ideally, it would be nice if one can written down a short explanation on how these magic exponent comes from. (2) The following paper seems very relevant? [1] Regret Minimization and Convergence to Equilibria in General-sum Markov Games

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.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

no.

Summary

This paper studies the problem of learning a Nash equilibrium in two-player zero-sum Markov games with bandit feedback. The proposed algorithm introduces the entropy regularization technique into online mirror descent. First, the author proves that the proposed algorithm converges to an equilibrium in two-player normal-form games. Then, the last-iterate convergence rate for irreducible Markov games is provided. Finally, the paper presents a path convergence rate for Markov games without the irreducible assumption.

Strengths

* The problem is well-motivated. In many scenarios, the last-iterate convergence property under bandit feedback is more suitable than the average-iterate convergence property. * It seems novel to derive the last-iterate convergence rates under bandit feedback. * The proof sketch of Theorem 1 is intuitive and easy to follow.

Weaknesses

* Since action probabilities of strategies in $\Omega_t$ are lower bounded by $\frac{1}{At^2}$, line 6 in Algorithm 1 seems to have no closed-form solution. I wonder how much computational cost it will take to update the strategy. * The term of $\ln^{20}(SAT/\delta)$ in Theorem 3 depends heavily on $T$. This term would be dominant practically and would not be able to be ignored. * I could not completely follow the sketch of Theorem 3. I would have appreciated more detail.

Questions

* How much computational cost will it take to update the strategy (e.g., line 6 in Algorithm 1)? * Does the path convergence imply the average-iterate convergence? * What prior knowledge of the game is required for setting of $\epsilon,\beta$, and $\eta$ in Theorem 3?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The authors adequately addressed the limitations.

Summary

This paper studies algorithms for two-player zero-sum Markov games that are uncoupled, convergent, and rational. Previous attempts at designing such algorithms failed short in one aspect or the other. This work uses recent advances in entropy-based regularization to design new algorithms that overcome the inherent challenges. The other main contribution of this work is deriving the convergent rates of the proposed algorithms in Matrix, Markov, and general Markov games.

Strengths

1. The proposed algorithms do not require the two players to exchange information (including that related to entropy) 2. The proposed ideas extend to general Markov games without any assumptions on the dynamics. 3. The work seems technically sound. The algorithms follow easy-to-implement modifications of existing methods. 4. The problem setup, the algorithms, and the proofs are written in an easy-to-digest format.

Weaknesses

See Questions.

Questions

1. How tight are the obtained convergence rates? 2. My understanding of the proposed algorithm is that at time step $t,$ player 1 plays action $a _t$ and player 2 action $b_t.$ Thereafter, the local update steps are carried out. If this is correct, then why do the authors claim that their proposed algorithm does not require the two players to have synchronized policy updates?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors do address the limitations in their work adequately.

Response to Author Rebuttal

Thanks for the answer to my question. If the changes suggested by the authors is implemented I think this is a good paper worthy of acceptance. Best regards, Reviewer EDuK