Independent Reinforcement Learning in Discounted Markov Games

In this work, we study radically uncoupled learning in discounted general-sum Markov games. Assuming “$\mathsf{ETH}$ for $\mathsf{PPAD}$", we show that, for every fixed discount factor, there is no polynomial-time algorithm for computing inverse-polynomially accurate coarse correlated equilibria in discounted general-sum Markov games when players learn independently in decentralized settings. Complementing this hardness result, we present what appears to be the first radically uncoupled algorithm that achieves sub-exponential convergence to coarse correlated equilibria in discounted general-sum Markov games, without imposing any structural assumptions on the game, under both full-feedback and partial-feedback settings. Our approach builds on a layered variant of optimistic mirror descent, equipped with an increasing step-size schedule designed to address the multi-agent setting.