# Reward Machines for Cooperative Multi-Agent Reinforcement Learning

arXiv: https://arxiv.org/abs/2007.01962 · HTML: https://mlsanity.com/paper/2007.01962/

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jul 2020.

## Built on by (most cited first, 30 of 35)

- [Compositional Reinforcement Learning from Logical Specifications](https://mlsanity.com/paper/2106.13906/) (2021)
- [Verifiable and Compositional Reinforcement Learning Systems](https://mlsanity.com/paper/2106.05864/) (2021)
- [Automaton-Based Representations of Task Knowledge from Generative Language Models](https://mlsanity.com/paper/2212.01944/) (2022)
- [Reward Machines for Deep RL in Noisy and Uncertain Environments](https://mlsanity.com/paper/2406.00120/) (2024)
- [Noisy Symbolic Abstractions for Deep RL: A case study with Reward Machines](https://mlsanity.com/paper/2211.10902/) (2022)
- [Specification-Guided Learning of Nash Equilibria with High Social Welfare](https://mlsanity.com/paper/2206.03348/) (2022)
- [Decentralized Graph-Based Multi-Agent Reinforcement Learning Using Reward Machines](https://mlsanity.com/paper/2110.00096/) (2021)
- [Reinforcement Learning with Stochastic Reward Machines](https://mlsanity.com/paper/2510.14837/) (2025)
- [Learning Quadruped Locomotion Policies using Logical Rules](https://mlsanity.com/paper/2107.10969/) (2021)
- [Lifelong Reinforcement Learning with Temporal Logic Formulas and Reward Machines](https://mlsanity.com/paper/2111.09475/) (2021)
- [Categorical semantics of compositional reinforcement learning](https://mlsanity.com/paper/2208.13687/) (2022)
- [Reinforcement Learning with Knowledge Representation and Reasoning: A Brief Survey](https://mlsanity.com/paper/2304.12090/) (2023)
- [ARM-FM: Automated Reward Machines via Foundation Models for Compositional Reinforcement Learning](https://mlsanity.com/paper/2510.14176/) (2025)
- [Hierarchies of Reward Machines](https://mlsanity.com/paper/2205.15752/) (2022)
- [Efficient Reinforcement Learning in Probabilistic Reward Machines](https://mlsanity.com/paper/2408.10381/) (2024)
- [Logic-based Reward Shaping for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2206.08881/) (2022)
- [DistSPECTRL: Distributing Specifications in Multi-Agent Reinforcement Learning Systems](https://mlsanity.com/paper/2206.13754/) (2022)
- [Verifiable Reinforcement Learning Systems via Compositionality](https://mlsanity.com/paper/2309.06420/) (2023)
- [Logical Specifications-guided Dynamic Task Sampling for Reinforcement Learning Agents](https://mlsanity.com/paper/2402.03678/) (2024)
- [Multi-Agent Reinforcement Learning with a Hierarchy of Reward Machines](https://mlsanity.com/paper/2403.07005/) (2024)
- [Learning Reward Machines in Cooperative Multi-Agent Tasks](https://mlsanity.com/paper/2303.14061/) (2023)
- [Discovering Causality for Efficient Cooperation in Multi-Agent Environments](https://mlsanity.com/paper/2306.11846/) (2023)
- [Learning to Model Diverse Driving Behaviors in Highly Interactive Autonomous Driving Scenarios with Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2402.13481/) (2024)
- [Beyond Fixed Tasks: Unsupervised Environment Design for Task-Level Pairs](https://mlsanity.com/paper/2511.12706/) (2025)
- [PlatoLTL: Scaling LTL-Guided Multi-Task RL](https://mlsanity.com/paper/2601.22891/) (2026)
- [Automata-Conditioned Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2511.02304/) (2025)
- [Model-Based Reinforcement Learning in Discrete-Action Non-Markovian Reward Decision Processes](https://mlsanity.com/paper/2512.14617/) (2025)
- [Sample Efficient Reinforcement Learning by Automatically Learning to Compose Subtasks](https://mlsanity.com/paper/2401.14226/) (2024)
- [Maximally Permissive Reward Machines](https://mlsanity.com/paper/2408.08059/) (2024)
- [Synthesis of Reward Machines for Multi-Agent Equilibrium Design (Full Version)](https://mlsanity.com/paper/2408.10074/) (2024)

## Abstract (arXiv)

In cooperative multi-agent reinforcement learning, a collection of agents learns to interact in a shared environment to achieve a common goal. We propose the use of reward machines (RM) -- Mealy machines used as structured representations of reward functions -- to encode the team's task. The proposed novel interpretation of RMs in the multi-agent setting explicitly encodes required teammate interdependencies, allowing the team-level task to be decomposed into sub-tasks for individual agents. We define such a notion of RM decomposition and present algorithmically verifiable conditions guaranteeing that distributed completion of the sub-tasks leads to team behavior accomplishing the original task. This framework for task decomposition provides a natural approach to decentralized learning: agents may learn to accomplish their sub-tasks while observing only their local state and abstracted representations of their teammates. We accordingly propose a decentralized q-learning algorithm. Furthermore, in the case of undiscounted rewards, we use local value functions to derive lower and upper bounds for the global value function corresponding to the team task. Experimental results in three discrete settings exemplify the effectiveness of the proposed RM decomposition approach, which converges to a successful team policy an order of magnitude faster than a centralized learner and significantly outperforms hierarchical and independent q-learning approaches.