Cooperative Multi-agent Reinforcement Learning: Asynchronous Communication And Linear Function Approximation

Abstract

We study multi-agent reinforcement learning in the setting of episodic Markov decision processes, where multiple agents cooperate via communication through a central server. We propose a provably efficient algorithm based on value iteration that enable asynchronous communication while ensuring the advantage of cooperation with low communication overhead. With linear function approximation, we prove that our algorithm enjoys an \(\tilde\{\mathcal\{O\}\}(d^\{3/2\}H^2\sqrt\{K\})\) regret with \(\tilde\{\mathcal\{O\}\}(dHM^2)\) communication complexity, where \(d\) is the feature dimension, \(H\) is the horizon length, \(M\) is the total number of agents, and \(K\) is the total number of episodes. We also provide a lower bound showing that a minimal \(Ω(dM)\) communication complexity is required to improve the performance through collaboration.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keymin2023cooperative

Related papers

• Provably Efficient Cooperative Multi-agent Reinforcement Learning With Function Approximation (2021)0.00
• Resilient Consensus-based Multi-agent Reinforcement Learning With Function Approximation (2021)0.00
• Distributed Value Function Approximation For Collaborative Multi-agent Reinforcement Learning (2020)8.60
• Breaking The Curse Of Multiagency: Provably Efficient Decentralized Multi-agent RL With Function Approximation (2023)0.00
• Provably Efficient Multi-agent Reinforcement Learning With Fully Decentralized Communication (2021)0.00
• Nearly Minimax Optimal Reinforcement Learning For Linear Markov Decision Processes (2022)0.00
• Provably Efficient Model-free RL In Leader-follower MDP With Linear Function Approximation (2022)0.00
• Reward-free Model-based Reinforcement Learning With Linear Function Approximation (2021)0.00