# Independent Learning in Stochastic Games

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 90 references that are in the map.
- First posted on arXiv 23 Nov 2021.

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

- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Deep Reinforcement Learning for Robotic Manipulation with Asynchronous Off-Policy Updates](https://mlsanity.com/paper/1610.00633/) (2016)
- [Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving](https://mlsanity.com/paper/1610.03295/) (2016)
- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [Provable Self-Play Algorithms for Competitive Reinforcement Learning](https://mlsanity.com/paper/2002.04017/) (2020)
- [Near-Optimal Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2006.12007/) (2020)
- [A Sharp Analysis of Model-based Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2010.01604/) (2020)
- [Independent Policy Gradient Methods for Competitive Reinforcement Learning](https://mlsanity.com/paper/2101.04233/) (2021)
- [Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium](https://mlsanity.com/paper/2002.07066/) (2020)
- [Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2007.07461/) (2020)
- [Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games](https://mlsanity.com/paper/2102.04540/) (2021)
- [Online Reinforcement Learning in Stochastic Games](https://mlsanity.com/paper/1712.00579/) (2017)
- [Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization](https://mlsanity.com/paper/2105.15186/) (2021)
- [Decentralized Q-Learning in Zero-sum Markov Games](https://mlsanity.com/paper/2106.02748/) (2021)
- [The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces](https://mlsanity.com/paper/2106.03352/) (2021)
- [Towards General Function Approximation in Zero-Sum Markov Games](https://mlsanity.com/paper/2107.14702/) (2021)
- [Policy Optimization Provably Converges to Nash Equilibria in Zero-Sum Linear Quadratic Games](https://mlsanity.com/paper/1906.00729/) (2019)
- [Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity](https://mlsanity.com/paper/1908.11071/) (2019)
- [Decentralized Q-Learning for Stochastic Teams and Games](https://mlsanity.com/paper/1506.07924/) (2015)
- [Fictitious play in zero-sum stochastic games](https://mlsanity.com/paper/2010.04223/) (2020)
- [Learning Nash Equilibrium for General-Sum Markov Games from Batch Data](https://mlsanity.com/paper/1606.08718/) (2016)
- [Global Convergence of Policy Gradient for Sequential Zero-Sum Linear Quadratic Dynamic Games](https://mlsanity.com/paper/1911.04672/) (2019)
- [On Reinforcement Learning for Turn-based Zero-sum Markov Games](https://mlsanity.com/paper/2002.10620/) (2020)

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

- [Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence](https://mlsanity.com/paper/2202.04129/) (2022)
- [Policy Mirror Ascent for Efficient and Independent Learning in Mean Field Games](https://mlsanity.com/paper/2212.14449/) (2022)
- [Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Model](https://mlsanity.com/paper/2208.10458/) (2022)
- [Multi-Player Zero-Sum Markov Games with Networked Separable Interactions](https://mlsanity.com/paper/2307.09470/) (2023)
- [Independent Learning in Constrained Markov Potential Games](https://mlsanity.com/paper/2402.17885/) (2024)
- [From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications](https://mlsanity.com/paper/2506.03464/) (2025)
- [Independent Policy Mirror Descent for Markov Potential Games: Scaling to Large Number of Players](https://mlsanity.com/paper/2408.08075/) (2024)
- [Unsynchronized Decentralized Q-Learning: Two Timescale Analysis By Persistence](https://mlsanity.com/paper/2308.03239/) (2023)
- [Population-size-Aware Policy Optimization for Mean-Field Games](https://mlsanity.com/paper/2302.03364/) (2023)
- [Two-Timescale Q-Learning with Function Approximation in Zero-Sum Stochastic Games](https://mlsanity.com/paper/2312.04905/) (2023)
- [SwiftRL: Towards Efficient Reinforcement Learning on Real Processing-In-Memory Systems](https://mlsanity.com/paper/2405.03967/) (2024)
- [Ego-centric Learning of Communicative World Models for Autonomous Driving](https://mlsanity.com/paper/2506.08149/) (2025)
- [Is Thompson Sampling Susceptible to Algorithmic Collusion?](https://mlsanity.com/paper/2405.17463/) (2024)
- [A New Policy Iteration Algorithm For Reinforcement Learning in Zero-Sum Markov Games](https://mlsanity.com/paper/2303.09716/) (2023)
- [Decentralized Multi-Agent Reinforcement Learning for Continuous-Space Stochastic Games](https://mlsanity.com/paper/2303.13539/) (2023)
- [A Scalable Game Theoretic Approach for Coordination of Multiple Dynamic Systems](https://mlsanity.com/paper/2409.11358/) (2024)
- [Online Multi-Agent Control with Adversarial Disturbances](https://mlsanity.com/paper/2506.18814/) (2025)
- [Online Learning for Dynamic Vickrey-Clarke-Groves Mechanism in Unknown Environments](https://mlsanity.com/paper/2506.19038/) (2025)
- [Emergence of Fair Leaders via Mediators in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2508.02421/) (2025)
- [Aggregate Fictitious Play for Learning in Anonymous Polymatrix Games (Extended Version)](https://mlsanity.com/paper/2508.19371/) (2025)
- [Actor-Dual-Critic Dynamics for Zero-sum and Identical-Interest Stochastic Games](https://mlsanity.com/paper/2602.00606/) (2026)
- [Learning under Opponent Unawareness in Linear-Quadratic Stochastic Games](https://mlsanity.com/paper/2608.08268/) (2026)
- [Decentralized Bandit Learning of Markov Perfect Equilibria](https://mlsanity.com/paper/2610.14333/) (2026)

## Abstract (arXiv)

Reinforcement learning (RL) has recently achieved tremendous successes in many artificial intelligence applications. Many of the forefront applications of RL involve multiple agents, e.g., playing chess and Go games, autonomous driving, and robotics. Unfortunately, the framework upon which classical RL builds is inappropriate for multi-agent learning, as it assumes an agent's environment is stationary and does not take into account the adaptivity of other agents. In this review paper, we present the model of stochastic games for multi-agent learning in dynamic environments. We focus on the development of simple and independent learning dynamics for stochastic games: each agent is myopic and chooses best-response type actions to other agents' strategy without any coordination with her opponent. There has been limited progress on developing convergent best-response type independent learning dynamics for stochastic games. We present our recently proposed simple and independent learning dynamics that guarantee convergence in zero-sum stochastic games, together with a review of other contemporaneous algorithms for dynamic multi-agent learning in this setting. Along the way, we also reexamine some classical results from both the game theory and RL literature, to situate both the conceptual contributions of our independent learning dynamics, and the mathematical novelties of our analysis. We hope this review paper serves as an impetus for the resurgence of studying independent and natural learning dynamics in game theory, for the more challenging settings with a dynamic environment.