mlsanityData to 14 Oct 2026

Markov α-Potential Games

arXiv 2305.12553 ↗First posted 21 May 2023cs.GT cs.AI cs.MAcited by 6

Not on the map. Why?

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.

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

24 of 57 references.

References · 24

  1. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 567
  2. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 101
  3. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 93
  4. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 67
  5. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 63
  6. 2021Decentralized Q-Learning in Zero-sum Markov Gamescited by 58
  7. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 57
  8. 2019Policy Optimization Provably Converges to Nash Equilibria in Zero-Sum Linear Quadratic Gamescited by 42
  9. 2021Independent Natural Policy Gradient Always Converges in Markov Potential Gamescited by 37
  10. 2015Decentralized Q-Learning for Stochastic Teams and Gamescited by 35
  11. 2021Gradient play in stochastic games: stationary points, convergence, and sample complexitycited by 34
  12. 2022On Last-Iterate Convergence Beyond Zero-Sum Gamescited by 31
12 more
  1. 2022On the Global Convergence Rates of Decentralized Softmax Gradient Play in Markov Potential Gamescited by 22
  2. 2022Independent and Decentralized Learning in Markov Potential Gamescited by 22
  3. 2018Learning Parametric Closed-Loop Policies for Markov Potential Gamescited by 21
  4. 2019Decentralized Learning for Optimality in Stochastic Dynamic Teams and Games with Local Control and Global State Informationcited by 13
  5. 2021Best-Response Dynamics and Fictitious Play in Identical-Interest and Zero-Sum Stochastic Gamescited by 10
  6. 2022Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularizationcited by 10
  7. 2022Learning in Congestion Games with Bandit Feedbackcited by 10
  8. 2021Satisficing Paths and Independent Multi-Agent Reinforcement Learning in Stochastic Gamescited by 9
  9. 2023Convergence Rates for Localized Actor-Critic in Networked Markov Potential Gamescited by 9
  10. 2021Potential iLQR: A Potential-Minimizing Controller for Planning Multi-Agent Interactive Trajectoriescited by 8
  11. 2022Episodic Logit-Q Dynamics for Efficient Learning in Stochastic Teamscited by 3
  12. 2021Decentralized Fictitious Play in Near-Potential Games with Time-Varying Communication Networkscited by 2

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 5.

6 papers.

  1. 2023Fast Policy Learning for Linear Quadratic Control with Entropy Regularizationcited by 13
  2. 2024Provable Policy Gradient Methods for Average-Reward Markov Potential Gamescited by 5
  3. 2024MF-OML: Online Mean-Field Reinforcement Learning with Occupation Measures for Large Population Gamescited by 5
  4. 2024Exploiting Approximate Symmetry for Efficient Multi-Agent Reinforcement Learningcited by 2
  5. 2024Convergence to Nash Equilibrium and No-regret Guarantee in (Markov) Potential Gamescited by 1
  6. 2024Simulation-Based Optimistic Policy Iteration For Multi-Agent MDPs with Kullback-Leibler Control Costcited by 0