Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: As far as I understand, the authors study Lyapunov chaos that occur in learning in non-zero-sum games.


Main issues:
1.	The current structure of the paper is very unusual what makes the presentation of the key results very unclear. Just for instance:
-	Given overall 8 pages, the presentation of claimed results starts from 6th page (before that we have Introduction and Preliminaries)
-	No conclusion: the main text chops on Theorem 11 without any discussion on this theorem after. 
2.	Continuing presentation issues, I did not get at all the core of the contributions. I’ve expected to get them in the paragraph titled “Our Contributions.” (in Page 2). But this and next paragraphs provide no any insight on the contributions of this paper.
3.	It would be interesting to get insights on how the paper is related to learning community: despite the authors articulate on this in Abstract and Introduction, it is still unclear how the obtained results can improve learning / learning algorithms and/or improve their application in practice.

I believe that even notable and important contributions for the community must have a significantly better presentation, because otherwise it will be quite difficult for readers to obtain and understand these results.


Minor issues:
-	Abstract is too long for this ICLR format.
-	I’m not sure that the format of ICLR allows have Appendix in the main text instead of using supplementary materials.
=====


I raise up my score after the authors' changes 
review_title: Weak presentation that harms understanding of the results and contribution

final_score: rating: 7: Good paper, accept
review_content: This paper provides tools for classifying the payoff dynamics in general-sum n-player games as Lyapunov chaotic assuming three common algorithms are used: multiplicative weights update (FTRL with entropy regularizer), optimistic MWU, and FTRL with L2 regularizer. Previous work (Cheung & Piliouras) showed that the existence of Lyapunov chaos in the dual space is indicated by the sign of a function C of the game. This work shows that this function can be decomposed into a sum: C of the zero-sum part + C of the coordination part. They also show how to use trivial matrices (which don't affect C) to further reduce parts of the game in a way that eases the analysis. As part of their analysis, they prove that the set of bi-matrix games exhibiting chaos has positive Lebesgue measure and discuss how the relative strength of the zero-sum and coordination parts determines the ultimate sign of C.

Overall, I think this is a solid paper and should be accepted. The work is original and significant. The paper could benefit from additional discussion and explanation of the claims (see below) so that the paper is more self-contained.

Definition of Chaos and Interpretation of Results in Primal Space:
Wouldn't the system $\frac{dx}{dt} = x$ with $x(t) = e^t$ satisfy Def 1? In other words, any $\dot{x} = Ax$ with $A \succ 0$ Is this better characterized as divergent? Shouldn't it be required that $\phi(t,B)$ remains inside $\mathcal{O}$ for all time? By inspection, the Lorenz system seems to satisfy this. The authors state "eigenvalues of the local Jacobian characterizes chaotic behaviors". To my knowledge, no linear dynamical system would be said to exhibit chaos. Maybe a sentence or two early on can put to rest a reader's confusion if they already have some background in nonlinear dynamics and chaos theory.

The authors prove chaos in the dual space (which is unbounded), but do not formally relate this to chaos in the primal space (which is bounded). It is stated, "This can be shown to imply instability in the mixed strategy (primal) space." Can the authors provide some explanation or intuition so this part of the paper is more self-contained? It seems like "chaos" according to Def 1 in the dual space is not too surprising because we're measuring divergence of a cumulating function (which naturally defines growth).

Why does the sign of C matter? Can you explain where this Eqn comes from? Can you provide any intuition or must we read the Cheung & Piliouras (2020)? Similar to above, it would be best if this part of the paper was more self-contained.


Quality:
The work is of high quality. I did not check the proofs in the appendix, but those in the main body look correct (Lemma 4 is correct).

Clarity:
The paper is mostly clear, however, I have some questions regarding the definition of chaos (see above) and how to interpret chaos in the dual space in terms of the primal space (which I think we care about more).

Originality:
This work is substantially original. Showing C can be decomposed into a sum of the zero-sum part and coordination part is novel. Also, the tools for removing trivial matrices and bounding C using the output of a linear program is new (assuming we can identify the right trivial matrix). Lastly, proving chaos is "common" is original.

Significance:
Proving chaos is common in games is significant because it means we have to adjust our algorithm design to account for it. Providing tools for determining whether a game exhibits chaos for popular algorithms can tell us whether to redesign the algorithm for that game or to adjust the game in some way.

Minor:

I would suggest backing off the statement that "Understanding chaos is an important but long-ignored aspect of AI/ML". Maybe say it has not received as much attention as it should. A few works come to mind. No need to cite necessarily.
- A RECURRENT NEURAL NETWORK WITHOUT CHAOS (ICLR 2017).
- Exponential expressivity in deep neural networks through transient chaos (NIPS 2016).
- FROM OPTIMIZATION TO EQUILIBRATION: UNDERSTANDING AN EMERGING PARADIGM IN ARTIFICIAL INTELLIGENCE AND MACHINE LEARNING (UMass Thesis 2018, Section 5.7); approximates the Lyapunov exponents of GANs to identify chaos.

"We answer the above question affirmatively". Instead of "How does...", say "Does the..." so that the question admits a yes/no response.

"–The second technique" - remove the dash.

"of a multi-player potential games" - game singular.

"mixed strategy space of dimension n" - the simplex defined with n-probabilities is (n-1)-dimensional.

Explain $\mathbb{E}[A_{jk}] = \mathbb{E}[A_j] = \mathbb{E}[A_k]$. This is not obvious to me, and in fact, appears trivially false so I'm probably misunderstanding your notation. I can easily construct an A matrix and mixed strategy y such that this does not hold.

Maybe say $u=v=[2, 0, 2]$ to construct the trivial matrix in the Simple Example.

Use logical and "$\land$" maybe instead of $\texttt{and}$ in Section 3.2.

Def 4 looks like the magnitude of the determinant of the elementwise log of a matrix. I just thought I'd share. I'm not sure if there's anything there, but determinant pops up in volume analysis as you know and the matrices can represent exponential expansion so the log maybe makes sense by a very hand-wavy connection.

"it is easy to see that there is quite many games" - are quite many

"zero-sum part $\theta$-dominate" - dominates

Can you provide a constructive way to discover the trivial matrix defined by $g_j$ and $h_k$ in Eqn 8? Or in general?
review_title: This paper provides tools for classifying the payoff dynamics in general-sum games as Lyapunov chaotic under common FTRL algorithms.

final_score: rating: 7: Good paper, accept
review_content: Summary:

This paper studies the chaos phenomena of learning in general normal-form games beyond zero-sum and coordination games. Building upon the previous works by Cheung & Piliouras, the authors apply the canonical decomposition of a general bimatrix game to a sum of a zero-sum game and a coordination game. The authors further devise two new techniques: matrix domination and linear program to help analyze the game dynamics.

Detailed Comments:

This paper is generally well-written and clear. The topic concerning the dynamics of learning algorithms is interesting and important for the DL community. This work extends the previous results for zero-sum and coordination games to more general games in a non-trivial way, and it demonstrates the existence of a broad class of games suffering from the chaos phenomena. The ideas of trivial matrices and matrix dominations look nice. 

1. It would be better to explain the logic behind C_{(A, B)} more intuitively, since most analysis in this paper focuses on this quantity. It is very interesting that MWU and OMWU have totally opposite dependency on this quantity. The reviewer understands that this result is from the previous work, but it would be better to explain it more clearly and intuitively in this paper to make it self-contained.

2. Could you comment on the games whose dynamic cannot be determined by matrix domination or linear program? For the games that could appear in the DL applications, e.g., GAN, could those games' dynamic be determined by matrix domination or linear program? If not, shall we expect them to have chaos phenomena or not?
review_title: ICLR 2021 Conference Paper2387 AnonReviewer2

final_score: rating: 7: Good paper, accept
review_content: Summary:
This paper studies Lyapunov chaos in learning algorithms for matrix games. It appears to extend earlier work by Cheung and Piliouras to more general-sum settings with the conclusion that in these more common settings the learning algorithms considered exhibit chaos. The paper also presents an interesting notion of matrix domination which is a necessary and sufficient condition for chaos, and also a linear programming approach for the purpose of identifying chaotic games.

Strengths:
* very nice example before section 3.2
* thm 7 is very interesting
* (8) is also very clever

Weaknesses (in rough order of appearance):
* constantly referring to "AI/ML" - just pick one
* "measurement errors in real economies" - why "economies" all of a sudden?
* "Nash equilibrium is not achievable in general." - this is patently false. There is a wealth of recent literature on learning algorithms which stably approach Nash equilibria, see, e.g., https://arxiv.org/pdf/1901.00838
* the whole motivation with roundoff errors reads very naive... these issues have been studied for decades and are taught in standard courses on numerical methods. A good reference which covers these issues with rigor would be the classic book by James Demmel (who is also, coincidentally, known for his work on LAPACK). It is also worth pointing out the extensive work behind (and Turing award for) the development of the IEEE floating point standard. My point being that problems of algorithmic stability arising from finite-precision computation have been (and continue to be) studied extensively, and much theory absolutely considers the presence of computation errors.
* I do not follow footnote 1
* repeated references to "dual space" - what is this? It does not appear to be defined
* (1) is confusing. Some prose description would be good.
* The definitions following "convex regularizer function" are unclear.
* I found (4) onward (through the end of pg. 5) very confusing and didn't really follow
* Notation of "u_i" in Def. 3 is not introduced before
* In 3.2.2 I don't understand why the "iff" property above doesn't apply
* The end at pg. 8 is extremely abrupt. Please offer further interpretation of the results (e.g., what should the reader take away from Thm 11?) and a proper conclusion for the paper.
* [throughout] there are numerous syntax/semantic errors that should be corrected before publication. I suggest employing a copy editor.
* [high level comment] matrix games are a nice theoretical starting point for game theory, but I have yet to see them used in realistic settings. I'm sure that theoretical results may be very interesting, but practically speaking I have difficulty seeing the motivation. I would suggest providing stronger motivation for the reader early on.
* [high level comment] there are *no* experiments at all. Please show at least some numerical examples, if for no other reason than to convince skeptics of the theoretical results.
* [high level comment] numerous times, the paper referred to something like a definition that did not appear until much later in the paper. this is a little awkward for the reader

Overall:
While this paper does offer some interesting ideas, I cannot recommend publication at this time. I have pointed out a number of directions in which the manuscript could be improved; I hope that the authors are able to clarify these points in later revision.
review_title: Some neat tricks but very tough to follow

Meta-review: This paper looks at chaos in learning in games, extending a line of work in two players zero-sum games (that I found quite restrictive in the past). It somehow reduces the class of more general games to zero-sum and cooperative games (this decomposition is already known) so that the techniques can be transposed here.

The paper is interesting, yet sometimes difficult to follow, and I am not certain that it gives many new insights. 

Nonetheless, we believe its quality justify acceptance.
Decision: Accept (Poster)