THE EVOLUTION OF UNCERTAINTY OF LEARNING IN GAMES
Year: 2021

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, 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 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 Followthe-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.

heading: 1 INTRODUCTION
text: A primary goal of ML research is to understand the behaviors of learning algorithms in various settings. One standard approach is from each initial condition, we determine whether a learning algorithm converges to a local optimum or stable state. Yet, in the context of online learning in games, and more generally in distributed multi-agent learning, it is natural to consider the evolution of a probability distribution over initial conditions instead. In these settings, each agent forms an initial belief on her own, and she typically does not reveal her belief to other agents or external modelers/analysts. For a modeler to understand the 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 use this inference to predict the likelihoods of different outcomes in the future, either by simulation or by analysis. Also, random initialization can happen due to random external signals, e.g. weather, as well as noisy measurements. For readers who want to know more intuitions and mathematical aspects of such models, see Appendix A.
In such cases, it is critical to understand whether the initial probability distribution evolves toward stability, or if its uncertainty gets amplified. Such analysis provides insight into the learning system’s robustness against random initialization and environment perturbations. If a coordinator of the system 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 it. A natural choice is entropy. In his seminal work in 1948, Claude Shannon formulated an axiomatic foundation of information theory and introduced the seminal definition of Shannon entropy (SE): given a discrete random variable with possible outcomes x1, . . . , xn which occur with probability p1, . . . , pn, its SE is − ∑n i=1 pi log pi = E [log(1/pi)]. Entropy is the canonical measure of uncertainty: when pi = 1 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 log n. For continuous
random variables with probability density function g, Shannon proposed an extension of SE called the differential entropy (DE), defined as E [log(1/g(x))] = − ∫ X g(x) log g(x) dx, where X is the support set of the random variable. We will analyze how DE evolves in multi-agent learning.
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).1 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 a broad range of learning-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 smooth initial distribution with bounded support.
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 a uniform distribution over [−1, 1]. In the cumulative payoff space, the distribution at time T converges to a multivariate Gaussian distribution with variance Θ(T ), and hence the entropy grows at a rate of O(log 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 a region that yields slower DE growth or decline; such region does not cover any point in the cumulative payoff space that corresponds to an interior Nash equilibrium. We will refer to this phenomenon by “the grand escape”. For the implications in information theory, we refer readers to Chapter 8 of Cover & Thomas (2006).
The central tool in analyzing the changes of DE is the Jacobian matrix of our multi-agent dynamical system. This is also the key notion in volume analysis, which was used in a recent series of papers to demonstrate Lyapunov chaos in learning-in-game systems. (Cheung & Piliouras (2019; 2020); Cheung & Tao (2020)) By showing that the determinant of the Jacobian matrix is strictly above 1 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 a set of large diameter, thus demonstrating a general Lyapunov chaos phenomenon in learning-in-game. Indeed, the same property of Jacobian matrix guarantees linear increase of DE. Additionally, we present the first Jacobian analysis of online learning in 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.
Our model and analysis can be viewed as an a strengthening of volume analysis. Volume analysis focuses on whether it is possible to reach a state or not, whereas in our model we are also concerned with how probable/likely it is to reach a state. More explicitly, a state can be reached but only with a tiny chance. When studying chaos and volume, such states matter, but less so 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 a few plots in Figure 2. The top-left plot shows the initial set, which is a small square around the unique Nash equilibrium. The top-right plot shows the range of possibility after 40000 steps (a similar figure was first presented by Cheung & Piliouras (2019)). In our model, we assume the initial distribution is uniform over the small square, and plot the heat-map of probability densities after 40000 steps (bottom-left). We observe that the states in the boundary of the vortex are more probable to 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
1As we shall point out in Section 3, all our results about MWU also extend easily to the broad family of Follow-the-Regularized-Leader (FTRL) algorithms, which is a generalization of MWU. For clarity of our presentation, we choose to focus on MWU in this paper.
the preferred solution. Lahkar & Seymour (2013) studies online learning under random initialization in population dynamics, where one population game is a common payoff model. In population dynamics, there exists a large population of agents who have different initial choices of mixed strategies, modeled as a distribution. The dynamics proceed by randomly pairing up agents in each round to play a game. Lahkar & Seymour (2014) extends this framework to other learning dynamics to describe the evolution of a distribution of mixed strategies in a population playing variants of RockPaper-Scissors games establishing local convergence to 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 (2018); Cheung (2018), 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 zerosum games are undesirable for ML applications such as GANs thus a lot of effort has been invested in developing algorithms that achieve convergence Daskalakis et al. (2017); Mertikopoulos et al. (2019); Daskalakis & Panageas (2018); Gidel et al. (2019); Mokhtari et al. (2020); Perolat et al. (2021). Our research direction here is in some sense orthogonal. We aim to characterize in a more detailed fashion the behavior of learning dynamics despite their instability.
The instability of MWU, FTRL and other optimization-driven dynamics in games has attracted a lot of attention in recent years. One formal technique to establish the unpredictability of MWU and other dynamics is based on proving Li-Yorke chaos, which has been established robustly in different families of routing/potential/Cournot games (Palaiopanos et al. (2017); Chotibut et al. (2020); Bielawski et al. (2021); Cheung et al. (2021)). 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 a very recent series of works, Flokas et al. (2020); Giannou et al. (2021) established that all (even partially) mixed equilibria 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 dynamics can be arbitrarily complex Andrade et 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 a 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 Cover & Thomas (2006), “there is need for some care in using the concept”.2 Nevertheless, DE remains as an effective measure of uncertainty3, 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); Vega-Redondo (1996).

heading: 2 MODEL
text: We use bold small letters to denote vectors, and bold capital letters to denote matrices. Let ∆d denote the probability simplex of dimension d: ∆d := {x ∈ Rd : for each j, xj ≥ 0, and ∑d j=1 xj = 1}.
MWU and OMWU. When an agent uses MWU, she wants to choose among d ≥ 2 pure actions based on the past cumulative payoffs to these actions. The process starts at discrete time t = 0, where the agent chooses an initial cumulative payoff vector p0 ∈ Rd. At any time t ≥ 1, upon receiving the payoffs to the each of the d actions at time t − 1, which are denoted by a vector rt−1 ∈ Rd, the agent updates the cumulative payoff vector by the rule
∀j = 1, 2, . . . , d, ptj ← pt−1j + · r t−1 j , (1)
where > 0 is the step-size of the update. At any time t ≥ 0, the agent chooses randomly among the d pure actions depending on the value of pt. Precisely, the agent chooses a mixed strategy xt ∈ ∆d which is a function of pt.For MWU, xt is determined by the rule
∀j = 1, 2, . . . , d, xtj ← exp(ptj)/ ( d∑ k=1 exp(ptk) ) . (2)
For OMWU, we start with p0 = p1, and for t ≥ 2,
∀j = 1, 2, . . . , d, ptj ← pt−1j + · (2r t−1 j − r t−2 j ), (3)
and xt is determined by the same rule (2). In general, the payoff vectors rt−1 can be arbitrary, and they may or may not depend on the mixed strategy xt−1. However, in the context of learning-in-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.
Two-Player Matrix Games. In a two-player matrix game, Player 1 has n actions and Player 2 has m actions. The game is specified by two matrices A,B ∈ [−1, 1]n×m. When Player 1 chooses action j and Player 2 chooses action k, Ajk, Bjk are the payoffs to Players 1 and 2 respectively. When the players choose mixed strategies, the payoffs are extended via expectation. Denote the mixed strategies of Players 1 and 2 by x ∈ ∆n and y ∈ ∆m. The payoff to action j of Player 1 is [Ay]j , while the payoff to action k of Player 2 is [BTx]k. When both players use MWU or OMWU
2Two 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 we will always stick to a fixed coordinate system which is natural in learning-in-games.
3DE 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 a bounded support set, the uniform distribution over the support set attains maximum DE.
to play this game repeatedly, we have the following discrete-time dynamical system, where pt,qt denote the cumulative payoff vectors at time t of Players 1 and 2 respectively. The two players choose initial cumulative payoff vectors p0,q0.
∀t ≥ 1, pt ← pt−1 + ·Ayt−1; qt ← qt−1 + ·BTxt−1. (4)
Note that xt−1 is a function of pt−1 as specified in (2); similarly, yt−1 is a function of qt−1. Thus, we can also view (4) as an iterated function that maps from (pt−1,qt−1) to (pt,qt).
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 is a “reference game” (A,B), but at each round the actual game being played is a perturbation of the reference game. Precisely, the game at time t is (At,Bt) = (A,B) + (∆tA,∆ t B), where ∆ t A,∆ t B are matrices with maximum absolute entry at most β, for some small β > 0.
One-Population Games. One-population games is a fundamental model in mathematical biology, which is widely used to explain the evolution of a population of different of species over time. An one-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, one population) in this game, while a mixed strategy xt represents the fraction of different species among the population. An one-population game is specified by a matrix A ∈ Rn×n. When the mixed strategy of the player is x ∈ ∆n, the payoff to action j is [Ax]j . The resultant discrete-time dynamical system with MWU is ∀t ≥ 1, pt ← pt−1 + ·Axt−1, (5) where xt−1 is a function of pt−1 as in (2).
Random Initial Cumulative Payoff Vectors. In Section 1, we explained why we consider uncertainty of the initial cumulative payoff vectors. This can be captured by a model where these vectors follow a distribution. We use two-player game for discussion below; for one-population game it is similar. Assume that the initial vectors (p0,q0) follow a joint probability distribution in the domain Rn × Rm. As the initial vectors are random and they are updated according to the discrete-time dynamical system (4), for any t ≥ 0, (pt,qt) also follows a distribution, which is the main object we analyze in this work. We are interested in knowing certain statistics of uncertainty of this distribution, say differential entropy, which is the subject of the next section.

heading: 3 DIFFERENTIAL ENTROPY
text: 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 : Rd → Rd be a smooth function. Its Jacobian matrix is
Jf =  ∂f1 ∂x1 ∂f1 ∂x2 · · · ∂f1∂xd ... ... . . .
... ∂fd ∂x1 ∂fd ∂x2 · · · ∂fd∂xd  . Let X be a continuous random variable in Rd. Let g be its probability density function, whose
support set is X . The DE of X is h(X) := − ∫ X g(x) log g(x) dx. For any function f : R
d → Rd, f(X) is another random variable; we denote its probability density function by ĝ, and its support set by Y . If f is a diffeomorphism, it is known that ĝ(y) = g(f−1(y)) · ∣∣det Jf−1(y)∣∣. Using multivariate integration by substitution, the DE of f(X) can be computed as follows:
h(f(X)) = − ∫ Y ĝ(y) log ĝ(y)dy
= − ∫ Y g(f−1(y)) · ∣∣det Jf−1(y)∣∣ · log (g(f−1(y)) · ∣∣det Jf−1(y)∣∣) dy = −
∫ X g(x) · ∣∣det Jf−1(f(x))∣∣ · log (g(x) · ∣∣det Jf−1(f(x))∣∣) df(x) = −
∫ X g(x) · ∣∣det Jf−1(f(x))∣∣ · log (g(x) · ∣∣det Jf−1(f(x))∣∣) · |det Jf (x)| dx.
By the Inverse Function Theorem, ∣∣det Jf−1(f(x))∣∣ · |det Jf (x)| = 1. We have (Duvenaud et al. (2016))
h(f(X)) − h(X) = ∫ X g(x) log |det Jf (x)| dx. (6)
Thus, the determinant of the Jacobian matrix directly affects the change of DE. In particular, if there exists α > 0 such that |det Jf (x)| ≥ 1 +α for all x ∈ X , then h(f(X))−h(X) ≥ log(1 +α) > 0. In order to use (6) to analyze the changes of DE of learning in two-player matrix games, we view the dynamical system (4) as a function that maps from (pt−1,qt−1) to (pt,qt) in each round t ≥ 1. If the change of DE per round is at least log(1 + α) > 0, then the DE increases linearly with time.
The Relationship Between DE and Volume. Before discussing the relationship, we first recap what is volume. Let X ⊂ Rd be a measurable set with positive Lebesgue measure (which is sometimes called the volume of the set), and let f : Rd → Rd be a diffeomorphism. The volume of f(X ) is ∫ X |det Jf (x)| dx. When |det Jf (x)| ≥ 1 + α for all x ∈ X , the volume increases by a factor of at least (1 +α). 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 (6) is not a coincidence, but with a simple intuition behind. The Jacobian yields a linear approximation of f locally: for any x ∈ Rd and any small perturbation vector ∆x ∈ Rd, f(x + ∆x) ≈ f(x) + Jf (x) ·∆x. We consider a tiny hypercube with volume v around x, and its image under the function f . By the linear approximation, the image is approximately a parallelotope (the high-dimensional analogue of parallelogram), whose volume is known to be |det Jf (x)| · 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 x is 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 f(x) is g(x)/ |det Jf (x)|. If the volume increases locally at x, i.e. |det Jf (x)| > 1, it intuitively means the uncertainty level increases locally. This intuition is captured by DE: the contribution to DE by the tiny hypercube is −g(x) · v log(g(x) · v), while the contribution to DE by the parallelotope is −g(x) ·v log g(x)·v|detJf (x)| . Thus, the local change of DE is g(x) ·v log |det Jf (x)|, which has the same sign as (|det Jf (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 (2019; 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.)

heading: 4 APPLICATIONS
text: In this section, we consider two applications: MWU in two-player zero-sum games and onepopulation games. In Appendix B, we also consider OMWU dynamics in two-player coordination games and one-population games, and the settings where the game in each round is perturbed. A two-player game (A,B) is zero-sum if A = −B. We focus on non-trivial games, defined below.
Definition 4.1 (Cheung & Piliouras (2019)) A zero-sum game (A,−A) is trivial if there exists real numbers a1, a2, · · · , an and b1, b2, · · · , bm such that Ajk = aj + bk. The same definition applies for one-population game A.
Cheung & Piliouras pointed out that a trivial game is not interesting as the players have dominant strategies. They provided a measure of distance of a zero-sum game (A,−A) from triviality by
c(A) = min a1,··· ,an,b1,··· ,bm
[max(Ajk − aj − bk)−min(Ajk − aj − bk)] (7)

heading: 4.1 MWU IN TWO-PLAYER ZERO-SUM GAME
text: Recall from (4) that in zero-sum game (A,−A), MWU dynamic in the cumulative payoff space is
pt+1 = pt + ·Ay(qt) and qt+1 = qt + · (−A)>x(pt)
where x(pt) and y(qt) are the mixed strategies of two players at time t: xj(pt) = exp(ptj)/ ∑ j′ exp(p t j′) and yk(q t) = exp(qtk)/ ∑ k′ exp(q t k′). Two different regions are considered: the interior region S1 := {(p,q) | x(p) ≥ δ and y(q) ≥ δ}, and the boundary region S2, which is the complement to S1. Note that if the game possesses an interior Nash equilibrium, then the equilibrium lies in S1 for any sufficiently small δ.
Let gt(p,q) denote the probability density of (p,q) at round t. Recall from 6 that the change of entropy is ∫ gt(p,q) log |det Jf (p,q)| d(p,q). If gt(p,q) is fully supported by S1, then by using the Jacobian analysis of Cheung & Piliouras (2019), who showed that the determinant of the Jacobian matrix is strictly larger than 1 in S1, we show the differential entropy increases linearly.
Theorem 4.2 For any non-trivial two-player zero-sum game (A,−A), with MWU dynamics of step-size ≤ min{1/(32n2m2), δ2c(A)2/8}, if gt(p,q) > 0 only for (p,q) ∈ S1, then the differential entropy will increase by at least δ
2c(A)2· 2/8 1+δ2c(A)2· 2/8 in round t.
Proof: For MWU dynamics, f(p,q) = (p+ Ay(q),q− A>x(p)) by (2). Cheung & Piliouras (2019) showed that if ≤ min{1/(32n2m2), δ2c(A)2/8}, then det Jf (p,q) ≥ 1 + δ 2c(A)2 8 · 2 for any (p,q) ∈ S1, where c(A) is the measure of the distance of a zero-sum game (A,−A) from triviality (7). As log(1 + r) ≥ r1+r for any r > −1,∫
gt(p,q) log |det Jf (p,q)| d(p,q) ≥ δ2c(A)2 · 2/8
1 + δ2c(A)2 · 2/8 .
Actually, the assumption that gt(p,q) is fully supported in S1 can be weakened. We show that if a sufficiently large probability lies in S1, 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 (pt,qt) ∈ S2 will be at least some constant.
Theorem 4.3 If ∫ S1 g(p,q) d(p,q) ≥ λ, then the entropy will increase by at least δ 2c(A)2· 2/8 1+δ2c(A)2· 2/8 · λ− 3
1− 3 · (1− λ) in round t, which is strictly positive whenever λ > 16 δ2c(A)2 .
Proof: Cheung & Piliouras (2019) showed that if ≤ min{1/(32n2m2), δ2c(A)2/8}, then det Jf (p,q) ≥ 1+ δ 2c(A)2 8 · 2 for any (p,q) ∈ S1, and det Jf (p,q) ≥ 1− 3 for any (p,q) ∈ S2.
Recall that the change of entropy is ∫ gt(p,q) log |det Jf (p,q)| d(p,q). As log(1 + r) ≥ r1+r for any r > −1, the change of entropy is at least∫ S1 gt(p,q) log ( 1 + δ2c(A)2 8 · 2 ) d(p,q) + ∫ S2 gt(p,q) log(1− 3) d(p,q)
≥ δ 2c(A)2 · 2/8
1 + δ2c(A)2 · 2/8 ∫ S1 gt(p,q) d(p,q)− 3 1− 3 ∫ S2 gt(p,q) d(p,q).
In Theorem 4.3, for any fixed δ and c(A), the lower bound of λ decreases with . In particular, if = δ2c(A)2/64, the lower bound is 1/4, i.e. it only requires a small probability in S1 for the DE to strictly increase.
Theorem 4.3 indicates that the DE growth is at least linear (Ω(T )) as long as the 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 T )) 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 is insufficient amount of probability lying in S1 after a sufficiently long time. We formalize this in Theorem 4.5 below.
Lemma 4.4 Suppose the initial distribution has bounded support in [−b, b]n+m, 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 |pt+1j − ptj | ≤ and |qt+1k − qtk| ≤ . Thus, the distribution at time T has bounded support in [− T − b, T + b]n+m. Within this box, the maximal differential entropy is attained by the uniform distribution over it, which is (n+m) log( T + b).
Theorem 4.5 For any non-trivial two-player zero-sum games (A,−A), with MWU dynamics of step-size ≤ min{1/(32n2m2), δ2c(A)2/8}, for any initial distribution with bounded support, and for any λ > 16 δ2c(A)2 , there exists an infinite sequence of times (T1, T2, · · · ) such that the probability in S2 at each round Ti is at least 1− λ.
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.

heading: 4.2 MWU IN ONE POPULATION GAME
text: Recall from (5) that in one-population game A, MWU dynamics in the cumulative payoff space is
pt+1 = pt + ·Ax(pt), where xk(pt) = exp(ptk)∑ k′ exp(p t k′) .
Similar to the two-player zero-sum games, we also consider two different regions: the interior region S1 = {p | x(p) ≥ δ}, and the boundary region S2, which is the complement to S1. Let gt(p) denote the probability density of p at time t. We will show that for some sub-classes of onepopulation 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 t, the probability of pt ∈ S2 will be at least a constant. First of all, we present the Jacobian analysis of such systems.
Jacobian Analysis. The Jacobian of the dynamics is J = I + ·R, where I is the n× n identity matrix, and R is an n× n matrix, in which
Rjk = Ajk exp(pk)∑ k′′ exp(pk′′) − ∑ k′ Ajk′ exp(pk′) exp(pk) ( ∑ k′′ exp(pk′′)) 2 = xk(p)
( Ajk −
∑ k′ Ajk′xk′(p)
) .
For simplicity, with a little abuse of notation, we use xk as a shorthand of xk(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 :
det(J(p)) = 1 + · (first order term) + 2 · (second order term) + · · · ,
where the first order term is∑ k Rkk = ∑ k xkAkk − ∑ k,k′ xkxk′Akk′ = 1 2 ∑ k 6=k′ xkxk′(Akk +Ak′k′ −Akk′ −Ak′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-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 Akk + Ak′k′ ≥ Akk′ + Ak′k for all k, k′. Moreover, if Akk + Ak′k′ ≥ Akk′ + Ak′k for all k, k′ and the inequality is strict for some k, k′, then the first order term is strictly positive for all x ≥ δ.
In the terminology of mathematical biology, Akk is the payoff to species k for the intra-species play within the species, while Akk′ is the payoff to species k for the inter-species play between species k and k′. Informally speaking, the condition in the above lemma is: the one-population game rewards intra-species play more than to inter-species play.
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 4.6, a clear sufficient condition is: Akk + Ak′k′ ≥ Akk′ + Ak′k for all k 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) = 1 2 ·maxk,k′{Akk +Ak′k′ −Akk′ −Ak′k}.
For the first case, we now bound the higher order terms. Note that since |Akk′ | ≤ 1 and hence |Rkk′ | ≤ 2. When expanding the determinant using the Leibniz formula, we get a polynomial of . For any i ≥ 2, each i term in the expansion must be of the format i times a product of i factors of the form Rk1,k2 , so each such term has absolute value bounded by 2
i i. To count the number of such terms, note that within each term, the collection of k1’s is same as the collection of k2’s, but the order of k2 can be any permutation of the k1’s. A simple counting shows there are at most( n i ) · i! ≤ ni such terms, and hence the i-th order coefficient is bounded by ni · 2i. Therefore, when
≤ δ 2s(A) 16n2 , det J(p) ≥ 1 + δ2s(A) 2 · for all p ∈ S1, and det J(p) ≥ 1 − 8n
2 2 for all p ∈ S2. With a similar argument as in two-player zero-sum game, we achieve the following theorems.
Theorem 4.7 If ∫ S1 gt(p) dp ≥ λ, then the entropy will increase by at least δ 2s(A)· /2 1+δ2s(A)· /2 · λ −
8n2 2 1−8n2 2 · (1− λ) in round t, which is strictly positive whenever λ > 32n2 δ2s(A) .
Theorem 4.8 In a population game A such that Akk + Ak′k′ ≥ Akk′ + Ak′k for all k and k′ and there exist k and k′ such that the inequality is strict, with MWU dynamics of step-size ≤ δ
2s(A) 16n2 ,
for any initial distribution with bounded support, and for any λ > 32n 2
δ2s(A) , there exists an infinite series of time (T1, T2, · · · ) such that, for any i, the probability in S2 at round Ti is no less than 1−λ.
In Appendix C, in the same spirit we did in Figure 2, we present a few plots of MWU in an one-population game that satisfies the condition in the above theorem.
Next, we consider the case that Akk + Ak′k′ = Akk′ + Ak′k for all k and k′. In this case, the first order term is 0. Therefore, we will focus on the second order term, which is∑
k1<k2
(Rk1k1Rk2k2 −Rk1k2Rk2k1)
= −1 2 ∑ k1,k2 xk1xk2 ( Ak1k2 − ∑ k′ Ak1k′xk′ )( Ak2k1 − ∑ k′ Ak2,k′xk′ ) . Let C(A,B)(x,y) = − ∑ k1,k2 xk1yk2 (Ak1k2 − ∑ k′ Ak1k′yk′) (Bk1k2 − ∑ k′ Bk′,k2xk′). Then the second order term is 12C(A,A>)(x,x). We will show this term is non-negative.
Lemma 4.9 If Akk + Ak′k′ = Akk′ + Ak′k for all k and k′, then 12C(A,A>)(x, x) = 1 2C(A,−A)(x, x) ≥ δ2c(A) 8 .
Proof: By Cheung & Tao (2020), C(A,B)(x, y) = C(A,B+T)(x, y) if Tkk′ = uk + vk′ for all k and k′. As (A>−(−A))ij = Aji+Aij = Aii+Ajj , the first equality holds. The second 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 1 2C(A,A >), which is at least δ 2c(A) 8 in S1. Moreover, the i-th order term is bounded by n i2i i. Therefore, when ≤ δ 2c(A) 256n3 , det J(p) ≥ 1+ δ2c(A) 16 ·
2 for any p ∈ S1, and det J(p) ≥ 1−16n3 3 for x ∈ S2. With this, we obtain the following theorems.
Theorem 4.10 If ∫ S1 gt(p) dp ≥ λ then the entropy will increase by at least δ 2c(A)· 2/16 1+δ2c(A)· 2/16 · λ −
16n3 3 1−16n3 3 · (1− λ) in round t, which is strictly positive whenever λ > 512n3 δ2c(A) .
Theorem 4.11 In a population game A such that Akk + Ak′k′ = Akk′ + Ak′k for all k and k′ and A is non-trivial, with MWU dynamics of step-size ≤ δ 2c(A) 256n3 , for any initial distribution with bounded support, and for any λ > 512n 3
δ2c(A) , there exists an infinite series of time (T1, T2, · · · ) such that, for any i, the probability in S2 at round Ti is at least 1− λ.

heading: REPRODUCIBILITY STATEMENT
text: We present complete proofs for all theoretical results in this work.

heading: ETHICS STATEMENT
text: We do not see any ethical or future societal consequences of this work.

heading: A MOTIVATING EXAMPLE
text: To explain our mathematical model intuitively, we present the following simple one-dimensional example. Let f(x) = 2x, and suppose that X0 is a random variable uniform on the interval [0, 1]. Then X1 = f(X0) becomes another random variable, which is uniform on [0, 2]. Analogously, X2 = f(X1) is a new random variable being uniform on [0, 4]. Generally speaking, the problem is to understand how the initial random variableX0 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-games.
In a learning-in-game system, X0 = (p0,q0) represents a distribution over initial beliefs (initial cumulative payoffs) of the two players, and Xt = (pt,qt) represents the distribution of cumulative payoffs at time t. Such a 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, a 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 a bimatrix game (A,B), the update rule f is given by (4).
Unlike the motivating example, for learning-in-game systems the dimensions can be arbitrarily high, and the update rule is non-linear. Thus, deriving the exact evolution of the distribution of Xt 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 in certain one-population games. Section 2 has precise descriptions of the learning algorithms and the games. These results can be extended to a broad family of non-zero-sum and non-coordination games, via the Jacobian analysis by Cheung & Tao (2020). The results also extend to gradient ascent, as it is known to be a special case of FTRL.

heading: B MORE APPLICATIONS

heading: B.1 OMWU IN TWO-PLAYER COORDINATION GAMES
text: A two-player game (A,B) is a coordination game if A = B. Similar to the MWU dynamics in twoplayer zero-sum games, here we also look at two different areas: S1 = {(p, q)|x(p) ≥ δ and y(q) ≥ δ} and S2, which is the complement to S1, S2 = S1. For a coordination game (A,A), Cheung & Piliouras (2020) showed that when (p, q) ∈ S1, then det Jf (x) ≥ 1 + δ 2c(A)2 8 · 2 when is small enough and, when (p, q) ∈ S2, then det Jf (x) ≥ 1 − O( 3). Therefore, by a calculation which is similar to MWU in two-player zero-sum game, we obtain the following theorems.
Theorem B.1 If ∫ S1 gt(p,q) d(p,q) ≥ λ then the entropy increases by at least δ 2c(A)2· 2/8 1+δ2c(A)2· 2/8 ·λ− O( 3) · (1− λ).
Theorem B.2 For any non-trivial two-player coordination games (A,A), with OMWU dynamics of a small enough step-size , for any initial distribution with bounded support, and for any λ such that = o(λ), there exists an infinite series of time (T1, T2, · · · ), such that the probability in S2 at round Ti is at least 1− λ.

heading: B.2 OMWU IN ONE POPULATION GAMES
text: As pointed out in Cheung & Piliouras (2020), the continuous analogue of OMWU, in the context of online learning, is as follows. There are n actions. Let p(t) ∈ Rn denote the cumulative payoff vector up to time t, and u(t) ∈ Rn denote the instantaneous payoff vector to the n actions at time t. The continuous analogue is ṗ = u + · u̇. (8) In one-population game, u(t) = A ·x(t), where for the logit conversion used in MWU and OMWU, xk = exp(pk)/ ∑ ` exp(p`). It is easy to compute that
∂xk ∂pk = xk − (xk)2 and ∂xk ∂x` = −xkx` when ` 6= k.
Then for any ` = 1, 2, . . . , n, we have ∂[Ax]j ∂p` = ∑ k Ajk · ∂xk ∂p` = Aj`x` − ∑ k Ajkxkx` = x` (Aj` − [Ax]j) .
Following the notation in MWU case, ∂[Ax]j∂p` = Rj`. By the chain rule, we have
u̇j = d[Ax]j
dt = n∑ `=1 Rj` · ṗ`.
Putting the above equality into (8) yields ṗj = [Ax]j + · n∑ `=1 Rj` · ṗ`,
which is a recurrence of the variables ṗ1, ṗ2, . . . , ṗn. Unwinding this recurrence yields ṗj = [Ax]j + · n∑ `=1 Rj` · [Ax]` + O( 2).
The above system, upon Euler discretization to a discrete-time dynamical system with time interval , becomes
∀j, pt+1j = p t j + · [Ax]j + 2 · n∑ `=1 Rj` · [Ax]` + O( 3). (9)
Observe that on the RHS of (9), the first two terms coincide with that in the MWU case. The remaining terms can be viewed as a second-order perturbation. Consequently, the Jacobian of the system equation 9 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 j=1Rjj .
Therefore, for the case that Akk +Ak′k′ ≥ Akk′ +Ak′k for all k and k′ and there exist k and k′ such that the inequality is strict, we obtain the following theorems. Recall that S1 = {p|x(p) ≥ δ} and S2, which is the complement to S1, S2 = S1; and s(A) = maxk,k′{Akk+Ak′k′−Akk′−Ak′k}.
Theorem B.3 If ∫ S1 gt(p) dp ≥ λ, then the entropy increases by at least δ 2s(A) /2 1+δ2s(A) /2 · λ−O(
2) · (1− λ) for a small enough step size .
Theorem B.4 In an one-population game A such that Akk +Ak′k′ ≥ Akk′ +Ak′k for all k and k′ and there exist k and k′ such that the inequality is strict, with OMWU dynamics with a small enough step-size , for any initial distribution with bounded support, and for any λ such that = o(λ), there exists an infinite series of time (T1, T2, · · · ) such that, for any i, the probability in S2 at round Ti is no less than 1− λ.
For the case thatAkk+Ak′k′ = Akk′+Ak′k for all k and k′, we consider the second-order term. The second-order terms of the two determinants (MWU and OMWU) are not the same though. The second-order term of the determinant of Jacobian for the OMWU case is∑
1≤j<k≤n
RjjRkk − ∑
1≤j<k≤n
RjkRkj + n∑ j=1 n∑ `=1 Rj`R`j + n∑ j=1 n∑ `=1 ∂Rj` ∂pj · [Ax]`.
Observe that the first two summations are just the same as those in the MWU case. Next, a straightforward calculation gives
∂Rj` ∂pj = Rjj · 1j=` − xjRj` − x`Rjj ,
where 1j=` = 1 if j = `, and 0 otherwise. Hence n∑ j=1 n∑ `=1 ∂Rj` ∂pj · [Ax]` = n∑ j=1 Rjj · [Ax]j − n∑ j=1 n∑ `=1 (xjRj` + x`Rjj) · [Ax]j
= n∑ j=1 Rjj · [Ax]j − n∑ j=1 xj [Ax]j n∑ `=1 Rj` − n∑ j=1 Rjj [Ax]j n∑ `=1 x`.
Since ∑n `=1 x` = 1 and ∑n `=1Rj` = 0, we have ∑n j=1 ∑n `=1 ∂Rj` ∂pj · [Ax]` = 0. To conclude, the second-order term is ∑ 1≤j<k≤n RjjRkk − ∑ 1≤j<k≤n RjkRkj + n∑ j=1 n∑ `=1 Rj`R`j
= n∑ j=1 (Rjj) 2 + ∑ 1≤j<k≤n RjjRkk + ∑ 1≤j<k≤n RjkRkj
=  n∑ j=1 Rjj 2 − ∑ 1≤j<k≤n RjjRkk + ∑ 1≤j<k≤n RjkRkj
Note that whenAkk+Ak′k′ = Akk′+Ak′k for all k and k′, ∑ j Rjj = 0. Therefore, the second order term of OMWU is the negative of the second order term of MWU, which will be smaller than − δ
2c(A) 8 .
Theorem B.5 In an one-population game A such that Akk +Ak′k′ ≥ Akk′ +Ak′k for all k and k′, with OMWU dynamics, if ∫ p∈S1 g(p) dp ≥ λ, then the entropy decreases by at least δ2c(A)2 2
1+δ2c(A)2 2 · λ−O( 3) · (1− λ) for a small enough step size .

heading: B.3 PERTURBATIONS TO PAYOFFS
text: In the main body, we focus on two-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.
First, we define the following function on the cumulative payoff space of two-player games, which depends on a matrix M ∈ Rn×m.4
LM(p,q) := 1
4 ∑ 1≤j,j′≤n 1≤k,k′≤m xj(p)xj′(p)yk(q)yk′(q) · (Mjk +Mj′k′ −Mjk′ −Mj′k)2,
where xj , xj′ , yk, yk′ is as defined in (2). For any general game (A,B), we can decompose it into the sum of a zero-sum game and a coordination game as (A,B) = (Z,−Z) + (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,B) is 1 + (LZ(p,q)− LC(p,q)) 2 + O( 4). We rewrite LZ(p,q)− LC(p,q) as 1
4 ∑ 1≤j,j′≤n 1≤k,k′≤m xj(p)xj′(p)yk(q)yk′(q) · (Ajk +Aj′k′ −Ajk′ −Aj′k)(Bjk′ +Bj′k −Bjk −Bj′k′).
Thus, if
max j,j′,k,k′
[(Ajk +Aj′k′ −Ajk′ −Aj′k)(Bjk′ +Bj′k −Bjk −Bj′k′)] ≥ L > 0 (10)
and min
j,j′,k,k′ [(Ajk +Aj′k′ −Ajk′ −Aj′k)(Bjk′ +Bj′k −Bjk −Bj′k′)] ≥ 0, (11)
then in the domain S1 = {(p,q) | ∀j, k, xj(p) ≥ δ and yk(q) ≥ δ}, the determinant is at least 1 + δ4L 2/8 for all sufficiently small .
Since the product (Ajk +Aj′k′ −Ajk′ −Aj′k)(Bjk +Bj′k′ −Bjk′ −Bj′k) depends on A,B continuously, it is natural to expect that when A,B are slightly perturbed, the value of the product
4This function was denoted by C(M,−M)(p,q) in Cheung & Tao (2020), but to avoid confusion and cluster of notation, we change it to LM(p,q).
changes also slightly. To make this precise, we suppose that in each round t, the actual payoff matrices are (At,Bt), and their entries are perturbations from (A,B) by at most an absolute value of β ≤ 2.5 Recall that the entries in A,B are bounded in the interval [−1, 1], so the absolute values of Ajk + Aj′k′ − Ajk′ − Aj′k and Bjk′ + Bj′k − Bjk − Bj′k′ are bounded by 4, while the perturbations to their values are bounded by 4β. By the lemma below, for the game (At,Bt), the bound in (10) still hold by replacing its lower bound with L− 34β, and the bound in (11) still hold by replacing its lower bound with −34β. Thus the determinant of the Jacobian matrix in S1 is at least 1 + (δ4L/4− 34β) 2/2 ≥ 1 + δ4L 2/16 if β ≤ δ4L/272.
Lemma B.6 If β ≤ 2, |a|, |b| ≤ 4 and |a′ − a|, |b′ − b| ≤ 4β, then a′b′ ≥ ab− 34β.
Proof: Let a′− a = βa, b′− b = βb. Then a′b′− ab = bβa + aβb +βaβb ≥ −16β− 16β−β2 ≥ −34β.

heading: C PLOTS OF UNCERTAINTY EVOLUTION OF MWU IN ONE-POPULATION GAME
text: 2.0 1.5 1.0 0.5 0.0 0.5 1.0 1.5 2.0 2.0
1.5
1.0
0.5
0.0
0.5
1.0
1.5
2.0
2.0 1.5 1.0 0.5 0.0 0.5 1.0 1.5 2.0 2.0
1.5
1.0
0.5
0.0
0.5
1.0
1.5
2.0
2.0 1.5 1.0 0.5 0.0 0.5 1.0 1.5 2.0 2.0
1.5
1.0
0.5
0.0
0.5
1.0
1.5
2.0
1.5 1.0 0.5
0.0 0.5
1.0 1.5
0.75 0.50
0.25 0.00
0.25 0.50
0.75 1.00
0.38
0.40
0.42
0.44
0.46
Figure 2: We plot the evolution of uncertainty for MWU in an one-population game specified by
the matrix A =
[
0.1 1.0 −1.0 −1.0 0.1 1.0 1.0 −1.0 0.1
]
, with step-size = 0.01. As we did in Figure 2, in the top 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.
5We assume that the entries in both (A,B) and (At,Bt) are in the interval [−1, 1], so β is at most 2.

Review summaries:
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.

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.  The 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.