mlsanityData to 7 Oct 2026

O(T-1) Convergence of Optimistic-Follow-the-Regularized-Leader in Two-Player Zero-Sum Markov Games

arXiv 2209.12430 ↗First posted 26 Sep 2022cs.LG cs.GTcited by 11

Not on the map. Why?

Abstract (arXiv)

We prove that optimistic-follow-the-regularized-leader (OFTRL), together with smooth value updates, finds an O(T-1)-approximate Nash equilibrium in T iterations for two-player zero-sum Markov games with full information. This improves the tildeO(T-5/6) convergence rate recently shown in the paper Zhang et al (2022). The refined analysis hinges on two essential ingredients. First, the sum of the regrets of the two players, though not necessarily non-negative as in normal-form games, is approximately non-negative in Markov games. This property allows us to bound the second-order path lengths of the learning dynamics. Second, we prove a tighter algebraic inequality regarding the weights deployed by OFTRL that shaves an extra log T factor. This crucial improvement enables the inductive analysis that leads to the final O(T-1) rate.

Key facts. Cited by 11 papers in the map (data through 7 Oct 2026). Builds on 24 of its 42 references that are in the map. First posted on arXiv 26 Sep 2022.

Builds on

24 of 42 references.

References · 24

  1. 2019Dota 2 with Large Scale Deep Reinforcement Learningcited by 1,084
  2. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
  3. 2018Is Q-learning Provably Efficient?cited by 485
  4. 2013Optimization, Learning, and Games with Predictable Sequencescited by 187
  5. 2015Fast Convergence of Regularized Learning in Gamescited by 149
  6. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  7. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
  8. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
  9. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  10. 2020Game-Theoretic Multiagent Reinforcement Learningcited by 92
  11. 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 91
  12. 2021Near-Optimal No-Regret Learning in General Gamescited by 85
12 more
  1. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 66
  2. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 61
  3. 2020Hedging in games: Faster convergence of external and swap regretscited by 57
  4. 2021Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Gamescited by 43
  5. 2019Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexitycited by 41
  6. 2022No-Regret Learning in Time-Varying Zero-Sum Gamescited by 36
  7. 2022Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Gamescited by 35
  8. 2022On Last-Iterate Convergence Beyond Zero-Sum Gamescited by 30
  9. 2022When is Offline Two-Player Zero-Sum Markov Game Solvable?cited by 27
  10. 2019Feature-Based Q-Learning for Two-Player Stochastic Gamescited by 23
  11. 2022Regret Minimization and Convergence to Equilibria in General-sum Markov Gamescited by 22
  12. 2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 4; 2024: 4; 2025: 2.

11 papers.

  1. 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 28
  2. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 26
  3. 2022Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Gamescited by 25
  4. 2024Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertaintycited by 24
  5. 2023On the Convergence of No-Regret Learning Dynamics in Time-Varying Gamescited by 14
  6. 2024Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Gamescited by 11
  7. 2024Minimax-Optimal Multi-Agent Robust Reinforcement Learningcited by 4
  8. 2023Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Propertycited by 2
  9. 2024widetildeO(T-1) Convergence to (Coarse) Correlated Equilibria in Full-Information General-Sum Markov Gamescited by 0
  10. 2025Playing Markov Games Without Observing Payoffscited by 0
  11. 2025Near Optimal Convergence to Coarse Correlated Equilibrium in General-Sum Markov Gamescited by 0