Scalable Neighborhood-Based Multi-Agent Actor-Critic
Rasmus Jensen · 2026
Read Scalable Neighborhood-Based Multi-Agent Actor-Critic by Rasmus Jensen (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-18190.txt.
Introduction
Goppelsroeder and Jensen propose MADDPG-K, a scalable method for training teams of cooperating or competing agents. Standard centralized critics grow with the number of agents, since each critic sees every observation and action. MADDPG-K instead limits each critic to the k nearest agents by Euclidean distance, keeping its input size fixed. Tests in the Multi-Particle Environment suite show competitive or better performance, faster cooperative convergence, and runtime that scales more gracefully.
Catalog record
| CREATOR | Rasmus Jensen |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 27383 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.18190
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Scalable Neighborhood-Based Multi-Agent Actor-Critic Rasmus Jensen Abstract We propose MADDPG-K, a scalable extension to Multi-Agent Deep Deterministic Policy Gradient (MADDPG) that addresses the computational limitations of centralized critic approaches. Centralized critics, which condition on the observations and actions of all agents, have demonstrated significant performance gains in cooperative and competitive multi-agent settings. However, their critic networks grow linearly in input size with the number of agents, making them increasingly expensive to train at scale. MADDPG-K mitigates this by restricting each agent’s critic to the k k closest agents under a chosen metric which in our case is Euclidean distance. This ensures a constant-size critic input regardless of the total agent count. We analyze the complexity of this approach, showing that the quadratic cost it retains arises from cheap scalar distance computations rather than the expensive neural network matrix multiplications that bottleneck standard MADDPG. We validate our method empirically across cooperative and adversarial environments from the Multi-Particle Environment suite, demonstrating competitive or superior performance compared to MADDPG, faster convergence in cooperative settings, and better runtime scaling as the number of agents grows. Our code is available at https://github.com/TimGop/MADDPG-K . 1 Introduction Multi-Agent Reinforcement Learning (MARL) has shown significant potential across fields including robotics, traffic control, and game-playing, with recent results such as AlphaStar [ 15 ] demonstrating its capacity to handle complex multi-agent environments. A cornerstone of many successful MARL approaches is the centralized critic architecture, most prominently exemplified by Multi-Agent Deep Deterministic Policy Gradient (MADDPG) [ 6 ] , in which each agent’s critic is conditioned on the observations and actions of all agents in the environment. This design addresses the non-stationarity that arises when multiple agents learn simultaneously, and has been shown to substantially outperform independent learning baselines. However, centralized critics carry a significant scalability cost, namely that the input dimensionality of each critic network grows linearly with the number of agents, making every forward and backward pass more expensive as the environment scales. This limits the practical applicability of MADDPG to environments with relatively few agents, and motivates the need for more efficient alternatives. In this paper we propose MADDPG-K, which resolves this bottleneck by providing each agent’s critic only with information from the k nearest agents under the Euclidean metric, rather than all agents in the environment. This reduces the critic input to a fixed size regardless of n , while preserving the locality of information that is most relevant to each agent’s decision. We note that the Euclidean metric is a natural choice for the spatial environments we consider, but the approach generalizes in a straightforward manner to any metric, or to a learned embedding function that maps agent state to a space in which proximity reflects behavioral relevance. We also briefly report a negative result from an alternative approach we explored. For this approach we used a shared centralized critic updated across groups of cooperative agents using a sliding window scheme. This approach failed to achieve competitive performance in preliminary experiments and was not pursued further. The remainder of the paper is structured as follows. Section 2 reviews related work. Section 3 describes the MADDPG-K algorithm and provides a complexity analysis. Section 4 presents experimental results across three MPE environments at varying agent counts, and Section 5 concludes with directions for future work. 2 Related Work The amount of research in deep reinforcement learning increased significantly after the seminal DQN paper [ 7 ] by researchers at DeepMind, which taught agents to play Atari games using Q-learning, a popular reinforcement learning algorithm combined with a deep neural network that estimates Q-values. Research in the years following established methods to extend DQNs to be able to handle continuous action spaces using an actor-critic approach. This led to the development of algorithms such as Deep Deterministic Policy Gradient (DDPG) [ 5 ] , Twin Delayed Deep Deterministic Policy Gradient (TD3) [ 3 ] , and Soft Actor Critic (SAC) [ 4 ] . A naive extension of these algorithms to MARL environments is possible in the form of independent Q-learning [ 13 ] , however recent research such as the MADDPG paper [ 6 ] outlines a more informed approach, where in MADDPG the DDPG algorithm is extended by augmenting each agent’s critic input with the critic input that all other agents would traditionally receive (i.e., all agents’ observations and actions are fed into each agent’s critic). This is done to alleviate the non-stationarity of the Markov Decision Process when multiple agents are involved. MADDPG showed improved performance on all environments tested in the paper [ 6 ] over DDPG, especially on their cooperative communication and predator-prey environments (i.e. tag). Recent advancements in the field have integrated MADDPG and SAC, leveraging the attention mechanism to facilitate the joint training of critics. This innovative approach is exemplified by the MAAC (Multi-agent Actor-Attention-Critic) algorithm [ 12 ] , which samples actions from all target actors, as opposed to just the current agent. This modification has demonstrated enhanced performance across various test environments. Other non-attention based variants of this approach exist and have themselves shown to be quite capable [ 11 , 10 ] . A major drawback of most algorithms that use a centralized critic approach like MADDPG is that the input to the agents’ critics scales linearly with the number of agents present in the environment. This is because the critic receives the observations and actions of all agents in the environment. In our project, we aim to remedy this by restricting the critic’s input for a given agent to the K agents closest to that agent, according to the Euclidean distance between them. This helps to focus on more relevant information if the correct metric is used, and also reduces complexity, allowing the algorithm to scale to environments with larger numbers of agents. An alternative approach to this is given by [ 16 ] , where the critic’s scaling problem is solved by averaging over pairwise local interactions between a given agent and other agents in a neighborhood around the given agent. Concurrently to the work on the MADDPG, a separate group developed a similar approach [ 2 ] , also with a centralized critic, but using a counterfactual baseline. This baseline estimates the expected return if an agent were to take a different action while other agents maintain their current actions. By comparing an agent’s actual return with this counterfactual baseline, COMA can potentially more accurately attribute credit for rewards. However high variance of the counterfactual baseline can cause the gradients for updates to become unstable [ 9 ] . Since we are working on an extension to MADDPG, we need access to the environments used in the MADDPG paper [ 6 ] . However, the original environments are no longer maintained and contain obsolete code. Instead, we access them through Petting Zoo [ 14 ] , which is the multi-agent equivalent of openAI gym [ 1 ] and contains a currently maintained version of these environments. 3 Methods/Algorithms The use of a centralized critic, which obtains actions and observations from all agents as input can improve the efficiency of a MARL algorithm by dealing with the non-stationarity of the Markov decision process when multiple agents