The Evolution of Uncertainty of Learning in Games
Authors: Yun Kuen Cheung
Georgios Piliouras
Yixin Tao
Venue: ICLR 2022 Poster (2022)
Keywords: learning in games
differential entropy

Abstract: Learning in games has become an object of intense interest for ML due to its connections to numerous AI architectures. We study standard online learning in games but from a non-standard perspective. Instead of studying the behavior of a single initial condition and whether it converges to equilibrium or not, we study the behavior of a probability distribution/measure over a set of initial conditions. This initial uncertainty is well-motivated both from a standard game-theoretic perspective (e.g. a modeler's uncertainty about the agents' initial beliefs) as well as from a ML one (e.g. noisy measurements, system initialization from a dataset distribution). Despite this, little is formally known about whether and under what conditions uncertainty is amplified or reduced in these systems. We use the popular measure of differential entropy to quantify the evolution of uncertainty. We find that such analysis shares an intimate relationship with volume analysis, a technique which was recently used to demonstrate the occurrence of Lyapunov chaos when using Multiplicative Weights Update (MWU) or Follow-the-Regularized-Leader (FTRL) algorithms in zero-sum games. This allows us to show that the differential entropy of these learning-in-game systems increases linearly with time, formalizing their increased unpredictability over time. We showcase the power of the framework by applying it in the study of multiple related systems, including different standard online optimization algorithms in numerous games and dynamics of evolutionary game theory.

Published as a conference paper at ICLR 2022
THE EVOLUTION OF UNCERTAINTY OF LEARNING IN GAMES
Yun Kuen Cheung"
Georgios Piliouras" Singapore University of Technology and Design
Yixin Tao" London School of Economics
Royal Holloway University of London
ABSTRACT
Learning saaming-in-gamee in-games has become an object of intense interest for ML due to its connections numerous AI architectures. We study standard online learning in games but from a non-standard perspective. Instead of studying the behavior of a single initial condition and whether it converges equilibrium not, we study the behavior of a probability distributiin//measure over set of initial conditions. This initial uncertainty well motivated both from standard game-theoretic perspec- tive (e.g. a modeler's s uncertainty about the agents' initial belief',, random external signals) as well as from a ML one (e.g. noisy measurements, system initialization from a dataset distribution). Despite this, little is formally known about whether and under what conditions uncertainty amplified or reduced in these systems. We use the popular measure of differential entropy to quantify the evolution of uncertainty. We find that such analysis shares an intimate relationship with vol- ume analysis, a technique which was recently used to demonstrate the occurrence of Lyapunov chaos when using Multiplicative Weights Update (MWU) or Follow- the- Rregularized-Leade (FTRL) algorithms in zero-sum games. This allows us show that the differential entropy these learning-ing -in gane systems increases lin- early with time, formalizing their increased unpredictability over time. We show- case the power of the framework by applying it in the study of multiple related systems, including different standard online optimization algorithms in numerous games and dynamics of evolutionary game theory.
INTRODUCTION
A primary goal of ML research is to understand the behavior of learning algorithms in various settings. One standard approach to determine from each initial condition whether a learning algo- rithm converges a local optimum stable state. Yet, in the context of online learning in games, and more generally in distributed multi-agent learning, is natural to consider the evolution a probability distribution over initial conditions instead. In these settings, each agent forms initial belief on her own, and she typically does not reveal her belief to other agents or external model- ers/analysts. For modeler to understand the possible behaviors of the system while being uncertain of the agents' beliefs, one natural approach is to infer how the initialization distributes by using data of observations from the past. The modeler then uses this inference to predict the likelihoods of different outcomes in the future, either by simulation or by analysis. Also, random initialization can happen due random external signals, e.g. weather, as well as noisy measurements. For readers who wish to learn more mathematical aspects and intuition behind of such models, see Appendix A
such cases, it is critical to understand whether the initial probability distribution evolves to- ward stability, or if its uncertainty gets amplified. Such analysis provides insight into the learning system's 's robustness against random initialization and environmental perturbations. If a system coor- dinator desires stability but the analysis shows the uncertainty gets amplified, she ought to coordinate with the agents to make changes, e.g. encourage them to use other online learning algorithms.
To analyze how uncertainty evolves, we need a measure of A natural choice entropy. In his seminal work in 1948, Claude Shannon formulated an axiomatic foundation of informa- tion theory and introduced the seminal definition of Shannon entropy (SE); given a discrete ran- dom variable with possible outcomes .1...., Fr which occur with probability pi,..., Pn, its SE is
FF-mails: yunkuen. chsung@rhul ac. uk,
Y. Taol 601 se. ac.uk ukk

---

Published as a conference paper at ICLR 2022
E [lo((1/p))]. Entropy is the canonical measure of uncertainty: when p: for some i, the distribution is considered certain and its entropy is zero; uniform distribution is viewed as the most uncertain, and it attains the maximum possible entropy of logn. n. For continuous random variables with probability density function g. Shannon proposed an extension of SE called the differential entropy (DE), defined as E [l support set of the random variable. We will analyze how DE evolves in multi-agent learning.
/g(x))) = fx g(a) log ((x)) dx, where X' is the
Our Contributions. In our model, a learning- in-game system starts with a distribution over a set of initial conditions in the cumulative payoff space, a coordinate system which is inherent in the implementations of many online learning algorithms. The initial distribution evolves over time depending on the combination of agents' learning algorithms and the underlying game. We focus on two popular learning algorithms, Multiplicative Weights Update (MWU) and its optimistic variant (OMWU) The game settings include the standard two-player matrix games, and one-population games which are fundamental in biological evolution models. We show that the DE of broad range of learning- in- in-game systems increases linearly with time (up to a certain limit), formalizing their increased unpredictability. Such systems include MWU in zero-sum games, OMWU in coordination games, and MWU in certain one-population games which reward more to intra-species play than to inter-species play. Our results apply to any initial distribution of absolutely continuous random vectors with finite differential entropy.
At this point one may naturally wonder: What level of uncertainty does a linear increase of DE indicate? What are its implications? To answer these questions, it is best to compare ourselves against other simple benchmarks. Consider the following simple learning system: in each round, the payoffs for each action are generated from uniform distribution over [-1, In the cumula- tive payoff space, the distribution at time T converges to a multivariate Gaussian distribution with variance (T), and hence the entropy grows at rate of Ollo T), much slower than linear growth. In Section 4.1 we present an implication of linear DE growth in learning-in-game systems. Briefly speaking, the DE cannot increase substantially for an indefinite amount of time in such systems. Thus, the distribution after a sufficiently long time must concentrate in region that yields slower DE growth or decline; such region does not cover any point in the cumulative payoff space that cor- responds to an interior Nash equilibrium. We will refer to this phenomenon by "the grand escape". See Theorem for the formal description of the grand escape phenomenon; an additional assump- tion, namely the initial distribution has bounded support, is needed to establish this theorem. For the implications in information theory, we refer readers to Chapter 8 ofver & Thomas (2006).
The central tool in analyzing the changes of DE is the Jacobian matrix of our multi-agent dy- namical system. This is also the key notion in volume analysis, which was used in recent series of papers demonstrate Lyapunov chaos in learning-in-gante systems. (Cheung & Piliouras (001 2 Cheung & Tao (2020)) By showing that the determinant of the Jacobian matrix is strictly above I in a large domain of the cumulative payoff space, they showed that the volume (Lebesgue measure) of a small set of initial conditions will blow up exponentially to become set of large diameter, thus demonstrating a general Lyapunov chaos phenomenon in learning-in-game the same property of Jacobian matrix guarantees linear increase of DE. Additionally, we present the first Jacobian analysis of online learning in one- one-population games. Finally, our DE analysis is robust against small perturbations. Consequently, our results extend to the setting where the game in each round can be different, as long as the payoffs are perturbations of each other. Such settings capture many games in the real world, where we know the "reference values" of the payoffs, but the accurate payoffs in each round differ slightly due to unknown external (random or adversarial) factors.
Indeed,
Our model and analysis can be viewed as an a strengthening of volume analysis. Volume analysis focuses on whether it is possible to reach state or not, whereas in our model we are also concerned with how probable/likely with tiny chance. When studying chaos and volume, such states matter, but less when studying uncertainty as their contributions to entropy will be low. To illuminate this, we simulate MWU (with step-size 0.01) in Matching Pennies game, and present few plots in Figure 2 The top-left plot shows the initial set, which is small square around the unique Nash equilibrium. The top-right plot
is to reach a state. More explicitly, a state can be reached but only
As we shall point out in Section 3 all our results about MWU also extend easily to the broad family of Saallo-thh-Regglaiie Lader (FTRL. algorithms, which is generalization of MWU. For clarity of our presentation, we choose to focus MWU in this paper.
2

---

Published as a conference paper at ICLR 2022
1.50
1.8
015
675
-315
-1.0
611
025
965
-31
-35
415
C23
-32
425
-355
090
Figure 1: "Possible" vs. "Probable": the heat-map, red (warm) and blue (cool) colors represent high and low densities respectively.
shows the range of possibility after 40000 steps In model, assume the initial distribution uniform over the small square, and plot the heat-map of probability densities after 40000 steps (bottom-leftt. We observe that the states in the boundary of the vortex more probable occur, while the densities around the Nash equilibrium decline. The bottom-right plot shows the densities that generate the heat-map.
Further Related Work. Learning models that explicitly study the effects random initialization have received relatively little attention in game theory where static equilibrium concepts are typically the preferred solution. Lahkar & Seymour (2013) studies online learning under random initializa- tion in population dynamics, where one population game is common payoff model. In population dynamics, there exists a large population of agents who have different initial choices of mixed strate- gies, modeled as distribution. The dynamics proceed by randomly pairing up agents in each round to play game. [Lahkar & Seymour (2014) extends this framework to other learning dynamics to describe the evolution of distribution of mixed strategies in population playing variants of Rock- Paper-Scise Scissors games establishing local convergence the interior equilibrium. Recently, further learning models inspired by Q-learning dynamics have been defined (Hu et al. 2019). Very little is formally known about the behavior of such models particularly under instability.
For zero-sum games with an interior Nash equilibrium, "the grand escape" phenomenon follows from Bailey & Piliouras (018); Cheung (018). who showed that MWU diverges away from Nash. Our results are more general, since their analysis only works with those zero-sum game dynamics, while our technique applies to many other game dynamics as well. Such instability results in zero- sum games are undesirable for ML applications such as GANs thus lot of effort has been invested in developing algorithms that achieve convergence Daskalakis al. (2017): Mertikopoulos et al. (209 Daskalakis Panageas (2018); Gidel et al. (2019); Mokhtari et al. 2020); Perolat et al. 2021. Our research direction here in some sense orthogonal. We aim characterize more detailed fashion the behavior of learning dynamics despite their instability.
The instability of MWU, FTRL and other optimization-drive dynamics in games has attracted a lot of attention in recent years. One formal technique to establish the unpredictability of MWU
TThis phenomenon first discussed in Cheung & Piliouras 2019) and called the "von Neumann vortex".
3

---

Published as a conference paper at ICLR 2022
and other dynamics is based on proving Yorke chaos, which has been established robustly in dif- ferent families of routing/potetial/Coomoo games (Palaiopanos et al. (0117): Chotibut et al. (2020); Bielawski et al. (202T); Cheung et al. (202T)). The techniques in those papers are independent from ours as they require the identification of one dimensional invariant manifolds, and Li- Yorke chaos implies the existence of periodic orbits, which is not possible in our systems. In very recent series of works, Flokass et al. (2020); Giannou et al. (2021) established that all (even partially) mixed equi- libria in all games are not asymptotically stable for any choice for FTRL dynamics both in discrete as well as in the idealized continuous-time limit. In fact, it is possible to construct simple matrix games such that the orbits of the resulting dynamies can be arbitrarily complex (Andrade al. (2021). If, inspired by ML applications, we allow for more complex differentiable games it becomes even simpler to establish strong instability results for effectively any type of training algorithms (Letcher (2020): Balduzzi et al. (2020)) The sweeping nature of these strong negative results showcases the practical interest in uncovering more information about the nature of unstable dynamics of games. Our proposed framework introduces novel, quantitative methodology for their study.
The notion of differential entropy (DE) has been used as uncertainty measure in many works across multiple disciplines. We note that while the extended definition of DE seems natural, it is not considered as the perfect generalization of SE since it misses some favorable properties, and therefore, as quoted from the popular information theory text of [over & Thomas (2006), "there is need for some care in using the concept" Nevertheless, DE remains an effective measure of uncertainty which is commonly used in physics, economics, control theory, engineering, biology, medical research and beyond. For a general discussion, we refer readers to the text of Cover & Thomas (2006). For background information of evolutionary game theory, we recommend Hofbauer & Sigmund 1998): Sandholm (2010); Eega-Redondo (1996).
2 MODEL
We use bold small letters to denote vectors, and bold capital letters denote matrices. Let A denote the probability simplex of dimension d: A d == {x E Rdd for each j, Ø3 2 0, and E 2j = 1}.
MWU and OMWU. When an agent uses MWU, she wants to choose among d 2 2 pure actions based the past cumulative payoffs to these actions. The process starts at discrete time / = 0. where the agent chooses an initial cumulative payoff vector pd E Rd. At any time 2 1, upon receiving the payoffs to the each of the d actions at time t 1, which are denoted by vector r11 Rd. the agent updates the cumulative payoff vector by the rule
(1) where > is the step-size of the update. At any time 1 2 O. the agent chooses randomly among the pure actions depending on the value of p'. Precisely, the agent chooses a mixed strategy x² E A which is function of p¹ For MWU, x' is determined by the rule
Vj = 1.2.......
pj + pj -
Vj 1.2.....da d, InJ + exple3)/ Σ cspplts)
(2)
For OMWU, we start with pd = =p', and for 2 2.
Vjj = 1, .,.,....d d, p} + pj 1-1 + - -199 and x' is determined by the same rule 2
In general, the payoff vectors r can be arbitrary, and they may may not depend on the mixed strategy x' However, in the context of learning-in- mamiing-i--game the underlying game generates the payoff vectors that depend on the mixed strategies of the agents involved. We discuss two popular game models relevant to our work, namely two-player matrix games and one-population games.
3 "woo issues with DE are: (1) DE can be negative and indeed it has no finite lower bound, while SE is always positive; (2) DE depends on the choice of coordinate system. The positivity of SE is favorable in information theory where they want to measure information contents of different communications. But for the purpose of measuring and comparing uncertainty, positivity does not seem relevant. (2) is not an issue for us, since will always stick a fixed coordinate system which is natural in learning-in-games
'DE captures uncertainty well, e.g. for all popular distributions (Gaussian, uniform, exponential, Rayleigh etc). their DE increases with their variances. Also, among all distributions over bounded support set, the uniform distribution over the support set attains maximum DE.
4

---

Published as a conference paper at ICLR 2022
Two-Player Matrix Games. In two-player matrix game, Player has actions and Player has m actions. The game is specified by two matrices A, [-1, When Player chooses action j and Player 2 chooses action k, Aje, Bjkk the payoffs to Players 1 and respectively. When the players choose mixed strategies, the payoffs are extended via expectation. Denote the mixed strategies of Players 1 and 2 by x E A and y E A.. The payoff to action of Player is [Ayl,, while the payoff to action A of Player 2 is B xJa-- When both players use MWU or OMWU to play this game repeatedly, we have the following discrete-time dynamical system, where p' q' denote the cumulative payoff vectors at time of Players and 2 respectively. The two players choose initial cumulative payoff vectors .º.
vt V2 1, p' + ----- cc. Ay'AA"";; q' + d 4'=
(4)
Note that x²-1 a function of p' as specified in 2 similarly, y" is a function of q' Thus, can also view (4) as iterated function that maps from (p' ,q' to q²).
In the above setting, the game (A, B) is the same at all times t. It is also interesting to consider scenarios where the game varies in each round. Our results extend to settings where there a "reference game" (A, B). but at each round the actual game being played is perturbation of the reference game. Precisely, the game at time t (A', B¹) = (A, B) + (A) A B)). where A A matrices with maximum absolute entry most 3, for some small 3 > 0.
One- Ane-Population Games. One-population games is a fundamental model in mathematical biology, which is widely used to explain the evolution of population of different of species over time. An nne-population game is similar to a two-player game, but now Player 1 is playing against herself; there is only one player (or in biology term, population) in this game, while mixed strategy x' represents the fraction of different species among the population. An one-population game is specified by matrix A Raxx When the mixed strategy of the player is A", the payoff to action j is [Ax],. The resultant discrete-time dynamical system with MWU is
Vt 11,, p + p 1- -- Ax
(5)
where x' 1- is function of p p' as in
Random Initial Cumulative Payoff Vectors. In Section [| we explained why we consider uncer- lainty of the initial cumulative payoff vectors. This can be captured by model where these vectors g follow distribution. We use two-player game for discussion below; for one- one- one-oppulation game is similar. Assume that the initial vectors (p (p".q") follow a joint probability distribution in the domain RR RT As the initial vectors are random and they are updated according to the discrete-time dynamical system (4. for any / 2 0, (p', q') also follows distribution, which is the main ob- ject we analyze in work. We are interested knowing certain statisties of uncertainty of this distribution, say differential entropy, which is the subject of the next section.
3 DIFFERENTIAL ENTROPY
In this section, we discuss how changes of differential entropy (DE) can be analyzed in general, and provide some intuition of the relationship between DE and volume. To proceed, we need a crucial notion called the Jacobian matrix. Let f Rdd Rdd be a smooth function. Its Jacobian matrix is
8/1
0f
0/1
821
822
82g
J,
8fa
U2
Dzz
Uza
We also need multivariate integration by substitution; see Appendix B for discussion of it.
Let X be an absolutely continuous random variable in Rdd Let g be its probability density func- tion, whose support set is X. The DE of X is h(X) := - fxx (xx) log g(x) dx, which we assume to be finite. For any function f : gd + Rd, f(X) is another random variable; we denote its prob- ability density function by g. and its support set by y. If f is diffeomorphism, using integration
5

---

Published as a conference paper at ICLR 2022
by substitution, we have ((v) (v)- |det (-) Using integration by substitution again, the DE of ((X) can be computed as follows:
h(f(X)) - -f, ((v) log (
/ g(f 9(f (v)) d (
log (g(f det J x dy
Jx
J log (9(x) y (f(x)) - |det Jdet , dz. [o(l) g(x)
(6)
By the Inverse Function Theorem, y- det (x) = 1. Thus,
h(((x)) - h(X) = / g(ø) log |det J (a)) dæ
when the integral on the RHS is finite. This is true if |det (x)) is differentiable and bounded function of x, which holds in all learning-in-gan
systems we study. Thus, the Jacobian's 's deter- 0 such that |det , (2)] 2
minant directly affects the change of DE. If there exists
for all x E X. then hx)( - h(X)= 2 log(1 + a) > O. In order to use 7 to analyze the changes of DE of learning in two-player matrix games, we view the dynamical system (4) function that maps from (p'-1,"' qq'=1) to (p', q') in each round / 2 1. If the change of DE per round is at least log(1 a) > 0, then the DE increases linearly with time.
The Relationship Between DE and Volume. Before discussing the relationship, we first recap what volume. Let X' C Rdd be a measurable set with positive Lehesgue measure (which some- times called the volume of the set), and let f: Rd -> Rd be a diffeomorphism. The volume of f(Y) is fx J [x)) dx. When |det / 2 1 ++ a for all x E X, the volume increases by a factor of least (1 a.) If this occurs in a dynamical system every round, the volume of the initial set grows exponentially with time, and hence also its diameter, establishing that Lyapunov chaos occurs.
The occurrence of the Jacobian in both the formulae for computing volume and the change of DE in (7) is not coincidence, but with simple intuition behind. The Jacobian yields linear approximation of f locally: for any x E IRd and any small perturbation vector Ax E IRd, f(x + Ar) f(x) J (xx) Ar. We consider a tiny hypercube with volume around ær, and its image under the function f. By the linear approximation, the image is approximately parallclotope (the high-dimensional analogue of parallelogram), whose volume is known to be |det J 1. v. By partitioning X' into infinitesimal tiny hypercubes and summing up. this is intuitively how the integral formula for computing volume is obtained. Next, suppose the probability density at g(x). The probability of the tiny hypercube is approximately g(x) v. After the transformation f. this amount of probability is spread approximately uniformly in the parallelotope, thus the new density at (xx) is g(x)// J (x:)]. If the volume increases locally at i.e. |del yxx)] >> 1, it intuitively means the uncertainty level increases locally. This intuition is captured by DE: the contribution to DE by the tiny hypercube is -9(x)- v log(g(x)) t), while the contribution to DE by the parallelotope is -g(x) -v log g(z).e [( Thus, the local change of DE is g(x) v log det (.)) which has the same sign as (IdetJ (x)] 1). To summarize, local volume increase is equivalent local DE increase.
This equivalence allows us to spot that for those learning systems in two-player matrix games studied in the series of volume analysis papers of Cheung & Piliouras (019 2020); Cheung & Tao 2020), their DE with our model increases linearly in a large domain of the cumulative payoff space. We present this result formally Section 4.1, and present an interesting consequence of the DE growth. Partly motivated by Lahkar & Seymour (2013), we also transfer the techniques to analyzing one-population games in Section 4.2] and we present two sufficient conditions on these games that leads to linear DE growth with MWU.
As first spotted by Cheung & Piliouras (2019), these results not only cover MWU and OMWU, but also the broad family of FTRL algorithms, since the properties of the Jacobian for FTRL is very similar to that of MWU. (This is not surprising since FTRL is a generalization of MWU.)
4 APPLICATIONS
In this section, we consider two applications: MWU in two-player zero-sum games and one- population games. In Appendix C also consider OMWU dynamics in two-player coordination

---

Published as a conference paper at ICLR 2022
games and poppulatii games, and the settings where the game in each round is perturbed. A two-player game (A, B) is zero-sum A = =B. We focus on non- non-trivial games, defined below.
Definition 4.1 (Cheung & Piliouras 2019)) A zero-sum game (A,-A) A) is trivial if there exists real numbers a1, 02.-.. On and b1, "2. bm such that Azk- aj + by- The same definition applies for one pne-populttion game A.
Cheung & Piliouras pointed out that a trivial game is not interesting as the players have dominant strategies. They provided measure of distance of zero-sum game (A, -A) from triviality by
c(A) On bi ..m [max( (Axx (jj ba) min( Asa aj bw.
min
4.1
MWU IN TWO-PLAYER ZERO- SUM GAME
Recall from that in zero-sum game (A, A), MWU dynamic in the cumulative payoff space is p p'-l=p' c.. Ay(q') and q = q" c (-A) "x(p')
where x(p') and y(q') are the mixed strategies of two players at time t: xp(p') exp(p))/ E, exp(p))) and (='q')) = exp(g))/ Ex exp(gf)). Two different regions are consid- ered: the interior region S == {(P, q) x(p) 2 5 and y(a) 2 6), and the boundary region S2, which is the complement to Sr. Note that if the game possesses an interior Nash equilibrium, then the equilibrium lies in S₁ for any sufficiently small 5.
Let g6 (p. q) denote the probability density of (p. q) at round t. Recall from 7 that the change of entropy f g' g',p q) log |det J (P. q) d(p. q). If g' (p. q) is fully supported by S1, then by using the Jacobian analysis of Cheung & Piliouras (019), who showed that the determinant of the Jacobian matrix is strictly larger than S1, we show the differential entropy increases linearly.
Theorem 4.2 For any non-trivial two-plat two-player zero-sum game AA, with MWU dynamics of 5% A))² /8), if ig (p, q) > 0 only for (p, q) E St, then the differ-
step-size e S
= in round t.
ential entropy will increase by at least (4)5e(AA)..
Proof: For MWU dynamics, f(p. = (p cy(g), x(p)) by 2 Cheung & Piliouras
{ 2019) showed that if S min(1/(32n2m ('((A) //), then det J (
1+ d-c(A)" 2
8
for any (p.q) E S1, where c(A) is the measure of the distance of a sero-sum game AA A)
for any r > 1, J (p. q) log J q)l d(p, Z from triviality ( As log(1 + r) Z I=
Actually, the assumption that (p,,, q) fully supported in S can weakened. We show that if sufficiently large probability lies in Sj. then the differential entropy still increases linearly. With this result, we can show Theorem 4.5 below, which states that there exists infinitely many rounds, such that in each of these rounds t, the probability of (p', q') E S2 will be at least some constant.
Theorem 4.3 If Js, g(P, q) d(p. 2 then the entropy will increase by at least I+5"c(A)
8CAA))
I-c (1 X) in round I, which is stricaly positive whenever d-A(A]]
Proof:
Cheung & Piliouras 2019) showed that if S min mnin11(3n22m)),8dd (c(A)))))) then
det (p, q) 2 1+ 8'((A)" .² for any (p, q) E S1, and det q) 2 1- for any (p. q) S2-
Recall that the change of entropy is g (p, q) log Jdet (p. d(p. q). As log(1 + 2 _ for
any -1, the change of entropy is at least
f 5.
d' q)
log log
1+ 82c(AA)
2 d(p..))
/
82
1 8c 2/8 J g'(p.q))((p.)) 1-2 / ()
)2(((A2 2//
Theorem 4.3 for any fixed ō and c(A), the lower bound of À decreases with e. In particular,
if 82 A)2 74, the lower bound is 1 1/4, i.e. it only requires small probability in S for the DE
7

---

Published as a conference paper at ICLR 2022
to strictly increase. Theorem distribution has a sufficient amount of probability lying in S1. Next, in Lemma 4.4 we show that the DE growth is at most logarithmic (O(log whenever the initial distribution has bounded support. These two seemingly contradicting bounds can only be compatible for one reason: the condition needed by Theorem 4.3 will eventually be violated, i.e. there insufficient amount of probability lying in S after a sufficiently long time. We formalize this in Theorem 4.50mm/..bboooo
4.3
indicates that the DE growth is at least linear (2((T) long the
Lemma 4.4 Suppose the initial distribution has bounded support in [-b, blmmm for some b 0. Then the differential entropy at time T is at most (n + m) log(<T + b).
Proof: Since every entry in A is bounded in the interval [-1, 1]. we have W,, - p31 S e and 1ok+1 off I Thus, the distribution at time T has bounded support in [-cT b, cT + bl Within this box, the maximal differential entropy is attained by the uniform distribution over it. which is (n + m) log(eT + b).
Theorem 4.5 For any non-trivial two-player zero-sum games (A, (A, with MWU dynamics of step-size E min (min(1/(3nnmm)) (²)(()) /8). any initial distribution with bounded support, and for any À > Te[AA] there exists an infinite sequence of times (Ti, ..,)...)) such that the probability in S2 each round T, is at least 1 X.
16s
The above theorem gives a lower bound of 1 - À on the probability in the boundary area for infinitely many steps, which is the "grand escape" phenomenon we mentioned in the introduction.
4.2 MWU IN ONE POPULATION GAME
Recall from 5) that in one-population game A, MWU dynamics in the cumulative payoff space is
p ++1 I' + AAx(p', where æx (p') = Σv exp(p)))
exp(r))
Similar to the two-player zero-sum games, we also consider two different regions: the interior region S {p x(p) > d}. and the boundary region Sz, which is the complement to Sj. Let g' (P) denote the probability density of p at time t. We will show that for some sub-classes one- population games A, MWU dynamics increase differential entropy linearly under some conditions. Also we show the analogue of Theorem 4.5) there exists infinitely many rounds, such that at each of these rounds I, the probability of p' E 52 will be least a constant. First of all, present the Jacobian analysis of such systems.
Jacobian Analysis. The Jacobian of the dynamics is J = =I R. where I is the n x n identity matrix, and R is an n x n matrix, in which
exp(pk)
Σ Ase exp(pw) exp(pk) exp(p=))xp((p)) x (p) (Ast Σ
Aywmme(p))
Ry*- Ash AsK EES exp(p>")
K² (Euo exp(xx)) ))²
R²
For simplicity, with a little abuse of notation, we use Ty as a shorthand of (p). Next, we calculate the determinant of the Jacobian. When we compute it using the Leibniz formula, it can be expressed in the following form, which is a polynomial of c: det (Jp)) 1 +e e (first order term) + e2. (second order term) +
where the first order term is
ERAA = Σ A Σ EnaamAu =
1 Σ
CA + Avk kef
A - Awk).
2
k.k'
Thus, the following lemma gives the condition with which the first order term is non-negative. Note that in order to have a increasing differential entropy, non-negen non-negative first order term is a necessary condition for a small enough step size.
Lemma 4.6 The first order term is non-negative for all possible x if and only if Ark + Age > Agx + Awk for all k, W. Moreover, if Ask + Agw 2 ARK + Awk for all k, k' and the inequality is for some k, k', then the first order term is strictly positive for all x 2 8.
In the terminology of mathematical biology, A&s is the payoff to species & for the intra-species play within the species, while Ag is the payoff to species & for the inter-species play between species lo and K. Informally speaking, the condition in the above lemma is: the one-population game rewards intra-species play more than inter-species play.
8

---

Published as a conference paper at ICLR 2022
Two Sufficient Conditions for Linear DE Growth. Recall that to demonstrate linear DE growth, we want the determinant of the Jacobian to be strictly larger than 1. By Lemma a clear sufficient condition is: Agk Age 2 ARk + Ark for all & and K' and there exist k, k' such that the inequality is strict. But when there is no k, k with strict inequality, it is still possible to have linear DE growth if the second order term is strictly positive. We present precise statements regarding these two cases below. To proceed, we define s(A), which is positive for the first case:s (A)
maxk, {AAR AKE A& AWRR.
For the first case, now bound the higher order terms. Note that since |Ari [Rawl I 2. When expanding the determinant using the Leibniz formula, we get a polynomial of For any i 2 2, each e' term in the expansion must be of the format ct times product of i factors of the form ,,, so each such term has absolute value bounded by 2'c'. To count the number of such terms, note that within each term, the collection of kj 's is same the collection of k₂ ss, but the order of l/2 can be any permutation of the kj 's. A simple counting shows there are at most (9) iil S n' such terms, and hence the i-th order coefficient is bounded by n² 2 Therefore, when d²a(A)
and hence
< 16p det J(p) 2 1 + (a(A)) for all p S1, and det J(p) 2 -n for all p E S2- With a similar argument as in two-player sero-sum game, we achieve the following theorems.
Theorem 4.7 If Ss, g' (p)) 2 X, then the entropy will increase by at least 6'a(A)-e/2 A
32n²c (1 X) A) in round which is strictly positive whenever X > 82a(A))
T-8
Theorem 4,8 In a populatioo game such that Ask + Ak' 2 A& + Ark for all and K' and there exist is and k' such that the inequality is strict, with MWU dynamics of step-size e Pa(A).
16n²
for any initial distribution with bounded support, and for any X > 32n²e 8=s(A), there exists an infinite
series of time (Ti,T2.- such that, for any i, the probability in S2 round T; no less than 1 1-x.
In Appendix D in the same spirit we did in Figure 2 we present few plots of MWU in an one- noc-population game that satisfies the condition in the above theorem.
Next, we consider the case that A& AR ARE ARi for all and k. In this case, the first order term is O. Therefore, we will focus on the second order term, which is Σn, <k2 (Rerks Rack2 Reyky Begk)), ), which upon expansion becomes
E Am (Anata - E AngAAcE )
1
Σ ki
Tkz
AANk2
2
K2,
Let (x),))(x,)) = = -E Tbi yk2 (Akihz - -E A Bie (Brikz - -Ex BN 2kr). Then the second order term is ((A,AT)) x). We will show this term is non-negative.
Lemma 4.9 If Ask + AWE
ARR + Avk for all and k', then (C(A,AT)(E,)) =
2 (C(A-A)((,, > (2A(A)
Proof: By Cheung & Tao 2020), C(A,B) = C.A.BTT (z, TRK = us + uw for all and W. As -A- AA));; A + Aij = An + Ajj, the first equality holds. The inequality follows from Cheung & Piliouras (2019).
Thus, for the determinant of the Jacobian, the first order term is 0 and the second order term is least 8'c(A) in St. Moreover, the i-th order term is bounded by 24, Therefore, when e S 256
(²c(A)
del (p) 2 1 de((A) e² for any p E Si, and del. (p) Z 36 3 for x E S2.
16
Theorem 4.10 If Ss, g'(p) 2 X then the entropy will increase by at least
I-8-
16n 12
-11 A) in round t, which is strictly positive whenever X >> 512n's 8*c(A)
Theorem 4.11 In a population game A such that AgE + AA = Ark + Agk for all le and ke 8c((A)
and A is non-trivial, with MWU dynamics of step-size
"iims for any initial distribution with
bounded support, and for any X > 512m's (Fc(A)' there exists an infinite series of time (T1, T2....) such
that, for any i, the probability in S2 at round T; is at least X.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
We thank several anonymous reviewers for their suggestions. This research/project is supported in part by the National Research Foundation, Singapore under its AI Singapore Program (AISG Award No: LISG2-RP-2020-00
NRF 2018 Fellowship NRF-NRFF2018-08 AME Programmatic Fund (Grant No. A20H6b0151)
NRF2019-NRF-ANRON
ALIAS grant, grant MIE-SGP-AI-20200 from the Agency for Science, Technology and Research (A*STAR) and Provost's Chair Professor- ship grant RGEPPV2101. Yixin Tao acknowledges ERC Starting Grant ScaleOpt-757481.
REPRODUCIBILITY STATEMENT
We present complete proofs for all theoretical results this work.
ETHICS STATEMENT
We do not see any ethical or future societal consequences of this work.
REFERENCES
Gabriel P Andrade, Rafael Frongillo, and Georgios Piliouras. Learning in matrix games can be arbitrarily complex. COLT, 2021.
James P. Bailey and Georgios Piliouras. Multiplicative weights update in zero-sum games. In EC, pp. 321-338, 2018.
David Balduzzi, Wojeiech M Czarnecki, Thomas W Anthony, Ian M Gemp, Edward Hughes, Joel Leibo, Georgios Piliouras, and Thore Graepel. Smooth markets: A basic mechanism for organiz- ing gradient-based learners. arXiv preprint arXiv:2001.04678, 2020.
Jakub Bielawski, Thiparat Chotibut, Fryderyk Falniowski, Grzegorz Kosiorowski, Michal Misi- urewicz, and Georgios Piliouras. Folllow-hhereggllrizee-eeeddd routes chaos in routing games.
ICML, 2021.
Yun Kuen Cheung. Multiplicative weights updates with constant step-size in graphical constant-sum games. In NeurlPS 2018, 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, pp. 807-834. PMLR, 2019.
Yun Kuen Cheung and Georgios Piliouras. Chaos, extremism and optimism: Volume analysis of learning in games. In NeurIPS 2020, 2020.
Yun Kuen Cheung and Yixin Tao. Chaos of learning beyond zero-sum and coordination via game decompositions. In International Conference on Learning Representations, 2020.
Yun Kuen Cheung, Stefanos Leonardos, and Georgios Piliouras. Learning in markets: Greed leads to chaos but following the price is right. In Zhi-Hua Zhou (ed.), IJCAI, pp. 111-117. ijcai.org, 2021. doi: 10. 2024963//jcii.2222/166
Thiparat Chotibut, Fryderyk Falniowski, Michal Misiurewicz, and Georgios Piliouras. The route chaos in routing games: When is price of anarchy too optimistic? NeurlPS, 2020.
Thomas M. Cover and Joy A. Thomas. Elements of Information Theory 2nd Edition (Wiley Series in Telecommunications and Signal Processing). Wiley-Interscience, 2006. ISBN 0471241954,
Constantinos Daskalakis and Ioannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. arXiv preprint 1xXiv:1807.03900 2018.
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. arXiv preprint /711 2017.
Lampros Flokas, Emmanouil-Vasiled Vlatakis- Gkaragkounis, Thanasis Lianeas, Panayotis Mer- tikopoulos, and Georgios Piliouras. No-regret learning and mixed nash equilibria: They do not mix. NeurlPS, 2020.
10

---

Published as a conference paper at ICLR 2022
David Heaver Fremlin. Measure theory, volume 4. Torres Fremlin, 2000.
Angeliki Giannou, camaanoui-VVaiilioos Vasileios Vlatakis- Gkaragkounis, and Panayotis Mertikopoulos. Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information. COLT, 2021.
Gauthier Gidel, Reyhane Askari Hemmat, Mohammad Pezeshki, Rémi Le Priol, Gabriel Huang, Si- mon Lacoste-Julien and Ioannis Mitliagkas. Negative momentum for improved game dynamics. In The 22nd International Conference on Artificial Intelligence and Statisties, pp. 1802-1811. PMLR, 2019.
Josef Hofbauer and Karl Sigmund. Evolutionary Games and Population Dynamics. Cambridge University Press, 1998. doi: 10.1017/CB09781 1111///89998111997799999 139173179.
Shuyue Hu, Chin-wing Leung, and Ho-fung Leung. Modelling the dynamics of multiagent q- learning in repeated symmetric games: mean field theoretic approach. Advances in Neural Information Processing Systems, 32:12125-12135, 2019.
Ratul Lahkar and Robert M. Seymour. Reinforcement learning in population games. Games and Economic Behavior, 80(C):10-38, 2013. doi: 10. 2.016//.eeb.201...
Ratul Lahkar and Robert M Seymour. The dynamics of generalized reinforcement learning. Journal of Economic Theory, 151:584-500 2014.
Alistair Letcher. On the impossibility of global convergence in multi-loss optimization. arXiv
preprint arXiv:2005. 12649, 2020.
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan- Foo, Vijay Chan- drasekhar, and Georgios Piliouras. Optimistic mirror descent saddle-point problems: Going the extra (gradient) mile. International Conference on Learning Representations (ICLR), 2019.
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In International Conference Artificial Intelligence and Statistics, pp. 1497-1507. PMLR, 2020.
Gerasimos Palaiopanos, Ioannis Panageas, and Georgios Piliouras. Multiplicative weights update with constant step-size in congestion games: Convergence, limit cycles and chaos. NeurIPS, 2017.
Julien Perolat, Remi Munos, Jean- Saan-Baptiste Lespiau, Shayegan Omidshafiei, Mark Rowland, Pedro Ortega, Neil Burch, Thomas Anthony, David Balduzzi, Bart De Vylder, al. From poincaré currence to convergence in imperfect information games; Finding equilibrium via regularization. In International Conference on Machine Learning, pp. 0255-855.. PMLR, 2021.
William H. Sandholm. Population Games and Evolutionary Dynamics. MIT Press, 2010.
Fernando Vega-Redondo. Evolution, games, and economic behaviour. Oxford University Press, 1996.

---

Published as a conference paper at ICLR 2022
A MOTIVATING EXAMPLE
To explain our mathematical model intuitively, we present the following simple one-dimensiona example. Let f(z) 2x, and suppose that X is random variable uniform on the interval [0, 1]. Then X = f(X") becomes another random variable, which is uniform on [0, 2]. Analogously, X² = f(X") is new random variable being uniform on [0, 4]. Generally speaking, the problem is to understand how the initial random variable X evolves under a given deterministic iterated update rule f. and to study how the uncertainty evolves using the measure of differential entropy. In our paper, we focus on such systems which arise in the context of learning-in-gamee
In a learning-in- in-game system, X = (p" qa)) represents a distribution over initial beliefs (initial cumulative payoffss) of the two players, and X (p', q') represents the distribution of cumulative payoffs at time f. Such probabilistic formulation is natural from the perspective of an external analyst (who is not a player of the game), who cannot be certain about what the initial beliefs the players have. For her to proceed with an analysis of the system, natural approach is to infer the initial distributions from either the past data, or her knowledge about how random external signals influence the initializations. The iterated update rule f in this case is determined by the learning algorithms used by the players, and by the underlying game. For instance, if both players are using MWU in bimatrix game (A, B), the update rule f is given by (4).
Unlike the motivating example, for learning-ing -aaning-in-game game systems the dimensions can be arbitrarily high, and the update rule non-linear. Thus, deriving the exact evolution of the distribution of X is very hard in general. But we can still use the popular statistical measure, differential entropy (DE), to understand the evolution of uncertainty. We show that the DE increases linearly with time for various combinations of learning algorithms and games, including MWU in zero-sum games, OMWU in coordination games, and MWU certain one-population games. Section has precise descriptions of the learning algorithms and the games. These results can be extended to broad family of non-zero-sun and non-co con-coordinatoo games, via the Jacobian analysis by [Cheung & Tao (2000). The results also extend to gradient ascent, as it is known to be special case of FTRL.
B INTEGRATION BY SUBSTITUTION
general theorem of integration by substitution is stated below.
Theorem B.1 (Fremlin (2000), Theorem 263D) Let D C Bd be any measurable set, and Φ D Rd be an injective function differentiable relative to its domain at each point of D. For each x E D, let J (x) be the Jacobian of & relative D at x. Then for any real-valued function h defined on <( (D).
( h(x) dr = J. M((x)) . |det J
(DD)
if either integral is well-defined, provided that h(((x)) deet xx(t) (x) is interpreted as zero when det (z(z) and h()(z)) is undefined.
In Section 3 we use integration by substitution twice. First, in the above theorem, by setting g. 2 and D = f(x'') for any measurable set X' C X, we have
[ dx = Jea, (x) det J (x)
Recall that g is a probability density function of the absolutely continuous random variable X, so the LHS of the above equality is same as IP [X E X'). Thus, the integrand of the integral in the RHS the probability density function of f(X), g(x) = -()- det J, (x)].
To derive ((D)= = =V.
(6). in the above theorem, set h(z) -g(x) log o f. D X and hence
C
MORE APPLICATIONS
C.I OMWU IN TWO-PLAYER COORDINATION GAMES
two-player game (A, B) is a coordination game = B. Similar to the MWU dynamics in two- player zero-sum games, here we also look at two different areas: S {(p, 4)(=(p) > 8 and v(z) 2
12

---

Published as a conference paper at ICLR 2022
)) and S2. which is the complement to S1, S2 S1. For coordination game (A, A). Cheung &
Piliouras 2020) showed that when (p, q) E Si, then det , f(x) 2 1+ de((A)" E²² when is small enough and. when (p, q) E S2, then det J f(x) 2 1 O(e"). Therefore, by calculation which is similar MWU in two-player zero-sum game, we obtain the following theorems.
8 P
Theorem C.1 Js, g' d(p. q) 2 X then the entropy increases by least O X)
Theorem C.2 For any non-trivial two-player coordination games AA, with OMWU dynamics of a small enough step-size for any initial distribution with bounded support, and for any X such that = o()), there exists an infinite series of time (T,:T2 T2....). such that the probability in S2 at round T; is at least X.
C.2 OMWU IN ONE POPULATION GAMES
As pointed out in Cheung & Piliouras (020), the continuous analogue of OMWU, in the context of online learning, as follows. There are actions. Let p(t) TR" denote the cumulative payoff vector up time t, and u(t) E R" denote the instantaneous payoff vector the n actions at time t. The continuous analogue is
P + -. In one-population game, u(t) A xt), where for the logit conversion used in MWU and OMWU, F3 exp(p))/ Ee exp(pe). It is easy to compute that
(9)
Ouk
Oz
25 (xx))
and
I2 when L # k.
0pk
0x
Then for any = 1,2..... we have
0 o[Ax]]
Ozk Öp:
Σ
Ask
Aseat Σ AsuaAa
xz (Aje [Ax]j).
Öp:
0[Ax|,
Following the notation in MWU case,
Rye- By the chain rule, we have
Opz
d[Ax]]
Σ Rse Dt.
úg
dl
Putting the above equality into 9 yields
i3 = [Ax], + >
Ry
pr,
8=1
which is recurrence of the variables ph, ...,...,,n Dn- Unwinding this recurrence yields
p = [Ax]] + Σ
Rge [Ax], + O(e)).
t=1
The above system, upon Euler discretization to discrete-time dynamical system with time interval e, becomes
Vj. p =p e [Ax], e² - [Ax]e + O(e3).
(10)
Observe that the RHS of (TO). the first two terms coincide with that in the MWU case. The remaining terms can be viewed as second-order perturbation. Consequently. the Jacobian of the system equation 10 is a second-order perturbation of the Jacobian for the MWU case, and hence the constant and first-order terms of the determinants of these two Jacobians are the same, which is Σn= Rzj-
Therefore, for the case that Agt + Agrk 2 A + Atrk for all is and K'' and there exist and K such that the inequality is strict, obtain the following theorems. Recall that {p|x(p) > 8} and S2, which is the complement SI, S2 S1: and ((A) max & (Aka + Ag A ArR)-
13

---

Published as a conference paper at ICLR 2022
Theorem C.3 Ss, g (p) X, then the entropy increases by least 8'a(A) [+872
(1 for small enough step size e.
Theorem C.4 In an one-population game A such that Ags. + Agw 2 ARE + Awk for all and ke' and there exist k and k' such that the inequality is strict, with OMWU dynamics with small enough step-size for any initial distribution with bounded support, and any such that = o(A), there exists an infinite series of time (Ti, ......) such that, for any the probability in S2 at round T3 is no less than X.
For the case that A&: + A A&x + AR for all k and k', we consider the second-order term. The second-order terms of the determinants (MWU and OMWU) are not the same though. The second-order term of the determinant of Jacobian for the OMWU case is
RRje Op,
Σ S
RKK
Σ Isicken
Ra + ΣΣ
Res +
[Ax]e.
j=1
j=1 Em
Observe that the first two summations are just the same as those in the MWU case. Next, a straight- forward calculation gives
ORye
= Rgj 1=== xzg Rye xz R250
Öp,
where 1 j=t jf j-
and 0 otherwise. Hence
ÄRze
[xxe
Σ
Ry [Ax],
2 Rye + x(Rgj)) [Ax]]
Öp:
f=1 1=1
==1
j=1 1=1
n
Σ Rig [Ax], Σ
xz [Ax| Σ Rge Σ
Raj [xx]
Σ xt.
Since Σ Jz
and Ei= Rye have ΣØ=1 Ei=1
0Rg Op,
[Ax]; = To conelude, the
second-order term is
Σ Isicksn
RijRak
Σ
Ry +
RyeRes
Isisken
Σ
(Rz))
+
Σ
Ryk +
Σ
j=1
Isicksn
Isicken
Σ
Rij
Σ ISiCken
REj
Σ 1sjckšn
Ris
Note that when A&t + Agk = ABk + Akrk for all and W,, E, Rıj = O. Therefore, the second order term of OMWU is the negative of the second order term of MWU, which will be smaller than
8 (()())
Theorem C.5 an one-population game A such that Agt + AkK 2 ARy + for all k and with OMWU dynamics, if fpes, g(p) dp 2 X, then the entropy decreases by at least &cAA) -(2))) (1 for small enough step size e.
1482
C.3 PERTURBATIONS TO PAYOFFS
In the main body, we focus two- wwo-player zero-sum games. In this appendix, we discuss the Jacobian analysis for two-player general games based on Cheung & Tao (2020), and explain why it is robust against perturbations.
14

---

Published as a conference paper at ICLR 2022
First, we define the following function the cumulative payoff space of two-player games, which depends on a matrix M Rexm
[M q)
Σ Sa IER,''S
3y (p)) (Mzz My MYk Mxk))²
where Ty' yk Me is as defined
For any general game (A, (A,B), B), coordination game as (A, B) (Z, -2) + (C, C), where Z = (A - B)/2 and C = (A B)/2. Cheung Tao (2020) showed that the determinant of the Jacobian matrix of MWU with step-size in the game A, is is
decompose it into the sum of zero-sum game and
1 + (Iz(P. - ()( + 0(6))
We rewrite q) Lc(p.q) as
Σ
())D)ay(D))u())ukk (Ask + Ayw Agx Ayx)( + Byr Byb Byw)
ISAf'sn ISk Sm
Thus,
max [[Age + Apw ASN ABz) ByR BiN Bywr 2 L (11) ko
and
min [AAx + Ayk A J3' k.k
- AAx)) + Byx Byk Byw) 2 0, (12)
then in the domain S (p. Vj,k, zy(p) 2 and (n()) 2 8}. the determinant is least
1 + 5*Le2/8 /8 for all sufficiently small
Since the product (A,x + Ay Asu- ABj) + By Bi By*)) depends on A, B continuously, is natural to expect that when A, B are slightly perturbed, the value the product suppose that in each round I, the actual payoff matrices are (A B'), and their entries are perturbations from (A, B) by at most an absolute value of < 2 F Recall that the entries A, are bounded in the interval [-1, 1], so the absolute values of A,k + Apw - Ası - Ay'k and B + By' Byx By are bounded by 4. while the perturbations
changes also slightly. To make this precise,
their values are bounded by 43. By the lemma below, for the game (A* B'), the
bound in [1] still hold by replacing its lower bound with I 348, and the bound in (12) still hold by replacing its lower bound with 338.. Thus the determinant of the Jacobian matrix in S is at least 1 + (6 T/4 343)e² /2 2 8 2/16/16 if 3 S 8TT.272.
Lemma C.6 1/3 -2, 2, |a]. bl < and |a' al, V b) < 48, then a'U' 2 ab -3,3
Proof:
Let - = Ba, b Bb. Then d'b' - ab = b3, + a3, + 3, 2 -163 - 163 - B2 3348.
D PLOTS OF UNCERTAINTY EVOLUTION OF MWU IN POE-LAPUNN GAME
'This function was denoted by (P, q) in Cheenn Tao 2020 but to avoid confusion and cluster of notation, we change to (M q)-
We assume that the entries in both (A, B) and (A', B¹) in the interval [-1, 1), so / most
15

---

Published as a conference paper at ICLR 2022
1.0
1.0
0.0
0.0
-.5
-0.5
-1.0
-1.0
-1.
-1.5
-2.0
-1.5
-10
0.0
0.5
2.0
-15
-1.0
0.0
0.5
2.0
1.0
0.44
-05
0.38
1,00
0.75
0.50
0.25
-15
-1.
0.00
-1.0
-05
0.0
0.50
-0.25
-0.75
-1.5
Figure 2: We plot the evolution of uncertainty for MWU in an one-population game specified by
0.1
1.0
-1.07
the matrix A =
- 1.0
0.1
1.0
with step-size 0.01. As we did in Figure in the top
1.0
-1.0
0.1
left plot is the initial distribution, which is uniform in the small square. The top right plot shows the "possibility" plot after 6000 steps, and the bottom left plot shows the corresponding heat-map plot of probability densities.
16


Reviews:
[{"review_id": "wB9LUYbvK5_", "reviewer": "Reviewer_2Gu6", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Learning in games is a relevant and active area of research, and I believe the contributions of this paper are original and novel with respect to previous works. Moreover, the paper is well-written and the authors did a good job in illustrating the motivations and putting their work into context. As mentioned by the authors, the obtained results are orthogonal w.r.t. past works that study non-convergence in games, as the proposed approach quantifies the increase of unpredictability via the notion of differential entropy. \n\nIn my opinion, however, the paper has also some weaknesses:\nThe paper lacks experimental results which perhaps could better illustrate the studied phenomena (e.g., the obtained DE rates).  Moreover, the obtained theoretical results, albeit novel, revolve around a few technical arguments and sound a bit repetitive.", "summary_of_the_paper": "The paper studies the evolution of uncertainty in multi-agent game dynamics. More specifically, it studies how the probability distribution over the players' cumulative payoffs evolves as players use typical online learning algorithms to play the game. \nThe game uncertainty is quantified by the notion of Differential Entropy (DE) of such distribution, a quantity related to the Jacobian of the game dynamics. Authors show that DE increases linearly with time for a set of games including two-player zero-sum, coordination games, and population games, confirming the negative convergence results obtained in past works.", "summary_of_the_review": "To summarize, although the paper could improve from additional experiments and the technical contributions are limited, I have appreciated the motivations and model proposed by the authors, as well as the obtained theoretical results.\nHence, my accept score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "pZPYaOeJy1T", "reviewer": "Reviewer_8PmF", "summary": "", "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": "Strengths\n - Enables looking at differential entropy, and not just the volume, of a distribution of strategies for a game.\n - Strengthens the approach of previous work by splitting the space into a boundary region and interior region and analyzing the change in probability mass between the two.\n - Contributes a possibly novel analysis of the determinant of a Jacobian of a population game\n - Results are claimed to be robust to small perturbations in the game.\n\nWeaknesses\n - Is differential entropy (DE) the most appropriate way to index the deviation of the strategy vector from equilibrium?  This paper could provide arguments for why DE makes more sense than other statistics that could be considered, e.g. determinant of covariance matrix, trace of covariance, Nash gap (max difference between a player's payoff and the payoff for their best response holding other players fixed.)\n - Is the use of DE key to the results on non zero-sum games, or could similar results have been obtained through volume analysis?   This paper could make it clear which novel results are exclusive to the choice of using DE.\n - The significance of the results, in spite of a brief reference to the \"grand escape\" (which is not further elaborated outside of the introduction), is not made clear to the reader.  This paper could describe in greater detail what happens to make the entropy increase slow down.\n\nMinor comments\n - Does there exist a reference for the derivation for eq. 6?  It seems to be known in the literature, e.g. see Duvenald et al. 2016 \"Early Stopping as Nonparametric Variational Inference\"\n - pg. 2 \"more probably to occur\" -> \"more probable to occur\"\n - pg. 4 after eq (1) \"depending on the value of qt\" -> \"depending on the value of pt\"", "summary_of_the_paper": "This paper extends the existing line of research of the dynamics of multiplicative weights update and similar algorithms for games.  It shows that for zero-sum two-player games and for population games satisfying certain conditions, that the entropy increases linearly as long as the strategies are far from the distribution; this implies that the strategies concentrate near the boundary in the long-run, in a sense that the paper formalizes.  Compared to previous work, this analysis applies to games that are not zero-sum--specifically, population games that satisfy a certain condition on the payoffs.", "summary_of_the_review": "This paper adds some new results extending previous work that established divergence from Nash equilibrium for a class of learning algorithms for games.  I was not convinced of the main argument of the paper, which claims that the advantage of using differential entropy to analyze the learning dynamics.  What seemed more novel was the analysis of the Jacobian of the population game.  Hence, overall I am recommending weak acceptance.  If I were to be convinced that the use of differential entropy is a promising approach for the field, then I would raise my score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "nZGk9_7CEAs", "reviewer": "Reviewer_Xwzj", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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 paper studies the dynamics of online learning. Different from the standard perspective, the paper investigates the behavior of a probability distribution over a set of initial conditions.\nThe paper provides a novel theoretical insight on how this probability distribution over initial conditions envolve. The technical/theoretical aspects of this paper seem to be rigorous. \n\n1. Second line below eq (1), what is q^t here? should be p^t?\n2. In eq (1), the agent updates the cumulative payoff vector using the exact payoff at the current time step. I’m curious whether the main results still hold if the agent uses the empirical payoffs till to current time step?\n3. The authors characterize the evolution of the differential entropy of the distribution of cumulative payoff vectors. When the probability distribution over the initial conditions is discrete, which is often seen in practice, can the authors still achieve the same characterization for Shannon entropy?\n", "summary_of_the_paper": "The paper studies how the uncertainty of the initial cumulative payoff vectors evolves in the process of learning in games. Looking to the differential entropy, the authors show that for a broad range of learning-in-game systems, including two-player matrix games and one-population games, the differential entropy of the distribution over the cumulative payoff vectors increases linearly with time in two learning algorithms (Multiplicative Weights Update, and Optimistic Multiplicative Weights Update). ", "summary_of_the_review": "I’m not super familiar with the related literature of this work. But as far as I’m aware, the perspective adopted in this paper on studying the dynamics of online learning in games is original to me. The characterization on the evolution of cumulative payoff vectors seems pretty novel to me. I feel the results obtained in this work may have implications on other studies on the behavior dynamics of online learning in games, especially for those who need random initial conditions. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Dg7BcBFBgp", "reviewer": "Reviewer_8gHb", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "Questions:\n* Fig. 1 is extremely unclear, and it would be better to explain the meaning of each sub-fig in the caption or main text.\n* I think this paper is not easy to follow, and many clarifications are needed. For example, a general problem setting before the model section would be useful. Why choose MWU in zero-sum games, OMWU in coordination games? Would the same conclusions still hold when using other learning algorithms in games like gradient ascent, joint action learner?", "summary_of_the_paper": "This paper proposes a differential entropy framework to quantify the evolutionary stability of learning in games with different initial conditions. The paper finds that differential entropy of these learning-in-game systems increases linearly with time for Multiplicative Weights Update (MWU) or Follow- the-Regularized-Leader (FTRL) algorithms in zero-sum games.\n", "summary_of_the_review": "Investigating the uncertainty/stability during the learning in games with different initial conditions is an interesting problem. But from my understanding, this problem has not been well formalized in the paper, and many additional clarifications are required to make the people unfamiliar with this research problem get the paper's key points.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper examines the evolution of densities of initial conditions under the multiplicative weights update rule for learning in two-player zero-sum games. Specifically, the authors estimate the differential entropy (DE) of a density of initial conditions as it evolves over time (what they call "uncertainty"), and they show that (a) as long as the density of states assigns sufficient mass to all strategies, its DE will increase; and (b) the density of states will get arbitrarily close to the boundary of the state space infinitely often (i.e., at least one pure strategy will be employed with arbitrarily small probability infinitely often). The authors also apply these results to a population-like model of learning as well as an optimistic variant of the MWU protocol (the latter in the supplement).

The paper was extensively discussed during the review/rebuttal phase. While the reviewers appreciated the conceptual contributions of the paper, they also identified certain technical shortcomings that were only partially addressed by the authors. One of these issues concerned the possibility that the density of initial conditions may exhibit singularities, in which case the DE may fail to be well-defined. As a result, one of the reviewers indicated an intent to downgrade their score from "8" to "3" due to concerns on the correctness of the results presented in the paper.

After discussing with both the authors and the reviewers, my view is that the merits of the paper outweigh its flaws, so I am making an "accept" recommendation. At the same time, there is a number of revisions that the authors will have to undertake in the camera-ready version of their paper:

1. The authors need to be more careful with their assumptions and notation. The reviewers already indicated a number of glitches, most of them easily fixable (so they are not of particular concern). On the other hand, the issue of whether the initial density of states becomes singular or not is more subtle and led one of the reviewers to drastically change their evaluation of the paper.

  The problem here is that the authors are not being precise in their assumptions for $g^1$ and its support, and this confusion remained throughout the discussion: the authors are looking at distributions that are "smooth with bounded support", but this does not exclude singularities. The counterexample given to the authors was a random variable $X$ supported on $\mathcal{X} = (0,1)$ with density $g(x) = 1/(2\sqrt{x})$; this density has bounded support and it is smooth on its support, but it is not itself bounded. [There is an ambiguity here in whether the authors are considering the support to be closed or not.]

  The issue for the initial density can be trivially fixed by asking that $g^1$ be itself bounded (or smooth over the closed support, or any other similar statement). However, even if this is assumed for $g^1$, the density at some later time $t$ could, a priori, become singular (incidentally, this is a problem that arises frequently in the study of densities that evolve over time, e.g., as in optimal transport). Thus, even an explicit assumption for $g^1$ does not suffice to ensure that $g^t$ does not develop singularities in future stages. [Incidentally, the authors' reply that the singularity has measure zero and therefore does not contribute to the integral misses the heart of the matter (and raises concerns about the authors' overall treatment of this question): the function $g(x) = (\log 2) \big/ (x \log^2x)$ has infinite differential entropy over $(0,1/2)$ even though it is a smooth density over $(0,1/2)$.]

  To be clear, I do not believe that blow-ups actuall occur in the authors' model, but there is still something that needs to be shown here. However, since it is impossible to check an argument or proof at this stage (and I do not think it would be fair to let this stand in the way of accepting the paper), the authors should instead revise their paper to add as an **explicit** assumption that $g^t$ has bounded support and is bounded over its support (or clarify whether they take the support to be closed or not).

1. Another concern revolves around the use of the word "uncertainty" to describe the basic premise of the paper. In the authors' model, this does not refer to uncertainty among the learners (all their observations are perfectly certain and deterministic), so it is not used in the sense that is standard in game theory and learning (cf. the classic works of Bertsekas, Dekel, Fudenberg, Tsitsiklis, and many others). Instead, the authors' use of the word seems to refer to some "outside spectator" who can only partially guess the players' initial conditions, and tries to guess the evolution of the players' mixed strategies (but still has full information about the learning model that players use, its parameters, etc.). However, this model is not fleshed out in sufficient detail by the authors, so the term "uncertainty" does not seem appropriate here.

  During the rebuttal phase, the authors argued that the goal of their paper is "bringing the notion of DE to machine learning audience's attention as a measure of uncertainty, explaining how the change of DE is related to the Jacobian of the underlying dynamical systems" and they asked "that [the paper's] title remains as is". While I am sympathetic to the authors' request, the fact remains that the current title (and part of the discussion in the abstract) is not representative of the paper.

  Given the authors' stated objective, the simplest solution would be to frame the paper as the "evolution of differential entropy under..." or the "evolution of spectator/observer uncertainty" or something of the sort. Both titles carry more information and, based on the authors' input, are more appropriate for the range of ideas the authors wish to convey – but simply saying "uncertainty" goes against the established terminology of the field.

Overall, I would urge the authors to avoid vague/ambiguous terminology and statements, and focus instead on exact mathematical definitions that are not open to interpretation. The ideas presented in the paper are interesting and fresh, so they deserve a likewise sharp and precise treatment.
Decision: Accept (Poster)