mlsanityData to 7 Oct 2026

Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Games

arXiv 2102.07404 ↗First posted 15 Feb 2021cs.LG math.OC stat.MLcited by 25

Not on the map. Why?

Abstract (arXiv)

We study reinforcement learning for two-player zero-sum Markov games with simultaneous moves in the finite-horizon setting, where the transition kernel of the underlying Markov games can be parameterized by a linear function over the current state, both players' actions and the next state. In particular, we assume that we can control both players and aim to find the Nash Equilibrium by minimizing the duality gap. We propose an algorithm Nash-UCRL based on the principle "Optimism-in-Face-of-Uncertainty". Our algorithm only needs to find a Coarse Correlated Equilibrium (CCE), which is computationally efficient. Specifically, we show that Nash-UCRL can provably achieve an tildeO(dH√T) regret, where d is the linear function dimension, H is the length of the game and T is the total number of steps in the game. To assess the optimality of our algorithm, we also prove an tildeOmega( dH√T) lower bound on the regret. Our upper bound matches the lower bound up to logarithmic factors, which suggests the optimality of our algorithm.

Key facts. Cited by 25 papers in the map (data through 7 Oct 2026). Builds on 26 of its 53 references that are in the map. First posted on arXiv 15 Feb 2021.

Builds on

26 of 53 references.

References · 26

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  3. 2018Is Q-learning Provably Efficient?cited by 485
  4. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 301
  5. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  6. 2019A Theoretical Analysis of Deep Q-Learningcited by 212
  7. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  8. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  9. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  10. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  11. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  12. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
14 more
  1. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
  2. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
  3. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  4. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  5. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  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. 2017Online Reinforcement Learning in Stochastic Gamescited by 67
  9. 2019Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexitycited by 41
  10. 2020Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexitycited by 28
  11. 2019Feature-Based Q-Learning for Two-Player Stochastic Gamescited by 23
  12. 2018Near-Optimal Time and Sample Complexities for Solving Discounted Markov Decision Process with a Generative Modelcited by 22
  13. 2016Learning Nash Equilibrium for General-Sum Markov Games from Batch Datacited by 20
  14. 2020Minimax Sample Complexity for Turn-based Stochastic Gamecited by 13

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 8; 2023: 7; 2024: 4; 2025: 2; 2026: 4.

25 papers.

Sort:

By area:

  1. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 53
  2. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 29
  3. 2022Near-Optimal Learning of Extensive-Form Games with Imperfect Informationcited by 26
  4. 2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
  5. 2023Offline Learning in Markov Games with General Function Approximationcited by 16
  6. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  7. 2022Efficient Model-based Multi-agent Reinforcement Learning via Optimistic Equilibrium Computationcited by 14
  8. 2022Representation Learning for General-sum Low-rank Markov Gamescited by 14
  9. 2023On the Statistical Efficiency of Mean-Field Reinforcement Learning with General Function Approximationcited by 13
  10. 2023Can We Find Nash Equilibria at a Linear Rate in Markov Games?cited by 9
  11. 2024Model-Based RL for Mean-Field Games is not Statistically Harder than Single-Agent RLcited by 9
  12. 2023Finite-sample Guarantees for Nash Q-learning with Linear Function Approximationcited by 4
13 more
  1. 2024Refined Sample Complexity for Markov Games with Independent Linear Function Approximationcited by 3
  2. 2022One Policy is Enough: Parallel Exploration with a Single Policy is Near-Optimal for Reward-Free Reinforcement Learningcited by 2
  3. 2024Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learningcited by 2
  4. 2026Learning Approximate Nash Equilibria in Cooperative Multi-Agent Reinforcement Learning via Mean-Field Subsamplingcited by 2
  5. 2022Learning Two-Player Mixture Markov Games: Kernel Function Approximation and Correlated Equilibriumcited by 1
  6. 2023Sample-Efficient Multi-Agent RL: An Optimization Perspectivecited by 1
  7. 2024Imprecise Multi-Armed Banditscited by 1
  8. 2025Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Gamescited by 1
  9. 2025Distributionally Robust Online Markov Game with Linear Function Approximationcited by 1
  10. 2023Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Gamescited by 0
  11. 2026Strategically Robust Multi-Agent Reinforcement Learning with Linear Function Approximationcited by 0
  12. 2026Bayesian Learning in Episodic Zero-Sum Gamescited by 0
  13. 2026Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximationcited by 0