Finite-Sample Guarantees for Learning Dynamics in Zero-Sum Polymatrix Games
Not on the map. Why?
Abstract (arXiv)
We study best-response type learning dynamics for zero-sum polymatrix games under two information settings. The two settings are distinguished by the type of information that each player has about the game and their opponents' strategy. The first setting is the full information case, in which each player knows their own and their opponents' payoff matrices and observes everyone's mixed strategies. The second setting is the minimal information case, where players do not observe their opponents' strategies and are not aware of any payoff matrices (instead they only observe their realized payoffs). For this setting, also known as the radically uncoupled case in the learning in games literature, we study a two-timescale learning dynamics that combine smoothed best-response type updates for strategy estimates with a TD-learning update to estimate a local payoff function. For these dynamics, without additional exploration, we provide polynomial-time finite-sample guarantees for convergence to an ε-Nash equilibrium.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 13 of its 43 references that are in the map. First posted on arXiv 29 Jul 2024.
Builds on
13 of 43 references.
References · 13
- 2013Optimization, Learning, and Games with Predictable Sequencescited by 187
- 2015Fast Convergence of Regularized Learning in Gamescited by 149
- 2022A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Gamescited by 64
- 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 61
- 2020Hedging in games: Faster convergence of external and swap regretscited by 57
- 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
- 2021Decentralized Q-Learning in Zero-sum Markov Gamescited by 53
- 2022Mastering the Game of No-Press Diplomacy via Human-Regularized Reinforcement Learning and Planningcited by 47
- 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 28
- 2021Exploration-Exploitation in Multi-Agent Competition: Convergence with Bounded Rationalitycited by 20
- 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
- 2014A Counter-Example to Karlin's Strong Conjecture for Fictitious Playcited by 10
1 more
- 2022Asynchronous Gradient Play in Zero-Sum Multi-agent Gamescited by 5
Built on by
Citing papers per year: 2026: 2.
2 papers.