Agents
Independent Reinforcement Learning in Discounted Markov Games
arXiv:2609.00504v1 Announce Type: cross Abstract: In this work, we study radically uncoupled learning in discounted general-sum Markov games. Assuming ``mathsf{ETH} for mathsf{PPAD}', we show that, fo
arXiv:2609.00504v1 Announce Type: cross Abstract: 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 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.
Related
- When Actions Disappear: Adversarial Action Removal in Self-Play Reinforcement Learning
- The Bidding Games: Reinforcement Learning for MEV Extraction on Polygon Blockchain
- CCKS: Consensus-based Communication and Knowledge Sharing
- A Survey of Multi-Agent Deep Reinforcement Learning with Graph Neural Network-Based Communication
Source: arXiv cs.AI | 2026-09-02