# On the Global Convergence Rates of Decentralized Softmax Gradient Play in Markov Potential Games

arXiv: https://arxiv.org/abs/2202.00872 · HTML: https://mlsanity.com/paper/2202.00872/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Feb 2022.

## Built on by (most cited first, 22 of 22)

- [Natural Actor-Critic for Robust Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/2307.08875/) (2023)
- [Independent and Decentralized Learning in Markov Potential Games](https://mlsanity.com/paper/2205.14590/) (2022)
- [Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Games](https://mlsanity.com/paper/2310.09727/) (2023)
- [Convergence Rates for Localized Actor-Critic in Networked Markov Potential Games](https://mlsanity.com/paper/2303.04865/) (2023)
- [Provably Learning Nash Policies in Constrained Markov Potential Games](https://mlsanity.com/paper/2306.07749/) (2023)
- [Markov α-Potential Games](https://mlsanity.com/paper/2305.12553/) (2023)
- [Independent Policy Mirror Descent for Markov Potential Games: Scaling to Large Number of Players](https://mlsanity.com/paper/2408.08075/) (2024)
- [Provable Policy Gradient Methods for Average-Reward Markov Potential Games](https://mlsanity.com/paper/2403.05738/) (2024)
- [Independent Learning in Performative Markov Potential Games](https://mlsanity.com/paper/2504.20593/) (2025)
- [The Oversight Game: Learning to Cooperatively Balance an AI Agent's Safety and Autonomy](https://mlsanity.com/paper/2510.26752/) (2025)
- [High entropy leads to symmetry-equivariant policies in Dec-POMDPs](https://mlsanity.com/paper/2511.22581/) (2025)
- [Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property](https://mlsanity.com/paper/2312.12067/) (2023)
- [Convergence to Nash Equilibrium and No-regret Guarantee in (Markov) Potential Games](https://mlsanity.com/paper/2404.06516/) (2024)
- [Linear Convergence of Independent Natural Policy Gradient in Games with Entropy Regularization](https://mlsanity.com/paper/2405.02769/) (2024)
- [Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibria](https://mlsanity.com/paper/2602.12181/) (2026)
- [Independent Learning of Nash Equilibria in Partially Observable Markov Potential Games with Decoupled Dynamics](https://mlsanity.com/paper/2605.06377/) (2026)
- [Decentralized Diffusion Policy Learning for Enhanced Exploration in Cooperative Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2605.07101/) (2026)
- [Action Dependency Graphs for Globally Optimal Coordinated Reinforcement Learning](https://mlsanity.com/paper/2506.00797/) (2025)
- [Online Multi-Agent Control with Adversarial Disturbances](https://mlsanity.com/paper/2506.18814/) (2025)
- [Internal State-Based Policy Gradient Methods for Partially Observable Markov Potential Games](https://mlsanity.com/paper/2604.00433/) (2026)
- [Distributed Zeroth-Order Policy Gradient for Networked Multi-agent Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2605.15697/) (2026)
- [Fully Online Decentralized Learning in Stochastic Games with Unknown Independent Chains](https://mlsanity.com/paper/2610.01181/) (2026)

## Abstract (arXiv)

Softmax policy gradient is a popular algorithm for policy optimization in single-agent reinforcement learning, particularly since projection is not needed for each gradient update. However, in multi-agent systems, the lack of central coordination introduces significant additional difficulties in the convergence analysis. Even for a stochastic game with identical interest, there can be multiple Nash Equilibria (NEs), which disables proof techniques that rely on the existence of a unique global optimum. Moreover, the softmax parameterization introduces non-NE policies with zero gradient, making it difficult for gradient-based algorithms in seeking NEs. In this paper, we study the finite time convergence of decentralized softmax gradient play in a special form of game, Markov Potential Games (MPGs), which includes the identical interest game as a special case. We investigate both gradient play and natural gradient play, with and without log-barrier regularization. The established convergence rates for the unregularized cases contain a trajectory-dependent constant that can be arbitrarily large, whereas the log-barrier regularization overcomes this drawback, with the cost of slightly worse dependence on other factors such as the action set size. An empirical study on an identical interest matrix game confirms the theoretical findings.