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:
- 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.
- Decomposition: The core innovation of MATEA is decomposing the global automaton into Individual Strategy Automata based on local events relevant to each specific agent.
- Reward Machines (RM): These individual automata are converted into Reward Machines that provide internal rewards, guiding agents through complex logical sequences.
- Simplification: A pruning function eliminates redundant states and self-loops, leading to massive reductions in the state space agents must navigate.
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.
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