DistSPECTRL: Distributing Specifications in Multi-Agent Reinforcement Learning Systems

Joe Eappen, Suresh Jagannathan

Introduction

Reinforcement Learning (RL) has demonstrated remarkable success in solving complex control tasks, yet it remains notoriously difficult to tune due to the "sparse reward" problem. Agents often struggle to learn when feedback is only provided upon the completion of a long, multi-stage objective. While frameworks like SPECTRL have addressed this in single-agent settings by using formal logic to automatically shape rewards, extending these methods to Multi-Agent Reinforcement Learning (MARL) introduces a significant scalability challenge.

In a multi-agent environment, a centralized task monitor must track every possible combination of agent states, leading to an exponential state-space explosion ($O(K^N)$ for $N$ agents and $K$ subtasks). Furthermore, agents must balance individual constraints—such as collision avoidance—with collective goals like group synchronization. DistSPECTRL addresses these hurdles by decentralizing the task-tracking process, allowing MARL systems to satisfy complex global and local objectives efficiently.

Methodology

DistSPECTRL introduces a framework that distributes formal specifications across agents, transforming a centralized monitoring problem into a manageable, distributed one. The methodology relies on four primary innovations:

1. Local vs. Global Predicates

The framework distinguishes between objectives based on their scope. Local predicates depend solely on an individual agent's state (e.g., "Agent A must stay within bounds"), while global predicates require knowledge of the entire system (e.g., "All agents must meet at the rendezvous point").

2. Distributed Composite Task Monitors

Rather than relying on a single centralized "brain," DistSPECTRL equips every agent with a copy of a "Composite Task Monitor." This allows agents to track their own progress locally. By distributing the automaton, the state-space complexity is reduced from exponential to linear ($O(NK)$), making the system significantly more scalable.

3. Synchronization States

To minimize communication overhead, the system identifies specific "Sync" states within the task logic. Agents operate independently for the majority of the task, only requiring consensus and synchronization when the logical specification dictates that a collective milestone must be reached before proceeding.

4. MA-Dec Scaling

To handle large-scale swarms, the authors propose a curriculum learning approach called MA-Dec Scaling. This method is designed for "MA-Decomposable" specifications. Training begins with small groups of agents; once they successfully satisfy the goal, these groups are merged into larger collectives. This progressively narrows the search space, allowing the entire swarm to coordinate effectively without the need to learn complex group dynamics from scratch.

Experimental Evaluation

The researchers evaluated DistSPECTRL across three distinct environments designed to test navigation, dimensionality, and tactical coordination:

  1. 2D Navigation: A benchmark where three agents must reach a specific sequence of coordinates.
  2. 3D Particle Motion: A higher-dimensional environment used to test the framework's scaling potential in complex physical spaces.
  3. StarCraft Multi-Agent Challenge (SMAC): Using the "8m" map (8 marines vs. 8 marines), the authors introduced a "kiting" specification. This requires agents to balance attacking the enemy with maintaining a safe distance to avoid return fire, a task requiring high-precision synchronization.

Key Insights and Results

Scalability and Performance

In tests involving 6 and 10 agents, centralized SPECTRL baselines failed to converge or performed poorly due to the state-space explosion. In contrast, DistSPECTRL maintained nearly 100% task completion rates. The results demonstrate that distributing the logical automaton allows agents to maintain a "local version" of a global truth, checking in with others only when necessary.

Tactical Coordination in StarCraft II

In the SMAC environment, DistSPECTRL successfully learned complex kiting behaviors. It achieved an 86.79% satisfaction rate for the kiting specification, whereas centralized approaches and baselines without monitor states failed completely (0% success).

Automatic Reward Shaping

By utilizing the "depth" of the task monitor (the agent's progress through the logical sequence), DistSPECTRL automatically generates a dense reward signal. This effectively provides a "getting warmer" feedback loop, guiding agents through complex tasks even before the final objective is reached.

Limitations and Future Work

While DistSPECTRL represents a significant advancement in MARL, several areas for future research remain:

  • Heterogeneity: The current model assumes homogeneous agents with identical state and action spaces. Future iterations could extend this to heterogeneous swarms, such as ground robots coordinating with aerial drones.
  • Training Centralization: Although execution is decentralized, the training phase still utilizes a centralized critic and requires access to the global state to evaluate global predicates.
  • Communication Robustness: The current synchronization relies on a majority-vote consensus. Future work may explore more sophisticated protocols to handle the unreliable or noisy communication links common in real-world deployments.

Conclusion

DistSPECTRL provides a robust framework for applying formal specifications to multi-agent systems. By decentralizing task monitoring and employing a logic-based curriculum, it overcomes the scalability limits of previous approaches, enabling agents to solve complex, coordinated tasks with high efficiency and reliability.

Summary updated

BibTeX
@inproceedings{eappen2022distspectrl,
  author = {Joe Eappen and Suresh Jagannathan},
  title = {{DistSPECTRL: Distributing Specifications in Multi-Agent Reinforcement Learning Systems}},
  booktitle = {ECML/PKDD},
  year = {2022},
  url = {https://openreview.net/forum?id=2rAirZMQ1Yp},
}
Figure