Prediction Accuracy of Learning in Games : Follow-the-Regularized-Leader meets Heisenberg

Yi Feng, Georgios Piliouras, Xiao Wang
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:13278-13325, 2024.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-feng24g, title = {Prediction Accuracy of Learning in Games : Follow-the-Regularized-Leader meets Heisenberg}, author = {Feng, Yi and Piliouras, Georgios and Wang, Xiao}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {13278--13325}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/feng24g/feng24g.pdf}, url = {https://proceedings.mlr.press/v235/feng24g.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Prediction Accuracy of Learning in Games : Follow-the-Regularized-Leader meets Heisenberg %A Yi Feng %A Georgios Piliouras %A Xiao Wang %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-feng24g %I PMLR %P 13278--13325 %U https://proceedings.mlr.press/v235/feng24g.html %V 235 %X 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.
APA
Feng, Y., Piliouras, G. & Wang, X.. (2024). Prediction Accuracy of Learning in Games : Follow-the-Regularized-Leader meets Heisenberg. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:13278-13325 Available from https://proceedings.mlr.press/v235/feng24g.html.

Related Material