Provably Efficient Multi-Agent Reinforcement Learning with Fully Decentralized Communication

2021-10-14 · Justin Lidard, Udari Madhushani, Naomi Ehrich Leonard

A challenge in reinforcement learning (RL) is minimizing the cost of sampling associated with exploration. Distributed exploration reduces sampling complexity in multi-agent RL (MARL). We investigate the benefits to performance in MARL when exploration is fully decentralized. Specifically, we consider a class of online, episodic, tabular $Q$-learning problems under time-varying reward and transition dynamics, in which agents can communicate in a decentralized manner.We show that group performance, as measured by the bound on regret, can be significantly improved through communication when each agent uses a decentralized message-passing protocol, even when limited to sending information up to its $\gamma$-hop neighbors. We prove regret and sample complexity bounds that depend on the number of agents, communication network structure and $\gamma.$ We show that incorporating more agents and more information sharing into the group learning scheme speeds up convergence to the optimal policy. Numerical simulations illustrate our results and validate our theoretical claims.

📄 PDF Abstract BibTeX arXiv:2110.07392

Code (0)

등록된 구현이 없습니다.

Tasks

Multi-agent Reinforcement LearningQ-Learningreinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximation

2023-02-13 · Yuanhao Wang, Qinghua Liu, Yu Bai, Chi Jin

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 wit…

Multi-agent Reinforcement Learning

Decentralized Deterministic Multi-Agent Reinforcement Learning

2021-02-19 · Antoine Grosnit, Desmond Cai, Laura Wynter

[Zhang, ICML 2018] provided the first decentralized actor-critic algorithm for multi-agent reinforcement learning (MARL) that offers convergence guarantees. In that work, policies are stochastic and are defined on finite…

Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Fully Decentralized Cooperative Multi-Agent Reinforcement Learning: A Survey

2024-01-10 · Jiechuan Jiang, Kefan Su, Zongqing Lu

Cooperative multi-agent reinforcement learning is a powerful tool to solve many real-world cooperative tasks, but restrictions of real-world applications may require training the agents in a fully decentralized manner. D…

Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning Survey

Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Games

2021-10-12 · Weichao Mao, Tamer Başar

This paper addresses the problem of learning an equilibrium efficiently in general-sum Markov games through decentralized multi-agent reinforcement learning. Given the fundamental difficulty of calculating a Nash equilib…

Multi-agent Reinforcement Learning Q-Learning reinforcement-learning Reinforcement Learning+1

MA2QL: A Minimalist Approach to Fully Decentralized Multi-Agent Reinforcement Learning

2022-09-17 · Kefan Su, Siyuan Zhou, Jiechuan Jiang, Chuang Gan 외

Decentralized learning has shown great promise for cooperative multi-agent reinforcement learning (MARL). However, non-stationarity remains a significant challenge in fully decentralized learning. In the paper, we tackle…

Multi-agent Reinforcement Learning Q-Learning reinforcement-learning Reinforcement Learning (RL)