Multi-agent reinforcement learning

Similarly to single-agent reinforcement learning, multi-agent reinforcement learning is modeled as some form of a Markov decision process (MDP). For example,

• A set ${\displaystyle S}$ of environment states.
• One set ${\displaystyle {\mathcal {A}}_{i}}$ of actions for each of the agents ${\displaystyle i\in I=\{1,...,N\}}$.
• ${\displaystyle P_{\overrightarrow {a}}(s,s')=\Pr(s_{t+1}=s'\mid s_{t}=s,{\overrightarrow {a}}_{t}={\overrightarrow {a}})}$ is the probability of transition (at time ${\displaystyle t}$) from state ${\displaystyle s}$ to state ${\displaystyle s'}$ under joint action ${\displaystyle {\overrightarrow {a}}}$.
• ${\displaystyle {\overrightarrow {R}}_{\overrightarrow {a}}(s,s')}$ is the immediate joint reward after the transition from ${\displaystyle s}$ to ${\displaystyle s'}$ with joint action ${\displaystyle {\overrightarrow {a}}}$.

In settings with perfect information, such as the games of chess and Go, the MDP would be fully observable. In settings with imperfect information, especially in real-world applications like self-driving cars, each agent would access an observation that only has part of the information about the current state. In the partially observable setting, the core model is the partially observable stochastic game in the general case, and the decentralized POMDP in the cooperative case.

When multiple agents are acting in a shared environment their interests might be aligned or misaligned. MARL allows exploring all the different alignments and how they affect the agents' behavior:

• In pure competition settings, the agents' rewards are exactly opposite to each other, and therefore they are playing against each other.
• Pure cooperation settings are the other extreme, in which agents get the exact same rewards, and therefore they are playing with each other.
• Mixed-sum settings cover all the games that combine elements of both cooperation and competition.

Mixed-sum settings

In this mixed sum setting, each of the four agents is trying to reach a different goal. Each agent's success depends on the other agents clearing its way, even though they aren't directly incentivized to assist each other.[16]

Most real-world scenarios involving multiple agents have elements of both cooperation and competition. For example, when multiple self-driving cars are planning their respective paths, each of them has interests that are diverging but not exclusive: Each car is minimizing the amount of time it's taking to reach its destination, but all cars have the shared interest of avoiding a traffic collision.[17]

Zero-sum settings with three or more agents often exhibit similar properties to mixed-sum settings, since each pair of agents might have a non-zero utility sum between them.

Mixed-sum settings can be explored using classic matrix games such as prisoner's dilemma, more complex sequential social dilemmas, and recreational games such as Among Us,[18] Diplomacy[19] and StarCraft II.[20][21]

Mixed-sum settings can give rise to communication and social dilemmas.

As in game theory, much of the research in MARL revolves around social dilemmas, such as prisoner's dilemma,[22] chicken and stag hunt.[23]

While game theory research might focus on Nash equilibria and what an ideal policy for an agent would be, MARL research focuses on how the agents would learn these ideal policies using a trial-and-error process. The reinforcement learning algorithms that are used to train the agents are maximizing the agent's own reward; the conflict between the needs of the agents and the needs of the group is a subject of active research.[24]

Various techniques have been explored in order to induce cooperation in agents: Modifying the environment rules,[25] adding intrinsic rewards,[4] and more.

An autocurriculum[28] (plural: autocurricula) is a reinforcement learning concept that's salient in multi-agent experiments. As agents improve their performance, they change their environment; this change in the environment affects themselves and the other agents. The feedback loop results in several distinct phases of learning, each depending on the previous one. The stacked layers of learning are called an autocurriculum. Autocurricula are especially apparent in adversarial settings,[29] where each group of agents is racing to counter the current strategy of the opposing group.

The Hide and Seek game is an accessible example of an autocurriculum occurring in an adversarial setting. In this experiment, a team of seekers is competing against a team of hiders. Whenever one of the teams learns a new strategy, the opposing team adapts its strategy to give the best possible counter. When the hiders learn to use boxes to build a shelter, the seekers respond by learning to use a ramp to break into that shelter. The hiders respond by locking the ramps, making them unavailable for the seekers to use. The seekers then respond by "box surfing", exploiting a glitch in the game to penetrate the shelter. Each "level" of learning is an emergent phenomenon, with the previous level as its premise. This results in a stack of behaviors, each dependent on its predecessor.

Autocurricula in reinforcement learning experiments are compared to the stages of the evolution of life on earth and the development of human culture. A major stage in evolution happened 2-3 billion years ago, when photosynthesizing life forms started to produce massive amounts of oxygen, changing the balance of gases in the atmosphere.[30] In the next stages of evolution, oxygen-breathing life forms evolved, eventually leading up to land mammals and human beings. These later stages could only happen after the photosynthesis stage made oxygen widely available. Similarly, human culture couldn't have gone through the industrial revolution in the 18th century without the resources and insights gained by the agricultural revolution at around 10,000 BC.[31]

Multi-agent reinforcement learning has been applied to a variety of use cases in science and industry:

There are some inherent difficulties about multi-agent deep reinforcement learning.[47] The environment is not stationary anymore, thus the Markov property is violated: transitions and rewards do not only depend on the current state of an agent.

There are various tools and frameworks for working with multi-agent reinforcement learning environments:

• Stefano V. Albrecht, Filippos Christianos, Lukas Schäfer. Multi-Agent Reinforcement Learning: Foundations and Modern Approaches. MIT Press, 2023. https://www.marl-book.com
• Kaiqing Zhang, Zhuoran Yang, Tamer Basar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Studies in Systems, Decision and Control, Handbook on RL and Control, 2021.
• Yang, Yaodong; Wang, Jun (2020). "An Overview of Multi-Agent Reinforcement Learning from Game Theoretical Perspective". arXiv:2011.00583 [cs.MA].