mlsanityData to 7 Oct 2026

Refined Sample Complexity for Markov Games with Independent Linear Function Approximation

arXiv 2402.07082 ↗First posted 11 Feb 2024cs.LG cs.GT stat.MLcited by 3

Not on the map. Why?

Abstract (arXiv)

Markov Games (MG) is an important model for Multi-Agent Reinforcement Learning (MARL). It was long believed that the "curse of multi-agents" (i.e., the algorithmic performance drops exponentially with the number of agents) is unavoidable until several recent works (Daskalakis et al., 2023; Cui et al., 2023; Wang et al., 2023). While these works resolved the curse of multi-agents, when the state spaces are prohibitively large and (linear) function approximations are deployed, they either had a slower convergence rate of O(T-1/4) or brought a polynomial dependency on the number of actions Amax -- which is avoidable in single-agent cases even when the loss functions can arbitrarily vary with time. This paper first refines the AVLPR framework by Wang et al. (2023), with an insight of designing *data-dependent* (i.e., stochastic) pessimistic estimation of the sub-optimality gap, allowing a broader choice of plug-in algorithms. When specialized to MGs with independent linear function approximations, we propose novel *action-dependent bonuses* to cover occasionally extreme estimation errors. With the help of state-of-the-art techniques from the single-agent RL literature, we give the first algorithm that tackles the curse of multi-agents, attains the optimal O(T-1/2) convergence rate, and avoids poly(Amax) dependency simultaneously.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 30 of its 45 references that are in the map. First posted on arXiv 11 Feb 2024.

Builds on

30 of 45 references.

References · 30

  1. 2019Emergent Tool Use From Multi-Agent Autocurriculacited by 308
  2. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 301
  3. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  4. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  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. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  10. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
  11. 2020Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPscited by 49
  12. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
18 more
  1. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 45
  2. 2020Efficient and Robust Algorithms for Adversarial Linear Contextual Banditscited by 42
  3. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
  4. 2021Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Gamescited by 42
  5. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 29
  6. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 26
  7. 2021Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Gamescited by 25
  8. 2013Efficient Reinforcement Learning in Deterministic Systems with Value Function Generalizationcited by 19
  9. 2023First- and Second-Order Bounds for Adversarial Linear Contextual Banditscited by 19
  10. 2023Refined Regret for Adversarial MDPs with Linear Function Approximationcited by 18
  11. 2023Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Banditscited by 18
  12. 2022A Self-Play Posterior Sampling Algorithm for Zero-Sum Markov Gamescited by 14
  13. 2022Representation Learning for General-sum Low-rank Markov Gamescited by 14
  14. 2023Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimizationcited by 14
  15. 2023Rate-Optimal Policy Optimization for Linear Markov Decision Processescited by 14
  16. 2023Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedbackcited by 12
  17. 2022Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Gamescited by 11
  18. 2022Stabilizing Q-learning with Linear Architectures for Provably Efficient Learningcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 1; 2026: 2.

3 papers.

  1. 2025Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Gamescited by 1
  2. 2026Strategically Robust Multi-Agent Reinforcement Learning with Linear Function Approximationcited by 0
  3. 2026Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximationcited by 0