Abstract
Scaling Multi-Agent Reinforcement Learning (MARL) to large-scale systems is hindered by the exponential growth of the joint state-action space and the "straggler effect" in distributed training environments. We present DARL1N (Distributed multi-Agent Reinforcement Learning with One-hop Neighbors), a framework designed to address these bottlenecks. By localizing agent interactions to one-hop neighborhoods and employing coding theory for distributed gradient updates, DARL1N achieves significant computational efficiency and resilience to hardware latency. Our evaluations across diverse environments show that DARL1N scales linearly with the number of agents and provides substantial speedups over state-of-the-art baselines.
Introduction
The "curse of dimensionality" remains a primary obstacle in MARL, where the complexity of accounting for every agent's impact on others leads to prohibitive computational costs. Furthermore, distributed training often suffers from the "straggler effect," where the slowest node determines the overall system throughput. DARL1N addresses these issues by combining localized learning with a fault-tolerant distributed architecture.
Methods
DARL1N's architecture is built on two pillars: localized interaction and coded computation. Instead of a global Q-function, each agent learns based on its immediate one-hop neighbors in a proximity graph. This reduction in input dimensionality allows for faster convergence and better generalization across varying agent densities.
To handle distributed training, DARL1N utilizes coded distributed learning. By introducing intentional redundancy through coding schemes like Maximum Distance Separable (MDS) or Low-Density Generator Matrix (LDGM) codes, a central controller can update model parameters as soon as a sufficient subset of learners completes their tasks, effectively bypassing slow "straggler" nodes.
Key Results
The framework was evaluated across five environments, including the Ising Model and Multi-Access Wireless Communication. Key findings include:
- Massive Speedups: In a 64-agent Ising Model, DARL1N converged in just 110 seconds, a nearly 20x improvement over the popular MADDPG algorithm (1,996 seconds).
- Linear Scalability: Unlike baseline methods (MADDPG, MFAC), DARL1N’s training time grows linearly as the number of agents increases, making it suitable for massive-scale systems.
- Straggler Mitigation: In experiments simulating a 50% chance of nodes being slow, the LDGM-coded version maintained high training efficiency and policy quality, whereas uncoded systems saw performance plummet.
Conclusion
DARL1N provides a robust path for scaling MARL to massive systems by leveraging spatial locality and coding theory. By turning an exponential problem into a linear one and mitigating hardware bottlenecks, it enables efficient training of large-scale multi-agent systems. Future research will explore dynamic neighborhood topology learning and fully decentralized coded architectures to further enhance system resilience and flexibility.
Summary updated