Decomposing Temporal Equilibrium Strategy for Coordinated Distributed Multi-Agent Reinforcement Learning

Chenyang Zhu, Wen Si, Jinyu Zhu, Zhihao JiangAAAI 2024 · DOI

Abstract

This paper introduces MATEA (Multi-Agent Temporal Equilibrium Analysis), a novel framework designed to facilitate agent coordination in complex, time-sensitive environments. By bridging formal logic and multi-agent reinforcement learning (MARL), MATEA synthesizes global temporal equilibrium strategies from Linear Temporal Logic (LTL) specifications and decomposes them into decentralized reward machines. This approach allows agents to satisfy non-Markovian requirements while drastically reducing state-space complexity. Experimental results show that MATEA significantly outperforms centralized methods and existing state-of-the-art tools in both computational efficiency and learning performance.

Introduction

Standard Reinforcement Learning (RL) typically focuses on maximizing scalar rewards based on the current state. However, many real-world tasks involve complex "temporal" requirements—non-Markovian rules where the optimal action depends on the system's history (e.g., "visit location A, then B, only if agent X has reached C"). Integrating Linear Temporal Logic (LTL) into Multi-Agent RL (MARL) to handle these rules is challenging due to the exponential growth of the state space and the difficulty of ensuring decentralized coordination toward a global goal.

The MATEA Framework

The authors propose a hierarchical framework that translates high-level temporal goals into decentralized "reward machines." The process involves several key stages:

  1. Specification and Synthesis: Agent goals and environmental constraints are defined in LTL and converted into Deterministic Parity Words (DPW). The problem is then treated as a parity game to find a global Temporal Equilibrium Strategy.
  2. Decomposition: The core innovation of MATEA is decomposing the global automaton into Individual Strategy Automata based on local events relevant to each specific agent.
  3. Reward Machines (RM): These individual automata are converted into Reward Machines that provide internal rewards, guiding agents through complex logical sequences.
  4. Simplification: A pruning function eliminates redundant states and self-loops, leading to massive reductions in the state space agents must navigate.
Overview of the MATEA framework, illustrating the pipeline from LTL specification to decentralized reward machines.

Experimental Evaluation

The framework was evaluated in a 40x40 grid-world across several scenarios, including sequential coordination (coop(n)), networking protocols (gossip(3)), and mutual exclusion models (ring-based(3)).

Key Results

  • Computational Efficiency: In the coop(7) task, MATEA synthesized strategies in 42.03 ms, compared to 449.69 ms for the previous state-of-the-art tool, EVE.
  • State-Space Reduction: For the same 7-agent task, MATEA reduced the strategy from 1092 states to just 14 states.
  • Learning Performance: Decentralized training using MATEA's decomposed strategies proved far more effective than centralized paradigms. In coop(3), MATEA achieved an accumulated reward of 250, while centralized models struggled to reach 30, often failing to learn the necessary inter-agent dependencies.
Comparison of learning performance between decentralized MATEA and centralized paradigms across different task specifications and maps.

Discussion and Conclusion

MATEA demonstrates that logic-based reward shaping through decomposition is a powerful tool for MARL. By transforming sparse global rewards into dense local logical rewards, it enables agents to master complex temporal tasks that were previously computationally intractable. Future work will focus on extending MATEA to continuous state spaces and integrating it with Deep RL algorithms like DQN and DDPG to handle more complex sensory inputs.

Summary updated

BibTeX
@inproceedings{zhu2024decomposing,
  author = {Chenyang Zhu and Wen Si and Jinyu Zhu and Zhihao Jiang},
  title = {{Decomposing Temporal Equilibrium Strategy for Coordinated Distributed Multi-Agent Reinforcement Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i16.29713},
}
Figure