mlsanityData to 7 Oct 2026

Gap-Dependent Bounds for Two-Player Markov Games

arXiv 2107.00685 ↗First posted 1 Jul 2021cs.LG stat.MLcited by 5

Not on the map. Why?

Abstract (arXiv)

As one of the most popular methods in the field of reinforcement learning, Q-learning has received increasing attention. Recently, there have been more theoretical works on the regret bound of algorithms that belong to the Q-learning class in different settings. In this paper, we analyze the cumulative regret when conducting Nash Q-learning algorithm on 2-player turn-based stochastic Markov games (2-TBSG), and propose the very first gap dependent logarithmic upper bounds in the episodic tabular setting. This bound matches the theoretical lower bound only up to a logarithmic term. Furthermore, we extend the conclusion to the discounted game setting with infinite horizon and propose a similar gap dependent logarithmic regret bound. Also, under the linear MDP assumption, we obtain another logarithmic regret for 2-TBSG, in both centralized and independent settings.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 31 of its 54 references that are in the map. First posted on arXiv 1 Jul 2021.

Builds on

31 of 54 references.

References · 31

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  3. 2018Is Q-learning Provably Efficient?cited by 485
  4. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  5. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  6. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  7. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  8. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  9. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  10. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  11. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  12. 2014Generalization and Exploration via Randomized Value Functionscited by 112
19 more
  1. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  2. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  3. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
  4. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
  5. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  6. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  7. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  8. 2019Variance-reduced Q-learning is minimax optimalcited by 72
  9. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  10. 2020Q-learning with Logarithmic Regretcited by 59
  11. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 56
  12. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  13. 2019Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDPcited by 53
  14. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 48
  15. 2016On Lower Bounds for Regret in Reinforcement Learningcited by 39
  16. 2018Exploration in Structured Reinforcement Learningcited by 34
  17. 2019Feature-Based Q-Learning for Two-Player Stochastic Gamescited by 23
  18. 2020Regret Bounds for Discounted MDPscited by 19
  19. 2020Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexitycited by 19

Built on by

Cited by year

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

5 papers.

  1. 2022Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonuscited by 29
  2. 2023Offline Learning in Markov Games with General Function Approximationcited by 16
  3. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  4. 2023Instance-dependent Sample Complexity Bounds for Zero-sum Matrix Gamescited by 6
  5. 2025Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPscited by 3