Convergence to Nash Equilibrium and No-regret Guarantee in (Markov)
  Potential Games
Jing Dong Baoxiang Wang Yaoliang Yu
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 carefully
balancing the reuse of past samples and exploration of new samples, we then
extend the results to Markov potential games and improve the best available
Nash regret from $O(T^{5/6})$ to $O(T^{4/5})$. Moreover, our algorithm requires
no knowledge of the game, such as the distribution mismatch coefficient, which
provides more flexibility in its practical implementation. Experimental results
corroborate our theoretical findings and underscore the practical effectiveness
of our method.