Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.

main_review: Questions:
* Fig. 1 is extremely unclear, and it would be better to explain the meaning of each sub-fig in the caption or main text.
* 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_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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.
main_review: Strengths
 - Enables looking at differential entropy, and not just the volume, of a distribution of strategies for a game.
 - 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.
 - Contributes a possibly novel analysis of the determinant of a Jacobian of a population game
 - Results are claimed to be robust to small perturbations in the game.

Weaknesses
 - 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.)
 - 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.
 - 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.

Minor comments
 - 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"
 - pg. 2 "more probably to occur" -> "more probable to occur"
 - pg. 4 after eq (1) "depending on the value of qt" -> "depending on the value of pt"
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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). 
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.
The 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. 

1. Second line below eq (1), what is q^t here? should be p^t?
2. 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?
3. 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?

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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 
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.
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. 

In my opinion, however, the paper has also some weaknesses:
The 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_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.
Hence, my accept score.
review_title: null

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)