SOURCE-LINKED INTELLIGENCE

Independent Reinforcement Learning in Discounted Markov Games

arXiv · AI, language, vision and robotics · article · Sep 1, 2026 · UTC

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 provide what appears to be the first \emph{radically uncoupled} algorithm with sub-exponential convergence guarantees to coarse correlated equilibria in discounted

Read original source ↗ Open in workspace

recordType

paper

region

Global