# Markov α-Potential Games

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 57 references that are in the map.
- First posted on arXiv 21 May 2023.

## Builds on (most cited first, 24 of 24)

- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Independent Policy Gradient Methods for Competitive Reinforcement Learning](https://mlsanity.com/paper/2101.04233/) (2021)
- [Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games](https://mlsanity.com/paper/2106.01969/) (2021)
- [When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?](https://mlsanity.com/paper/2110.04184/) (2021)
- [Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization](https://mlsanity.com/paper/2105.15186/) (2021)
- [Decentralized Q-Learning in Zero-sum Markov Games](https://mlsanity.com/paper/2106.02748/) (2021)
- [Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence](https://mlsanity.com/paper/2202.04129/) (2022)
- [Policy Optimization Provably Converges to Nash Equilibria in Zero-Sum Linear Quadratic Games](https://mlsanity.com/paper/1906.00729/) (2019)
- [Independent Natural Policy Gradient Always Converges in Markov Potential Games](https://mlsanity.com/paper/2110.10614/) (2021)
- [Decentralized Q-Learning for Stochastic Teams and Games](https://mlsanity.com/paper/1506.07924/) (2015)
- [Gradient play in stochastic games: stationary points, convergence, and sample complexity](https://mlsanity.com/paper/2106.00198/) (2021)
- [On Last-Iterate Convergence Beyond Zero-Sum Games](https://mlsanity.com/paper/2203.12056/) (2022)
- [On the Global Convergence Rates of Decentralized Softmax Gradient Play in Markov Potential Games](https://mlsanity.com/paper/2202.00872/) (2022)
- [Independent and Decentralized Learning in Markov Potential Games](https://mlsanity.com/paper/2205.14590/) (2022)
- [Learning Parametric Closed-Loop Policies for Markov Potential Games](https://mlsanity.com/paper/1802.00899/) (2018)
- [Decentralized Learning for Optimality in Stochastic Dynamic Teams and Games with Local Control and Global State Information](https://mlsanity.com/paper/1903.05812/) (2019)
- [Best-Response Dynamics and Fictitious Play in Identical-Interest and Zero-Sum Stochastic Games](https://mlsanity.com/paper/2111.04317/) (2021)
- [Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularization](https://mlsanity.com/paper/2204.05466/) (2022)
- [Learning in Congestion Games with Bandit Feedback](https://mlsanity.com/paper/2206.01880/) (2022)
- [Satisficing Paths and Independent Multi-Agent Reinforcement Learning in Stochastic Games](https://mlsanity.com/paper/2110.04638/) (2021)
- [Convergence Rates for Localized Actor-Critic in Networked Markov Potential Games](https://mlsanity.com/paper/2303.04865/) (2023)
- [Potential iLQR: A Potential-Minimizing Controller for Planning Multi-Agent Interactive Trajectories](https://mlsanity.com/paper/2107.04926/) (2021)
- [Episodic Logit-Q Dynamics for Efficient Learning in Stochastic Teams](https://mlsanity.com/paper/2205.13266/) (2022)
- [Decentralized Fictitious Play in Near-Potential Games with Time-Varying Communication Networks](https://mlsanity.com/paper/2103.09845/) (2021)

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

- [Fast Policy Learning for Linear Quadratic Control with Entropy Regularization](https://mlsanity.com/paper/2311.14168/) (2023)
- [Provable Policy Gradient Methods for Average-Reward Markov Potential Games](https://mlsanity.com/paper/2403.05738/) (2024)
- [MF-OML: Online Mean-Field Reinforcement Learning with Occupation Measures for Large Population Games](https://mlsanity.com/paper/2405.00282/) (2024)
- [Exploiting Approximate Symmetry for Efficient Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2408.15173/) (2024)
- [Convergence to Nash Equilibrium and No-regret Guarantee in (Markov) Potential Games](https://mlsanity.com/paper/2404.06516/) (2024)
- [Simulation-Based Optimistic Policy Iteration For Multi-Agent MDPs with Kullback-Leibler Control Cost](https://mlsanity.com/paper/2410.15156/) (2024)

## Abstract (arXiv)

We propose a new framework of Markov α-potential games to study Markov games. We show that any Markov game with finite-state and finite-action is a Markov α-potential game, and establish the existence of an associated α-potential function. Any optimizer of an α-potential function is shown to be an α-stationary Nash equilibrium. We study two important classes of practically significant Markov games, Markov congestion games and the perturbed Markov team games, via the framework of Markov α-potential games, with explicit characterization of an upper bound for α and its relation to game parameters. Additionally, we provide a semi-infinite linear programming based formulation to obtain an upper bound for α for any Markov game. Furthermore, we study two equilibrium approximation algorithms, namely the projected gradient-ascent algorithm and the sequential maximum improvement algorithm, along with their Nash regret analysis, and corroborate the results with numerical experiments.