Refined Sample Complexity For Markov Games With Independent Linear Function Approximation
2024 · Yan Dai, Qiwen Cui, Simon S. Du
Abstract
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 \(A_\{\max\}\) -- 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 line
Authors
(none)
Tags
Stats
Related papers
- Breaking The Curse Of Multiagents In A Large State Space: RL In Markov Games With Independent Linear Function Approximation (2023)0.00
- Robustness And Sample Complexity Of Model-based MARL For General-sum Markov Games (2021)0.00
- RL In Markov Games With Independent Function Approximation: Improved Sample Complexity Bound Under The Local Access Model (2024)0.00
- Incentivize Without Bonus: Provably Efficient Model-based Online Multi-agent RL For Markov Games (2025)0.00
- Breaking The Curse Of Multiagency: Provably Efficient Decentralized Multi-agent RL With Function Approximation (2023)0.00
- Breaking The Curse Of Multiagency In Robust Multi-agent Reinforcement Learning (2024)0.00
- Minimax-optimal Multi-agent RL In Markov Games With A Generative Model (2022)2.26
- Minimax-optimal Multi-agent Robust Reinforcement Learning (2024)0.00