Markov α-Potential Games: Equilibrium Approximation and Regret Analysis
share
This paper proposes a new framework to study multi-agent interaction in Markov games: Markov α-potential games. Markov potential games are special cases of Markov α-potential games, so are two important and practically significant classes of games: Markov congestion games and perturbed Markov team games. In this paper, α-potential functions for both games are provided and the gap α is characterized with respect to game parameters. Two algorithms – the projected gradient-ascent algorithm and the sequential maximum improvement smoothed best response dynamics – are introduced for approximating the stationary Nash equilibrium in Markov α-potential games. The Nash-regret for each algorithm is shown to scale sub-linearly in time horizon. Our analysis and numerical experiments demonstrates that simple algorithms are capable of finding approximate equilibrium in Markov α-potential games.
READ FULL TEXT