# Online Reinforcement Learning in Stochastic Games

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

## Key facts

- Cited by 67 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Dec 2017.

## Built on by (most cited first, 30 of 67)

- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [Independent Policy Gradient Methods for Competitive Reinforcement Learning](https://mlsanity.com/paper/2101.04233/) (2021)
- [Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games](https://mlsanity.com/paper/2102.04540/) (2021)
- [Decentralized Q-Learning in Zero-sum Markov Games](https://mlsanity.com/paper/2106.02748/) (2021)
- [The Complexity of Markov Equilibrium in Stochastic Games](https://mlsanity.com/paper/2204.03991/) (2022)
- [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)
- [Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Games](https://mlsanity.com/paper/2110.05682/) (2021)
- [On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2110.05707/) (2021)
- [Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximation](https://mlsanity.com/paper/2302.06606/) (2023)
- [Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback](https://mlsanity.com/paper/2303.02738/) (2023)
- [Sample-Efficient Reinforcement Learning of Partially Observable Markov Games](https://mlsanity.com/paper/2206.01315/) (2022)
- [Near-Optimal Learning of Extensive-Form Games with Imperfect Information](https://mlsanity.com/paper/2202.01752/) (2022)
- [Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Games](https://mlsanity.com/paper/2102.07404/) (2021)
- [Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?](https://mlsanity.com/paper/2112.13521/) (2021)
- [ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regret](https://mlsanity.com/paper/2206.04122/) (2022)
- [Regret Minimization and Convergence to Equilibria in General-sum Markov Games](https://mlsanity.com/paper/2207.14211/) (2022)
- [Improving LLM General Preference Alignment via Optimistic Online Mirror Descent](https://mlsanity.com/paper/2502.16852/) (2025)
- [Independent Learning in Stochastic Games](https://mlsanity.com/paper/2111.11743/) (2021)
- [Independent and Decentralized Learning in Markov Potential Games](https://mlsanity.com/paper/2205.14590/) (2022)
- [On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Games](https://mlsanity.com/paper/2109.01795/) (2021)
- [Offline Learning in Markov Games with General Function Approximation](https://mlsanity.com/paper/2302.02571/) (2023)
- [Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limits](https://mlsanity.com/paper/2203.06803/) (2022)
- [Policy Optimization for Markov Games: Unified Framework and Faster Convergence](https://mlsanity.com/paper/2206.02640/) (2022)
- [Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Model](https://mlsanity.com/paper/2208.10458/) (2022)
- [A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Games](https://mlsanity.com/paper/2303.03100/) (2023)
- [Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2306.00212/) (2023)
- [Performative Reinforcement Learning in Gradually Shifting Environments](https://mlsanity.com/paper/2402.09838/) (2024)
- [No-Regret Learning in Dynamic Stackelberg Games](https://mlsanity.com/paper/2202.04786/) (2022)
- [Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Games](https://mlsanity.com/paper/2206.01588/) (2022)

## Abstract (arXiv)

We study online reinforcement learning in average-reward stochastic games (SGs). An SG models a two-player zero-sum game in a Markov environment, where state transitions and one-step payoffs are determined simultaneously by a learner and an adversary. We propose the UCSG algorithm that achieves a sublinear regret compared to the game value when competing with an arbitrary opponent. This result improves previous ones under the same setting. The regret bound has a dependency on the diameter, which is an intrinsic value related to the mixing property of SGs. If we let the opponent play an optimistic best response to the learner, UCSG finds an varepsilon-maximin stationary policy with a sample complexity of tildeOleft(poly(1/varepsilon)right), where varepsilon is the gap to the best policy.