# Independent Reinforcement Learning in Discounted Markov Games

arXiv: https://arxiv.org/abs/2609.00504 · HTML: https://mlsanity.com/paper/2609.00504/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Multi-agent reinforcement learning, one of 15 directions in Deep reinforcement learning methods.
- Builds on 4 of its 77 references that are in the map.
- First posted on arXiv 1 Sep 2026.

## Placed in

- Deep reinforcement learning methods / [Multi-agent reinforcement learning](https://mlsanity.com/deeprl/multi-agent-reinforcement-learning/)

## Builds on (most cited first, 4 of 4)

- [Regret Minimization and Convergence to Equilibria in General-sum Markov Games](https://mlsanity.com/paper/2207.14211/) (2022)
- [Decentralized Best-Response-Based Learning in Two-Player Zero-Sum Stochastic Games: A Finite-Sample Analysis](https://mlsanity.com/paper/2409.01447/) (2024)
- [Convergence of Decentralized Actor-Critic Algorithm in General-sum Markov Games](https://mlsanity.com/paper/2409.04613/) (2024)
- [Near Optimal Convergence to Coarse Correlated Equilibrium in General-Sum Markov Games](https://mlsanity.com/paper/2511.02157/) (2025)

## Built on by (most cited first, 1 of 1)

- [Normal-Form Correlation in Markov Games](https://mlsanity.com/paper/2610.03621/) (2026)

## Abstract (arXiv)

In this work, we study radically uncoupled learning in discounted general-sum Markov games. Assuming ``mathsfETH for mathsfPPAD", 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 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 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.