mlsanityData to 14 Oct 2026

Finite-sample Guarantees for Nash Q-learning with Linear Function Approximation

arXiv 2303.00177 ↗First posted 1 Mar 2023cs.LG cs.AIcited by 4

Not on the map. Why?

Abstract (arXiv)

Nash Q-learning may be considered one of the first and most known algorithms in multi-agent reinforcement learning (MARL) for learning policies that constitute a Nash equilibrium of an underlying general-sum Markov game. Its original proof provided asymptotic guarantees and was for the tabular case. Recently, finite-sample guarantees have been provided using more modern RL techniques for the tabular case. Our work analyzes Nash Q-learning using linear function approximation -- a representation regime introduced when the state space is large or continuous -- and provides finite-sample guarantees that indicate its sample efficiency. We find that the obtained performance nearly matches an existing efficient result for single-agent RL under the same representation and has a polynomial gap when compared to the best-known result for the tabular case.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 26 of its 42 references that are in the map. First posted on arXiv 1 Mar 2023.

Builds on

26 of 42 references.

References · 26

  1. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 567
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  3. 2020Is Pessimism Provably Efficient for Offline RL?cited by 364
  4. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 233
  5. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
  6. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 114
  7. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 109
  8. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 105
  9. 2017A Survey of Learning in Multiagent Environments: Dealing with Non-Stationaritycited by 94
  10. 2020Game-Theoretic Multiagent Reinforcement Learningcited by 94
  11. 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 92
  12. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
14 more
  1. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 67
  2. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  3. 2021Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Gamescited by 42
  4. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 40
  5. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 30
  6. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 27
  7. 2021Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Gamescited by 25
  8. 2022Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimalitycited by 24
  9. 2021Provably Efficient Cooperative Multi-Agent Reinforcement Learning with Function Approximationcited by 23
  10. 2018Cooperative and Distributed Reinforcement Learning of Drones for Field Coveragecited by 20
  11. 2021On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Gamecited by 20
  12. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  13. 2022Representation Learning for General-sum Low-rank Markov Gamescited by 15
  14. 2022One Policy is Enough: Parallel Exploration with a Single Policy is Near-Optimal for Reward-Free Reinforcement Learningcited by 2

Built on by

Cited by year (2026 to 14 Oct)

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

4 papers.

  1. 2023Two-Timescale Q-Learning with Function Approximation in Zero-Sum Stochastic Gamescited by 2
  2. 2024RL in Markov Games with Independent Function Approximation: Improved Sample Complexity Bound under the Local Access Modelcited by 0
  3. 2026Strategically Robust Multi-Agent Reinforcement Learning with Linear Function Approximationcited by 0
  4. 2026Finite-Time Analysis of Q-Value Iteration for General-Sum Stackelberg Gamescited by 0