mlsanityData to 7 Oct 2026

A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Games

arXiv 2303.03100 ↗First posted 3 Mar 2023cs.GT cs.LGcited by 15

Not on the map. Why?

Abstract (arXiv)

We study two-player zero-sum stochastic games, and propose a form of independent learning dynamics called Doubly Smoothed Best-Response dynamics, which integrates a discrete and doubly smoothed variant of the best-response dynamics into temporal-difference (TD)-learning and minimax value iteration. The resulting dynamics are payoff-based, convergent, rational, and symmetric among players. Our main results provide finite-sample guarantees. In particular, we prove the first-known tildeO(1/ε2) sample complexity bound for payoff-based independent learning dynamics, up to a smoothing bias. In the special case where the stochastic game has only one state (i.e., matrix games), we provide a sharper tildeO(1/ε) sample complexity. Our analysis uses a novel coupled Lyapunov drift approach to capture the evolution of multiple sets of coupled and stochastic iterates, which might be of independent interest.

Key facts. Cited by 15 papers in the map (data through 7 Oct 2026). Builds on 47 of its 82 references that are in the map. First posted on arXiv 3 Mar 2023.

Builds on

47 of 82 references.

References · 47

  1. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  2. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 149
  3. 2017On the Properties of the Softmax Function with Application in Game Theory and Reinforcement Learningcited by 136
  4. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 120
  5. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  6. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  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. 2018Learning to Navigate in Cities Without a Mapcited by 103
  10. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  11. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
  12. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 93
35 more
  1. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 93
  2. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 89
  3. 2019Finite-Sample Analysis for SARSA with Linear Function Approximationcited by 85
  4. 2017Online Reinforcement Learning in Stochastic Gamescited by 67
  5. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 66
  6. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 61
  7. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
  8. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 54
  9. 2021Decentralized Q-Learning in Zero-sum Markov Gamescited by 53
  10. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 45
  11. 2022Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasetscited by 42
  12. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 41
  13. 2022Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methodscited by 37
  14. 2021On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learningcited by 35
  15. 2015Decentralized Q-Learning for Stochastic Teams and Gamescited by 34
  16. 2021Gradient play in stochastic games: stationary points, convergence, and sample complexitycited by 32
  17. 2022Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonuscited by 29
  18. 2022When is Offline Two-Player Zero-Sum Markov Game Solvable?cited by 27
  19. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 26
  20. 2021Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysiscited by 25
  21. 2022Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Gamescited by 25
  22. 2020Fictitious play in zero-sum stochastic gamescited by 24
  23. 2022Regret Minimization and Convergence to Equilibria in General-sum Markov Gamescited by 22
  24. 2020Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithmscited by 19
  25. 2022Independent and Decentralized Learning in Markov Potential Gamescited by 19
  26. 2021Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Gamescited by 18
  27. 2022Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Gamescited by 18
  28. 2022Global Convergence of Localized Policy Iteration in Networked Multi-Agent Reinforcement Learningcited by 18
  29. 2021Global Optimality and Finite Sample Analysis of Softmax Off-Policy Actor Critic under State Distribution Mismatchcited by 17
  30. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  31. 2021Best-Response Dynamics and Fictitious Play in Identical-Interest and Zero-Sum Stochastic Gamescited by 9
  32. 2022Fictitious Play in Markov Games with Single Controllercited by 9
  33. 2022Symmetric (Optimistic) Natural Policy Gradient for Multi-agent Learning with Parameter Convergencecited by 8
  34. 2021Finite-Sample Analysis of Decentralized Q-Learning for Stochastic Gamescited by 4
  35. 2022Smooth Fictitious Play in Stochastic Games with Perturbed Payoffs and Unknown Transitionscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 4; 2024: 5; 2025: 2; 2026: 4.

15 papers.

Sort:

By area:

  1. 2024Independent Learning in Constrained Markov Potential Gamescited by 10
  2. 2023Multi-Player Zero-Sum Markov Games with Networked Separable Interactionscited by 8
  3. 2025From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applicationscited by 6
  4. 2024Approximate Global Convergence of Independent Learning in Multi-Agent Systemscited by 3
  5. 2025A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policiescited by 3
  6. 2026Efficient Uncoupled Learning Dynamics with tildeO!left(T-1/4right) Last-Iterate Convergence in Bilinear Saddle-Point Problems over Convex Sets under Bandit Feedbackcited by 3
  7. 2023Two-Timescale Q-Learning with Function Approximation in Zero-Sum Stochastic Gamescited by 2
  8. 2023Learning in Zero-Sum Markov Games: Relaxing Strong Reachability and Mixing Time Assumptionscited by 2
  9. 2023Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Propertycited by 2
  10. 2024Finite-Sample Guarantees for Learning Dynamics in Zero-Sum Polymatrix Gamescited by 2
  11. 2026Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actionscited by 2
  12. 2024Is Thompson Sampling Susceptible to Algorithmic Collusion?cited by 1
3 more
  1. 2024Risk Sensitivity in Markov Games and Multi-Agent Reinforcement Learning: A Systematic Reviewcited by 0
  2. 2026Actor-Dual-Critic Dynamics for Zero-sum and Identical-Interest Stochastic Gamescited by 0
  3. 2026Online Security Learning in Cooperative Multi-Agent Systems under Hidden Byzantine Attackscited by 0