Chaos, Extremism and Optimism: Volume Analysis of Learning in Games
Authors: Yun Kuen Cheung, Georgios Piliouras
NeurIPS 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 ML. ... 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. |
| Researcher Affiliation | Academia | Yun Kuen Cheung Royal Holloway University of London yunkuen.cheung@rhul.ac.uk Georgios Piliouras Singapore University of Technology and Design georgios@sutd.edu.sg |
| Pseudocode | No | The paper describes update rules using mathematical equations but does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper only provides a link to an animation: "An animation is available at http://cs.rhul.ac.uk/~cheung/mwu-graphical-matching-pennies.mp4." It does not provide concrete access to source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not involve empirical studies with datasets. Therefore, it does not provide information about public datasets used for training. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical studies with datasets. Therefore, it does not provide information about dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe empirical experiments that would require specific hardware. No hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe empirical experiments with specific software implementations. No software dependencies with version numbers are mentioned. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments. Therefore, it does not provide details about experimental setup, hyperparameters, or training settings. |