While the OGDA algorithm, first studied in [1]} under a different name, has been extensively used in recent years for learning matrix games (a special case of Markov games with one state), to the best of our knowledge, no previous work has applied it to learning Markov games and derived a concrete last-iterate convergence rate.
Several recent works derive last-iterate convergence of OGDA for matrix games [2]}, [3]}, [4]}, [5]}, [6]},
and our analysis is heavily inspired by the approach of [6]}. However, the extension to infinite-horizon Markov games is highly non-trivial as there is additional “instability penalty” in the system that we need to handle; see sec:analysis for detailed discussions.
