Data to 7 Oct 2026

Online Reinforcement Learning in Stochastic Games

arXiv 1712.00579 ↗First posted 2 Dec 2017cs.LGcited by 67

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 18; 2022: 19; 2023: 15; 2024: 4; 2025: 5; 2026: 6.

67 papers.

Sort:

By area:

2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 66
2021Decentralized Q-Learning in Zero-sum Markov Gamescited by 53
2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 45
2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
2021Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Gamescited by 42
2021On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learningcited by 35
2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 29
2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 28
2022Near-Optimal Learning of Extensive-Form Games with Imperfect Informationcited by 26

38 more

2022Sample-Efficient Reinforcement Learning of Partially Observable Markov Gamescited by 26
2021Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Gamescited by 25
2021Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?cited by 24
2022ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regretcited by 24
2025Improving LLM General Preference Alignment via Optimistic Online Mirror Descentcited by 24
2022Regret Minimization and Convergence to Equilibria in General-sum Markov Gamescited by 22
2021Independent Learning in Stochastic Gamescited by 20
2022Independent and Decentralized Learning in Markov Potential Gamescited by 19
2021On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Gamescited by 18
2022Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limitscited by 17
2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
2023Offline Learning in Markov Games with General Function Approximationcited by 16
2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
2023Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learningcited by 13
2024Performative Reinforcement Learning in Gradually Shifting Environmentscited by 13
2022No-Regret Learning in Dynamic Stackelberg Gamescited by 12
2022Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Gamescited by 11
2022Self-Play PSRO: Toward Optimal Populations in Two-Player Zero-Sum Gamescited by 11
2022Adapting to game trees in zero-sum imperfect information gamescited by 11
2021Satisficing Paths and Independent Multi-Agent Reinforcement Learning in Stochastic Gamescited by 9
2022Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitionscited by 9
2022Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instrumentscited by 9
2023Can We Find Nash Equilibria at a Linear Rate in Markov Games?cited by 9
2022Specification-Guided Learning of Nash Equilibria with High Social Welfarecited by 8
2023Two-sided Competing Matching Recommendation Markets With Quota and Complementary Preferences Constraintscited by 5
2021Finite-Sample Analysis of Decentralized Q-Learning for Stochastic Gamescited by 4
2023Robust Subtask Learning for Compositional Generalizationcited by 4
2021A Bayesian Learning Algorithm for Unknown Zero-sum Stochastic Games with an Arbitrary Opponentcited by 3
2021Online Markov Decision Processes with Non-oblivious Strategic Adversarycited by 3
2023Population-size-Aware Policy Optimization for Mean-Field Gamescited by 3
2023Finite-Time Analysis of Minimax Q-Learning for Two-Player Zero-Sum Markov Games: Switching System Approachcited by 3
2024Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithmscited by 3
2025Bellman Optimality of Average-Reward Robust Markov Decision Processes with a Constant Gaincited by 3
2026Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regretcited by 3
2026Offline Two-Player Zero-Sum Markov Games with KL Regularizationcited by 3
2023Local and adaptive mirror descents in extensive-form gamescited by 2
2023Learning in Zero-Sum Markov Games: Relaxing Strong Reachability and Mixing Time Assumptionscited by 2

50 most cited of 67 All 67 (JSON)