Convergence to Nash Equilibrium and No-regret Guarantee in (Markov) Potential Games

arXiv:2404.06516v1 Announce Type: cross
Abstract: In this work, we study potential games and Markov potential games under stochastic cost and bandit feedback. We propose a variant of the Frank-Wolfe algorithm with sufficient exploration and recursive gradient estimation, which provably converges to the Nash equilibrium while attaining sublinear regret for each individual player. Our algorithm simultaneously achieves a Nash regret and a regret bound of $O(T^{4/5})$ for potential games, which matches the best available result, without using additional projection steps. Through …

abstract algorithm arxiv convergence cost cs.gt cs.lg equilibrium exploration feedback frank games gradient markov nash equilibrium recursive stochastic study type work