Learning Multi-agent Communication under Limited-bandwidth Restriction for Internet Packet Routing

Hangyu Mao, Zhibo Gong, Zhengchao Zhang, Zhen Xiao, Yan NiarXiv 2019 · OpenReview

TL;DR

This paper tackles the challenge of limited bandwidth in multi-agent communication for real-world applications like internet packet routing. They introduce GACML, a novel approach that uses a gating mechanism to intelligently prune unnecessary messages, allowing agents to communicate effectively even under strict bandwidth constraints.

What Problem Does This Paper Address?

In many real-world multi-agent systems, communication is crucial for coordination and performance. However, these systems often operate under severe bandwidth limitations, meaning agents cannot afford to send messages constantly. Existing Deep Reinforcement Learning (DRL) methods for multi-agent communication typically assume unlimited communication channels, leading agents to send messages incessantly in every control cycle. This makes them impractical for scenarios like internet packet routing, where link capacities are finite. The paper aims to bridge this gap by developing a communication strategy that is both effective and bandwidth-aware.

Methods

The authors first propose ACML (Actor-Critic with Message Learning), a foundational model that combines the strengths of existing DRL-based communication methods. ACML features separate networks for message generation (MessageGeneratorNet) and policy execution (ActorNet) within each agent. A shared MessageCoordinatorNet aggregates local messages into a global message for each agent, enabling full observability. A shared CriticNet aids in training.

To address the bandwidth limitation, ACML is extended to GACML (Gated Actor-Critic with Message Learning). The core innovation here is a gating mechanism implemented by an additional GatingNet in each agent. This GatingNet learns to predict the probability of a message being beneficial. Based on this probability and a threshold, a gate value (0 or 1) is generated. If the gate is closed (0), a zero vector is sent, effectively pruning the message. This "zero padding" is crucial for signaling to the coordinator that a message was intentionally omitted.

The training of the gating mechanism is achieved through a novel auxiliary task. This task aims to train the GatingNet to predict whether sending a message will lead to a significant improvement in the Q-value (a measure of expected future rewards) compared to not sending it. This allows the gating mechanism to adaptively prune messages that offer little to no benefit, while preserving those that are critical for performance. The paper also discusses methods for setting the pruning threshold, including fixed and dynamic approaches.

Datasets

The paper evaluates its methods on:

  • Real-world packet routing tasks: Specifically, three network topologies (small, moderate, and large) are used, inspired by internet traffic engineering and a collaborator's industrial needs. These topologies differ in the number of routers, links, and paths.
  • Four benchmark tasks: These are mentioned as being in the appendix but not detailed in the main text.

Key Insights and Ideas

  • Bandwidth is a critical, often overlooked, constraint: The paper highlights that most DRL communication methods ignore practical bandwidth limitations, rendering them unsuitable for real-world deployment.
  • Intelligent message pruning is key: Instead of sending messages all the time, agents can learn to selectively communicate, significantly reducing bandwidth usage without sacrificing performance.
  • "Zero padding" is an effective signaling mechanism: Using zero vectors to represent pruned messages provides a clear signal to the receiving agent and coordinator, preventing misinterpretations of stale or absent information.
  • Auxiliary tasks can train non-differentiable components: The paper demonstrates a clever way to train the gating mechanism, which involves a non-differentiable threshold function, by framing it as a supervised learning problem with a carefully designed auxiliary task.
  • Adaptability is crucial: The dynamic threshold setting for message pruning allows the system to adapt to changing environmental conditions, a significant advantage in real-world scenarios.

Key Results

  • Significant message reduction: The gating mechanism can prune more than 80% of messages with minimal impact on performance. In one experiment, GACML achieved 56.3% message reduction while only experiencing an 8.2% decrease in rewards compared to ACML.
  • Outperforms state-of-the-art: GACML significantly outperforms existing DRL-based (IND-AC, MADDPG, AMP) and rule-based (WCMP, TeXCP) methods in packet routing tasks, especially in more complex topologies.
  • Improved stability and convergence: GACML demonstrates a higher convergence ratio and greater stability during training compared to other methods, particularly in the moderate topology.
  • Effective bandwidth control: The method can control message quantity to a desired threshold, making it practical for limited-bandwidth environments.

Limitations and Future Work

  • Limitations:
    • The paper notes that the ATOC and IC3Net methods are unsuitable for the routing tasks due to their homogeneous agent structure.
  • MADDPG-M is limited to 2D tasks.
  • SchedNet's reliance on a hard-coded parameter M for communication scheduling is difficult to apply to real-world systems.
  • The paper mentions evaluating the use of another GatingNet to decide whether to prune the global message M, which was not explored in this work.
  • Future Work:
    • The authors suggest exploring the use of another GatingNet to decide whether to prune the global message M.
  • The paper's focus is on limited bandwidth; future work could explore other communication constraints like message delay or privacy.

Summary updated

Abstract

Communication is an important factor for the big multi-agent world to stay organized and productive. Recently, the AI community has applied the Deep Reinforcement Learning (DRL) to learn the communication strategy and the control policy for multiple agents. However, when implementing the communication for real-world multi-agent applications, there is a more practical limited-bandwidth restriction, which has been largely ignored by the existing DRL-based methods. Specifically, agents trained by most previous methods keep sending messages incessantly in every control cycle; due to emitting too many messages, these methods are unsuitable to be applied to the real-world systems that have a limited bandwidth to transmit the messages. To handle this problem, we propose a gating mechanism to adaptively prune unprofitable messages. Results show that the gating mechanism can prune more than 80% messages with little damage to the performance. Moreover, our method outperforms several state-of-the-art DRL-based and rule-based methods by a large margin in both the real-world packet routing tasks and four benchmark tasks.
BibTeX
@misc{mao2019learning,
  author = {Hangyu Mao and Zhibo Gong and Zhengchao Zhang and Zhen Xiao and Yan Ni},
  title = {{Learning Multi-agent Communication under Limited-bandwidth Restriction for Internet Packet Routing}},
  year = {2019},
  eprint = {1903.05561},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1903.05561},
}
Figure