Policy update method converges fast in multi-player zero sum games
Last-Iterate Convergence of Policy Dynamics in Zero-Sum Networked Separable Markov Games
Computer Science and Game Theory
Summary
Finding stable strategies (Nash equilibria) in games where multiple players interact over time is usually very hard. The authors study a special kind of game where players compete in pairs and all interactions together form a network. They introduce a new way for players to update their strategies that is simple and efficient. Their method quickly finds an approximate solution that no player can benefit from changing, and they prove it converges reliably after a certain number of steps.
What this means in practice
- •For multi-agent system developers: Design stable strategy updates for competitive environments where agents interact over networks with pairwise zero-sum relations.
- •For reinforcement learning engineers: Implement faster and reliable policy optimization algorithms for structured multi-player games with known transitions and full information.
Authors
Zailin Ma
Abstract
Solving Nash equilibria for general multi-player Markov games is computationally intractable, while two-player zero-sum Markov games admit fast last-iterate policy-optimization methods. Finite-horizon zero-sum networked separable Markov games occupy an important middle ground: they retain global competition structure through pairwise interactions, while preserving computational tractability of Nash equilibria (NE) in the full-information and known-transition setting. Existing algorithms for this class either proceed through equilibrium-collapse arguments for a simplified setting where a single controller determines the transition probability, or backward dynamic programming that relies on equilibrium solvers at each stage. However, the design and analysis of direct policy-update approaches remain inadequate. To address this issue, we propose the entropy-regularized optimistic multiplicative weights update (ER-OMWU), a complementary single-loop policy dynamic that updates players' policies symmetrically and returns an approximate NE in the last iteration. We provide a first last-iterate convergence analysis of policy dynamics in the games of interest: after $\widetilde{O}(1/ε)$ iterations, the returned policy is an $ε$-approximate Nash equilibrium. The result preserves the near-linear convergence rate achieved by policy optimization in two-player zero-sum Markov games, but extends the policy-dynamics viewpoint to a more complicated but structured multi-player setting.