Asynchronous Cooperative Multi-Agent Reinforcement Learning with Limited Communication

Technical Summary: Asynchronous Cooperative Multi-Agent Reinforcement Learning with Limited Communication

Problem Statement
The paper addresses the challenge of coordinating multiple autonomous agents in unknown, communication-constrained environments. Traditional Multi-Agent Reinforcement Learning (MARL) approaches typically assume synchronous communication, where agents broadcast states and execute actions simultaneously at every time step. However, in extreme environments such as space or underwater operations, communication is often limited by power constraints, latency, or physical obstructions. In these scenarios, agents operate on independent time scales and cannot communicate frequently or synchronously. Existing asynchronous MARL methods often compensate for the lack of synchronization by increasing communication frequency, which defeats the purpose of operating in constrained environments. The core problem is to develop a MARL framework that enables effective cooperation while minimizing communication overhead and accommodating asynchronous, infrequent interactions.

Methodology: AsynCoMARL
The authors propose AsynCoMARL, an asynchronous MARL framework that utilizes graph transformers to learn communication protocols from dynamic graphs. The methodology is built upon the following components:

• Asynchronous Formulation: Unlike standard MARL where all agents act at every global time step $t$, AsynCoMARL introduces a specific time scale $\tau^{(i)}$ for each agent $i$. Agents take actions at different intervals determined by a randomized delay parameter $\mu$. The replay buffer is constructed based on these action-specific time steps rather than global time steps.
• Dynamic Graph Representation: The environment is modeled as a dynamic, weighted, directed graph. Nodes represent agents, obstacles, and goals. Edges are formed dynamically based on two conditions:
  1. Proximity: Agents must be within a specific communication radius $\lambda$.
  2. Activity: Edges only exist between agents if they are both active (taking an action) at the same time step.
     This results in a masked adjacency matrix where inactive agents or those outside the communication range are excluded from the graph structure during message passing.
• Graph Transformer Architecture: The core of the communication protocol is a Graph Transformer based on the Unified Message Passing Model (UniMP). It processes node features (position, velocity, goal location, entity type) and edge features (Euclidean distance). The transformer uses multi-head dot-product attention to selectively prioritize messages from neighboring agents based on relevance.
• Centralized Training, Decentralized Execution (CTDE):
  • Critic: A centralized critic receives the full graph embedding (via global mean pooling) to evaluate the value function, utilizing the global state and the complete graph context.
  • Actor: Each agent has an individual actor network that conditions its policy on its local observation and the aggregated message from its local graph neighborhood.
• Reward Structure: The paper experiments with various reward formulations. The most effective configuration identified is a "Single Goal-Reaching Reward + Active Agent Sharing," where agents receive a one-time reward upon reaching a goal, and collaborative rewards are shared only among agents that are actively communicating at that specific time step. This prevents agents from "hiding" after reaching a goal and encourages active coordination.

Key Contributions

1. Proposal of AsynCoMARL: The introduction of a graph-transformer-based communication protocol specifically designed for asynchronous MARL, utilizing dynamic graphs to capture infrequent and asynchronous interactions.
2. Empirical Evaluation: The method is evaluated on two benchmarks: Cooperative Navigation (simulating satellite dynamics) and Rover-Tower (simulating planetary exploration).
3. Performance with Reduced Communication: The study demonstrates that AsynCoMARL achieves success and collision rates comparable to leading baselines while significantly reducing the number of messages passed between agents.

Experimental Results
The authors conducted experiments with varying numbers of agents ($N=3, 5, 7, 10$) in the Cooperative Navigation environment and a 4-rover/4-tower scenario in the Rover-Tower environment.

• Communication Efficiency: AsynCoMARL achieved similar success rates to baselines like asyncMAPPO and Actor-Attention-Critic but with 26% fewer messages passed between agents.
• Scalability: In the Cooperative Navigation task with $N=10$, AsynCoMARL maintained a high success rate (86%) with a very low communication frequency ($f_{comm} = 0.05$). In contrast, baselines like GCS struggled to scale without additional training time, and TransfQmix suffered from low success rates despite low collisions.
• Rover-Tower Performance: In the more complex Rover-Tower environment, AsynCoMARL achieved a 50% success rate with a communication frequency of 0.14, outperforming Actor-Attention-Critic (56% success, 0.21 frequency) in terms of communication efficiency and episode completion time, despite using a single network for both agent classes rather than separate networks.
• Ablation Studies:
  • Graph Transformer: Removing the graph transformer resulted in significantly higher collision rates and lower success rates, particularly when the number of active agents was low, confirming the importance of the attention mechanism in dynamic graphs.
  • Reward Formulation: The "Single Goal-Reaching Reward + Active Agent Sharing" structure yielded the best results (97% success rate for $N=3$), highlighting that limiting rewards to active, communicating agents prevents agents from ceasing cooperation once a goal is reached.

Significance and Claims
The paper claims that AsynCoMARL effectively addresses the trade-off between communication frequency and coordination performance in asynchronous settings. By leveraging dynamic graphs and graph transformers, the method allows agents to learn when and with whom to communicate, rather than relying on constant broadcasting or synchronous updates. The authors state that their approach enables agents to operate independently on different time scales while still receiving sufficient information to coordinate effectively. The work suggests that asynchronous coordination does not necessarily require increased communication overhead if the communication protocol is learned adaptively based on the dynamic topology of agent interactions. The paper concludes that this framework is a step toward more realistic multi-agent systems for space and planetary exploration where communication is inherently constrained.