Timezone: »
We perform volume analysis of Multiplicative Weights Updates (MWU) and its optimistic variant (OMWU) in zero-sum as well as coordination games. Our analysis provides new insights into these game/dynamical systems, which seem hard to achieve via the classical techniques within Computer Science and Machine Learning.
First, we examine these dynamics not in their original space (simplex of actions) but in a dual space (aggregate payoffs of actions). Second, we explore how the volume of a set of initial conditions evolves over time when it is pushed forward according to the algorithm. This is reminiscent of approaches in evolutionary game theory where replicator dynamics, the continuous-time analogue of MWU, is known to preserve volume in all games. Interestingly, when we examine discrete-time dynamics, the choices of the game and the algorithm both play a critical role. So whereas MWU expands volume in zero-sum games and is thus Lyapunov chaotic, we show that OMWU contracts volume, providing an alternative understanding for its known convergent behavior. Yet, we also prove a no-free-lunch type of theorem, in the sense that when examining coordination games the roles are reversed.
Using these tools, we prove two novel, rather negative properties of MWU in zero-sum games. (1) Extremism: even in games with a unique fully-mixed Nash equilibrium, the system recurrently gets stuck near pure-strategy profiles, despite them being clearly unstable from game-theoretic perspective. (2) Unavoidability: given any set of good states (with a rather relaxed interpretation of “good” states), the system cannot avoid bad states indefinitely.
Author Information
Yun Kuen Cheung (Royal Holloway University of London)
Georgios Piliouras (Singapore University of Technology and Design)
More from the Same Authors
-
2020 Poster: No-Regret Learning and Mixed Nash Equilibria: They Do Not Mix »
Emmanouil-Vasileios Vlatakis-Gkaragkounis · Lampros Flokas · Thanasis Lianeas · Panayotis Mertikopoulos · Georgios Piliouras -
2020 Poster: Efficient Online Learning of Optimal Rankings: Dimensionality Reduction via Gradient Descent »
Dimitris Fotakis · Thanasis Lianeas · Georgios Piliouras · Stratis Skoulakis -
2020 Poster: The route to chaos in routing games: When is price of anarchy too optimistic? »
Thiparat Chotibut · Fryderyk Falniowski · Michał Misiurewicz · Georgios Piliouras -
2020 Spotlight: No-Regret Learning and Mixed Nash Equilibria: They Do Not Mix »
Emmanouil-Vasileios Vlatakis-Gkaragkounis · Lampros Flokas · Thanasis Lianeas · Panayotis Mertikopoulos · Georgios Piliouras -
2019 Poster: Efficiently avoiding saddle points with zero order methods: No gradients required »
Emmanouil-Vasileios Vlatakis-Gkaragkounis · Lampros Flokas · Georgios Piliouras -
2019 Poster: Poincaré Recurrence, Cycles and Spurious Equilibria in Gradient-Descent-Ascent for Non-Convex Non-Concave Zero-Sum Games »
Emmanouil-Vasileios Vlatakis-Gkaragkounis · Lampros Flokas · Georgios Piliouras -
2019 Spotlight: Poincaré Recurrence, Cycles and Spurious Equilibria in Gradient-Descent-Ascent for Non-Convex Non-Concave Zero-Sum Games »
Emmanouil-Vasileios Vlatakis-Gkaragkounis · Lampros Flokas · Georgios Piliouras -
2019 Poster: Fast and Furious Learning in Zero-Sum Games: Vanishing Regret with Non-Vanishing Step Sizes »
James Bailey · Georgios Piliouras