Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms

By Kaiqing Zhang, Zhuoran Yang, Tamer Basar. 2019

1,692 citations recorded by the source corpus.

Recent years have witnessed significant advances in reinforcement learning (RL), which has registered great success in solving various sequential decision-making problems in machine learning. Most of the successful RL applications, e.g., the games of Go and Poker, robotics, and autonomous driving, involve the participation of more than one single agent, which naturally fall into the realm of multi-agent RL (MARL), a domain with a relatively long history, and has recently re-emerged due to advances in single-agent RL techniques. Though empirically successful, theoretical foundations for MARL are relatively lacking in the literature. In this chapter, we provide a selective overview of MARL, with focus on algorithms backed by theoretical analysis. More specifically, we review the theoretical results of MARL algorithms mainly within two representative frameworks, Markov/stochastic games and extensive-form games, in accordance with the types of tasks they address, i.e., fully cooperative, fully competitive, and a mix of the two. We also introduce several significant but challenging applications of these algorithms. Orthogonal to the existing reviews on MARL, we highlight several new angles and taxonomies of MARL theory, including learning in extensive-form games, decentralized MARL with networked agents, MARL in the mean-field regime, (non-)convergence of policy-based methods for learning in games, etc. Some of the new angles extrapolate from our own research endeavors and interests. Our overall goal with this chapter is, beyond providing an assessment of the current state of the field on the mark, to identify fruitful future research directions on theoretical studies of MARL. We expect this chapter to serve as continuing stimulus for researchers interested in working on this exciting while challenging topic.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Continuous Coordination As a Realistic Scenario for Lifelong Learning (2021, methodology): “LLL for MARL: Standard MARL methods typically focus on the centralized training with decentralized execution setting where agents have access to other agents’ policies and observations during training (Zhang et al., 2019; OroojlooyJadid & Hajinezhad, 2019).”
Reinforcement Learning for Selective Key Applications in Power Systems: Recent Advances and Future Challenges (2021, background): “An overview on related theories and algorithms is provided in [55].”
Reinforcement Learning based Recommender Systems: A Survey (2021, background): “From a game theory prospective, MARL methods can be generally divided into three groups: fully cooperative, fully competitive, and a mix of the two [192].”
Large Language Model Guided Tree-of-Thought (2023, methodology): “While there are many multi-agent reinforcement learning algorithms (MARL) proposed in the literature [29, 30, 31], in this work we adopt a relatively simple approach which uses a modiﬁed version of the REINFORCE algorithm [32] to train the policy networks of the ToT controller and the prompter…”
Single and Multi-Agent Deep Reinforcement Learning for AI-Enabled Wireless Networks: A Tutorial (2020, methodology): “We refer the readers to [85], [87], and [88] for a extensive review of deep MARL literature.”
A survey of multi-agent deep reinforcement learning with communication (2022, neutral): “Zhang et al. [69] and Yang et al. [21] review communication from a theoretical perspective.”
A Review of Safe Reinforcement Learning: Methods, Theory and Applications (2022, background): “Safety Guarantee Efficiently in Large Number of Agents’ Environments Since the decision-making space is incredibly large when the number of agents increases in a safe MARL setting, it is difficult to optimise the policy and control of multi-agents to finish tasks safely [308, 315].”
A Review of Safe Reinforcement Learning: Methods, Theories, and Applications (2024, neutral): “Since the decision-making space is incredibly large when the number of agents increases in a safe MARL setting, it is not easy to optimize the multi-agent policy to ﬁnish tasks safely [257].”
Communication-Efficient and Distributed Learning Over Wireless Networks: Principles and Applications (2020, background): “Depending on the existence of a central controller and the types of interactions, MARL is categorized into centralized/decentralized and cooperative/competitive frameworks, respectively [83].”
Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applications (2021, background): “For applications without central coordinators, e.g., autonomous driving, decentralized MARL is essential wherein the agents only allow the exchange of messages with their neighbors over a communication connectivity graph [163].”
Edge Learning for B5G Networks With Distributed Signal Processing: Semantic Communication, Edge Computing, and Wireless Sensing (2022, positive): “methods discussed above, MARL is also a typical distributed EL technique, which can achieve optimal decision by interacting with the dynamic environments [203], [204].”
A Cordial Sync: Going Beyond Marginal Policies for Multi-Agent Embodied Tasks (2020, methodology): “For a survey of centralized and decentralized MARL methods, kindly refer to [106].”
Applications of reinforcement learning in energy systems (2021, background): “[199,200], and for the distributed optimization-based MARL, cf [201,202].”
Multi-agent deep reinforcement learning: a survey (2021, background): “For theoretical contributions, one may consider the works of Qu et al. (2020), Zhang et al. (2018) and Zhang et al. (2019) whereas the paper of Chu et al. (2020) provides an application perspective in the domain of traffic light control.”
A Survey on Offline Reinforcement Learning: Taxonomy, Review, and Open Problems (2022, background): “Finally, we have not found any offline RL datasets for multiagent environments, which may arise in settings like robot team navigation, smart grid operation, and control of mobile sensor networks [76].”
Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium (2020, background): “…and Sandholm, 2018, 2019), autonomous driving (Shalev-Shwartz et al., 2016), and learning communication and emergent behaviors (Foerster et al., 2016; Lowe et al., 2017; Bansal et al., 2017; Jaques et al., 2018; Baker et al., 2019); see the surveys in Busoniu et al. (2008); Zhang et al. (2019).”
Provable Self-Play Algorithms for Competitive Reinforcement Learning (2020, result): “We refer the readers to several recent surveys for these results (see e.g. Bus¸oniu et al., 2010; Nguyen et al., 2018; OroojlooyJadid and Hajinezhad, 2019; Zhang et al., 2019).”