Research map / Multi-agent systems and games / Cooperative multi-agent RL
Decomposing Temporal Equilibrium Strategy for Coordinated Distributed Multi-Agent Reinforcement Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes MATEA, a hierarchical framework that synthesizes temporal equilibrium strategies for multi-agent LTL games via parity games, decomposes them into individual reward machines, and trains agents with tabular Q-learning in a decentralized setting.
Problem
Multi-agent reinforcement learning with non-Markovian LTL goals suffers from high computational cost of equilibrium strategy synthesis and exponential state-space growth with the number of agents, plus difficulty designing reward functions.
Approach
Reduce Nash-equilibrium strategy synthesis for multi-agent LTL games to an emptiness check over deterministic parity/Streett automata with optimized states, then decompose the synthesized team strategy into per-agent reward machines based on local event sets, with forward simulation used to argue Nash equilibrium is preserved under parallel composition.
Key results
- MATEA reduces analysis time on coop(7) to 42.03 ms versus 449.69 ms for EVE, and state count from 1092 to 14.
- On coop(2), decentralized Q-learning reaches steady accumulated reward of 90 versus 10 for centralized.
- On coop(3), decentralized reaches accumulated reward of 250 versus 30 for centralized.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use MATEA instead of EVE for temporal equilibrium synthesis | MATEA · coop(5) | states: 352 -> 10 | Helped |
| use MATEA instead of EVE for temporal equilibrium synthesis | MATEA · coop(7) | time (ms): 449.69 -> 42.03 | Helped |
| use MATEA instead of EVE for temporal equilibrium synthesis | MATEA · gossip(3) | states: 36 -> 9 | Helped |
| use MATEA instead of EVE for temporal equilibrium synthesis | MATEA · ring-based(3) | states: 136 -> 8 | Helped |
| decompose the temporal equilibrium strategy for decentralized rather than centralized MARL | Q-learning with temporal equilibrium strategies · coop(2), map:0 | reward per episode: 10 -> 90 | Helped |
| decompose the temporal equilibrium strategy for decentralized rather than centralized MARL | Q-learning with temporal equilibrium strategies · coop(3), map:0 | reward per episode: 30 -> 250 | Helped |
Limitations
- Only tabular Q-learning in discrete state and action spaces is used.
- The paper's complexity analysis still yields a worst-case state count exponential in the formula size.
- Experiments are limited to grid-world scenarios with a small number of agents.
Experimental setup
Datasets: procedurally generated 40x40 grid-world maps in OpenAI Gym gossip(3) scenario (from Hammond et al. 2021) ring-based(3) scenario (from Gutierrez et al. 2017)
Benchmarks: coop(2) coop(3) coop(5) coop(7) gossip(3) ring-based(3)
Metrics: number of states number of state transitions analysis time (ms) accumulated reward per episode
Baselines: EVE centralized MARL Q-learning
Builds on: reward machines Nash equilibrium for multi-agent LTL games (EVE) Streett automata Dec-POMDP
Closest papers by meaning
- Revisiting Some Common Practices in Cooperative Multi-Agent Reinforcement Learning (ICML 2022 · similarity 0.90)
- Foundations of Multi-Agent Learning in Dynamic Environments: Where Reinforcement Learning Meets Strategic Decision-Making (AAAI 2025 · similarity 0.89)
- Multi-Agent Meta-Reinforcement Learning: Sharper Convergence Rates with Task Similarity (NeurIPS 2023 · similarity 0.89)
- Coordination Between Individual Agents in Multi-Agent Reinforcement Learning (AAAI 2021 · similarity 0.89)
- DeCOM: Decomposed Policy for Constrained Cooperative Multi-Agent Reinforcement Learning (AAAI 2023 · similarity 0.89)
- Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.