Synthesising Reward Machines for Cooperative Multi-Agent Reinforcement Learning

Summary

This partial ingest is based on the extracted full PDF text. Varricchione et al. synthesize team and individual Reward Machines for cooperative multi-agent reinforcement learning from an Alternating-Time Temporal Logic specification and a model of the agents’ environment. The synthesized multi-agent reward machine can then be decomposed into individual projected reward machines for decentralized Q-learning, avoiding hand-built reward machines while preserving comparable or better task performance in the reported domains.

Key Claims

• Multi-agent reward machines help decompose team tasks in cooperative MARL, but prior work often assumed the team reward machine was hand-authored.
• ATL is a natural high-level language for specifying team tasks because it directly talks about coalition strategies.
• Given an ATL witness strategy for a coalition, the paper synthesizes both a team reward machine and individual reward machines for agents.
• Automatically synthesized reward machines perform broadly similarly to, and sometimes better than, hand-written reward machines in CooperativeButtons and Overcooked evaluations.
• ATL specifications make additional strategic or safety constraints easier to incorporate than low-level reward-machine hand design.

Methods / Formalism

• A reward machine is given as

$$R=⟨U,u_I,\Sigma ,t,r⟩,$$

with RM states, initial state, event alphabet, transition function, and transition reward.

• A cooperative Markov game with a reward machine combines a multi-agent environment, labeling function, and RM over joint events.
• The task specification is an ATL formula such as a coalition ability claim <<A>>phi.
• The synthesis procedure uses an ATL model checker to obtain a uniform strategy witness, then derives a coalitional reward machine and projected individual reward machines from the event sequences compatible with that witness.
• Cooperative Reward Machine Synthesis records the synthesis and projection construction.

Evidence / Experiments

• Domains: CooperativeButtons and Overcooked.
• Learning setup: Decentralized Q-Learning with Projected Reward Machines (DQPRM).
• Comparison: DQPRM using automatically synthesized RMs versus hand-written RMs from prior work.
• Reported behavior: synthesized RMs successfully encode the task, and learned policies achieve comparable or better performance in the evaluated settings.

Connections

• Extends Reward Machines toward cooperative multi-agent settings and specification-driven synthesis.
• Connects Alternating-Time Temporal Logic to reward-machine construction: ATL formulas provide strategic task specifications, while reward machines provide learning-facing progress signals.
• Adds a formal-methods route into Safe Multi-Agent Reinforcement Learning, especially for decentralized task decomposition.
• Complements Furelos-Blanco2023 - Hierarchies of Reward Machines: both reduce manual reward-machine design, one through hierarchy/ILASP and one through ATL witness synthesis.

Open Questions

• The approach assumes a model suitable for ATL model checking and a witness strategy; scaling that requirement to complex learned environments is nontrivial.
• The paper focuses on fully cooperative settings; non-cooperative cases are left for future work.
• Synthesizing partial-order or multi-strategy reward machines could make the resulting learning guidance less tied to one witness strategy.

Citation

Varricchione, G., Alechina, N., Dastani, M., and Logan, B. (2023). Synthesising Reward Machines for Cooperative Multi-Agent Reinforcement Learning. In Multi-Agent Systems - 20th European Conference, EUMAS 2023, LNCS 14282, 328-344. DOI: 10.1007/978-3-031-43264-4_21.