  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 thus, along the way, imply convergence to a correlated
equilibrium. Our algorithm is decentralized, computationally efficient, and
does not require any communication between agents. Our key observation is that
online learning via policy optimization in Markov games essentially reduces to
a form of weighted regret minimization, with unknown weights determined by the
path length of the agents' policy sequence. Consequently, controlling the path
length leads to weighted regret objectives for which sufficiently adaptive
algorithms provide sublinear regret guarantees.
