Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the authors aim to analyze the asymptotic behavior of online learning algorithms in periodic rather than static zero-sum games. In terms of positive results, they show that the time-evolving *periodic* versions of both zero-sum bilinear games (under Gradient Descent Ascent) and zero-sum polymatrix games with time-invariant equilibria (under FTRL) satisfy the notion of Poincare recurrence -- a formal guarantee of cyclic behavior. However, the authors provide negative results too: in the described cases, the time-average of the GDA/FTRL plays does not converge to a time-invariant Nash equilibrium (in the latter case there is utility convergence).
main_review: This work has sufficient clarity of exposition, technical contributions, and insights for a publication. However, I do have high level questions/concerns about the work itself. The particular choice of GDA and FTRL for the two game variants was not substantiated -- why not GDA in both cases for example? Since the results (negative and positive) are particular to these algorithms, it would be good to know how general the treatment is (would such arguments work for other algorithms). More importantly, given that the goal is to investigate time-evolving games, is there a reason to believe that Poincare recurrence or time-invariant equilibria are the right measures of performance. Finally, what can be said in terms of finite time convergence, computational efficiency, etc? (for future work)

At the same time, this work shows that there are many unanswered questions in this direction (some of which the authors answer here). I would like to see the discussion section to actually be about discussion -- what was answered and what else should be investigated. And please add a related works section (some is in section 7) after the intro (or subsection in intro). I am rating this submission as a weak accept which I'll upgrade to accept if there are no major issues found by other reviewers.

Minor comments: in Definition 1, there is no assumption about a time-invariant equilibrium, I'm guessing because (0, 0) is always one. This is a very trivial case in my opinion, and I think it's worth it to consider constrained action sets so that there is no obvious equilibrium one knows (Poincare recurrence is still nontrivial but time-average convergence of, say, GDA does not say as much).

The negative results in sections 4, 5 are specific to GDA/FTRL so they don't imply "that the time-evolving game model of periodic zero-sum games is at the cusp of complexity where positive results are achievable". This just makes the results in the paper regarding GDA, FTRL stronger as the set of assumptions for them is more or less tight.
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper aims to analyze online learning behaviors of the gradient descent-ascent(GDA) and the follow the regularized leader(FTRL) algorithms for periodic zero-sum games.
Seminal works [23, 19, 7] show that online no-regret learning dynamics is Poincar\'e recurrent in repeated static zero-sum games, but the techniques used in the seminal works does not work well in periodic one. To resolve this, the paper exploits an important theorem about volume preservation for periodic systems by [1], and shows that GDA dynamics in periodic zero-sum bilinear games and FTRL in periodic strategy polymatrix zero-sum games are Poincar\'e recurrent. The paper also shows a negative result that time-average strategy does not converge to time-invariant equilibrium, as a counter example. The empirical evaluation support the theoretical results.
(Reference number follows the paper.)
main_review: Originality:
Whereas the no-regret learning algorithm dynamics is known to be Poincar\'e recurrent in static zero-sum games , to the best of my knowledge, this is the first research showing that GDA and FTRL learning dynamics are Poincare recurrence in periodic zero-sum games.

Quality:
Proposed theorems and lemmas seem to be technically sound, and the experimental results support the theorems.

Clarity:
The paper is well-written and easy to follow, and honestly describe a negative result that there exists a counter example.

Significance:
It is significant to prove that GDA and FTRL learning dynamics are Poincar\'e recurrent in some games. Whereas periodic zero-sum games seem to have few applications, the proposed theorems are an important first step to explore dynamics in other games evolving over time.

limitations_and_societal_impact: As described in the significance, periodic zero-sum games are limited to dealing with the evolution over time and have few applications. However, I think the contributions of the paper outweigh this limit.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: #  Summary of Paper
The authors study the behaviour of two continuos time
learning dynamics under two types of periodic zero-sum games, continuous gradient descent ascent (GDA) in unconstrained bilinear games,
and continuous follow the regularized leader (FTRL) in polymatrix games.
It is shown that under mild conditions, both GDA and FTRL are Point-Care recurrent,
all orbits eventually return arbitrarily close to the initial conditions.
The techniques used are common tools from dynaimcal systems but the applications to periodic games seem novel. Futhermore, strong insights on assumptions are given by providing counter examples to the Theorems, and the authors address the important issue of average convergence
in games with insightful negative and positive results.


main_review: 

# Originality and Quality
The theoretical results seem both novel and insightful, it is my understanding that contrary to other recent papers, this work sheds light on the behaviour of dynamics in
games that change across time whereas other works do not address time-varying games. The results are non trivial and illuminating counterexamples are provided to justify their assumptions. Additionally, the authors go beyond what is expected and address the important question of average convergence, showing that tho Pointcaré recurrence seems to transfer from fixed game to ones changing in time, a similar result does not hold for average convergence.

# Clarity 
The paper is extremely well-written, making a technical topic accesible to a large audience,
though some technical details could use more clarification (as discussed below).

Although I believe the paper to be a good contribution, I have some issues regarding the technical details.
+ Where is the assumption of time-invariant Nash equilibrium used in the theorems? This seems to be hidden somewhere in the technical lemmas from the dynamical systems literature. Does it need to be unique or does the existence of one such equilibrium suffice?
+ Proposition 1 proves that both the periodic game assumption and the time-invariant equilibrium assumption are needed for the Poincare recurrent result for GDA. However I believe the second counterexample (regarding time invariant equilibrium) to be incorrect. In this example the second player is fixed, however, this implies that the dynamics no longer follow GDA, therefore the example is incompatible with the assumption of GDA dynamics.

# Suggested improvements and Clarifications

 + The assumption of a time-invariant equilibrium is mentioned in the definition of periodic polymatrix games but not in definition of periodic bilinear games, is this a mistake?
 + It is not exactly clear how volume preservation of the map $\phi^T$ and bounded orbits is used to show Pointcaré recurrence. In lines 219-221 it is argued that these conditions are sufficient for Pointcaré recurrence via Theorem 2 (on line 191), however, there is no mention of volume preservation or bounded orbits in this theorem, is this implied by the measure-preserving assumption? Or are these arguments following from line 187 (end of Theorem 1)? 
+ In Poincaré recurrence theorems for maps it seems to be commonly assumed that $\phi$ is one to one (see for example V.I Arnold Section 16 D or Theorem 7.6.3 in Wiggins), why is such an assumption not needed here?
 + Why does the existence of a time invariant scalar function $\Phi$  imply bounded dynamics?
   For example the constant function would be time invariant yet this tells us nothing about the dynamics. I can see that when this is used for example in Lemma 3 that it works but generally the statement does not seem to be correct. Do you need to assume for example that $\Phi$ is coercive? For example why does the $\Phi$ in Lemma 5 work? 
 + Why is zero-sum significant in polymatrix games? in general if there are more than two players then it seems that every game that is not zero-sum can be made zero-sum with the addition of a dummy player with one action and utility that is defined to be the negative sum of utilities of all other players.
 + Regarding Louiville's theorem and conservation of volume, from my understanding it is not an equivalence result, the divergence being zero implies the preservation of volume but is not a necessary condition (See for example Theorem 7.6.2 in Wiggins).

## Questions and Possible Future Work

+ There is a common reference to online learning methods, however, GDA is not a valid online method as no finite regret is guaranteed in the unconstrained setting (see for example lower bounds in Orabona). Therefore, why is GDA considered online learning?
+ Considering online mirror descent is a popular online method with continuous time analysis, it would be interesting to extensions to the case of continuous mirror descent.
+ A well-known online learning method games is that of Blackwell approachability, giving the famous regret-matching strategies (see Hart and Mas-Collel (3)). Given that there has also been continuous time analysis of Blackwelll approachability in games (Hart and Mas-Collel (4)), it would be interesting to investigate whether Pointcare recurrence appears under these dynamics as well.
+ It would be helpful to include more citations for some of the standard Dynamical systems results, for example Louiville's theorem.


# References
1. V. I. Arnol’d. Mathematical methods of classical mechanics, volume 60. Springer Science &
Business Media, 2013.
2. Wiggins, S., Wiggins, S. and Golubitsky, M., 1990. Introduction to applied nonlinear dynamical systems and chaos (Vol. 2). New York: springer-verlag.
3. Hart, S. and Mas‐Colell, A., 2000. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68(5), pp.1127-1150.
4. Hart, S. and Mas-Colell, A., 2003. Regret-based continuous-time dynamics. Games and Economic Behavior, 45(2), pp.375-394.
5. Orabona, F., 2019. A modern introduction to online learning. arXiv preprint arXiv:1912.13213.
limitations_and_societal_impact: There is sufficient discussion of limitations throughout the work, however, there is no discussion on potential negative societal impact. Although no explicit section or paragraph is included in the text, the authors address the issue in their response in the checklist "The work
is primarily theoretical, and thus does not have any directly negative societal impacts." And I am in agreement with the authors, that the work is mainly theoretical without direct societal impacts.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This article considers the behaviour of some modern learning in games dynamics (gradient ascent/descent and the follow the regularised leader family), applied in games that evolve periodically. The essence of the results are that if the equilibrium is constant throughout the cycle of the game, then the algorithms are periodic, whereas if the the equilibrium is not constant, or the game evolution non-periodic, then the algorithms may not be. Even in the recurrent cases, it is not always the case that the time average of strategies converge. Some simple experiments are given to demonstrate the results.
main_review: The article is very nicely written, correct so far as I can tell, and interesting in a virtuous/quirky sort of way. I don't have any objections to it so far as it goes. However it is the kind of research which takes something we know (learning in fixed games) and says "how far can we push this?". The conclusion is "not very far actually" - the class of games in which the results hold is really quite restricted - zero-sum (or the network extension), a fixed equilibrium despite periodic evolution of the game, and necessarily strictly periodic game evolution. The authors try to justify this as an interesting model of the world, but I really struggle to see it. As such, I find it difficult to get excited enough about the results to commend it for presentation at NeurIPS. It's perfectly good research, just not quite exciting or relevant enough to get in.

Just one or two specific comments on the paper:

- By the start of Section 3, I'm still not sure whether time is continuous or discrete! In fact the confusion continues beyond here even. Section 1 clearly talks about discrete rounds, and Section 2 talked about having a "sequence" of games, but in Section 3.1 time is continuous, reverting back to discrete at the end of Section 3.2, then a (reasonably standard) mixture of discrete and continuous when the Poincare map is introduced. Section 4 suddenly takes the payoff functions to be defined on continuous time and we never look back. A bit more clarity/honesty would be helpful.

- Typo in Lipschitz in footnote 2.

- The proof of Thm 2 shows that the x part of the FTRL dynamics are Poincarre recurrent, following on from the z's being Poincarre recurrent. However I do not think you claim that the y are Poincarre recurrent. You could be clearer on exactly what you mean here.

- In the experimental section, it would be helpful to remind the reader that the replicator dynamics is an example of FTRL - for those of us who are not quite so familiar with this line of research, it feels a little jarring to have been talking about FTRL all article then just see replicator dynamics in the experiments.

- Caption of Fig 2. It is far from clear to me what is meant by "Weighted constant of motion". I could probably decipher it, but could the caption be clearer perhaps?

limitations_and_societal_impact: Yes
review_title: null

Meta-review: No Reviewer has major concerns on this paper. The only objection is raised by Reviewer msZU and concerns the motivation behind the model and the significance. Such Reviewer also raises other points. I invite the authors to address these points carefully, together with the motivation behind the model, in the final version of the paper.
Decision: Accept (Poster)