Breaking The Curse Of Multiagency: Provably Efficient Decentralized Multi-agent RL With Function Approximation
2023 · Yuanhao Wang, Qinghua Liu, Yu Bai, et al.
Abstract
A unique challenge in Multi-Agent Reinforcement Learning (MARL) is the curse of multiagency, where the description length of the game as well as the complexity of many existing learning algorithms scale exponentially with the number of agents. While recent works successfully address this challenge under the model of tabular Markov Games, their mechanisms critically rely on the number of states being finite and small, and do not extend to practical scenarios with enormous state spaces where function approximation must be used to approximate value functions or policies. This paper presents the first line of MARL algorithms that provably resolve the curse of multiagency under function approximation. We design a new decentralized algorithm -- V-Learning with Policy Replay, which gives the first polynomial sample complexity results for learning approximate Coarse Correlated Equilibria (CCEs) of Markov Games under decentralized linear function approximation. Our algorithm always outputs Ma
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
- On Improving Model-free Algorithms For Decentralized Multi-agent Reinforcement Learning (2021)0.00
- V-learning -- A Simple, Efficient, Decentralized Algorithm For Multiagent RL (2021)0.00
- Provably Efficient Cooperative Multi-agent Reinforcement Learning With Function Approximation (2021)0.00
- Breaking The Curse Of Multiagency In Robust Multi-agent Reinforcement Learning (2024)0.00
- Incentivize Without Bonus: Provably Efficient Model-based Online Multi-agent RL For Markov Games (2025)0.00
- Fully Decentralized Multi-agent Reinforcement Learning With Networked Agents (2018)0.00
- Policy Distillation And Value Matching In Multiagent Reinforcement Learning (2019)10.48