2024/06/15 by Yi Feng, Georgios Piliouras, Feng, Yi +3 · 1 citation
Computer Science · #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Neural Networks and Applications
paper · pdf · doi:10.48550/arxiv.2406.10603
openalex publication_date 2024/06/15 · openalex created_date 2024/06/19 · openalex updated_date 2026/07/28
We investigate the accuracy of prediction in deterministic learning dynamics of zero-sum games with random initializations, specifically focusing on observer uncertainty and its relationship to the evolution of covariances. Zero-sum games are a prominent field of interest in machine learning due to their various applications. Concurrently, the accuracy of prediction in dynamical systems from mechanics has long been a classic subject of investigation since the discovery of the Heisenberg Uncertainty Principle. This principle employs covariance and standard deviation of particle states to measure prediction accuracy. In this study, we bring these two approaches together to analyze the Follow-the-Regularized-Leader (FTRL) algorithm in two-player zero-sum games. We provide growth rates of covariance information for continuous-time FTRL, as well as its two canonical discretization methods (Euler and Symplectic). A Heisenberg-type inequality is established for FTRL. Our analysis and experiments also show that employing Symplectic discretization enhances the accuracy of prediction in learning dynamics.