Introduction
Multi-agent reinforcement learning (RL) holds promise for optimizing complex, distributed systems like city-wide traffic grids and massive data centers. However, scaling these systems presents a fundamental challenge: as the number of agents grows, the amount of data required to learn effective policies can explode. This paper investigates the information-theoretic limits of learning in distributed RL, proving that sample complexity depends critically on the granularity of the reward signal. While learning from a single global reward requires a number of samples that scales linearly with the number of agents ($n$), leveraging local reward signals allows for logarithmic scaling ($O(\log n)$).
The Scalability Bottleneck: Global vs. Local Rewards
In standard distributed RL, the entire system is often treated as one giant agent receiving a single "global reward" (e.g., total network throughput). The authors identify a fundamental scalability bottleneck with this approach. Relying on a global reward is akin to grading an individual student based solely on the average score of their entire school. As the population grows, the signal-to-noise ratio for any individual agent's contribution vanishes.
The authors mathematically prove an $\Omega(n)$ lower bound on sample complexity for any algorithm relying strictly on a global reward signal. For a system with 100,000 agents, this linear scaling makes real-world training practically impossible, as it would require orders of magnitude more experience to isolate individual agent contributions.
Exploiting Locality in Factored MDPs
To overcome this bottleneck, the paper proposes exploiting the local structure inherent in most large-scale systems. A traffic light in New York does not directly affect one in Los Angeles; agents typically only influence their immediate neighbors.
By understanding this "neighborhood" structure and accessing individual local rewards, algorithms can decouple the learning problem. The authors prove an upper bound showing that estimating the system's dynamics and rewards in this factored manner requires only $O(\log n)$ samples. This logarithmic scaling is a massive breakthrough: doubling the number of agents only requires a small, constant increase in training data.
The proposed approach uses exploration data to build Maximum Likelihood Estimates (MLE) of local Conditional Probability Tables (CPTs) and reward functions, effectively solving the resulting factored Markov Decision Process (MDP) offline. Because every time-step provides a training example for every single agent's local transition model, data is used highly efficiently.
Empirical Validation
The theoretical findings are supported by empirical demonstrations across synthetic independent agent domains and the classic SYSADMIN benchmark (a network of computers where agents must decide which machines to reboot to maximize uptime).
The results starkly highlight the advantage of local rewards. In large multi-agent setups with hundreds of agents, a local learner achieves near-optimal performance almost instantly. In contrast, a global learner requires thousands of trajectories to show even marginal improvement. Furthermore, when testing a localized version of the REINFORCE policy gradient algorithm on the SYSADMIN task, the local variant learned significantly faster and maintained a nearly constant learning speed regardless of whether the network contained 10 or 100 agents.
Limitations and Future Work
While local rewards offer a clear path to scalable multi-agent RL, several challenges remain:
- Exploration Assumptions: The $O(\log n)$ sample complexity relies on a "good" exploration policy that visits local state-action configurations sufficiently often. Finding this exploration policy in highly complex environments can be difficult.
- Known Structure: The current methods assume the neighborhood influence graph (who influences whom) is known a priori. Learning this graph structure directly from data is a crucial next step.
- Local vs. Global Optima: A "greedy" local algorithm (like local REINFORCE) is not strictly guaranteed to converge to the globally optimal cooperative solution. Balancing the strong, efficient signal of local rewards with the need for global coordination remains an active area of research.
Summary updated