Independent Reinforcement Learning in Discounted Markov Games
Abstract
In this work, we study radically uncoupled learning in discounted general-sum Markov games. Assuming ``ETH for 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 general-sum Markov games without imposing any structural restrictions on the game. Our algorithm is a \emph{layered} variant of optimistic mirror descent with an increasing step-size schedule tailored to the multi-agent setting. Finally, we develop both full-feedback and partial feedback versions of the aforementioned algorithm and establish sub-exponential convergence guarantees for each case.
Related
- Horizon-Independent Contraction for Continuous-Time Discounted Regularized Mean-Field Games
- High-Probability Nash Regret for Decentralized Learning in Markov α-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games
- Continuous-Time Reinforcement Learning for N-Player Stochastic Differential Games with Exploratory Policies
- Near-Optimal √K-Regret for Online Learning in Uninformed Markov Games
- Reinforcement Learning with Markov Risk Measures and Multipattern Risk Approximation
BibTeX
@misc{yorulmaz2026independent,
title = {{Independent Reinforcement Learning in Discounted Markov Games}},
author = {Asrin Efe Yorulmaz and Ugur Aydin and Tamer Basar},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.00504},
eprint = {2609.00504},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.00504},
}
RIS
TY - UNPB
TI - Independent Reinforcement Learning in Discounted Markov Games
AU - Asrin Efe Yorulmaz
AU - Ugur Aydin
AU - Tamer Basar
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.00504
UR - https://arxiv.org/abs/2609.00504
AB - In this work, we study radically uncoupled learning in discounted general-sum Markov games. Assuming ``ETH for 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 general-sum Markov games without imposing any structural restrictions on the game. Our algorithm is a \emph{layered} variant of optimistic mirror descent with an increasing step-size schedule tailored to the multi-agent setting. Finally, we develop both full-feedback and partial feedback versions of the aforementioned algorithm and establish sub-exponential convergence guarantees for each case.
ER -