CoChat
Sign Up
Cited by 28Reinforcement Learning in RoboticsMulti-Agent Systems and NegotiationAdvanced Bandit Algorithms Research

The DOI matches its Crossref record.

Reward Machines for Cooperative Multi-Agent Reinforcement Learning

Open access
Neary, Cyrus, Xu, Zhe, Wu, Bo, Topcu, Ufuk·2021·International Joint Conference on Autonomous Agents and Multiagent Systems
DOI 10.65109/fzbc2933
Open this paper in CoChat — free accountOpen PDF

Abstract

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.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.65109/fzbc2933

Cites

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Previous work has considered parallel compositions of RMs in the multi-agent setting.

    “Previous work has considered parallel compositions of RMs in the multi-agent setting (Neary et al. 2021).”

    From Beyond Fixed Tasks: Unsupervised Environment Design for Task-Level Pairs (2025) · cites this paper as Neary et al. 2021

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

No references could be resolved yet.

Research works printed but not linked: 41

  1. [1][1] Christel Baier and Joost-Pieter Katoen. 2008. Principles of model checking . MIT press. -
  2. [2][2] Filippo Bonchi and Damien Pous. 2013. Checking NFA equivalence with bisimulations up to congruence. ACM SIGPLAN Notices 48, 1 (2013), 457-468. -
  3. [3][3] Craig Boutilier. 1996. Planning, learning and coordination in multiagent decision processes. In Proceedings of the 6th conference on Theoretical aspects of rationality and knowledge . Morgan Kaufmann Publishers Inc., 195-210. -
  4. [4][4] Alberto Camacho, R Toro Icarte, Toryn Q Klassen, Richard Valenzano, and Sheila A McIlraith. 2019. LTL and beyond: Formal languages for reward function specification in reinforcement learning. In Proceedings of the 28th International Joint Conference on Artificial Intelligence . 6065-6073. -
  5. [5][5] Christos G Cassandras and Stephane Lafortune. 2009. Introduction to discrete event systems . Springer Science & Business Media. -
  6. [6][6] Murat Cubuktepe, Zhe Xu, and Ufuk Topcu. 2020. Policy Synthesis for Factored MDPs with Graph Temporal Logic Specifications. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems . 267275. -
  7. [7][7] Jin Dai and Hai Lin. 2014. Automatic synthesis of cooperative multi-agent systems. In 53rd IEEE Conference on Decision and Control . IEEE, 6173-6178. -
  8. [8][8] Franck Djeumou, Zhe Xu, and Ufuk Topcu. 2020. Probabilistic Swarm Guidance with Graph Temporal Logic Specifications. In Proceedings of Robotics: Science and Systems XVI . -
  9. [9][9] Mohammad Ghavamzadeh, Sridhar Mahadevan, and Rajbala Makar. 2006. Hierarchical multi-agent reinforcement learning. Autonomous Agents and Multi-Agent Systems 13, 2 (2006), 197-229. -
  10. [10][10] Carlos Guestrin, Michail Lagoudakis, and Ronald Parr. 2002. Coordinated reinforcement learning. In International Conference on Machine Learning , Vol. 2. Citeseer, 227-234. -
  11. [11][11] Pablo Hernandez-Leal, Michael Kaisers, Tim Baarslag, and Enrique Munoz de Cote. 2019. A Survey of Learning in Multiagent Environments: Dealing with Non-Stationarity. arXiv:1707.09183 [cs.MA] - · arXiv
  12. [12][12] Pablo Hernandez-Leal, Bilal Kartal, and Matthew E Taylor. 2019. A survey and critique of multiagent deep reinforcement learning. Autonomous Agents and Multi-Agent Systems 33, 6 (2019), 750-797. -
  13. [13][13] John E Hopcroft. 1971. Alinear algorithm for testing equivalence of finite automata . Vol. 114. Defense Technical Information Center. -
  14. [14][14] Rodrigo Toro Icarte, Toryn Klassen, Richard Valenzano, and Sheila McIlraith. 2018. Using reward machines for high-level task specification and decomposition in reinforcement learning. In International Conference on Machine Learning . 21122121. -
  15. [15][15] Rodrigo Toro Icarte, Ethan Waldie, Toryn Klassen, Rick Valenzano, Margarita Castro, and Sheila McIlraith. 2019. Learning Reward Machines for Partially Observable Reinforcement Learning. In Advances in Neural Information Processing Systems . 15497-15508. -
  16. [16][16] Mohammad Karimadini and Hai Lin. 2011. Guaranteed global performance through local coordinations. Automatica 47, 5 (2011), 890-898. -
  17. [17][17] Mohammad Karimadini, Hai Lin, and Ali Karimoddini. 2016. Cooperative tasking for deterministic specification automata. Asian Journal of Control 18, 6 (2016), 2078-2087. -
  18. [18][18] Ali Karimoddini, Mohammad Karimadini, and Hai Lin. 2014. Decentralized hybrid formation control of unmanned aerial vehicles. In American Control Conference . IEEE, 3887-3892. -
  19. [19][19] Jelle R Kok and Nikos Vlassis. 2005. Using the max-plus algorithm for multiagent decision making in coordination graphs. In Robot Soccer World Cup . Springer, 1-12. -
  20. [20][20] Ratnesh Kumar and Vijay K Garg. 2012. Modeling and control of logical discrete event systems . Vol. 300. Springer Science & Business Media. -
  21. [21][21] Borja G. León and Francesco Belardinelli. 2020. Extended Markov Games to Learn Multiple Tasks in Multi-Agent Reinforcement Learning. arXiv:2002.06000 [cs.AI] - · arXiv
  22. [22][22] Feng Lin and Walter Murray Wonham. 1988. On observability of discrete-event systems. Information sciences 44, 3 (1988), 173-198. -
  23. [23][23] Michael L Littman. 1994. Markov games as a framework for multi-agent reinforcement learning. In Machine learning proceedings 1994 . Elsevier, 157-163. -
  24. [24][24] Anuj Mahajan, Tabish Rashid, Mikayel Samvelyan, and Shimon Whiteson. 2019. Maven: Multi-agent variational exploration. In Advances in Neural Information Processing Systems . 7613-7624. -
  25. [25][25] Rajbala Makar, Sridhar Mahadevan, and Mohammad Ghavamzadeh. 2001. Hierarchical multi-agent reinforcement learning. In Proceedings of the 5th International Conference on Autonomous Agents . 246-253. -
  26. [26][26] Laetitia Matignon, Guillaume J Laurent, and Nadine Le Fort-Piat. 2012. Independent reinforcement learners in cooperative markov games: a survey regarding coordination problems. The Knowledge Engineering Review 27, 1 (2012), 1-31. -
  27. [27][27] Devaprakash Muniraj, Kyriakos G Vamvoudakis, and Mazen Farhood. 2018. Enforcing signal temporal logic specifications in multi-agent adversarial environments: A deep Q-learning approach. In 2018 IEEE Conference on Decision and Control (CDC) . IEEE, 4141-4146. -
  28. [28][28] Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. 2018. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. In International Conference on Machine Learning . PMLR, 4295-4304. -
  29. [29][29] Mikayel Samvelyan, Tabish Rashid, Christian Schroeder de Witt, Gregory Farquhar, Nantas Nardelli, Tim GJ Rudner, Chia-Man Hung, Philip HS Torr, Jakob Foerster, and Shimon Whiteson. 2019. The StarCraft Multi-Agent Challenge. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems . 2186-2188. -
  30. [30][30] Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Earl Hostallero, and Yung Yi. 2019. Qtran: Learning to factorize with transformation for cooperative multiagent reinforcement learning. In International Conference on Machine Learning . PMLR, 5887-5896. -
  31. [31][31] Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Marc Lanctot, Nicolas Sonnerat, Joel Z Leibo, Karl Tuyls, et al. 2018. Value-decomposition networks for cooperative multi-agent learning based on team reward. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems . 2085-2087. -
  32. [32][32] Richard S Sutton and Andrew G Barto. 2018. Reinforcement learning: An introduction . MIT press. -
  33. [33][33] Ming Tan. 1993. Multi-agent reinforcement learning: Independent vs. cooperative agents. In Proceedings of the 10th International Conference on Machine Learning . 330-337. -
  34. [34][34] Hongyao Tang, Jianye Hao, Tangjie Lv, Yingfeng Chen, Zongzhang Zhang, Hangtian Jia, Chunxu Ren, Yan Zheng, Zhaopeng Meng, Changjie Fan, and Li Wang. 2019. Hierarchical Deep Multiagent Reinforcement Learning with Temporal Abstraction. arXiv:1809.09332 [cs.LG] - · arXiv
  35. [35][35] Arryon D Tijsma, Madalina M Drugan, and Marco A Wiering. 2016. Comparing exploration strategies for q-learning in random stochastic mazes. In 2016 IEEE Symposium Series on Computational Intelligence (SSCI) . IEEE, 1-8. -
  36. [36][36] Elise Van der Pol and Frans A Oliehoek. 2016. Coordinated deep reinforcement learners for traffic light control. Proceedings of Learning, Inference and Control of Multi-Agent Systems (at NIPS 2016) (2016). -
  37. [37][37] Hado Van Hasselt, Arthur Guez, and David Silver. 2016. Deep reinforcement learning with double q-learning. In Proceedings of the 13th AAAI Conference on Artificial Intelligence . -
  38. [38][38] Christopher JCH Watkins and Peter Dayan. 1992. Q-learning. Machine learning 8, 3-4 (1992), 279-292. -
  39. [39][39] K Wong. 1998. On the complexity of projections of discrete-event systems. In Proceedings of the International Workshop of Discrete Event Systems . Citeseer, 201-206. -
  40. [40][40] Zhe Xu, Ivan Gavran, Yousef Ahmad, Rupak Majumdar, Daniel Neider, Ufuk Topcu, and Bo Wu. 2020. Joint inference of reward machines and policies for reinforcement learning. In Proceedings of the International Conference on Automated Planning and Scheduling , Vol. 30. 590-598. -
  41. [41][41] Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. 2019. Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms. arXiv:1911.10635 [cs.LG] · arXiv

Cited by

Sorted by citations

Metadata

Authors
Neary, C., Xu, Z., Wu, B., & Topcu, U.
Affiliations
  • The University of Texas at Austin (US)
  • Arizona State University (US)
ORCID
Venue
International Joint Conference on Autonomous Agents and Multiagent Systems
Publisher
IEEE Computer Society
Published
2021-05-03
Pages
934-942
ISSN
  • 1548-8403 (ISSN-L)
  • 1558-2914
DOI
10.65109/fzbc2933
OpenAlex
W3176501542
Cited by
28
References
0
Citations by year
2026: 1 · 2025: 6 · 2024: 9 · 2023: 5 · 2022: 4 · 2021: 2
FWCI
2.31
Type
conference paper
Language
en
Open access
Locations
  • Adaptive Agents and Multi-Agents Systems (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Reinforcement Learning in Robotics
  • Physical Sciences › Computer Science › Artificial Intelligence › Multi-Agent Systems and Negotiation
  • Social Sciences › Decision Sciences › Management Science and Operations Research › Advanced Bandit Algorithms Research
Keywords
reward machines, Mealy machines, cooperative multi-agent reinforcement learning, task decomposition, decentralized learning, value function bounds, hierarchical reinforcement learning

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review