Multiplicative Weights Updates with Constant Step-Size in Graphical Constant-Sum Games
Since Multiplicative Weights (MW) updates are the discrete analogue of the continuous Replicator Dynamics (RD), some researchers had expected their qualitative behaviours would be similar. We show that this is false in the context of graphical constant-sum games, which include two-person zero-sum games as special cases. In such games which have a fully-mixed Nash Equilibrium (NE), it was known that RD satisfy the permanence and Poincaré recurrence properties, but we show that MW updates with any constant step-size ε > 0 converge to the boundary of the state space, and thus do not satisfy the two properties. Using this result, we show that MW updates have a regret lower bound of Ω(1/(εT )), while it was known that the regret of RD is upper bounded by O(1/T ). Interestingly, the regret perspective can be useful for better understanding of the behaviours of MW updates. In a two-person zero-sum game, if it has a unique NE which is fully mixed, then we show, via regret, that for any sufficiently small ε, there exist at least two probability densities and a constant Z > 0, such that for any arbitrarily small z > 0, each of the two densities fluctuates above Z and below z infinitely often.
************* POST-REBUTTAL ******************* I gave an "accept" recommendation during the first review phase, but I was (negatively) surprised when the authors' rebuttal completely ignored part of my review, namely that Theorem 2 has already been reported in a more general, unilateral setting by Sorin (Mathematical Programming, 2009), Hofbauer, Sorin and Viossat (Mathematics of Operations Research, 2009), and subsequently extended to more general dynamics by Kwon and Mertikopoulos (Journal of Dynamics and Games, 2017) and Mertikopoulos, Papadimitriou, and Piliouras (SODA, 2018). In particular, the first and third papers above discuss extensively the interplay between continuous and discrete time - an interplay which plays an important role in the current submission as well - while the second and last papers also identify constants of motion under the replicator dynamics and discuss Poincaré recurrence.  I still believe the paper should be accepted, but I've downgraded my recommendation to a "weak accept" to indicate my reservations concerning the authors' positioning relative to previous work.   ************* PRE-REBUTTAL ******************* In this paper, the authors study the behavior of the multiplicative-weights algorithm with a constant step-size in zero-sum games (both standard, two-player games, and graphical games played over an interaction graph). The authors' main contributions can be summarized as follows:  1. The continuous-time limit of the multiplicative weights algorithm (known as the replicator dynamics in evolutionary game theory) incurs regret that is at most O(1/T) after time T.  2. The dynamics are "permanent" in the sense that every trajectory thereof is contained in a compact set that is disjoint from the boundary of the game's mixed strategy space (i.e. in the long term, the share of every strategy is bounded away from zero).  3. The above conclusions do not hold if the algorithm is run with a constant, positive step-size: in this case, the algorithm's regret is bounded from below as \Omega(1/(epsilon T)) where epsilon is the algorithm's (constant) step-size, and the dynamics are not permanent (nor Poincaré recurrent).  The paper is well-written, clearly structured and I enjoyed reading it. However, some of the authors' contributions are not new (see below), so the overall novelty is limited. Still, the results that are new are (in my opinion) sufficient and will interest the NIPS community, hence my positive evaluation.   My main criticisms are as follows:  1. The fact that the discrete analogue of the replicator dynamics has a different behavior than the continuous dynamics is not as surprising as the authors claim, see for instance the 2009 paper of Sorin in Mathematical Programming and the monograph of Benaïm (1999) on stochastic approximations, where it is made clear that constant step-size discretizations of dynamical systems could have a wildly different behavior than their continuous-time counterparts.  2. The fact that the replicator dynamics (i.e. the continuous-time limit of the multiplicative weights algorithm) lead to O(1/T) regret was first reported by Sorin (Mathematical Programming, 2009) and Hofbauer, Sorin and Viossat (Mathematics of Operations Research, 2009), and subsequently extended to all mirror descent / follow-the-regularized-leader dynamics by Kwon and Mertikopoulos (Journal of Dynamics and Games, 2017) and Mertikopoulos, Papadimitriou and Piliouras (SODA, 2018). In fact, this O(1/T) bound does not even require a game: it holds for arbitrary (measurable) series of payoffs, even if those are not coming from a game.  2. The permanence result for the replicator dynamics is also alluded to in the classical book of Hofbauer and Sigmund and the more recent paper of Hofbauer, Sorin and Viossat (2009). [Granted, these works do not mention graphical zero-sum games, but the essence of the result is there and the proof strategy is exactly the same] See also the SODA 2018 paper of Mertikopoulos, Piliouras, and Papadimitriou where the authors prove a more general   4. In general, why would one want to employ the multiplicative weights algorithm with a constant step-size? As the authors state themselves, achieving no-regret in an anytime setting requires a decreasing step-size anyway (either due to a doubling trick or a sqrt{t} schedule). It is also well-known that a decreasing step-size is much better suited to stochastic environments (which are the norm in any randomized action selection framework), so it is not clear why one would want to use a constant step-size algorithm in the face of uncertainty (either temporal or informational).  There are some further minor issues (such as the requirement that epsilon ≤ 1/4), but these are not important enough to raise here.