Sample and Communication Efficient Fully Decentralized MARL Policy Evaluation via a New Approach: Local TD update

2024-03-23 · FNU Hairi, Zifan Zhang, Jia Liu

In actor-critic framework for fully decentralized multi-agent reinforcement learning (MARL), one of the key components is the MARL policy evaluation (PE) problem, where a set of $N$ agents work cooperatively to evaluate the value function of the global states for a given policy through communicating with their neighbors. In MARL-PE, a critical challenge is how to lower the sample and communication complexities, which are defined as the number of training samples and communication rounds needed to converge to some $\epsilon$-stationary point. To lower communication complexity in MARL-PE, a "natural'' idea is to perform multiple local TD-update steps between each consecutive rounds of communication to reduce the communication frequency. However, the validity of the local TD-update approach remains unclear due to the potential "agent-drift'' phenomenon resulting from heterogeneous rewards across agents in general. This leads to an interesting open question: Can the local TD-update approach entail low sample and communication complexities? In this paper, we make the first attempt to answer this fundamental question. We focus on the setting of MARL-PE with average reward, which is motivated by many multi-agent network optimization problems. Our theoretical and experimental results confirm that allowing multiple local TD-update steps is indeed an effective approach in lowering the sample and communication complexities of MARL-PE compared to consensus-based MARL-PE algorithms. Specifically, the local TD-update steps between two consecutive communication rounds can be as large as $\mathcal{O}(1/\epsilon^{1/2}\log{(1/\epsilon)})$ in order to converge to an $\epsilon$-stationary point of MARL-PE. Moreover, we show theoretically that in order to reach the optimal sample complexity, the communication complexity of local TD-update approach is $\mathcal{O}(1/\epsilon^{1/2}\log{(1/\epsilon)})$.

📄 PDF Abstract BibTeX arXiv:2403.15935

Code (0)

등록된 구현이 없습니다.

Tasks

Multi-agent Reinforcement Learning

Methods 이 논문이 사용한 방법론

SET Dynamic Sparse Training method where weight mask is updated randomly periodically

Focus 설명 없음

Taming Communication and Sample Complexities in Decentralized Policy Evaluation for Cooperative Multi-Agent Reinforcement Learning

2021-12-01 · NeurIPS 2021 12 · Xin Zhang, Zhuqing Liu, Jia Liu, Zhengyuan Zhu 외

Cooperative multi-agent reinforcement learning (MARL) has received increasing attention in recent years and has found many scientific and engineering applications. However, a key challenge arising from many cooperative M…

Multi-agent Reinforcement Learning Reinforcement Learning (RL)Stochastic Optimization

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

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

ClusterComm: Discrete Communication in Decentralized MARL using Internal Representation Clustering

2024-01-07 · Robert Müller, Hasan Turalic, Thomy Phan, Michael Kölle 외

In the realm of Multi-Agent Reinforcement Learning (MARL), prevailing approaches exhibit shortcomings in aligning with human learning, robustness, and scalability. Addressing this, we introduce ClusterComm, a fully decen…

Clustering Multi-agent Reinforcement Learning reinforcement-learning

Bayesian Ego-graph Inference for Networked Multi-Agent Reinforcement Learning

2025-09-20 · Wei Duan, Jie Lu, Junyu Xuan arxiv

In networked multi-agent reinforcement learning (Networked-MARL), decentralized agents must act under local observability and constrained communication over fixed physical graphs. Existing methods often assume static nei…

Multi-agent Reinforcement Learning

Finite-Sample Analysis of Decentralized Q-Learning for Stochastic Games

2021-12-15 · Zuguang Gao, Qianqian Ma, Tamer Başar, John R. Birge

Learning in stochastic games is arguably the most standard and fundamental setting in multi-agent reinforcement learning (MARL). In this paper, we consider decentralized MARL in stochastic games in the non-asymptotic reg…

Multi-agent Reinforcement Learning Q-Learning