{"id":"arxiv/2609.00504","url":"https://arxiv.org/abs/2609.00504","tags":["cs.GT","cs.AI","cs.LG","eess.SY","math.OC"],"score":0,"title":"Independent Reinforcement Learning in Discounted Markov Games","domain":"cs.GT","source":"arxiv","authors":["Asrin Efe Yorulmaz","Ugur Aydin","Tamer Basar"],"reviews":0,"subject":"cs.GT","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-01","reactions":{}}