Regret Minimization and Convergence to Equilibria in General-sum Markov Games. (arXiv:2207.14211v1 [cs.LG])

An abundance of recent impossibility results establish that regret
minimization in Markov games with adversarial opponents is both statistically
and computationally intractable. Nevertheless, none of these results preclude
the possibility of regret minimization under the assumption that all parties
adopt the same learning procedure. In this work, we present the first (to our
knowledge) algorithm for learning in general-sum Markov games that provides
sublinear regret guarantees when executed by all agents. The bounds we obtain
are for swap regret, and …

arxiv convergence equilibria games general lg markov