Online Learning in Periodic Zero-Sum Games
Authors: Tanner Fiez
Ryann Sim
EFSTRATIOS PANTELEIMON SKOULAKIS
Georgios Piliouras
Lillian J Ratliff
Venue: NeurIPS 2021 Poster (2021)
Keywords: game theory
Poincar\'{e} recurrence
dynamical systems
zero-sum games
equilibrium
online learning
regret

Abstract: A seminal result in game theory is von Neumann's minmax theorem, which states that zero-sum games admit an essentially unique equilibrium solution. Classical learning results build on this theorem to show that online no-regret dynamics converge to an equilibrium in a time-average sense in zero-sum games. In the past several years, a key research direction has focused on characterizing the transient behavior of such dynamics. General results in this direction show that broad classes of online learning dynamics are cyclic, and formally Poincar\'{e} recurrent, in zero-sum games. We analyze the robustness of these online learning behaviors in the case of periodic zero-sum games with a time-invariant equilibrium. This model generalizes the usual repeated game formulation while also being a realistic and natural model of a repeated competition between players that depends on exogenous environmental variations such as time-of-day effects, week-to-week trends, and seasonality. Interestingly, time-average convergence may fail even in the simplest such settings, in spite of the equilibrium being fixed. In contrast, using novel analysis methods, we show that Poincar\'{e} recurrence provably generalizes despite the complex, non-autonomous nature of these dynamical systems.

Online Learning in Periodic Zero-Sum Games
Tanner Fiez* University of Washington
Ryann Sim SUTD
Seattle, Washington fiezt@uw.c edu
Singapore
ryann_ ceenn_ssmmmmmaaaammmm sutd edu sg
Stratis Skoulakis'
Georgios Piliouras SUTD Singapore
Lillian Ratliff'
SUTD
University of Washington Seattle, Washington ratliff fluw. @uw
Singapore
efstratios@autd.edu
georgioaūsutd, edu. sg
Abstract
A seminal result in game theory is von Neumann's minmax theorem, which states that zero-sum games admit an essentially unique equilibrium solution. Classical learning results build on this theorem to show that online no-regret dynamics converge an equilibrium a time-average sense in zero-sum games. In the past several years, key research direction has focused on characterizing the day-to- day behavior of such dynamics. General results in this direction show that broad classes of online learning dynamics are cyclic, and formally Poincaré recurrent, in zero-sum games. We analyze the robustness these online learning behaviors in the case of periodic zero-sum games with fime-invarianl equilibrium. This model generalizes the usual repeated game formulation while also being a realistic and natural model of repeated competition between players that depends on exogenous environmental variations such as time-of-day effects, week-to-wedd trends, and seasonality. Interestingly, time-average convergence may fail even in the simplest such settings, in spite of the equilibrium being fixed. In contrast, using novel analysis methods, show that Poincaré recurrence provably generalizes despite the complex, non-autonomous nature of these dynamical systems.
Introduction
The study of learning dynamics in zero-sum games is arguably as old field as game theory itself, dating back to the seminal work of Brown and Robinson 7 (2), which followed shortly after the foundational minmax theorem of von Neumann [33]. The dynamics of online no-regret learning algorithms [10 29 of particular interest in zero-sum games as they are designed with an adversarial environment in mind. Moreover, well known results imply that such dynamics converge in time-average sense minmax equilibrium in zero-sum games 10 15).
Despite the classical nature of the study online no-regret learning dynamics zero-sum games, the actual transient behavior of such dynamics was historically not understood. However, in the past several years this topic has gained attention with a number of works studying such dynamics in zero- sum games (and variants thereof) with particular focus continuous-time analysis [24] 25 20 6 32 23, 22). The unifying emergent picture is that the dynamics are "approximately cyclic" in formal sense known Poincaré recurrence. Moreover, these results have acted as fundamental building blocks for understanding the limiting behavior their discrete-time variants 2
"Joint first authors
I Joint last authors
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Despite the plethora of emerging results regarding online learning dynamics in semo-sum games, an important and well motivated aspect of this problem has only begun to receive attention.
How do online learning dynamics behave if the zero-sum game evolves over time?
Clearly, the answer to this question depends critically on how the game is allowed to evolve.
Problem Setting and Model. We study periodic zero-sum games with a time-invariant equilibrium, which is a class of games we formally define in Section 2 In a periodic zero-sum game, the payoffs that dictate the game are both T-periodic and zero-sum at all times. We consider both periodic zero-sum bilinear games on infinite, unconstrained strategy spaces and periodic zero-sum matrix games (along with network generalizations thereof) on finite strategy spaces. The goal of this work is to evaluate the robustness of the archetypal online learning behaviors in zero-sum games, Poincaré recurrence and time-average equilibrium convergence, to this natural model of game evolution.
Connections to Repeated Game Models. The time-evolving game model we study can be seen as a generalization of usual repeated game formulations. A time-invariant game trivial version of a periodic game, in which case we recover the repeated static game setting. For a general periodic zero-sum game with period T, each stage game now is chosen according to fixed length T sequence of games, capturing interactions between the players with time-dependent payoff'.
Periodic zero-sum games can also fit into the frameworks of mullii-geen contextual games [28] and dynamic games (see, c.g., [.). In a multi-agent contextual game [28], the environment selects a context from before each round of play and this choice defines the game that is played. Periodic zero-sum games can be seen as a multi-agent contextual game where the environment draws contexts from the available set in T- T-periodic fashion with each context defining zero-sum game with common equilibrium. In the class of dynamic games, there is a game state on which the payoff's may depend that evolves with dynamics. Periodic zero-sum games can be interpreted as a dynamic game where the state transitions do not depend on the strategies of the players, the state is T -'periodiic and the payoff's are completely defined by the state. We remark that the focus of existing work on contextual games and dynamic games is distinct from the questions investigated in this paper.
The periodic zero-sum game model allows to capture competitive settings where exogenous environmental variations manifest in an effectively periodic/epochal fashion. This naturally occurs in market competitions where time-of-day effects, week-to- week trends, and seasonality can dictate the game between players. To illustrate this point, consider a competition between service providers that wish to maximize their users, while the total market size evolves seasonally over time. This evolution affects the utility functions, even if the fundamentals of the market, and consequently the equilibrium, remain invariant.
Contributions and Approach. In this paper, for the classes of periodic zero-sum bilinear games and periodic cero-sum polymatrix games with time-invariant equilibrium, we investigate the day-to- gradient descent-ascent (GDA) and follow-the-
day and time-average behaviors of continuous- regularized-leate (FTRL) learning dynamics, respectively. This study highlights the careful attention that must be given to the dynamical systems in periodic zero-sum games which preclude standard proof techniques for Poincaré recurrence, while also revealing that intuition from existing results on static zero-sum games can be totally invalidated even by simple restricted examples in periodic zero-sum games.
Contribution 1: Poincaré Recurrence. A key technical challenge in this work is that the dynamical systems which emerge from learning dynamics in periodic zero-sum games correspond non- autonomous ordinary differential equations, whereas learning dynamics in static zero-sum games correspond to autonomous ordinary differential equations. Consequently, the usual proof methods from static zero-sum games for showing Poincaré recurrence are insufficient on their own in periodic zero-sum games. We overcome this challenge by delicately piecing together properties of periodic systems to construct a discrete-time autonomous system that we are able to show is Poincaré recurrent. This approach allows to prove both the GDA and FTRL learning dynamics are Poincaré recurrent in the respective classes of periodic zero-sum games (Theorems) [ 2 Finally, we show both periodicity and time-invariant equilibrium are necessary for such results evolving games (Proposition) D).
Contribution 2: Time-Average Strategy Equilibration Fails. Given that Poincaré recurrence provably generalizes from static zero-sum games to periodic zero-sum games, it may be expected that the aveeaeeeraee strategics in periodic zero-sum games converge to the time- invariant equilibrium

---

as in static zero-sum games. Surprisingly, we show that counterexamples can be constructed to this intuition even in the simplest of periodic zero-sum games. In particular, we prove the negative result that the time-average GDA and FTRL strategies do not necessarily converge to the time-invariant equilibrium the respective classes of zero-sum games (Propositions 2 3
Contribution 3: Time-Average Equilibrium Utility Convergence. Despite the negative result on the timeaaeeagee strategy convergence, in the special case of periodic zero-sum bimatrix games we are able to show a complimentary positive result on the time-average utility convergence. Specifically, we show that the time-average utilities of the FTRL learning dynamics converge to the average of the equilibrium utility values of all the zero-sum games included in a single period of our time-evolving games. (Theorem
Organization. In Section 2 we formalize the classes of games that we study, We present character- istics of dynamical systems as they pertain to this work in Section [3 Section and S our results analyzing CDA and FTRL learning dynamics in continuous and finite strategy periodie zero-sum bilinear and polymatrix games, respectively. We present numerical experiments in Section 6 and finish with a discussion in Section 7
Proofs of are theoretical results are deferred to the appendix.
2
Game-Theoretic Preliminaries
2.1 Continuous Strategy Periodic Zero-Sum Games
For continuous strategy periodic zero-sum games, we study periodic zero-sum bilinear games. We begin by formalizing zero-sum bilinear games and then define the periodic variant.
Zero-Sum Bilinear Games. Given matrix A E R"2 zero-sum bilinear game on continuous strategy spaces can be defined by the max-min problem maxz) ER" milly #1 Ar2. Formally,
the game is defined by the pair of payoff matrices {A, -A and the action space of agents I and 2 are given by R and "2 respectively. Player seeks to maximize the utility function u1 (I1, = xj Ax while player 2 optimizes the utility uy(#1, x2) = -x² A Ø1- The game is zero-sum since for any I1 E R and 22 E R"= the sum of utility over each player is zero. For zero-sum bilinear games, a Nash equilibrium corresponds to a joint strategy (af, x²) such that for each player and j o i, us(2] , xz) u, u; xī), Vas E R"; Note that (x), = (0,0) is always a Nash equilibrium of a zero-sum bilinear game.
Periodic Zero-Sum Bilinear Games. We study the continuous-time GDA learning dynamics in class of games we refer to as periodic zero-sum bilinear games. The key distinction from a typical static zero-sum bilinear game is that the payoff matrix no longer fixed in this class of games. Instead, the payoff matrix may change at each time instant as long as game remains zero-sum and the continuous-time time sequence of payoff' is periodic. The next definition formalizes this class of games.
Definition 1 (Periodic Zero-Sum Bilinear Game). A periodic zero-sum bilinear game is an infinite sequence of zero-sum bilinear games {A(t), A(!) ) in which the player set and strategy spaces fixed and the payoff matrix is such that A(t) = A(t + T) for finite period T and all t Z O. Note that in such a game, (0, 0) is always a time aime-invriaat Nash equilibrium. Furthermore, we assume that the dependence of the payoff entries on time is smooth everywhere except for a finite set of points.
2.2 Finite Strategy Periodic Zero-Sum Games
For finite strategy periodic zero-sum games, we analyze periodic zero-sum srro-sum polymatrix games. In what follows we define zero-sum polymatrix game, which is a network generalization of bimatrix game, and then detail the periodic variant considered in this paper.
Zero-Sum Polymatrix Games. An N- N-player polymatrix game is defined by undirected graph G= -V, F) where V is the player set and F. is the edge set where a bimatrix game is played between the endpoints of each edge [8). Each player i E has set of actions A, {1,.... ..)) that can be selected at random from distribution z; called a mixed strategy. The mixed strategy set of player
i V is the simplex in RT. denoted by X; A - {sa E mL E.EA, Tia = 1} where Vio
denotes the probability of action a E A: The joint strategy space is denoted by by X I.vv
The bimatrix game on edge (i.j) described using a pair of matrices A E RR and A E gn, xn. The utility or payoff of agent i E V under the strategy profile I E X is given by ux(x)
3

---

EE(L)E o. 2 and corresponds to the sum of payoffs from the bimatrix games the player participates in. We further denote by (x) Ee(t,)EE (A the utility of player E V under the strategy profile x = -;) E X for a E A; The game called zero-sum if Eiev ux(x) = 0 for all x E X. Each bimatrix edge game is not necessarily zero-sum in zero-sum polymatrix game.
Nash equilibrium in a polymatrix game is a mixed strategy profile x X such that for each player i V, u,,2, x=1)) 2 ui(z;, x-.), Vz, E X, A Nash equilibrium is said to be interior if supp(æ;; = A; Vi V where supp(a;) =
{a E A; Iso > 0} is the support of x; E X2
Periodic Zero-Sum Polymatrix Games. We analyze the continuous time FTRL learning dynamics class of games we call periodic zero-sum polymatrix games. This class games such that the payoffs defined by the edge games evolve periodically. We consider that this periodic evolution is such that there is common interior Nash equilibrium that arises in each zero-sum polymatrix game that arrives. The following definition formalizes the games we study on finite strategy spaces.
Definition 2 (Periodic Zero-Sum Polymatrix Game), A periodic zero-sum polymatrix game is an infinite sequence of zero-sum polymatrix games {G(tt (V {(t)){= in which the set of players, strategy spaces, and edges are fixed and each bimatrix game on an edge (i.j) is such that (t) = A T) and (t) = A T) for some finite period T and all 2 We assume there is a common interior Nash equilibrium x² E XX of the polymatrix game Gtt) for all t 2 O. Furthermore, we assume that the dependence of the payoff entries on time is smooth everywhere except for finite set of points.
3 Preliminaries Dynamical Systems
We now cover concepts from dynamical systems theory that will help us analyze learning dynamics in periodic zero-sum games and prove Poincaré recurrence. Careful attention must be given to these preliminaries in this work since the dynamical systems we study are non-autonomous whereas typical recurrence analysis in the study of learning in games deals with autonomous dynamical systems.
3.1 Background on Dynamical Systems
We begin this section by providing dynamical systems background that is necessary both for defining Poincaré recurrence and sketching typical proof methods along with our approach.
Flows. Consider an ordinary differential equation à: = =(t,,x) on a topological space X. We can define the flow Φ x X + of a dynamical system ă, for which the following holds: (i) .(t,,): X + X, often denoted o² X X, is a homeomorphism for each t E R. (ii) ob + s, @l1, ((, for all 1,8 R and all E X, (iii) for each X, di (r=00(1,,2)) ((,,z)) = x[l) the solution.
I x), and (iv)
Existence and Uniqueness. We utilize Carathéodory's 's existence theorem to guarantec the existence of flow for é, even for some discontinuous functions f.
Theorem (Carathéodory's 's existence theorem [13] 16)). Consider differential equation + f(t, on rectangular domain R = {(t, It tol < a, |æ - æol S 6}. If f satisfies the following conditions:
1. ftt, is continuous in y for each fixed
2. [(1,x) is measurable in for each fixed y,
3. there is Lebesque-integrabbl function m [to a + a] + 10,00) such that
15(1,x)) S mm(t) for all (1, E R.
then the differential equation has solution. Moreover, if f is also Lipschitz continuous, meaning [(1,21) [(,,, x2)1 & k(())=z x2| with some Lebesgue-integrube function k: 1lo a, l0 + a)
[0, 00), then there exists a unique solution the differential equation.
In the settings we study, the above three conditions hold: Condition 1 holds because for every fixed the dynamics we study (specifically GDA and FTRL) are continuous functions of their state space. Condition 2 holds because the systems study are finite and continuous elmost-everywhere, and

---

so by Lusin's s theorem [18] are measurable for each fixed y. Finally, Condition 3 is always satisfied because the games we study always admit bounded orbits. Hence, it follows that a unique flow exists for all the dynamical systems studied in this paper.
Conservation of Volume. The flow o of an ordinary differential equations is called volume preserving if the volume of the image of any set U _ I under øf is preserved, meaning that vol( (U)) = VU)( Liouville's 's theorem states that flow volume preserving if the divergence of f at any point x E Rd equals zero: that is, xl), = tr(Df((,x)) = E af((.=) 82.
We now transition to give general Poincaré recurrence statements along with discussion of how the results are usually applied in game theory before we outline our proof methods.
3.2 Poincaré Recurrence in Autonomous Dynamical Systems
number of works in the past several years show that online no-regret learning dynamics are Poincaré recurrent in repeated static zero-sum games (see, e.g., 124 20 The proof methods for deriving such results crucially rely on the static nature of the game for the reason that the learning dynamics amount to an autonomous dynamical system. Informally, the standard Poincaré recurrence theorem states that if an autonomous dynamical system preserves volume and every orbit remains bounded, almost all trajectories return arbitrarily close to their initial position, and do so infinitely often (26]; this property of a dynamical system is known as Poincaré recurrence. Thus, proving the Poincaré recurrence of dynamics in repeated static zero-sum games is tantamount to verifying the volume preservation and bounded orbit properties. We now formalize the Poincaré recurrence theorem.
Given a flow of on topological space X, point x E X is nonwandering for ø' if for each open neighborhood U containing æ. there exists T' > such that U (U) + O. The set of all nonwandering points for ø', called the nonwandering set, is denoted (2())).
Theorem (Poincaré Recurrence for Continuous- Systems (26)). flow preserves volume and has only bounded orbits, then for each open almost all orbits intersecting the set intersect it infinitely often: if is a volume preserving flow on a bounded set Z C Rd, then 1((00)= Z.
In order to describe our proof methods in the following subsection for showing Poincaré recurrence in periodic zero-sum games, it will be useful for us to state an alternative formulation of the Poincaré recurrence theorem that is applicable to autonomous discrete- time systems.
Theorem (Poincaré Recurrence for Discrete-Time Maps (4). Let (X,E, be a finite measure space and let Φ: X + X be a measure measure-ppeserring preserving map. For any E E E, the set of those points x of E for which there exists N E N such that Φ² (x) & E for all n N has zero measure. In other words, almost every point of E returns to E. In fact, almost every point returns infinitely often. That is, p ((x E: AN s.I. (x) & E for all N)) 0.
3.3 Poincaré Recurrence in Periodic Dynamical Systems
The proof methods described in the last section for showing the Poincaré recurrence of dynamics in static zero-sum games cannot directly be applied to time-evolving zero-sum games result of the non-autonomous nature of the systems. In fact, we can construct time-evolving zero-sum games without both periodic payoffs and time-invariant equilibrium, where online learning dynamics not Poincaré recurrent Despite this hurdle, we show that in the natural subclass of time-evolving games covered by periodic zero-sum games (periodic payoffs and time-invariant equilibrium), we can develop proof methods to show the Poincaré recurrence of online learning dynamics. Given the previous claim regarding the possible non-recurrent nature of learning dynamics when there is not both periodic payoffs and a time-invarian equilibrium, this is perhaps the most general class of time-evolving zero-sum sum games with obtainable positive results in this direction.
We now give an overview of our approach, beginning by recalling properties of periodic systems.
Periodic Systems and Poincaré Maps. A system i = [((,xr) is T-periodic if ʃ(I (L+ +xx) = f(1, for all (xr, 1). Leet o² : Ra - R denote the mapping taking x E I to the value at time For a T T'periodic system, TT+ o² 8" so that O²T = (6 for any integer k. The mapping TT _R + R is called the Poincaré map or the mapping at period.
We formalize this statement in Proposition
I of the following section.
5

---

If the differential equation is well-defined for all I and has solution for all t E [0. T), then for each initial condition (where we have suppressed the dependence on To), the Poincaré map o" defines discrete-time autonomous dynamical system x = o² (a)). The learning dynamics we study in periodic zero-sum games form T --periodic dynamical systems. Thus, the discrete-time autonomous dynamical system x+ = x² (x) formed by the Poincaré map is key to the analysis methods we pursue. In particular, our approach is to show that this system is Poincaré recurrent, which we then use to conclude that the original continuous-tine non-autonomous system is Poincaré recurrent.
Given the previously presented Poincaré recurrence theorem for discrete- timeete-timeeee maps, proving the Poincaré recurrence of the system x o" (x) requires verifying the volume preservation and bounded orbit properties, which then implies the measure preserving property. The following result states that if the divergence of a T -periodic vector field f(r, t) is divergence free so that the flow of volume preserving. then the Poincaré map o² and the resulting discrete-time dynamical system at x²(xx) (a:) is also volume preserving.
Theorem (Volume preservation for T-Periodic Systems 3.1.B, Thm 2)). the T -periodiic system f(t, x) is divergence-free, then 6" preserves volume.
Similarly, if orbits of ă f(t, are bounded, then clearly the orbits of x (x) are bounded. Hence, to show the system x+ <² (ar) is Poincaré recurrent, we prove free vector-field (equivalently, that the flow is volume preserving) and only bounded orbits. This will
f(t, x)) has a divergence-
then be sufficient to conclude f(t, æ) Poincaré recurrent since the discrete-time system forms a subsequence of the continuous-time system.
4 Gradient Descent-Ascen in Periodic Zero-Sum Bilinear Games
This section focuses on the continuous-timg time GDA learning dynamics periodic zero-sum bilinear games. The dynamics such that each player seeks to maximize their utility by following the gradient with respect to their choice variable and are given by
d (t)) 2 = - A (t)
4.1 Poincaré Recurrence
The focus of this section is characterizing the transient behavior of the continuous-time GDA learning dynamics in periodic zero-sum games. Specifically, we show the following result.
Theorem 1. The continuous time GDA learning dynamics are Poincaré recurrent any periodic zero-sum bilinear game as given in Definition
Theorem establishes that the recurrent nature of continuous-time GDA dynamics in static zero-sum bilinear games is robust to the dynamic evolution of the payoffs in periodic zero-sum bilinear games.
Prior to outlining the proof steps for Theorem we elaborate on the claim from the previous section that without the periodicity property and a time-invariant equilibrium, such a result is unobtainable. In particular, we show the Poincaré recurrence of the GDA dynamics is not guaranteed without both properties by constructing counterexamples when only one of the properties holds.
Proposition 1. There exists time-evolving zero-sum games such that there is a time-invariant equilib- rium or the payoffs periodic (but not both simultaneously) in which the GDA dynamics not Poincaré recurrent.
This proposition highlights the strength of our results regarding GDA, given that the assumptions needed to obtain them are more or less tight.
We now outline the key intermediate results prove to obtain Theorem I following the techniques described in Section 3.3 For the GDA dynamics, we utilize the observation that the corresponding vector fields divergence free show that the learning dynamics volume-preserving. We now state this result formally.
Lemma 1.
The GDA learning dynamics are volume preserving in any periodic zero-sum bilinear game given in Definition]

---

We then proceed by showing that the GDA orbits are bounded by deriving a time-invarian function. This step relies on the fact that we have a time-im inveiinariantt equilibrium.
Lemma 2. The function (()) {
(1)x (l) + Io (1)=2(()) is time-invariant. Hence, the GDA orbits are bounded in any periodic zero-sum bilinear game as given in Definition !
Given the volume preservation and bounded orbit characteristies of the continuous- time GDA learning dynamics in periodic zero-sum games, the proof of recurrence follows by applying the arguments described in Section 3.3
4.2 Time-Average Convergence
The Poincaré recurrence continuous-time GDA learning dynamics in periodic zero-sum bilinear games indicates that the system has regularities which couple the evolving players and evolving game despite the failure to converge to a fixed point. A natural follow-up question to the cyclic transient behavior of the dynamics is whether the long-run converges to a game- theoretttoretcallly meaningful outcome.
We show that in periodic zero-sum bilinear games, the time-average of GDA learning dynamics may not converge to the time-invariant Nash equilibrium. To prove this, we consider periodic zero-sum bilinear game with the action space of each player on R so that the evolving payoff simply rescales the vector field. We construct the payoff sequence so that the dynamics return back the initial condition after period of the game, while the
of the dynamics are not equal to the time-invariant equilibrium (vj, xτ) = (0, 0). Given the simplicity of this example, effectively rules out hope to provide a meaningful time-average convergence guarantee in this class of games.
Proposition 2.
There exists periodic zero-sum bilinear games satisfying Definition D where the time-average strategies of the GDA dynamics fail to converge to the time-invariant equilibrium (0, 0).
Follow-the- hallow-the-Reguaaiize---eed in Periodic Zero-Sum Polymatrix Games
We now analyze continuous-timg FTRL learning dynamics in periodic zero-sum polymatrix games. Players that follow FTRL learning dynamics this class of games select a mixed strategy at each time that maximizes the difference between the cumulative payoff evaluated over the history of games and a regularization penalty. This adaptive strategy balances exploitation based on the past with exploration.
Formally, the continuous-time FTRL learning dynamics for any player E in periodic zero-sum polymatrix game with an initial payoff vector (0) Rn are given by
yi (1) = (0) +J' Σ JEJEER (T))
xr (4) argmax,,ex, (I - h,,xr)
where h;; X4 + iss penalty term which encourages exploration away from the strategy which maximizes the cumulative payoff' in hindsight. We assume that the regularization function h.()) for each player i E V is continuous, strictly convex on X, and smooth on the relative interior of every face of Xz These assumptions ensure the update x, (t) is well-defined since a unique solution exists.
Common FTRL learning dynamics include the multiplicative weights update and the projected gradient dynamics. The multiplicative weights dynamics for a player E arise from the regularization function hz(2,) = E Tia log Pia and correspond to the replicator dynamics. The projected gradient dynamics for a player V derive from the Euclidean regularization he(x:) _ ||
To simplify notation, the FTRL dynamics can equivalently be formulated as the following update
(t) (0) + fu (x((),
(1) = (1))
Observe that we denote by (2(2,, r) (uaa (z, 7) T)) the vector of each pure strategy E A, utility for agent E V under the joint profile x = (a, x) E X at time T 2 0. Moreover, Q; R": > X is known as the choice map and defined
Qt()(t)) argmax, xx (1)(tt, hx(x,))
7

---

In this notation. the utility of the player i E V under the joint strategy 2 (Iz. x_1) E X' at time
t 2 is given by u,(2, r) (v,(2, T), rz). Observe that in our notation of utility we are now including the time index to make the dependence on the evolving game and payoff's explicit.
For any player i V denote by h; TR R the convex conjugate of the regularization function hy X. + E which is given by the quantity h (t) maX,, i (2 (t)) (z;2)))
5.1 Poincaré Recurrence
We now focus characterizing the transient behavior of the continuous- time FTRL learning dynamics in periodic zero-sum polymatrix games. is known that the continuous- Poincaré recurrent in static zero-sum polymatrix games (20). The following result demonstrates that this characteristic holds even in games that are evolving in a periodic fashion with a time-invariant equilibrium, providing broad generalization.
FTRL learning dynamics
Theorem 2. The FTRL learning dynamics are Poincaré recurrent in any periodic zero-sum polymatrix game as given in Definition 2
For the remainder of this subsection, describe proof methods. The general approach is that prove the Poincaré recurrence transformed system using the techniques described in Section 3.3 This conclusion then allows to infer the equivalent property for the original FTRL system.
The utility differences for each player differential equation
V and pure strategy a E A.s \ evolve following the
Sio Via, (z(t), Us, (z)
Toward proving that this system is Poincaré recurrent, we show that the vector field é is divergence free and hence volume preserving.
Lemma 3. The dynamics defined by the system é are volume preserving in any periodic zero-sum polymatrix game given in Desinition
We then construct a time-invariant function along the evolution of the system that is sufficient to guarantee that the orbits generated by the å dynamics are bounded. Recall that x" denotes the common, imme-invariant interior Nash equilibrium of the periodic zero-sum polymatrix game.
Lemma 4, The function ((x", , y(t)) = Evev (hą (t)(t)) (xt (t) + h,(x;)) is time-invariat.. Hence, the orbits generated by the å dynamics are bounded in any periodic zero-sum polymatrix game as given in Definition)
From this point, we follow the arguments from Section 3.3 to conclude the ; dynamics are Poincaré recurrent. Finally, we show that Poincaré recurrence the system sufficient to guarantee the Poincaré recurrence of the FTRL learning dynamics.
The proofs of the results in this section can be found in Appendix D
5.2 Time-Average Convergence
number of well-known properties of zero-sum bimatrix games fail to generalize to zero-sum polymatrix games. Indeed, fundamental characteristics of zero-sum bimatrix games include that each agent has a unique utility value in any Nash equilibrium and that equilibrium strategies are exchangeable. However, Cai and Daskalakis [ show that neither of these properties guaranteed in zero-sum polymatrix games. Consequently, in general, time-average convergence to the set of equilibrium values in the utility and strategy spaces does not equate the stronger notion of pointwise convergence.
For the reasons just outlined, we pursue different notion of time-average convergence in periodic zero-sum polymatrix games. That is, we consider the subclass of periodic zero-sum bimatrix games (2-player periodic zero-sum polymatrix games) and show that the aineraeerage utility of each agent converges to the time-average of the game values (that is, the unique utility the player obtains at any Nash equilibrium)
a period of the periodic game.
Theorem 3.
In periodic zero-sum bimatrix games satisfying Desinition 2 if each player follors FTRL dynamics, then the time -veerage utility of each player converges to the lime-average over a period of the game equilibrium utility values.
8

---

Theorem 3 paints a positive view of the time-average behavior of FTRL learning dynamics in periodic zero-sum games. However, the following result demonstrates that much like in the case of GDA in periodic zero-sum bilinear games, the time-average strategies are not guaranteed to converge to the time-invariant Nash equilibrium.
Proposition 3. There exist periodic zero-sum bimatrix games satisfying Definition 2 in which the time-average strategies of FTRL dynamics fail converge to the time-invariant Nash equilibrium.
We prove the negative result in this proposition by constructing simple counterexample that corresponds to vime-na rescaling of Matching Pennies.
The proofs of the results in this section be found in Appendix
Experiments
In this section, we present several experimental simulations that illustrate our theoretical results. To begin, for continuous-time GDA dynamics show that Poincaré recurrence holds in periodic zero-sum bilinear game. We consider the ubiquitous Matching Pennies game with payoff matrix (-17) 7. We then the following periodic rescaling with period 2m:
sin(l) (2) (t mod( 2T)
< I
< 3m
a(t) -
T
S S 2T
When players follow the GDA learning dynamics, we see from Figure that the trajectories when plotted alongside the value of the periodic rescaling are bounded. A similar experimental result holds the case of FTRL dynamics. In the supplementary material, we simulate replicator dynamics with the same periodic rescaling as in Figure 1 bounded due to the invariance of the Kullback-Leible divergences (KL-divergence).
The trajectories in the dual/payoff space also remain
11-Dhargance
0,032
6:61
0.000
Time Slagss
Figure 2: Weighted sum of KL-divergences for 64-player periodically rescaled Matching Pennies game. Note that despite the complicated trajectories of each player, the weighted sum of their divergences remains constant.
Figure 1: Bounded trajectories for periodically rescaled Matching Pennies game updated using GDA.
Lemmas and 4 describe functions & which remain time-invariant. In the case of replicator dynamics, (() is the sum Hullback-Leible divergences measured between the strategy of each player and their mixed Nash strategy [1/2, 1/2]. We simulated a 64-player polymatrix extension to the Matching Pennies game, where each agent plays against the opponent immediately adjacent to them, forming 'toroid" -like chain of games. Furthermore,
randomly rescale each game with different periodic function. Figure 2 depicts the claim presented in the lemmas: although each agent's specific divergence term KL(x)) (t)) fluctuates, the sum Σiev KL(x (lx, remains constant.
To generate Figure 3 we show the data from simplified 64-player polymatrix game simulation, where the graph that represents player interactions is sparse. Here, the strategy of each player informs RGB value of a corresponding pixel on grid. the system exhibits Poincaré recurrence, we should eventually see similar patterns emerge the pixels change color over time (i.e., as their corresponding mixed strategies evolve). As observed in Figure 3, the system returns near the initial image time T 6226. Further details about the experiments be found in Appendix

---

T =
(b) T 700
(c) (c) 1500
(d) T 3300
(e) T 5000
( T 6226
Figure 3: Sequence of images showing Poincaré recurrence in an 8 x 8 zero-sum polymatrix game, where the changing color of cach pixel on the grid represents the mixed strategy of the player over time. After time T = 6226, we see that approximation of the original image is recovered, showing that the recurrence property holds.
7 Discussion
We study both GDA and FTRL learning dynamics in periodically varying zero-sum games. We prove that the recurrent nature of such dynamics carries over from static games to the classes of evolving games we study. Yet, in the settings we analyze, the time-average convergence behavior from static zero-sum games can fail to generalize. This work takes a step toward understanding the behavior of classical learning algorithms for games in the more realistic setting where the game itself is not fixed.
We conclude by discussing related works on learning dynamics in evolving games. The existing literature considers number of models that admit distinct results [I9 30 14] In class of time-evolving games where the evolution can be arbitrary [9] algorithms are designed that provide novel type of regret guarantee called Nash equilibrium regret. competitive against the Nash equilibrium of the tem--averaged payoff matrix. In an analysis of discrete-time time FTRL dynamics evolving games that are strictly/strongly monotone [14), sufficient conditions (e.g., when the evolving game stabilizes) under which the dynamics track/converge to the evolving equilibrium are derived. Unfortunately, zero-sum games do not satisfy these strong properties. Finally, in model of endogenously evolving zero-sum games where parametric game evolves itself adversarially towards the participating agents, a transformation that treats the game as additional "hidden" agents allows for reduction more standard static network zero-sum game has been developed [19 30 under which both ame-average convergence to equilibrium as well as Poincaré recurrence holds.
sense these algorithms are
This growing literature indicates that time- vareina games can exhibit distinet and often times more complex behavior than their classic static counterparts. As such, there is much potential for future work towards better understanding of their learning dynamics.
Acknowledgments and Disclosure of Funding
This rescarch/project is supported in part by the National Research Foundation, Singapore der its AI Singapore Program (AISG Award No: AISG2-RP- -020--01, NRF 2018 Fellowship NRF-NRFF2018
PRF2019-NRF-ANRO9 ALIAS grant, grant MIE-SGP-AI-208--- AME Pro- grammatic Fund (Grant No. A20H6b0151) from the Agency for Science, Technology and Research (A*STAR). Tanner Fiez was supported by National Defense Science and Engineering Graduate Fellowship.
References
[1] V. I. Amol'd. Mathematical methods of classical mechanics, volume 60. Springer Science & Business Media, 2013.
[2] J. P. Bailey and G. Piliouras. Multiplicatiie weights update in zero-sum games. In ACM Conference on Economics and Computation, pages 321-338, 2018.
[3] J. P. Bailey, G. Gidel, and G. Piliouras. Finite regret and cycles with fixed step-size via alternating gradient descent-ascent. Conference on Learning Theory, pages 391-407, 2020.
[4] I.. Barreira. Poincaré recurrence: old and new. In XIVih International Congress on Mathmattcal Physics, pages 415-422, World Scientific, 2006.
10

---

[5] T. Başar and G. J. Olsder. Dynamic noncooperative game theory. SIAM, 1998.
[6] V. Boone and G. Piliouras. From Darwin to Poincaré and von Neumann: Recurrence and Cycles in Evolutionary and Algorithmic Game Theory. International Conference on Web and Internet Economics, pages 85-99, 2019.
[7] G. Brown. Iterative solutions of games by fictitious play. In Activity Analysis of Production and Allocation, T.C. Koopmans (Ed.), New York: Wiley. 1951.
[8] Y. Cai and C. Daskalakis. On minmax theorems for multiplayer games. In Symposium of Discrete Algorithms, pages 217-234, 2011.
[9] A. R. Cardoso, J. Abernethy, H. Wang, and H. Xu. Competing against nash equilibria in adversarially changing zero-sum games. In International Conference on Machine Learning, pages 921-930, 2019.
[10] N. Cesa-Bianchi and G. Lugoisi. Prediction, Learning, and Games. Cambridge University Press, 2006.
[11] Y. K. Cheung. Multiplicative weights updates with constant step-size in graphical constant-sum games. In Advances Neural Information Processing Systems, pages 3528-3538, 2018.
[12] Y. K. Cheung and G. Piliouras. Vortices instead of equilibria in minmax optimization: Chaos and butterfly effects of online learning in zero-sum games. In Conference on Learning Theory, pages 807-834, 2019.
[13] E. A. Coddington and N. Levinson. Theory of ordinary differential equations. Tata McGraw- Education, 1955.
[14] B. Duvocelle, P. Mertikopoulos, M. Staudigl, and D. Vermeulen. Learning in time-varying games. arXiv preprint 1809,0/800903000 2018
[15] Y. Freund and F. Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1-2):79-103, 1999.
[16] J. K. Hale. Ordinary differential equations. Robert E. Krieger Publishing Company, 1980.
[17] M. Heino, J. A. Metz, and V. Kaitala, The enigma of frequency-dependent selection. Trends in Ecology & Evolution, 13(9):667-370, 1998.
[18] N. Lusin. Sur les propriétés des fonctions mesurables. CR Acad. Sci. Paris, 158025)1688-1169, 1912.
[19] T. Mai, M. Mihail, I. Panageas, W. Ratcliff, V. Vazirani, and P. Yunker. Cycles in Zero- Sum Differential Games and Biological Diversity. In ACM Conference on Economics and Computation, page 339-350, 2018.
[20] Mertikopoulos, C. Papadimitriou, and G. Piliouras. Cycles in adversarial regularized learning. In Symposium of Discrete Algorithms, pages 2703-2717, 2018.
[21] P. Mertikopoulos, B. Lecouat, H. Zenati, C.-S. Foo, V. Chandrasekhar, and G. Piliouras. Opti- mistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In International Conference on Learning Representations, 2019.
[22] S. G. Nagarajan, D. Balduzzi, and G. Piliouras. From chaos to order: Symmetry and conservation laws in game dynamics. In International Conference on Machine Learning, pages 7186-7196. 2020.
[23] J. Perolat, R. Munos, J.-B. Lespiau, S. Omidshafiei. M. Rowland, P. Ortega, N. Burch, T. An- thony, D. Balduzzi, B. De Vylder, G. Piliouras, M. Lanetot, and K. Tuyls. From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regular- ization. arXiv preprint arXiv:2002.08.4 2020.
[24] G. Piliouras and S. Shamma. Optimization despite chaos: Convex relaxations to complex limit sets via Poincaré recurrence. In Symposium of Discrete Algorithms, pages 861-873, 2014.
11

---

[25] G. Piliouras, C. Nieto-Granda, H. I. Christensen, and J. S. Shamma. Persistent patterns: Multi- agent learning beyond equilibrium and utility. In International Conference on Autonomous Agents and Multi-Agent Systems, pages 181-188, 2014.
[26] H. Poincaré. Sur le problème des trois corps et les équations de la dynamique. Acta mathematica, 13(1), 1890.
[27] J. Robinson. An iterative method solving a game. Annals of Mathematics, 54:296-301 301, 1951.
[28) G. Sessa, I. Bogunovic, A. Krause, and M. Kamgarpour. Contextual games: Multi-agent learning with side information. In Advances in Neural Information Processing Systems, 2020.
[29]
Shalev-Shwartz et al. Online learning and online convex optimization. Foundations and trends in Machine Learning, 4(2):107-194, 2011.
[30] S. Skoulakis, T. Fiez, R. Sim, G. Piliouras, and L. Ratliff. Evolutionary game theory squared: Evolving agents in endogenously evolving zero sum games. In AAAI Conference on Artificial Intelligence, 2021.
[31] A. R. Tilman, J. B. Plotkin, and E. Akçay. Evolutionary games with environmental feedbacks. Nature communications, 11(1):1-11, 2020.
[32] E.-V. Vlatakis Mattaki--Garagkkuniii L. Flokas, and G. Piliouras. Poincaré Recurrence, Cycles and Spurious Equilibria in Sradient-Descent-Aaee Games. In Advances in Neural Information Processing Systems, pages 10450-10461, 2019.
for Non-Convex Non-Concave Zero-Sum
[33] J. von Neumann. Zur theorie der gesellschaftssieee.. Mathematische Annalen, 100:295-300. 1928.
[34] Weitz, C. Eksin, Paarporn, P. Brown, and C. Ratcliff. An oscillating tragedy of the commons in replicator dynamics with game- came-ennironment feedback. National Academy of Sciences, 113(47), 2016.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] The contributions and scope are clearly stated and derived directly from results.
(b) Did you describe the limitations of your work? [Yes] We have explained the limitations of our work thoroughly in the Introduction, Preliminaries and Discussion.
(c) Did you discuss any potential negative societal impacts of your work? [No] The work primarily theoretical, and thus does not have any directly negative societal impacts. (d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] We have not used any human-derive data in work, and in general our paper conforms to the guidelines.
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] All assumptions are stated either in the main body or in the suppiementary material.
(b) Did you include complete proofs of all theoretical results? [Yes] See the supplementary material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] The code and instructions required to reproduce the results are given in several formats within the supplementary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A] Our simulations do not require the above.
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [N/A] Our simulations are deterministic.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]] We explain the resources and compute used in the supplementary material.
4. If you using existing assets (e.g., code, data, models) curating/releusing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A] All assets used are proprietary.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] Our work does not include human-derived data.
(e) Did you discuss whether the data you using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "qTbmm0bu5I2", "reviewer": "Reviewer_mKLL", "summary": "#  Summary of Paper\nThe authors study the behaviour of two continuos time\nlearning dynamics under two types of periodic zero-sum games, continuous gradient descent ascent (GDA) in unconstrained bilinear games,\nand continuous follow the regularized leader (FTRL) in polymatrix games.\nIt is shown that under mild conditions, both GDA and FTRL are Point-Care recurrent,\nall orbits eventually return arbitrarily close to the initial conditions.\nThe 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\nin games with insightful negative and positive results.\n\n", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n\n# Originality and Quality\nThe 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\ngames 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.\n\n# Clarity \nThe paper is extremely well-written, making a technical topic accesible to a large audience,\nthough some technical details could use more clarification (as discussed below).\n\nAlthough I believe the paper to be a good contribution, I have some issues regarding the technical details.\n+ 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?\n+ 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.\n\n# Suggested improvements and Clarifications\n\n + 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?\n + 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)? \n+ 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?\n + Why does the existence of a time invariant scalar function $\\Phi$  imply bounded dynamics?\n   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? \n + 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.\n + 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).\n\n## Questions and Possible Future Work\n\n+ 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?\n+ 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.\n+ 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.\n+ It would be helpful to include more citations for some of the standard Dynamical systems results, for example Louiville's theorem.\n\n\n# References\n1. V. I. Arnol’d. Mathematical methods of classical mechanics, volume 60. Springer Science &\nBusiness Media, 2013.\n2. Wiggins, S., Wiggins, S. and Golubitsky, M., 1990. Introduction to applied nonlinear dynamical systems and chaos (Vol. 2). New York: springer-verlag.\n3. Hart, S. and Mas‐Colell, A., 2000. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68(5), pp.1127-1150.\n4. Hart, S. and Mas-Colell, A., 2003. Regret-based continuous-time dynamics. Games and Economic Behavior, 45(2), pp.375-394.\n5. Orabona, F., 2019. A modern introduction to online learning. arXiv preprint arXiv:1912.13213.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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\nis 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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "adJnr2RExHW", "reviewer": "Reviewer_yvC8", "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).", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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)\n\nAt 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.\n\nMinor 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).\n\nThe 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "X9Og6i9x_tf", "reviewer": "Reviewer_msZU", "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nJust one or two specific comments on the paper:\n\n- 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.\n\n- Typo in Lipschitz in footnote 2.\n\n- 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.\n\n- 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.\n\n- 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?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "BsbegE-1Ex", "reviewer": "Reviewer_a6SU", "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.\nSeminal 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.\n(Reference number follows the paper.)", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:\nWhereas 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.\n\nQuality:\nProposed theorems and lemmas seem to be technically sound, and the experimental results support the theorems.\n\nClarity:\nThe paper is well-written and easy to follow, and honestly describe a negative result that there exists a counter example.\n\nSignificance:\nIt 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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4hours"}, "extra_text": {}}]

Author rebuttal:

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)