Venue: NeurIPS 2022 Conference

Reviews:

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: A two-player zero-sum quantum game consists of three steps. 

1) Two players prepare two mixed states $\sigma,\rho$.
2) A third party makes a joint measurement $R$ on the tensor product $\rho\otimes \sigma$.
3) The payoff of the first player receives is the result of the measurement, whereas the second player receives the negative of that value.

One may naturally define a notion of Nash equilibrium for such games. The general problem addressed here is the following: assuming a repeated game, do both players converge to the/a Nash equilibrium?

The present paper considers this problem in the case where both players follow a matrix multiplicative weights (MMW) algorithm, which (for suitable step sizes) achieves vanishing regret. Before I state the main results of this submission, I wish to mention two results in the corresponding classical setting with the multiplicative weights (MW) algorithm.

1) Bailey and Piliouras (2018 ACM Conference on Economics and Computation) prove that (under suitable assumptions) there is no convergence to Nash equilibria. 
2) Mertikopoulos et al (SODA 2018) that players' states are Poincaré recurrent in a continuous-time limit of MW (or more generally of "follow the regularized leader"). 

The present paper proves variants of the above results for the continuous-time limit of MMW, called quantum replicator dynamics (under suitable conditions). The proof of Poincaré recurrence is related to the second reference above, in that it requires showing that the quantum replicator flow is volume preserving (after a certain transformation) and has bounded trajectories. Another result shows that the quantum replicator dynamics leaves invariant a sum of relative entropies, each comparing "one half of a Nash equilibrium"(ie. one of the states in the pair constituting the equilibrium) to "one half of the quantum replicator dynamics". Additional bounds are given for the evolution of the relative entropies in discrete time. 

The above results are complemented by experiments.The introduction motivates these results by their relationship to quantum learning and quantum GANs. These connections are taken up in the conclusion as part of a discussion on future directions. 

strengths_and_weaknesses: *Strengths*

The paper is mostly clearly written (although not everywhere). Its main strength of the present paper is the (partial) extension of the two papers mentioned in the summary to the quantum setting. The conservation of the sum of relative entropies is a nice result, and the proof, although relatively simple, is different from those in the main references.  

*Weaknesses*

1. Unlike the first paper papers in the above summary, the present submission only considers the continuous-time limit, not the actual repeated game. 
2. Unlike the second paper, only multiplicative weights are considered (though this may be a limitation of online learning theory in the matrix setting). 
3. Although the main results are motivated by applications to quantum GANs, the connection seems somewhat tenuous. This raises the question of whether NeurIPS is a good fit for the paper. 
4. I have some reservations about the proofs of Theorems 3.5 and 4.3. Mostly they stem from the fact that $\rho_j,\sigma_j$ also depend on $\mu$. In particular, there seems to be a "order of limits" question there that I will discuss later. 

-- 

*Other comments \& suggested corrections*

Line 153: "can also be defined"- no, that's the actual definition.

Line 158: in general, how does one define a differential equation in a topological space?

The notation $A(t)$ used in Liouville's Theorem has another meaning later in the paper.

The use of time derivatives in (17) is confusing.

Line 234: here "typically" apparently should mean "in the classical (or commuting) case".

--

*Review update on 08/07*

The authors' answers to point 4 above have convinced me. I am satisfied that the proofs are correct. I am also clearer on the literature and their motivation for considering this specific algorithm.
 

questions: Q1) Can you explain the results about Quantum GANs that you would like to formalize (as per your conclusion)?

Q2) In the argument for Theorem 3.5, $\rho_j$ and $\sigma_j$ also depend on $\mu$. However, I do not quite see how the proof of the theorem accounts for this. Can you explain this point? Also, the reasoning in line 648 about evolving $\rho_j$ does not seem very rigorous (thought it could be made rigorous). 

Q3) Can you explain how exactly Definition 4.4 is used in the proof? Where would the proof "break" if this definition did not hold? 

*Update on 08/07*

I thank the authors for their clarifications.
limitations: The submission is good in this regard. It is "limited" in that it does not fully generalize the results from the classical setting.
review_title: null

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 consider (2 player) quantum zero-sum games and analyze two algorithms for learning the Nash equilibrium: matrix multiplicative weights and its continuous-time analog, the quantum replicator dynamics. As far as I understand, both algorithms have been previously described in the literature. The authors prove the convergence some entropic quantities during the execution of the algorithms. The main technical contribution is the proof of Poincare recurrence of quantum replicator dynamics.
strengths_and_weaknesses: The paper is well-written and provides just enough details to be understood at a superficial level. On the more fundamental level, some motivation and intuition should be given about the connections between section 4.1 and the part of the paper before it. Some space could be easily reclaimed by removing the definitions and claims that are not used outside of the appendix.
questions:  - Why do you analyze the change in the relative entropy instead of its actual value? Naively, it seems that proving that the change converges to 0 implies only that the relative entropy has converged to a fixed value which might or might not be 0. Has [25] already estabilished this convergence?
 - Are Theorems 3.5 and 4.2 interesting in their own right? How are they used to prove the main result, Theorem 4.3?
limitations: The work is purely theoretical, no direct social 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: The paper studies a specific case of two-player zero-sum games where each player strategy is to probabilistically prepare a quantum pure state that he/she sends to a referee who then performs a joint measurement on the two quantum states to determine the payoffs of the players. The restriction is that each player updates their strategy according to the Matrix Multiplicative Weight Update (MMWU) methods. The validity of their strategies is guaranteed by the trace normalization performed after updating according to MMWU. The main results of the paper are Theorem 3.5 and 4.2: the total quantum relative entropy is a constant of motion. 

strengths_and_weaknesses: I find the results of the papers are interesting with the strengths in the rigorous theoretical analysis deriving the main results of the papers. 
Nevertheless, I am having difficulties to understand the impact of the results to the quantum learning theory. Especially, the results are restricted to the specific rules of updating strategies according to the MMWU, which seems to be quite restrictive. 
 
Another weakness is the lack of comparison to the classical counterparts. Introducing quantum strategies can add more powers either to players. For example, what will happen if the two players share entangled states? Do Theorems 3.5 and 4.3 hold? Or, what if the players can only have shared random numbers but not entangled states? 

I also think the experimental results are weak as they are essentially 1-qubit strategy for each player. 


questions: 1. How are the main results similar or different from classical counterparts?
2. What happens if the two players share randomness and/or entangled states? 
3. Will the experiments with multi-qubit strategies differ from the current experiments with single-qubit strategies? 

limitations: Not applicable.
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: Quantum computing is an interesting research area these days, and this paper studies a specific problem in quantum computing, quantum zero-sum games. The authors consider a standard algorithm in zero-sum games, matrix multiplicative weight update (MMWU), and study its behavior of convergence in continuous time, in the sense of dynamical systems. Specifically, the authors prove that under the quantum replicator dynamics, the system exhibits conservation laws in a quantum information-theoretic sense. Moreover, the system exhibits the Poincare recurrence, i.e., all orbits return arbitrarily close to their initial conditions infinitely often. Numerical experiments are performed to corroborate the theoretical claims.
strengths_and_weaknesses: In general, both quantum computing and game theory are very important and interesting fields, and it’s great to see that the authors are able to prove some theoretical results for quantum games. As far as I see, previous quantum computing papers relevant to the topic studies different perspectives, and this result on the conservation law of quantum games under MMWU is novel to me. This is also a significant result and I believe that it can bring further attention to the interdisciplinary research between quantum computing and game theory.

In all, I think this paper can appropriately fit into NeurIPS 2022. However, the paper still has space to improve. In particular, the authors might be able to make more efforts to build the relevance of this work to the general machine learning audiences. To me, the conservation law & recurrence result is definitely nice to know, specifically that the authors are able to prove this in the quantum computing domain, but these are more like pure math results and I didn’t immediately see the implication to machine learning. From the perspective of game theory, does that imply any fast quantum/classical algorithm based on MMWU such that we can solve relevant quantum/classical game theory problems (or maybe other problems relevant to machine learning) faster? 

For the specific perspective of dynamical systems which covers the conservation law and recurrence properties studied by the paper, a similar story that has been well received by the ML community is the study of gradient descent methods in continuous time limit, in other words, characterization of optimization methods by differential equations. For instance, speaking of the methodology, this paper by Wibisono, Wilson, and Jordan published at PNAS https://www.pnas.org/content/113/47/E7351.short proposes a framework of continuous-time dynamics for understanding accelerated gradient descent methods, which is also based on the Bregman divergence (similar to this submission). It is noted that papers along this line have been well-received by the ML community with various NeurIPS and other top-venue papers. After reading this submission, I believe that it also has the potential to become more relevant as a systematic tool to understand game theory, but the authors should put more effort on this.
questions: My question is about the connection between this work and the machine learning community in general. Please see my discussions above.
limitations: Although the checklist mentioned that the limitations of the paper are described in the introduction and in the main text, I found a bit hard to locate that explicitly... It would be helpful if the authors can highlight this.
review_title: null

Meta-review: metareview: In this submission, the authors consider zero-sum games and analyze two algorithms for learning the Nash equilibrium. In this version, each player's strategy is to probabilistically prepare a "quantum pure state" that is sent to a referee who performs a joint measurement on the two quantum states to determine the payoffs of the players. This is an interesting generalization of zero-sum games to quantum computing.

While both algorithms (matrix multiplicative weights and its continuous-time analog, the quantum replicator dynamics) have been previously described in the literature. The authors prove many interesting new results, including the convergence of some observable, and the Poincare recurrence of quantum replicator dynamics.

The consensus among reviewers is that the paper is clearly written, and definitely presents a significant extension of known results on such problems. Following the reviewers' suggestions, the authors have expended their discussion on the relevance of this work to the general machine learning audiences. 
confidence: Less certain
Decision: Accept