Chaos of Learning Beyond Zero-sum and Coordination via Game Decompositions
Authors: Yun Kuen Cheung
Yixin Tao
Venue: ICLR 2021 Poster (2021)
Keywords: Learning in Games
Lyapunov Chaos
Game Decomposition
Multiplicative Weights Update
Follow-the-Regularized-Leader
Volume Analysis
Dynamical Systems

Abstract: It is of primary interest for ML to understand how agents learn and interact dynamically in competitive environments and games (e.g. GANs). But this has been a difficult task, as irregular behaviors are commonly observed in such systems. This can be explained theoretically, for instance, by the works of Cheung and Piliouras (COLT 2019; NeurIPS 2020), which showed that in two-person zero-sum games, if agents employ one of the most well-known learning algorithms, Multiplicative Weights Update (MWU), then Lyapunov chaos occurs everywhere in the payoff space. In this paper, we study how persistent chaos can occur in the more general normal game settings, where the agents might have the motivation to coordinate (which is not true for zero-sum games) and the number of agents can be arbitrary.

We characterize bimatrix games where MWU, its optimistic variant (OMWU) or Follow-the-Regularized-Leader (FTRL) algorithms are Lyapunov chaotic almost everywhere in the payoff space. Technically, our characterization is derived by extending the volume-expansion argument of Cheung and Piliouras via the canonical game decomposition into zero-sum and coordination components. Interestingly, the two components induce opposite volume-changing behaviors, so the overall behavior can be analyzed by comparing the strengths of the components against each other. The comparison is done via our new notion of "matrix domination" or via a linear program. For multi-player games, we present a local equivalence of volume change between general games and graphical games, which is used to perform volume and chaos analyses of MWU and OMWU in potential games.

Published as a conference paper at ICLR 2021
CHAOS OF LEARNING BEYOND ZERO-SUM AND COORDINATION VIA GAME DECOMPOSITIONS
Yun Kuen Cheung
Yixin Tao
Department of Computer Science Royal Holloway University of London Egham, UK
Department of Mathematics
London School of Economics
London, UK
yunkuen. cheungh rrul. acc uk
Y. Taol 60 aee.ac.to
ABSTRACT
It is of primary interest for Machine Learning to understand how agents learn and interact dynamically in competitive environments and games (e.g. GANs). But this has been difficult task, as irregular behaviors are commonly observed in such systems. This can be explained theoretically, for instance, by the works of Cheung & Piliouras (2019) 2020), which showed that in two-person zero-sum games, if agents employ one of the most well-known learning algorithms, Multi- plicative Weights Update (MWU), then Lyapunov chaos occurs everywhere in the cumulative payoff space. In this paper, we study how persistent chaos can occur in the general normal-form game settings, where the agents might have the mo- tivation to coordinate (which is not true for zero-sum games) and the number agents can be arbitrary.
We characterize bimatrix games where MWU, its optimistic variant (OMWU) Follow-the-Red Bellow-th-Reguuariiee--- Regularized-Leaade (FTRL) algorithms are Lyapunov chaotic almost everywhere in the cumulative payoff space. Our characterizations are derived by extending the volume-expansion argument of Cheung & Piliouras via the canon- ical game decomposition into zero-sum and coordination components. Interest- behaviors, so the
ingly, the two components induce opposite volume- overall behavior can be analyzed by comparing the strengths of the components against each other. The comparison is done via new notion of "matrix domi- nation" or via a linear program. For multi-player games, we present a local equiv- alence of volume change between general games and graphical games, which is used for volume and chaos analyses of MWU and OMWU in potential games.
INTRODUCTION
In Machine Learning (ML), is of primary interest to understand how agents learn in competitive environments. This is more strongly propelled recently due to the success of Generative Adversarial Networks (GANs), which can be viewed as two neural-networks playing zero-sum game. As such, Evolutionary Game Theory (EGT) (Hofbauer & Sigmund (1998); Sandholm (2010)), decades-old area devoted to the study of adaptive (learning) behaviors of agents in competitive environments arising from Economics, Biology, and Physics, has drawn attention from the ML community. In contrast with the typical optimization (or no-regret) approach in ML, EGT provides a dynamical- systemic perspective understand ML processes, which has already provided new insights into number of ML-related problems. This perspective is particularly helpful in studying "learning in games", where irregular behaviors are commonly observed, but the MI community currently lacks of a rigorous method to analyze such systems. In this paper, we study Lyapunov chaos, a central notion that captures instability and unpredictability in dynamical systems. We characterize general normal games where popular learning algorithms exhibit chaotic behaviors.
Lyapunov chaos captures the butterfly effect: when the starting point of a dynamical system is slightly perturbed, the resulting trajectories and final outcomes diverge quickly; see Definition for a formal definition. The perturbations correspond to round-off errors of numerical algorithms in ML (and Computer Science in general) While significant efforts have been spent in analyzing and
In games, such perturbations can also occur due to errors measuring payoffs.

---

Published as a conference paper at ICLR 2021
minimizing round-off effects of floating-poine computations (Demmel (1997), ) they are unavoidable in genera |
As round-offs are inevitable, and the round-off schemes can vary from machine to machine due to various hardware and software factors, we surely want to avoid chaotic learning that does not fulfill our primary goals in building predictable and reproducible learning systems. Such issues are exemplified by quote from Ali Rahimi|s
test-of-time award speech:
"Someone on another team changed the default rounding mode of some Tensor- flow internals from 'truncate toward zero' to 'round to even'. : Our training broke. our error rate went from less than 25% error to ~ 99.97% error."
To avoid chaotic learning, we first need to understand how it can arise. This is the main mo- tivation of our work. Recently, in the context of "learning in games", Cheung & Piliiurra (2019 2020) presented interesting theoretical analyses to show that in two-person zero-sum and graphical constant-sum games, if the agents employ Multiplicative Weights Update (MWU) or Follow-the- Regularized-Leace (FTRL) algorithms, then Lyарunov chaos occurs everywhere in the cumulative payoff space; the same result holds for the optimistic variant of MWU (OMWU) in coordination games [3] While zero-sum and coordination games are interesting in their own rights, they are rather small subspaces within the family of general normal games. In this paper, we present techniques and tools for characterizing general games where MWU, FTRL,, OMWU are Lyapunov chaotic almost everywhere. Next, we give an overview of our contributions and a discussion of related work.
Our Contributions. To show the results about chaos mentioned above, Cheung & Piliouras (2019) 2020) used a classical technique in the study of dynamical systems called volume analysis. Volume analysis considers a set of starting points of positive Lebesgue measure, e.g. ball centred at point; volume is an alternative name for Lebesgue measure in this context. When this set of starting points evolves according to the rule of dynamical system, it becomes a new set with a different volume. Intuitively, volume is measure of the range of possible outcomes, so the larger it is, the more un- predictable the system is. the set's volume increases exponentially with time, then its diameter increases exponentially too, which implies Lyapunov chaos. This indicates that when players re- peatedly play the games by employing the respective learning algorithms, a slight perturbation on the initiating condition can lead to a wide range of possible cumulative payoffs in the long run. This can be shown to imply instability in the mixed strategy space.
The technical starting point of Cheung & Piliouras is to show that when all agents in a bimatrix game G use MWU with step-size c, and when set S in the cumulative payoff' space evolves for one time step. its volume change can be expressed as e² Jg Cc (s) ds + O(E)), where CG is a function that depends on the game G, which we will define in Section 2 Clearly, the sign of Cc dictates the volume change behaviors for all small enough c. Cheung & Piliouras showed that CG is a positive function when G is a two-person zero-sum game. For a large region in the cumulative payoff space, this implies the volume change per time step is 2((=2)-volume( (S), i.e. volume expands exponentially. They also showed that CG a negative function if G is a two-person coordination game.
To extend their volume expansion results to general bimatrix games, we first discover that CG admits a clean decoupling w.r.t. the canonical decomposition of such games into zero-sum and coor- dination components (Basar & Ho (1974); Kalai & Kalai). Precisely, given any two-person general game (A, B). it can be written uniquely as a direct sum of a zero-sum game (Z. -Zi) and a coor- dination game (C, C), where Z = (A B) /2 and C (A + B2/2. Interestingly, we find that Ca(.) = (zz (+) + Cic.o, (-) in Lemma 6 Recall from the last paragraph that Ciz.-z)() is always positive, while C(c.o) (.) is always negative. Thus, to see whether volume expansion occurs, it boils down to comparing the strengths of (-))-z)()) and (C.
We also discover that the function CG is invariant upon additions of trivial matrices to the game G; see Definition 7 and Lemma 88 An immediate application of trivial matrices is for bimatrix potential games (Monderer & Shapley (haaley((1996)) for which show it can be transformed a coor- dination game via additions of trivial matrices. With the result in Cheung & Piliouras (2020), this immediately implies that OMWU in any bimatrix potential game is Lyapunov chaotic everywhere in the cumulative payoff space (Observation 10).
Based on the above discoveries, we identify two characterizations of bimatrix games where MWU and FTRL are Lyapunov chaotic almost everywhere (Theorems 15 and [7 As said before,
For instance, in learning algorithms we often evaluate the function e", while is an irrational numher. They also showed some other chaos results for various combinations of learning algorithms and games.
2

---

Published as a conference paper at ICLR 2021
the key is to compare the strengths of the C-functions of the zero-sum and the coordination com- ponents. The comparison is done via our new notion of matrix domination (see Definition IT), and also a linear program (Eqn. (7)) which is designed to prune out the trivial-matrix projection and keep the remaining part minimal. Such family of games has positive Lebesgue measure in the bimatrix game space, so it is not confined to any proper game subspace" [4] This justifies the claim that the occurrences of chaos are not only circumstantial, but a rather substantial issue in learning in games. Analogous result holds for OMWU.
For games with any number of players (multi-playe games), we use an observation in Cheung & Piliouras (211)) coupled with our new findings about bimatrix games discussed above, to present a new family of graphical games where MWU is Lyapunov chaotic almost everywhere (Theorem 18] the new family strictly includes all graphical constant-sum sum games. To facilitate volume analyses of learning in multi-playe games, we establish their local equivalence of volume change with graphical games. Briefly, we show that Ca (p) for a general game G is the same as (H) for some graphical game H; H will depend on the point p. that's why we say the equivalence is local (Theorem [9] This provides an intuitive procedure for understanding volume changes, as the volume change of learning in a graphical game is easier to compute. This is used to show that the volume-changing behaviors of MWU and OMWU are opposite to each other. We use these to analyze MWU and OMWU in multi-player potential games; in particular, we show that CG (p) of multi-player po- tential game G is identical to Cc(p) of corresponding multi-player graphical coordination game, while (p) < for any P (Proposition 2
Related Work. MWU and its variant, such as FTRL and Optimistic MWU, play important roles in online learning. We recommend the texts of "Cesa-Biiandll & Lugosi (006) and Hart& &
(2013) for a modern overview of online learning from Machine Learning or Economics perspectives.
Recently, there is a stream of works that examine how learning algorithms behave in games or min-max optimization from a dynamical-systemtte perspective. This provides new insights into learning systems which could hardly be obtained with classical tools in ML. For instance, some learning systems are shown to be nearly-periodic under the notion of Poincaré recurrence (Piliouras) & Shamma 4)014); Mertikopoulos et al. (2018). Using potential functions first proposed in EGT and other tools from mathematics, surprising behaviors of first-order methods in zero-sum games and min-max optimization were discovered (Daskalakis & Panageas (2018 2019); Bailey & Pil-
touras (0118); Cheung )018)). In Appendix A we give an account on some further related work.
Empirical evidences of Lyapunov chaos of learning in games were reported by [Sato et al. (2002)
and Galla & Farmer 2013). Li-Yorke chaos, another classical chaos notion, was proved to occur in several learning-in -n----n--ne -ame systems (Palaiopanos et al. (2017); Chotibut et al. (2020).
Volume analysis has long been technique of interest in the study of population and game dynamics. It was discussed in a number of famous texts; see (Hotbauer & Sigmund 1998, Section 11), (Fudenberg & Levine, 1998 Section 3) and (Sandholm 2010, Chapter 9).
We use game decomposition in this paper, which is a natural and generic approach to extend compelling results for specific family of games more general games. Let H. denote the specific family of games with some compelling properties. Given a general game, we seek to decompose it into a sum of its projection on H. plus one or more residue components. the residues are small, then it is plausible that those compelling properties extend (approximately). In seeking of games where learning is stable, game decompositions were used (Candogan et al. (ll(221)) 1 2013a b): Letcher et al. 2019)) with H being potential games.
PRELIMINARY
In this paper, every bold lower-case alphabet denotes vector, every bold upper-case alphabet de- notes a matrix or a game. When we say a "game", we always mean a normal-form game. Given n, let A " denote the mixed strategy space of dimension
22, ..... zn.) Σÿ= žj 1}. Normal-Form Games. Let N denote the number of players in a game. Let S, denote the strategy set of Player and S == S X x Sy. Let n, = |..]. (s),... 9N) E S denotes strategy
1 i.e. [(z1, {2,
"The families of zero-sum and coordination games proper subspaces of the bimatrix game space. Any proper subspace has Lebesgue measure zero
'The thcorem and propositions mentioned in this paragraph will be stated formally in Appendix C 'The probability simplex over n strategies is (n 1)ddimmnsionll.
3

---

Published as a conference paper at ICLR 2021
profile of all players, and (s) denotes the payoff to Player i when each player picks 8,. A mixed strategy profile is denoted by x = ,X,,'..,NN E A x ... x A "x, and i, is extended to take mixed strategies as imputs via u, Es [s](.)] We let -01,," ,.,))) denote the player set
xx)
other than players i1. ... .dg. We also let
, J1 (x) Es -i1 aay (1) [un (8%, = j1, 11 ,i, = jg. S- (ii... +))],,
(I)
which is the expected payoff to Player in when: for 1 g. Player is picks strategy jy, while for each player & (f1,--.ihh she picks a strategy randomly following x,. We also use Jijz--da if x is clear from the context. We say a game is a zero-sum game if Σ; u4(s) 0 for all E S, and we say a game is a coordination game if (s()) = (s)s) for all Players i and A and for all s E S.
adopt the notations below. Let (A, B) denote a bimatrix game, where for any j E St, k E S2, Aia := ki(ik)). Bi == u2(2, k). x and y denote mixed strategies of Players and 2 respectively. A bimatrix game is a zero-sum game if A = -B; it is a coordination game if A = B. Note that Uj = [Ay]], U/ [ [ which denote by Aj, B3 respectively when y,y clear from context; B,, As are defined analogously.
When N- = 2, such games are called bimatrix games, for which
MWU, FTRL and OMWU in Games. All three algorithms have a step-size e, and can be im- plemented updating in the cumulative payoff (dual) space. In each round, the players' actions (mixed strategies) in the strategy space are functions of the cumulative payoff vectors to be defined below, and these actions strategies, let p' E Rd denote her cumulative payoff vector at time t, and let p" E IR denote the starting point chosen by the player. For MWU in game, the update rule for Player i is
then used to determine the payoff's in the next round. For player with
p
p} + 6. (x''),
(2)
where U/ is the function defined in Eqn. Ip. and x" is the mixed strategy below:
aj = (p') = exp(e))/(E exp(p)))
(3)
For OMWU in a game, the update rule for Player i starts with p = p", and for t 2 2, p1+11
29 + e (x') (})+ where x" is determined by Eqn. 3
For FTRL in a game, the update rule for Player is same as Eqn. but x' is determined as below using convex regularizer function h, A + R: x' = arg max {(p', x h2 hx(x) As all the results for MWU can be directly generalized to FTRL as discussed in (Cheung & Piliouras 2019 Appendix D), keep our exposition simple, in the rest of this paper, we focus MWU and OMWU, and their comparisons. For bimatrix game, we use p. q to denote the cumulative payoff vectors of Players| and 2 respectively.
Dynamical Systems, Lyapumov Chaos and Volume Analysis. A learning-in-gant -nggnmme system can be viewed as discrete-time dynamical system, for which we present a simplified definition which suits our need. A tiscrete-time dynamical system in IRd is determined by a starting point (0) E Rd and an update rule r(t+1)= f (r(()), where f d + 1d is function The sequence r r(0), r(), r(2), is called a trajectory of the dynamical system. When f is clear from the context, we let : (N U {0)) xR + Rdd denote the function such that ott,, r) is the value of r(f) generated by the dynamical system with starting point set to r. Given a set 24 C Rd,, we let (1, = (t(t,r)) E UJ. Let 2(r,2) denote the open ball with center and radius z.
There are several similar but not identical definitions of Lyapunov chaos, all capturing the butter- fly effect: when the starting point is slightly perturbed, the resulting trajectories diverge quickly. We use the following definition, which was also used by Cheung & Piliouras (2019) 2020) implicitly. Intuitively. a system is Lyapunov chaotic in an open set O C Rd if for any r E O and any open ball B around r, as long as (t, B) remains inside O, there cxists r' E B such that [ r') - (tt, I) grows exponentially with f. Lyapunov exponent in the definition below is a measure of how fast the exponential growth is; the larger it is, the more unpredictable the dynamical system is.
Rigorously, OMWU in game is not dynamical system, as the update to p(t 1) depends on both p(t), p(t - 1). But there is function f such that p(t + 1) R f(((t)), while the volume-changing behavior not really affected (Cheung & Piliouras 2020
4

---

Published as a conference paper at ICLR 2021
Definition 1. A dynamical system is Lyapunov chaotic in open set O R if there exists
constant > O and a Lyapunov exponent 7 = (()) > 0, such that for any r E O for any
sufficiently small 8 > 0 for all satisfying 0 t < min 2 Φ(T, B(r, 6)) yf O),
sup r'e((r.8)
[| - ((),) 2 X-
Definition 2. A dynamical system is Lyapunov chaotic everywhere if it is Lyapunov chaotic in any bounded open subset of R...
In the above definitions, all norms and radii are Euclidean norms. For capturing round-off errors in computer algorithms and ML systems, it is more natural to use -norm with ó be the maximum round-off error per step, say 10-16 16 when IEEE 754 binary64 (standard double) used.
When O is small set, it is casy to determine whether dynamical system is Lyapumov chaotic in O. since the dynamic can be locally approximated by a linear dynamical system, where the eigenvalues of the local Jacobian characterizes chaotic behaviors. But when O is large, determining whether Lyapunov chaos occurs is difficult in general. Cheung & Piliouras (2019) found that volume analysis can be useful in this regard, based on the following simple observation.
Proposition 3. In Rd,, if a set U has volume at least u, then its radius w.n.t any point r E u is at least w2/d /2. Thus, if the volume of (t,UU) of some dynamical system is ((exp(1() for some 0, then the radius of ((1,U) w.r.l. any point E $(1,U) is (exp(( ()).
Cheung and Piliouras showed Lemma which, for bimatrix games, reduces volume anal- ysis to analyzing the sign of the function C(A.B) (P, a) defined in Eqn. (4) below; the sign also determines the local volume-changing behavior around the point (p, q) when MWU is used. Based on Proposition that converts volume expansion to radius expansion, the sign can be used to determine if the dynamical system is Lyapunov chaotic.
Let Aj Ev Ukk Vx, TxTA Ay] and A& = =E Fy Ay Vyu [x] Ay]; and, similarly,
B₁ Exs' B5 = Vx, By] and BB Cy Vy, [x[ [y]. Then,
(A. = - Ex,y [AA, A₁- (Bj - B5- Ba)] + Ex,y [Aja] Ex,y [Bxu]- (4)
Note that here x and y are the shorthand for x(p) and y(q). which are the mixed strate- gies (i.c. probability distributions over strategics) of Players and respectively, as computed via Eqn. 3p. Also, Ex.y [f k)] E (x()))))((())x(())) [f (j, k)] is the expected value of f(j k) when the strategies j and & are randomly chosen according to the distrubutions x(p) and y()) respectively.
For multi-player game G, the analogous function CG(.) is given below; the U quantities were defined in Eqn. (T). Lemma E is adapted from Cheung & Piliouras (2019) for games with any number of players. Derivation of Eqn. (5) uses the Jacobian of the corresponding dynamical system and integration by substitution; see Appendix
Ca ... .PN) = Σ
Σ
TieTTk (U
Ut) (U - Uj).
(5)
JESN, Assi, BES
Lemma 4. Suppose O is set in the cumulative payoff space Rd where nn + ... + nN, and
(o(() = (pi." (pi.". EEN)EO
inf Ca(pI, PN) > 0.
(6)
Then for the dynamical system in which MWU with any sufficiently small step-size e is employed to play the game G. it is Lyapunov chaotic in O with Lyapunov exponent ēc(O) è² /2d.
MSW is replaced by OMWU, then the same result holds by replacing the condition (6) with to (O) == (p. p -o..peoo-CCCPppp. .PN]] > 0.
'e note that many linear dynamical systems admits simple clased-form solutions (c.g. dz/ x has solution x(t) x00) e²), but they considered Lyapunov chaotic under this definition. This might not match with the intuitive meaning of "chaos" many people. However, for non-linear dynamical systems which mostly not admit closed-fore solutions (including all systems we study), Lyapunov chaos is well-received as a notion that captures unpredictability.
They showed that, in the cumulative payoff space, when the St evolved to gi+1 after one MWU step. then vol u (1*+1) = vo volume (St) + e" (pp4)) C(A.B)(P, ()(,q) dp dq + O(e*). Thus, C(A,B) (p.q) then the volume increasing, which indicates diverging trajectories, i.e. chaos.
5

---

Published as a conference paper at ICLR 2021
Note that if we start from Nash equilibrium in the strategy space, MWU and OMWU will stay the equilibrium. However, if this equilibrium (x",y") satisfies the conditions in Corollary 5 below, there are points arbitrarily close to the equilibrium that keep moving away from the equilibrium (if the region ((x'y') = (x(p), y (P)) q) E } is large in the strategy simplex A x A
Corollary 5 (Adapted from (Cheung & Piliouras 2020, Theorem 5)). Let yx) be a point in the interior of the strategy space. Suppose that there exists (p. q) in the cumulative payoff space, such that x* = x(p") and y" = =y(q"). Furthermore, suppose C(A,B) (P', > 0, and (p, q) E O where O is the set described in Lemma 4 Then there are strategy points arbitrarily close to (x", .Y) such that MWU in the game (A, B) eventually leaves the corresponding strategy set of O, L.e. ((x,x'))
y())) q) O}.
We give the intuitions behind the proof of Corollary 5 Suppose the contrary, i.e. for any open neighbourhood of (p" q'), its flow never escapes from First, the volume of the flow expands at Ieast exponentially with time. Second, by Eqn. (2). each p grows at most linearly with I (since UjI < maxj, (axx,,A(AAx], [Bxx)) and thus the volume of the flow can only expand at most polynomially with time.
O
Then there are two contradicting facts.
When the game is zero-sum, i.e., B - A, hence C(A.B) q) = Ex, [(Aj# - Aj - Ax)
Ex,y [(Axx))? Since Ex,y [Aya] = Ex,y [A₂] Ex [Ax] and hence Ex.y [Ajs Aj An]
- -xxy [Ajz]. C(A.B) (p, q) is indeed the variance of the random variable Ast Aj - Ag. and thus
non-negative. By Eqn. (4) we have C(A.B) q) = - -AA.B) BB (P, q). Thus, for any coordination
game (A, we have C(A.A)(P. C(A (A. S..
BIMATRIX GAMES
In this section, we focus on general bimatrix games (A, B). In Section 3.1 analyzing C(A,B) (.), and then provide an example to show how to use these tools. In Section 3.2 we present two characterizations such that the dynamics are Lyapunov chaotic almost everywhere.
we present two tools for
3.1 TOOLS FOR ANALYZING BIMATRIX GAME
First Tool: Canonical Decomposition for Bimatrix Games. For every bimatrix game (A, B), it admits a canonical decomposition (Basar & Ho 1974; Kalai & Kalai) into the sum of zero-sum game (Z. -Z) and a coordination game (C, C). where Z 5 - B) and C = 1 (A + B), i.e.
(A, B) (Z, -Z) CC,
We call (Z, -Z) the zero-sum part of the game (A, B), and (C, C) the coordination part of the game. Our first result shows that the function C(-) can be decomposed neatly into the two parts too. Lemma 6. For any bimatrix game B),
C(A.B)(P.q) q) = (p. + (c..c)(p..)
Proof. We use Eqn. to expand the following:
4 C(z. (P. q) + 4. (CC,,,;(p..)) q)
-E [[A}x B₁ A₁ + B, A + B&) E [Ajx B₁xl²
- -E [[AxM jk + B,д - A;-
-B As Ba) + +E [Ask: + Bjr]
-E [[A,x -Bik~ - A, + B, B,-A4 4.+BBb 3 + +Bik Ag - B, -Ax B=)
(B [A₃a] E 2 [A1 + E [B,,))²
-E + B, + (A A, A+)] + 4. E [AAya] I [[Aba] = 4 (...)))
By the end of Section 2 we discussed that Czz. (p. q) is always non-negative and C(c.cy(p. (p. q) is always non positive.... By the above lemma, we can analyze the volume-changing be- havior of a bimatrix game (A, B) by looking at its zero-sum and coordination parts independently. One simple intuition is that if the coordination (resp. zero-sum) part is small, then the volume- changing behavior of (A, B) is closer to the behavior of the zero-sum (resp. coordination) part. We realize this intuition quantitatively in the next subsection.

---

Published as a conference paper at ICLR 2021
Second Tool:
Trivial matrix. Trivial matrices are matrices which do not affect the volume- channing behavior, as depicted Lemma Beloo.
Definition (Trivial Matrix). T Raxm a trivial matrix if there exists real numbers U1, U2. Un and 01, 02. um such that Tzk. Uj U for all j E [n], E [m]. Lemma 8. For any two trivial matrices T', T any two matrices A, B E R
C(A.B)(P..) C(A+TIBBTT))P.. q).
One immediate application of this lemma is for two player potential games. Definition 9. A game G is potential gume if there exists a potential function P - R such that for any Player and any strategy profile S, ((si, -Ps.) 8-1) ui(8i, s-1) uu 8-.) s-i).
For the potential game, have the following observation:
Observation 10. For any bimatrix potential game (A, B), there is coordination game (P, P) such that A P, B are trivial matrices. P the matrix representation of the potential function P.
This observation immediately implies that the volume-changing behavior of potential game is equivalent to that of a corresponding coordination game.
We give a concrete example to show how these tools help us to analyze the (.).B)()).
Simple Example. We will show how to use our tools to demonstrate C(-) 2 everywhere for the following game. In the example, each player has three strategies. The payoff bimatrix
(A, B) is given below. The first number gives the payoff of the row player, who chooses a strategy from {a, c); the second number gives the payoff of the column player, who chooses strategy from {1, 2, 3). We first use our first tool to decompose this game into zero-sum part (Z, -Z) and
Strategy
Strategy 2
Strategy 3
Strategy a (4,4)
(12, 4)
(-6, 10)
Strategy b
(-8,8)
(0,0)
(12, -4)
Strategy
(14, -2)
(-8,8)
(4,
coordination part (C, C), where Z easily figure out which one is larger between C(z.- (-)-) and C(c, c)(.)
0 -8
and C
[44 2
0
At this point, we still cannot
L6 0
However, we can further
4
2
-21
decompose the coordination part by the second lool: C
+
+
where the first
0
matrix on the RHS is trivial matrix (using notations Definition
u TT = [2. 2). It's easy
to see the second matrix the RHS is I. Then by Lemmas 6 function C, for any point (p, q) in the cumulative payoff space,
and
8 and the definition of the
C(A.B)(P. q) C(z. z, (p. q) + ((.Z) (1-41/))) C(z.-z) (p. 20.
3.2 RESULTS FOR BIMATRIX GAMES
In this subsection, identify several characterizations for general bimatrix games in which have chaotic behavior with MWU dynamic in a following set 5 in the cumulative payoff space Rai+na Note that when 5 is tiny, its strategy correspondence covers almost the entirety of the strategy simplex A x A= thus we informally say that if the dynamical system is Lyapunov chaotic in S for tiny 8, then it is Lyapunov chaotic almost everywhere.
S (pppp) 9) MVj Si.k k E S2, 2,(p) 2 A (x) 8).
In order to show chaotic behavior of MWU in a specific bimatrix game (A, B), it is sufficient to show C(A.B) (p. q) is strictly positive in the region 5 due to Lemma 4. In the previous subsection, show that for each game (A, ; it can be decomposed into zero-sum part (Z, -Z) and coordination part (C, C). Furthermore, C(A.B) (p. q) = Ciz.-z) (p. q) + (p. We also raise an intuition that if the zero-sum part is small, then the volume behavior in the game (A, B) will be similar that in the coordination part; conversely, if the coordination part is small, then the volume behavior will be similar to the zero-sum part. However, we have not yet presented a way to compare the largeness of the parts. This is what we do here.
7

---

Published as a conference paper at ICLR 2021
3.2.1 FIRST CHARACTERIZATION! MATRIX DOMINATION
The first characterization we identify is matrix domination. In this part, we show that under certain conditions, the zero-sum part is always no less than the coordination part, i.. C(z,- (1z.z2) (p, q) 2 -Cic.c) (P. q) for all (p, q). This directly implies (A..B q) will be non-negative in the whole cumulative payoff space. Interestingly, the condition we identify both necessary and sufficient. Similar result can also be achieved in the case that coordination part is always no less than the zero-sum part. We first introduce the definition of the matrix domination.
Definition 11. We say matrix K dominates matrix L if they are of the same dimension, and for any row indices j and column indices ki k',
K + K
j. K'
Kjk Kyrl 2 [Lg + Low Lyg. Lgpal-
Note that the domination induces partial order on all matrices: K dominates L and L domi- nates M, then K dominates M. The theorem below gives the necessary and sufficient condition.
Theorem 12. CiA.B)(P.O) q) is non-negative for all (p, q) if and only if matrix of the zero-sum part Z dominates the matrix of the coondination part C.
The above theorem is based on the following crucial observation. Observation 13. For any matrix Z.
(z.-2)(P..)) = 4 Σ rp(p)
ye(() . (p) (q) (Zzx - Zow Zax -
Jd k.
Matrix domination only implies C(A, B) (p. q) is non-negative. In order to have C(A,B) q). to be strictly positive in the set S, we need f-domination.
Definition 14. We say matrix K 6-dominates (0 0) matrix L K dominates L, and there exist j.
j', k, W such that K, + Ky K5K' Kyn 2 Lys + -Ly L,j Llpxl +
The following theorem holds due to Lemma
Theorem 15. For any general bimatrix game B) which is decomposed into zero-sum part (Z. -b) and coordination part (C, C), Z 0 0-dominates C, then MWU with any sufficiently small step-size in the game (A, B) is Lyapunov chaotic in $ with Lyapunov exponent 2(n1+m2)
Note that Definition the context of Theorem 15 is easy to see that there are quite many games (A, B), such that Z 0- dominates C with all those incqualities strictly satisfied. Thus, there exists an open neighbourhood around these games such that every game in the neighbourhood has its zero-sum part 0-dominates its coordination part. This shows that such family of games has positive Lebesgue measure.
K 0-dominates if finite number of inequalities are satisfied. In
3.2.2 SECOND CHARACTERIZATION LINEAR PROGRAM
Note that matrix domination is not always true. In some scenarios, the zero-sum matrix might not dominate the coordination matrix. Yet, is still possible that ((A,B)(,, q) strictly positive in the region $6 when every entry in the coordination matrix is small.
Precisely, for general bimatrix game (A, B). if its coordination part (C, C) small in the sense that the absolute values of all entries in C are smaller than some constant r, then we can bound Cic._co cy( (-) by O(r²). This is not the only case where we can bound C(c.-cy()) by a small term. Even if the entries in matrix C are large, we can use trivial matrices to reduce them without affecting C(c,-o)()) (-). This is done via linear programming approach described below.
Given matrix K, let r(K) be the optimal value of following linear program:
min r such that Vj. k; r < 5 9j h < r20.ghh
Note that {gz h. & is trivial matrix. Let = = K (gj j.k. By Lemma C (.) (-)=
C(K: -K)())) ((K:-K/) (.). The following lemma shows that the value of C(K,KK) (-) is closely related to r(K).
Lemma 16. For any q) in 5 {(p q) V, 2,(p) and (q) 28, (r(K) 8)2 <
C(K.KK (P, q) S r(K)2.
8

---

Published as a conference paper at ICLR 2021
Then the theorem below follows by applying Lemma 16 with Lemma
Theorem 17. For any general bimatrix game (A, B) which is decomposed into zero-sum part (Z. -Z) and coordination part (C, C), if there exists 0 > O such that (r(Z) 8)² 2 (r(C))² + (, then MWU with any sufficiently small step-size e the game (A, Lyapunov chaotic in
S with Lyapunov exponent 8 2(2+
Intuitively, r() is a distance measure from the zero-sum game (Z, -Z) to the trivial game space; analogously, r( r(C) is distance measure from the coordination game (C, C) to the trivial game space. Theorem 17 shows that if the coordination part is much closer to the trivial game space than the zero-sum part, then MWU in this game is Lyapunov chaotic in 5
EXPERIMENT
To illuminate that volume expansion occurs when MWU is employed in game with small coordination part, we simulate T0 in a game which is the sum of zero-sum game (10 --
MWU in the reduced payoff space
0 -1 and coordination game
(I [[-0.05 0.03
] [ -00.5
-0.05
0.03
-0.05
In the strategy space, x" y (0.5, 0.5) the unique Nash equilibrium of the game. In the reduced dual space, the origin cor- responds to the equilibrium. We pick a square of side length 0.004 around the origin as the set of starting points (the small red square in the middle of Figure TD. As these starting points are evolved via MWU with step-size 0.02, take snapshots after every 1900 time steps, which are shown with colors blue, pink, lime, purple, orange and green (then the colors repeat) respectively. As shown in the fig- ure, the volume (which is area in two-dimensional space) increases, and its shape changes from a square to parallclogram.
Figure 1: Volume expansion
of MWU the bimatrix game ([0.95 0.03
[-1.6 -1.05
0.95
CONCLUSION AND FUTURE WORKS
In this paper, we analyze the volume-changing behavior of several well-known learning algorithms (MWU, OMWU, FTRL) on general bimatrix games and multi multi-player games, which leads to Lya- punov chaos analysis. For bimatrix games, we do this by decomposing a game into the zero-sum part and the coordination part. This decomposition turns the volume analysis into comparing the strengths of volume-expansion (zero-sum part) and volume-contraction (coordination part) of the MWU dynamics. The comparison of strengths is made via the notion of matrix domination and the use of linear program. For multi-player games, by the local equivalence, we show that the volume-changing behavior of MWU and OMWU are opposite to each other even in multi-player games. We also show, for general multi-player potential game, the key function CG is equal to corresponding multi-player coordination game, which implies it not positive.
Studying learning in matrix (normal-form) games, which are among one of the most classical game models, is good theoretical starting point. Matrix games admit mathematically amenable analyses, as demonstrated in our work and many previous works. For future works, we are im- mensely interested in chaos analyses on settings that are more relevant to applications in ML, e.g. general GANs and differential games. We believe the techniques we use (volume analysis, game decomposition, etc.) can be applicable.
ACKNOWLEDGMENTS
We thank several anonymous reviewers for their suggestions, which help improve the readability of this paper from its earlier version. Yixin Tao acknowledges NSF grant CCF-1527568, CCF- 1909538 and ERC Starting Grant ScaleOpt-757481. Yun Kuen Cheung acknowledges Singapore NRF 2018 Fellowship NRF-NRFF2018-07.
Reduced payoff' space is projection of the original payoff space. In the reduced payoff space, the horizonal axis is Pt P2, while the vertical axis is -2- The original cumulative payoff space is four-dimensional, for which it difficult to give graphical illumination. This is why we the reduced space instead.

---

Published as a conference paper at ICLR 2021
REFERENCES
James P. Bailey and Georgios Piliouras. Multiplicative weights update in zero-sum games. In EC, pp. 321-338, 2018.
Luis Barreira. Poincare recurrence: old and new. In X/Vih International Congress on Mathematical Physics. World Scientific.. pp. 415-422, 2006.
Tamer Basar and Yu-Chi Ho. Informational properties the nash solutions of two stochastic nonzero-sum games. Journal of Economic Theory, 7(4):370-387, 1974.
Victor Boone and Georgios Piliouras. From darwin poincaré and von neumann: Recurrence and cycles in evolutionary and algorithmic game theory. In International Conference on Web and Internet Economics (WINE), pp. 85-99. Springer, 2019.
Ozan Candogan, Ishai Menache, Asuman E. Ozdaglar, and Pablo A. Parrilo. Flows and decompo- sitions of games: Harmonic and potential games. Math. Oper. Res., 36(3):474-503, 2011. doi: 10.1287/moor. 10.0500. URL/attss//aoi. org. 10.g//1...0 1287 /ooo0./mor.... 1110. 0500
Ozan Candogan, Asuman Ozdaglar, and Pablo A. Parrilo. Dynamics in near-potential games. Games Econ. Behav., 82:66-90 90, 2013a. doi:
URL https://dooi
org
wtw.e...bb.... 001
Ozan Candogan, Asuman E. Ozdaglar, and Pablo A. Parrilo. Near-potential games: Geometry and dynamics. ACM Trans. Economics and Comput.. 1()):1::1-11333 2013b. doi: 10.1 10.1145/246576. 2465776. URL htttt:::////// http://dioorgg/11.1
wtgg/0....0. http:/...1114//// 1111/2445//69999 2465776
Nikolo Cesa-Biande and Gabor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
Yun Kuen Cheung. Multiplicative weights updates with constant step-size in graphical constant-sum games. In NeurlPS, pp. 3532-3542, 2018.
Yun Kuen Cheung and Georgios Piliouras. Vortices instead of equilibria in minmax optimization: Chaos and butterfly effects of online learning in zero-sum games. In Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, pp. 807-834, 2019. URL http:
//proceedings.oo mlr. press 999 cheung 9a. html
Yun Kuen Cheung and Georgios Piliouras. Chaos, extremism and optimism: Volume analysis of learning in games. In NeurIPS, 2020.
Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. In COLT 2012 The 25th Annual Conference on Learning Theory, June 25-27, 2012, Edinburgh, Scotland, pp. 6. 6.120. 2012. URL http:::p//rcccednnng/e mir..mmm.r...mm m.r. wwwpppesssss...
Thiparat Chotibut, Fryderyk Falniowski, Michat Misiurewicz, and Georgios Piliouras. Family of chaotic maps from game theory. Dynamical Systems, pp. 1-16, 2020, doi: 10.1080/14689367. 2020.1795624. Published online. Volume and number not yet assigned.
Constantinos Daskalakis and Ioannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. In Advances in Neural Information Processing Systems, pp. 9256-9266,
2018.
Constantinos Daskalakis and loannis Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. ITCS, 2019.
Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. Near-optimal no-regret algorithms for zero-sum games. Games and Economic Behavior, 92:327-348 2015.
James W. Demmel. Applied Numerical Linear Algebra. SIAM, 1997. doi: 10. 9781611971446,
Yoav Freund and Robert E. Schapire. decision-ttheoreti generalization of on-lin learning and an application to boosting. In FaroCOLT, pp. 23-37, 1995.
10

---

Published as a conference paper at ICLR 2021
Yoav Freund and Robert E. Schapire. Game theory, on-line prediction and boosting. In COLT, pp- 325-332, 1996.
Drew Fudenberg and David K. Levine. The Theory of Learning in Games. MIT Press Books. The MIT Press, 1998.
Tobias Galla and J. Doyne Farmer. Complex dynamics in learning complicated games. PNAS, 110 (4):1232-1236, 2013.
Sergiu Hart and Andreu Mas-Colell. Simple Adaptive Strategies:Frow From Regret- to Un- coupled Dynamics. Number 8408 in World Scientific Books. World Scientific Publishing Co. Pte. Ltd., June 2013. ISBN ARRAY(Ox3d2ca660) URL httthttts//deeeeee repes org/b/
wsi htt////bbook///00/ html
Elad Hazan and Satyen Kale. Extracting certainty from uncertainty; regret bounded by variation in costs. Mach. Learn., 80000000233331-1122. 2010. doi: 10. 10.1007/110944400-577333 URL https:
Josef Hofbauer and Karl Sigmund. Evolutionary Games and Population Dynamics. Cambridge University Press, 1998. doi: 0001017/CB097811399773
Adam Tauman Kalai and Ehud Kalai. Engineering cooperation two-player games. http://www.rooot..ox.aaa www.:roooossooo............ wwtp.s/.......//gooooouuonnnnnn. wtt.s/aaaaakkaaiiiiiiooo
Michael J. Kearns, Michael Littman, and Satinder P. Singh. Graphical models for game the- ory. In UAI '01: Proceedings of the 17th Conference in Uncertainty in Artificial Intelli- gence, University of Washington, Seattle, Washington, USA, August 2-5, 2001, pp. 253-260, 2001. URL 1eemm=22artiicleedoee0orereeeeee id=11
jsp ummuus
Alistair Letcher, David Balduzzi. Sébastien Racanière, James Martens, Jakob N. Foerster, Karl Tuyls, and Thore Graepel. Differentiable game mechanics. Mach. Learn. Res., 20:84:1-84:40, 2019. URL/attp:// /mmrrr/mmmrrrr
.tml
Nick Littlestone and Manfred K Warmuth. The weighted majority algorithm. Information and computation, 108(2):212-22)) 1994.
Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras. Cycles in adversarial regularized learning. In SODA, pp. 2703-2717, 2018.
D. Monderer and L. S. Shapley. Potential games. Games and Economic Behavior, pp. 124-143, 1996.
Gerasimos Palaiopanos, Ioannis Panageas, and Georgios Piliouras. Multiplicative weights update with constant step-size in congestion games: Convergence, limit cycles and chaos. NIPS, pp- 5884, 2017.
Julien Perolat, Remi Munos, Jean-Baptiss Lespiau, Shayegan Omidshafiei, Mark Rowland, Pedro Ortega, Neil Burch, Thomas Anthony, David Balduzzi, Bart De Vylder, et al. From poincaré re- currence convergence in imperfect information games: Finding equilibrium via regularization. arXiv preprint arXiv:2002.08443 2020.
Georgios Piliouras and Jeff S. Shamma. Optimization despite chaos: Convex relaxations complex limit sets via poincaré recurrence. In SODA, pp. 861-873, 2014.
H. Poincaré. Sur le problème des trois corps et les équations de la dynamique. Acta Math, 13:1-270, 1890.
Ali
Rahimi.
NIPS
2017
test-of-time award
presentation.
Alexander Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable se- quences. In NIPS, pp. 3066-3074, 2013a.

---

Published as a conference paper at ICLR 2021
Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In COLT 2013 The 26th Anmual Conference on Learning Theory, June 12-14, 2013, Princeton University, NJ, USA, pp. 993-1019, 2013b. URL http:// .rg.//rg//eo http:c/eediinggppppppsseeeee Rakh1
mm13.
William H. Sandholm. Population Games and Evolutionary Dynamics. MIT Press, 2010.
Yuzuru Sato, Eizo Akiyama, and J. Doyne Farmer. Chaos in learning simple two-person game. PNAS, 99(7):4748 4751, 2002.
Vasilis Syrgkanis, Alckh Agarwal, Haipeng Luo, and Robert E. Schapire. Fast convergence of regularized learning in games. In Proceedings of the 28th International Conference Neural Information Processing Systems, NIPS' 15, pp. 2989-2997, 2015.
Emmanouil-Vasiine Vlatakis- Gkaragkounis, Lampros Flokas, and Georgios Piliouras. Poincaré recurrence, cycles and spurious equilibria in gradient-deseent-assenl for non-convex non-concave zero-sum games. In Advances in Neural Information Processing Systems, pp. 10450-10461, 2019.
12

---

Published as a conference paper at ICLR 2021
A FURTHER RELATED WORK
In the study of no-regret learning (e.g. Littlestone & Warmuth (1994); Freund & Schapire 1995) )
vast literature concerns general or even adversarial settings, in which the online arrivals of payoff values come with no pattern or even from an adversary. More recently, settings where the online payoff's are more well-behaved, under the term of "predictable sequence" coined by Rakhlin & Srid- haran 2013b), have been studied. These settings include game dynamics, as the online payoff's are determined by the mixed strategy choices of the players, while these choices are updated gradually and somewhat predictably. For these settings, online learning algorithms that perform particularly well, e.g. achieving regret bound below the canonical (VVT) limit, are designed and studied (Hazan & Kale (2010); CChann et al. (2012); Syrgkanis et al. (2055). ). For instance, Nesterov's 's excessive gap technique and optimistic mirror descent are found to achieve near-optimal regret Olog T') in zero- sum games (Daskalakis et al. (2015); Rakhlin & Sridharan (2013a)), and thus the empirical average of the learning sequence converges to Nash equilibrium of the game (see Freund & Schapire (199) for an explanation). OMWU (with var-ingying step-sizes), and more generally optimistic vari- ant of FTRL (Rakhlin & Sridharan (213b)), are some canonical examples of such online learning algorithms.
Recently, there is a stream of work that examines how learning algorithms behave in games or min-max optimization from synamical-systema perspective. Replicator dynamics (RD; the continuous-time analogue of MWU) and continuous-time FTRL are found to achieve optimal regret in general settings (Mertikopoulos et al. (2018)) Furthermore, RD in zero-sum games graph- ical constant-sum games admits a constant of motion and preserves volume: these two properties near-periodic (Piliouras & Shammaa (2014); Mer- tikopoulos et al.] (2018); |Boone & Piliouras (2)19); Vlatakis-Gkkaaakkonn
used to show that such dynamical systems
et a (2019); Perolat
et al. (2020)), captured rigorously under the notion of Poincaré recurrence (Poincaré (1890): Bar- reira (0066). However, when MWU, the forward Euler discretization of RD, is used in discrete- setting in zero-sum games, the near-periodicity is destroyed totally; indeed, the system will never visit the same point (or its tiny neighbourhood) twice, converge to the boundary of the strategy simplex, and fluctuate there irregularly (Bailey Piliouras (2018); Cheung (0088). In contrast, tiscrete-time) OMWU in zero-sum game is shown to converge to Nash equilibrium (Daskalakis & Panageas (2019)) yet, in the more general setting of min-max optimization, it was found that Opti- mistic Gradient Descent Ascent (OGDA) can have limit points other than (local) min-max solutions Daskalakis & Panageas 2018)).
B PROOFS IN SECTION
Proof of Lemma g First, observe that it suffices to prove that the lemma holds when T is a trivial matrix and 2 is the zero matrix. Then the lemma holds for any trivial matrices T T due to symmetry: C(A,B) (P. q) = C(A+T () q) = C(A+T' BBTT> q)..).
Due to the definition of trivial matrix, we can write T3 uj Uk. Then
CIATTLB)(D.C q) - C(..B) (p.
-E
Ask + Uj U0k- - A₁ Uij Σ Wefle Aş - 0k Σ ueze/
(Byk- - -Bj--B--- -By-Bi BBa)
LES
LES.
E [Ajk Uj + Uk] E [Bje] + E.. [[{AAt Aj - Ac)( Bj BBa] - -B(AAa] E [19xk]]
E
Veyi Σ
UETE
(Bik Bj - BB) + E [uj + vn) E [Bab]
RES2
8ES,
E [0k + uy]
[BBx
B₁
B&]
E Elu uk] EE [Bjk]
By recalling that Byjk 0.
Bj
B&]
E (3yb. we have (P. - (P..))
Proof of Observation 10 Let Pjs be the potential value of potential game when Player 1 plays strategy j and Player 2 plays strategy k. Then according to the definition the potential function, for
any J1, 22 and k,
Aj Azzk Piik Pysk-
13

---

Published as a conference paper at ICLR 2021
In particular, for any j, k, Ask Pak + A1k Pik- This implies that there exists such that Ayk = Pysk + by for any j and k.
Similarly, there exists u such that B₁x Pas + u for any and k. This implies that any two-player potential games are coordination games plus trivial matrices.
Proof of Theorem 12
We first prove that Z dominates C, then C(A,B) q) is always non-
negative. By Observation B
CAAB)(P q) (p,,-z)(P.q) + (p..c)(P.g)
C(z,-z) q C(c.-cc
Σ
2z (1)))((a))y())bvx(()
4
[Z + Zyk -,x= Zyk)² (Czk + Cyk - Czk - -Crk))
20.
In contrast, if Z does not dominate C, then there exist 3. R. Re' and 8 > 0 such that
(Ox Cgp -3e
Czik) -
Zzz Zzz Zzx - Zz(k) + 6.
For each 17 > O, we construct p and q such that zz (p) Furthermore, we let Y denote the maximum absolute value of all entries in matrices A and B. Then, for all j and k. [Ziz| S T and |C,xl S Y. Therefore.
zz. (p) = y (q) = (p) = 2
(P.. Czz z) (p. q) + (p..)) (p. Czz
Cc..c,
Σ
x;( (p)xx()))))
4
JJJ ki.k'
(Zzz + Zyn Zin- - -Zyx)² - (Cza + Cy. - Cjk- - Cyr)²)
< -8
11
+ -1111. -S22
16Y 1
2
The last inequality holds as (Cjk + Cyr Cyk Cyk)² (Zzz + Zyr Zyz 2z s
16T The value of -0 (--1) + 18 |S212 vn 16T will be negative if we pick small enough
Proof of Observation 13 Consider random process, where j, E S₁ are randomly picked accord- ing to distribution x xp). and k. k E S2 are randomly picked according to distribution y(g). Then the RHS of Observation 13 can be expressed as 1 E [[Zzx + Zyn ZiK- )².
Then we expand the squared term in the expectation. Observing the symmetries within the expansion, we immediately have
4 E [Zj + Zyr - - = -1 B 2z
Let Zj := [Zyl, and Z₁ = [xxx]x Then we have
E 1Z
Σ j.k
Jzlkk Zik Σ
ye Zix = Σ x.y [yyl, Σ yk Zyk = Σ =
w²'
&
Similarly, E Z,, = E [[ Lastly, E [2 E [Znx]² 2. Thus, the RHS of Observa-
tion 13 is simplified to
E [
E [12))
F [( T3. [2 2
14

---

Published as a conference paper at ICLR 2021
We complete the proof by noting that from the definition of C(z,-z)() (-) in Eqn. 4 C(z.-z)()) can be rewritten as
E (Zza) - 2 + [[zz]
while E|Z = 2, En 2n Σ, 2, E [2,)) and similarly [2
[.
Proof Theorem 15 By Lemma it suffices to prove ((A.) = inf (Pa)ess ((A.))P. 2 0²
This holds because the matrix Z 0-dominates C, which implies there exist j. j', k; and k' such that
(Z,z + Zyrk' z - -y+1) 2 (Cjk= Cyt
+ +
By applying Observation
13 (z..zz(p..0
2 C(c.-c) (P. + 8288, because for (p. q) s
every xy (P), yı (g) ( Mkr (q) is at least 8. By noting that C(c.o) Cc
and C(A.B) (p.))pp.g)) q) C(z.-z) (p..g)pppg) q) Cic,oy (P, q). the result follows.
Proof of Lemma
16.
A key observation is the following equality:
Ck.. q) = min F(g, h), where F(g, h) = Σ x1((p) (x(() (Kja - hx)²
(8)
g.
j.k
= E [Kga]. The equality (8) holds due to the following observations: (i) F(g, h) is smooth convex function of its variables, thus all minimum points have the same function value; (ii) if OF ög; ah, are all zero at some point (g. h), then the point is a minimal point F; (iii) C(K,-K) (P. q) is the variance of the random variable Kjk- K5 K2 (see the end of Section 2p. and thus by definition of variance,
Recall the notations K, = E yk.Kk and K₁ = E, and we let =
and OF
(P..))(P.q)) = E [K5} - Kj - K₁ - E [K - K2 Kx))²]
E [K5z K₁ K2 + +c] (since E KKz Kÿ K&] [[[Ka]] e)
Enyun (Kzx - (K3 -e) - -K+)² F(g* h+#),
=
J.k
where # = K, e and h = Kui and (iv) at (g# h)), the partial derivatives stated in (ii) are all zero.
With this observation and comparing this with the definition of rZ)). it's easy to figure out that CIK, q) S r(K)².
To see C(K.KK) (p. ④) 2 (r(K)) 5)2, we first let g" and h" to be the optimal choice of g and in C(K, k) q) ming. h the linear program we have
i Iy (p) (n(g) (K3r 9J hx)² Due the specification of
2 r(K) S max(K 93 - -hi) min K5t 23 h2).
j.k
3.k
Therefore,
(maxx K5x - 99 3,5
2 )²
(minn((k 93 -13b } 2r(K)² r(K)2
max
hi3b
3,
This immediately implies that C(K,K) 9) 2 (r(K) 8)2.
II this is not true, we can let g and r(Z) to be gi gj and hę bj. Then we can achieve r(K) max,, (Kze - 8f MEj J- ming (K₃2 1 of n2) smaller.
max; max [K - M2 4 4mmn (K5a -9, 1
which make r r(K)
15

---

Published as a conference paper at ICLR 2021
C MULTI-PLAYER GAMES
Computing volume change of learning algorithm in multi-player game is slightly more involved than the two-player case. We present a local equivalence formula of volume change between normal-form and graphical games. This provides an intuitive procedure for understanding volume changes. Proposition 20 shows that in multi-player game, the volume-changing behaviors of MWU and OMWU are again opposite to each other (which was shown for bimatrix game in Cheung & Piliouras 2020)).
Graphical Games. A graphical Kearns et al. 2000 is special type of N N-player game where the payoffs can be compactly represented. In a graphical game H, for each pair of players i, k, there is an edge-game which is bimatrix game between the two players, denoted by (H (H*,)"),, where H E R= is the payoff matrix that denotes the payoff's to Player i. Then the payoff to Player at strategy profile
(51, $2, ... .8) is the sum of payoffss to Player i in all her edge- games, i.e. us(s) = Eizs H...... ei.ey. As is standard, this payoff function is extended via expectation when the inputs are mixed strategies.
Here, we first use an observation from Cheung & Piliouras (2019) construct family of multi- player graphical games where MWU is Lyapunov chaotic in S {(P.... Px Vi E [M]]j] E
Si, (Ps)P:) 2 53. It was observed that the function (p) defined in Eqn. (5 the sum of CaH (HH (H) (Ps. P&) of all pairs of Players i < k. This observation yields Theorem
18
Theorem 18. Let G denote the family of bimatrix games which satisfy the condition either in Theorem [5] or in Theorem [7 In an N N-player graphical game where each edge-game is drawn from G all players are employing MWU with sufficiently small step-size e, then the dynamical system is Lyapunov chaotic in S.N.5 with Lyapunov exponent (NN - 11)00822/4444 E nt.
Local Equivalence of General Games and Graphical Games. Next, we present a theorem which connects the value of (p) of general game (H()), where H is graphical game.
Theorem 19. Given an N-player normal-form game G and any point p in the camulative payoff space, the value of (p) is the same as (H()), where H is a graphical game specified as follows:
for each pair of Players i, k and j E St, l E S5, the payoff to Player i in her edge-game with Player k when Player picks j and Player picks is Hik = Uik where Uik defined in Eqn. (
This theorem shows that for any game G. the value of CG(p) is the same as in a particular graphical game, where each pair of players, (i, play bimatrix game whose utility is exactly the utility of the original game G, but taking the expectation on the randomness of the other players' strategies. If the original game G is a graphical game, then in the graphical game H 3e + C-i,-k, where C-i,-k is parameter which does not depend on Players i and k.
Theorem 19 will be used in Appendix Dito show the following proposition, which shows that the changing behaviors of MWU and OMWU are opposite to each other in multi multi-player game, generalizing a prior result in Cheung & Piliouras (020).
Proposition 20. The volume integrands of MWU and OMWU in multi-player game G are respec- tively 1 1 (p) 2² + O(e²) and - (p) . 2² + O(²). Thus, volume expands locally around a cumulative payoff point P for MWU (resp. OMWU) if CG(p) is positive (resp. negative).
Multiplayer Potential Game By Observation 10 we know that the volume behavior of a potential game is equivalent to a corresponding coordination game in bimatrix game. In this section, we want to show, this holds even in the multi player setting.
Proposition 21. Suppose P the potential function of a potential game U. Let U be a game that all players will receive P(s) when players play strategies s. Then Cu(p) = Crr (p) S O.
In Appendix F. we will discuss some situations where (v((p) strictly less than 0, thus OMWU is Lyapunov chaotic therein.
D LOCAL EQUIVALENCE OF VOLUME CHANGE BETWEEN NORMAL-FORMM AND GRAPHICAL GAMES
Here, we concern the volume change of a learning algorithm in multi-player game. We first recap from Cheung & Piliouras (2020) how the volume change is computed for dynamical systems
16

---

Published as a conference paper at ICLR 2021
which are gradual (i.e. those governed by small step-size), followed by continuous-tin analogue of OMWU in games, which are crucial for analyzing the volume change of discrete-time OMWU. Then we compute the volume changes of MWU and OMWU in multi- multi-player graphical games and normal-form games respectively. Once these are done, the proofs of Proposition and Theorem 17 become apparent.
D.1 DISCRETE- TIME DYNAMICAL SYSTEMS AND VOLUME OF FLOW
We consider discrete-time dynamical systems in Rd. Such a dynamical system determined recur- sively by starting point s(O) Rd and an update rule of the form s(t + 1) G(s(t)), for some function G gd + R. Here, we focus on the special case when the update rule is gradual, i.e. is in the form of
s(t + 1) =
= s(t) c F(s(t)),
where F Rd + R2 is a smooth function and step-size e > O. When and are given, the flow of the starting point s(0) at time 6, denoted by ((1, ((0),, is simply the point s(t) generated by the above recursive update rule. Then the flow of set S C R at time t, denoted by Φ(t, S), is the set { s) E S}. Since F does not depend on time ((41 + 5) = (12, S)),
have the following equality:
By equipping Idd with the standard Lebesgue measure, the volume of measurable set S, denoted by vS)( is simply its measure. Given bounded and measurable set S C IRd, if the discrete flow in one time step maps S S' = S) injectively, then by integration by substitution for multi- variables,
[ det (I e. J(s) dV,
vol(5")
Jees
where I is the identity matrix, and J(s) is the Jacobian matrix defined below:
a Fi (s)
Fi(s) F2(s)
(s)
88a
8g Dea
F2
3'
F2
((s
De2
(10)
0 Fa(s)
0 F((s)
a (s
882
Clearly, analyzing the determinant in the integrand in Eqn. 9 is crucial in volume analysis; call it the volume integrand. When the determinant is expanded using the Leibniz formula, it becomes a polynomial of e, in the form + C(s)- eh + +(eh+1) for some integer h 2 1. Thus, when the step-size e is sufficiently small, the sign of C(s) dictates whether the volume expands or contracts.
D.2 CONTINUOUS-TIME ANALOGUE OF OMWU
OMWU does not fall into the category of dynamical systems defined above, since its update rule in the form of s(t 1) G(s(t), s(t 1)). Fortunately, Cheung and Piliouras Cheung & Piliouras (2020) showed that OMWU can be well-approximated by the online Fuler discretization of a system of ordinary differential equations (ODE), and thus can well-approximated by dynamical system.
The ODE system is given below. is a dual (cumulative payoff) vector variable, u R -> RRd the function such that u(t) gives the instantaneous payoff vector at time We assume that is twice differentiable with bounded second-derivatio and ú denotes the time-derivative of u.
p = u cuteúú
(11)
Online Euler discretization (OED) of Eqn. (Il) refers to the following lime-discretizatio of the ODE system. In applications, i might not be explicitly given, and the sequence u00), u(1), u2)) are available online (i.e., at time we only have access u(r) for T = 0, 1.... t). As the dis- cretization step is 6, approximate úit) by (u(t) u(t 1))/c. By using this approximation, OED of Eqn. [1] yields
ptt + 1) = p()) + e. u(()) + e. u(t) u(t - 1) = pt)) + e. (2 u(t) - u(t - 1)),
17

---

Published as a conference paper at ICLR 2021
which is exactly the OMWU update rule in general context.
When compared the OED with the standard Euler discretization
p( + 1)
p(() + e (u(()) + e .()),,))
OED incurs local error that appears due to the approximation of útt). The local bounded by (E)). Cheung and Piliouras Cheung & Piliouras (2020) showed that eventually the determinant of the volume integrand is of the form + C(s) - (E"), the local error does affect the first and second highest-orde order terms, and hence can be ignored henceforth.
be
D.3 MWU IN GRAPHICAL. GAMES
Let H be graphical game of N players, where between every pair of Players and k. the payoff bimatrices are (H (H In cumulative payoff space, let p - (P1, ... PPx) denote cu- mulative payoff profile, and let x (x1, xx) denote the corresponding mixed strategy profile, where x; is a function of p,. We will write x, and x, interchangeably. The expected payoff to strategy j of Player is
Usy(p) = Σ H (px))
KEIN]
which will be used to compute the Jacobian matrices MWU and OMWU.
For MWU, the Jacobian matrix J is squared matrix with each and each column indexed by (i,j), where i is a Player and E Sz. The precise values of its entries are given below:
Duis
Vj,.2 E Si, eJ6.010 6
(12)
Öpija
and
Juij Pke
Vi + k. E le Sk: (J(.).
(Hz)
[H xxl,).
(13)
Then by expansion using Leibniz formula, the determinant of (I + e e.J)
1 - Σ Σ
(e)) + O(E3)
NE JES;
KS1 FESa
=
Tie (H H x;le) (Hz) H xxl,) + O(2))
(14)
KEIN
Ki LE9t
JES,
By noting the similarity of the double summation to ((A.B)()) in Eqn. we can immediately rewrite the above expression
1 1
1
2.
Σ
(PoT. + O(e2).
(15)
D.4 OMWU IN GRAPHICAL GAMES
For OMWU, as we pointed out already, we will first consider its continuous analogue first. Thus, need to compute ú in the aattinouus-time setting. By chain rule, we have
a (x())
dpue dt.
dpke
(p) Σ
Σ Tkk (H KE[N] kdi EESt
H
xxl;)
Opet
dt.
KE(N]
liskts EESk
and hence
dpis
dpke
Σ
H xx]; t Σ
Dkt (H H xxli)
dt
kE|M
A
kdd tES.
18

---

Published as a conference paper at ICLR 2021
Note that this is recurrence formulae for dp By iterating have
dpsa di
Σ H N
xxli + c. Σ
(H)) [ xxl1)
Σ
hr x.le
+ O
The
K
N rysk
kii
kzi
FESt
Hence, its standard Euler discretization, which approximates the OED with local error O(e"), can be written below (where we ignore the (Ee") error terms):
Piy(1+1) = PPs((() +e Σ H xxls +
Σ Ikk (Hz)
[ xxli)-
Σ
H x,le
KEIM
KE
NE rg
kşi
FES
With this, we are ready compute the Jacobian matrix J for OMWU. For all j1.32 E S
Ja = 2
The
(H [ xxlr.) Tija (H [H x.]e)
(16)
kE(N]
k
8E8%
and for all i i j. S E Sk.
ed(i)) eoue (H))
[ + 0
(17)
Then by expansion using Leibniz formula, the determinant of J) is
1
Σ
Σ NENN
Σ
+ 0(6)).
KEIN JES,
JES.
LES
T2
By direct expansions on Ti and Tr, it easy to see that Ti = 2I2 (after ignoring OEe3) terms). On the other hand, the coefficient of e" in T2 is exactly the same the double summation Eqn. (4) thus it equals to EikIIgkAN ((H))(HH)))(( equals to
P&). Overall, we show that the determinant
2
Σ
O(H (H9 O(e))
(18)
KRISKKKEN
Observation 22. The coefficient of è in Eqn. 18) is the exact negation of the coefficient of in Eqn. 75p.
D.5 COMPLETING THE LOCAL EQUIVALENCE PROOF
In a multiplayer normal-form game G, recall that notation Eqn. formulae:
We point out the following
OU ii
0
if E (ir, f2, .. ;.g);
Öp.j
aU
01
j1Ja--b Öp
Zij (1 Uhii f1f2--J0)
if & fa. .ig).
MWU. Here, MWU update rule is Pty(t + (ty(t) When computing the Jacobian matrix for this update rule using the formulae above, and comparing it with the Jacobian matrix computed in Eqn. 12) and Eqn. (13), it immediate that they are the same by setting Hit Tikk This derives Eqn. () and completes the proof of Theorem 19
j
For the formality why we iterations when is sufficiently small, see Cheung & Piliouras 2020
19

---

Published as a conference paper at ICLR 2021
OMWU. As before, we use the continuous analogue and compute ú. By the chain rule and the above formulae, we have
JU
dpRt dt
dpue
dss(p) (p) =
Σ
The
(Uje
Uÿ)
Opee
dt
[[[N] kepii RESk
KE(N] kgi RES
and hence
dpu
dpkt
Uj te. Σ The (Ut) -U:)
dt
KEIN]
kyi EESk
Iterating the above recurrence yields
dp
U}
+ 6. Σ Tki (U)² U3) U + 0(2).
dt
kE[N]
kifii 8ES
Its standard Euler discretization is
Pi 1) = =P:((t) +.. + 2
Σ Ikt (U)) - UJ) Up.
kEIN]
kylh
tES
Now compute the Jacobian matrix for this standard Euler discretization. For f1 j2 S..
e² Σ Ikk
(Uflee U2,)
Fija (U U
KE[N light tESa
and for all i + k. St, SE
cJ(L.).(k.)) CINI (U - UJ) O
By comparing this computed Jacobian matrix with the Jacobian matrix computed in Eqn. [6 and
Eqn. 17 it is immediate to see that their determinants are the same (after ignoring all O terms)
by setting H Usk With the result just derived, together with Observation 22 and Theo- Proposition follows.
rem 19
MULTI-PLAYER POTENTIAL GAME
Proof of Proposition 27
We know that the potential game satisfies the following condition:
P(s,, - P(s 8_1) = u, (s, s-4) Uy (sy, s-:).
Therefore, uz (((8888))) P(si, 8-:) of Note that (s does not depend on 8;, the strategy of player
By Theorem 19 let H(U) be the induced graphical game of U and H(UP) be the induced graphical game of P. Then,
Cu(p) = (H(U)(P)
(Theorem
Σ Canoyy
(By equation 15
i.k
Σ (HLUU)),, i,k
(see explanation below)
(H(UP)(p)
(By equation 15
(p).
(Theorem T9
20

---

Published as a conference paper at ICLR 2021
The third equality holds the difference between U() and H(UP) is trivial matrix:
H 3/ = U (U*) EE (i.a) (=*(s H(P)) sk )) + +E
E (1.0) [v*(s
where 13 E (i,k) (t,,,)
(x-)) doesn't It depend on j. the strategy of player i, and only depends on 1, the strategy of player k. The same argument applies for (H) and (H(U?){:)T.
O. observe that the induced graphical game of U between player i and k (H(UP) (H)))) is also bimatrix coordination game, which implies C(H (H(P))))))) S O. As Cu(p) Ei, CCLCUP)), (P:, p&), the result fol- lows.
To see Cu(p)
Next, we identify several cases such that Cu(p) is strictly negative in the region
S [x Zij 67.
The conditions we pose are on the corresponding potential function P. Note that H the induced lige-game between player and k, is also coordination game, i.e. H(UP)sk (H(U)) Case 1:
min
Σ
Σ
(Pik
sk 9j
8
x.g.
ISicKN
JES,
where Pik = Eg (1.)) ((ss = j. 8k = l, (i.))) With this condition, we can prove that
Cu(p) -82 for any S One key observation for this is true is that
Cu(p) = Σ
Pk)
i
(pj - 93th -1(0) =
Tis(P:)ake(Pp)
5.8
as H(UP))k Upik
pit
Case 2:
If is graphical game, then if there exists a pair of player é and ig. such that the game between i and ig is non-trivial game, then Ou will be strictly negative in S
Case 3:
Consider the payoff matrix of UP, the coordination game, between players i and is given strategy profile of the other players. There are total I .82 n, such matrices, one for each strategy profile of the other players, and each matrix is of dimension ni, 72z. We call these matrices the projected matrices for players i,, ig.
Let M denote the matrix space of nı T42 On the other hand, trivial matrices form subspace of dimension n,, + n4i 1 Let's call this the trivial space, denoted by T.
We consider the direct decomposition .M = T @ V. Let a set bases of M be B1, B2, B..... BrG, Rug" where the first n,, + n bases form a basis of T, and the remaining bases form basis of V. Without loss of generality, we assume that all bases are of L2 norm 15
"E (c.A) (s..) is the expectation over all the strategics taken by the players other than and and (s..) does not depend the strategy taken by player i.
"Recall that a trivial matrix T can be represented as {uy + eu J.k. Consider the natural linear map such that L(ui, u2, May, Vi, U2, -.- (nng) maps to the trivial matrix T. Note that the kernel of L is of dimension since if L(u1, u2, -.. Un. U1, .-, vvn.)) ) the zero matrix, then we must have 84 = uu; Thus, the
for all j, k. and hence the kernel of must be the span the vector 11,1,-..,, -.,
the 14 part
the part
dimension all trivial matrices is dimension of domain L,, which n4, + May minus the dimension of the kernel of L.
15 Here, the norm is defined the standard Frohenius matrix inner product.
21

---

Published as a conference paper at ICLR 2021
Given the above-mentioned bases of M, each of the projected matrices be written into a unique linear combination of these bases. Now, suppose there a base Bg for 12 n4, +2 (i.e. this base is in the set of bases for V), such that all projected matrices have non-positive (or non-negative) coefficients of this base, and at least one of these projected matrices (which we call special projected matrix) has strictly negative (or strictly positive) coefficient of the base. Then we claim that C(H(U"Y' ya "",,,,",,," (H((U)) (C))))s Piz) will be strictly negative in S This is because H(U is convex combination of all those projected matrices, and by our assumption above, when H(UP)'s expressed as the linear combinations of the bases of M, the coefficient of B3 is strictly negative (or strictly positive), thus H(UP) cannot be a trivial matrix.
Suppose further that there exists A > 0 such that a special projected matrix has negative (or positive) coefficient for B, which is smaller (or bigger) than -0 (or 0), then we are guar- anteed that ( is bounded away from T for distance of 05 I6 and hence as the calculations below show, C(H(UPYY "arr))rr,,,,(,( (H(UP))))))) (P1, P(2) S 02 -2, If there
exists a pair of player i and i2 such that this condition holds, then Cu S - 002
CaHuPyyne (H Piz)
min
Σ
Thy (Pr, )riz. (Piz) (Piz) (H(UP)ii - 9j - -2a)
g.h
S min 8²
(H(UP) -9 hx)
g.h
8 Σ [(H(UP)h 99 -h2)²
< - (08
where {0] + hihys jk is projection of H(UP))áí on the trivial space. The first inequality follows as p E 5 the second equality holds as the projection minimizing the distance to the trivial space, and the final inequality comes from the distance from H (U) to the trivial space.
For all these cases, we can have OMWU is Cu to be strictly negative in domain S*, which implies OMWU is Lyapunov chaotic in S
16To see why, when the coefficient for B; is bounded away from zero, we are guaranteed that the special projected matrix has a strictly positive distance from T. and this distance is at least 8. Then H'*") which is convex combination of all projected matrices where each projected matrix (in particular, the special projected matrix) has weight at least N22 has strietly positive distance from T too, which is at least a8*-2
22


Reviews:
[{"review_id": "oYzQEkzGzpb", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThis 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.\n\nStrengths:\n* very nice example before section 3.2\n* thm 7 is very interesting\n* (8) is also very clever\n\nWeaknesses (in rough order of appearance):\n* constantly referring to \"AI/ML\" - just pick one\n* \"measurement errors in real economies\" - why \"economies\" all of a sudden?\n* \"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\n* 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.\n* I do not follow footnote 1\n* repeated references to \"dual space\" - what is this? It does not appear to be defined\n* (1) is confusing. Some prose description would be good.\n* The definitions following \"convex regularizer function\" are unclear.\n* I found (4) onward (through the end of pg. 5) very confusing and didn't really follow\n* Notation of \"u_i\" in Def. 3 is not introduced before\n* In 3.2.2 I don't understand why the \"iff\" property above doesn't apply\n* 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.\n* [throughout] there are numerous syntax/semantic errors that should be corrected before publication. I suggest employing a copy editor.\n* [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.\n* [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.\n* [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\n\nOverall:\nWhile 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.", "extra_scores": {}, "extra_text": {}}, {"review_id": "njblkGaW5k4", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "As far as I understand, the authors study Lyapunov chaos that occur in learning in non-zero-sum games.\n\n\nMain issues:\n1.\tThe current structure of the paper is very unusual what makes the presentation of the key results very unclear. Just for instance:\n-\tGiven overall 8 pages, the presentation of claimed results starts from 6th page (before that we have Introduction and Preliminaries)\n-\tNo conclusion: the main text chops on Theorem 11 without any discussion on this theorem after. \n2.\tContinuing 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.\n3.\tIt 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.\n\nI 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.\n\n\nMinor issues:\n-\tAbstract is too long for this ICLR format.\n-\tI’m not sure that the format of ICLR allows have Appendix in the main text instead of using supplementary materials.\n=====\n\n\nI raise up my score after the authors' changes ", "extra_scores": {}, "extra_text": {}}, {"review_id": "aAEaAQeTwXb", "reviewer": "AnonReviewer2", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis 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.\n\nDetailed Comments:\n\nThis 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. \n\n1. 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.\n\n2. 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?", "extra_scores": {}, "extra_text": {}}, {"review_id": "LXJtJEgsJj8", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nOverall, 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.\n\nDefinition of Chaos and Interpretation of Results in Primal Space:\nWouldn'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.\n\nThe 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).\n\nWhy 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.\n\n\nQuality:\nThe 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).\n\nClarity:\nThe 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).\n\nOriginality:\nThis 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.\n\nSignificance:\nProving 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.\n\nMinor:\n\nI 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.\n- A RECURRENT NEURAL NETWORK WITHOUT CHAOS (ICLR 2017).\n- Exponential expressivity in deep neural networks through transient chaos (NIPS 2016).\n- 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.\n\n\"We answer the above question affirmatively\". Instead of \"How does...\", say \"Does the...\" so that the question admits a yes/no response.\n\n\"–The second technique\" - remove the dash.\n\n\"of a multi-player potential games\" - game singular.\n\n\"mixed strategy space of dimension n\" - the simplex defined with n-probabilities is (n-1)-dimensional.\n\nExplain $\\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.\n\nMaybe say $u=v=[2, 0, 2]$ to construct the trivial matrix in the Simple Example.\n\nUse logical and \"$\\land$\" maybe instead of $\\texttt{and}$ in Section 3.2.\n\nDef 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.\n\n\"it is easy to see that there is quite many games\" - are quite many\n\n\"zero-sum part $\\theta$-dominate\" - dominates\n\nCan you provide a constructive way to discover the trivial matrix defined by $g_j$ and $h_k$ in Eqn 8? Or in general?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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)