Metraipolis › archive › dc_91c59f03f4d1

Last-Iterate Convergence of Policy Dynamics in Zero-Sum Networked Separable Markov Games — arXiv:2609.08823

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.08823
License (as archived)
CC0-1.0
Archived
2026-10-16T13:32:14.997Z
SHA-256 of the archived text
472c3bbd4b3fe5f13e902f63e893111e6f41771060ca5c7dc7b18c36cffe6ad5
Stable URL of this page
https://metraipolis.com/documento/dc_91c59f03f4d1

How to cite

Last-Iterate Convergence of Policy Dynamics in Zero-Sum Networked Separable Markov Games — arXiv:2609.08823 — arXiv (en), https://arxiv.org/abs/2609.08823 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_91c59f03f4d1 (Metraipolis archive dc_91c59f03f4d1, sha256 472c3bbd4b3fe5f13e902f63e893111e6f41771060ca5c7dc7b18c36cffe6ad5)
BibTeX
@misc{dc91c59f03f4d1,
  title = {Last-Iterate Convergence of Policy Dynamics in Zero-Sum Networked Separable Markov Games — arXiv:2609.08823},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.08823},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_91c59f03f4d1; sha256 472c3bbd4b3fe5f13e902f63e893111e6f41771060ca5c7dc7b18c36cffe6ad5},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.08823. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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. Zero-sum networked separable Markov games occupy an important middle ground: they retain global multi-player competition structure through pairwise interactions, while preserving computational tractability of Nash equilibria (NE) in the finite-horizon 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 the first last-iterate convergence analysis of policy dynamics in the games of interest: after $\widetilde O\left(1/{\epsilon}\right)$ iterations, the returned policy is an $\epsilon$-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.

Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-09 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2609.08823 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T13:06:09.188Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).