On Local Rewards and Scaling Distributed Reinforcement Learning

J. Andrew Bagnell, Andrew Y. NgNeurIPS 2005 · OpenReview

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.

Factored MDP transition dynamics and local neighborhood structure

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).

Performance and sample complexity scaling for local vs. global learners

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

Abstract

We consider the scaling of the number of examples necessary to achieve good performance in distributed, cooperative, multi-agent reinforcement learning, as a function of the the number of agents n. We prove a worstcase lower bound showing that algorithms that rely solely on a global reward signal to learn policies confront a fundamental limit: They require a number of real-world examples that scales roughly linearly in the number of agents. For settings of interest with a very large number of agents, this is impractical. We demonstrate, however, that there is a class of algorithms that, by taking advantage of local reward signals in large distributed Markov Decision Processes, are able to ensure good performance with a number of samples that scales as O(log n). This makes them applicable even in settings with a very large number of agents n.
BibTeX
@inproceedings{bagnell2005local,
  author = {J. Andrew Bagnell and Andrew Y. Ng},
  title = {{On Local Rewards and Scaling Distributed Reinforcement Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2005},
  url = {https://openreview.net/forum?id=rk-TaLWdZB},
}
Figure