A Survey of Learning in Multiagent Environments: Dealing with Non-Stationarity

By Pablo Hernandez-Leal, Michael Kaisers, Tim Baarslag, Enrique Munoz de Cote. 2017

329 citations recorded by the source corpus.

The key challenge in multiagent learning is learning a best response to the behaviour of other agents, which may be non-stationary: if the other agents adapt their strategy as well, the learning target moves. Disparate streams of research have approached non-stationarity from several angles, which make a variety of implicit assumptions that make it hard to keep an overview of the state of the art and to validate the innovation and significance of new works. This survey presents a coherent overview of work that addresses opponent-induced non-stationarity with tools from game theory, reinforcement learning and multi-armed bandits. Further, we reflect on the principle approaches how algorithms model and cope with this non-stationarity, arriving at a new framework and five categories (in increasing order of sophistication): ignore, forget, respond to target models, learn models, and theory of mind. A wide range of state-of-the-art algorithms is classified into a taxonomy, using these categories and key characteristics of the environment (e.g., observability) and adaptation behaviour of the opponents (e.g., smooth, abrupt). To clarify even further we present illustrative variations of one domain, contrasting the strengths and limitations of each category. Finally, we discuss in which environments the different approaches yield most merit, and point to promising avenues of future research.

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

Learning with Opponent-Learning Awareness (2017, background): “One well-known shortcoming is that they fail to consider the learning process of the other agents and simply treat the other agent as a static part of the environment [19].”
Lenient Multi-Agent Deep Reinforcement Learning (2017, background): “One of the key challenges faced within MA-RL is the moving target problem: Given an environment with multiple agents whose rewards depend on each others’ actions, the difficulty of finding optimal policies for each agent is increased due to the policies of the agents being non stationary [5, 12, 31]”
A survey and critique of multiagent deep reinforcement learning (2018, methodology): “We aim to enable researchers with experience in either DRL or MAL to gain a common understanding about recent works, and open problems in MDRL, and to avoid having scattered sub-communities with little interaction [6,81,141,289].”
Off-Policy Multi-Agent Decomposed Policy Gradients (2020, background): “…the paradigm of centralized critic with decentralized actors (CCDA), which not only deals with the issue of non-stationarity (Foerster et al., 2017; Hernandez-Leal et al., 2017) by conditioning the centralized critic on global history and actions but also maintains scalable decentralized execution…”
Single and Multi-Agent Deep Reinforcement Learning for AI-Enabled Wireless Networks: A Tutorial (2020, background): “Hence, the Markov property, stating that the reward and transition functions depend only on the previous state and the agent’s action, is violated and the convergence guarantees of single agent RL are no longer valid [78].”
Actor-Critic Policy Optimization in Partially Observable Multiagent Environments (2018, methodology): “Our methods do no such modeling, and can be classified in the “forget” category of the taxonomy proposed in [33]: that is, due to its on-policy nature, actors and critics adapt to and learn mainly from new/current experience.”
A Deep Policy Inference Q-Network for Multi-Agent Systems (2017, unknown): “The literature contains numerous studies of MAS modeling [7, 10, 27] and investigations of non-stationarity issues [16].”
A Policy Gradient Algorithm for Learning to Learn in Multiagent Reinforcement Learning (2020, background): “The standard approach for addressing non-stationarity in MARL is to consider information about the other agents and reason about the effects of their joint actions (Hernandez-Leal et al., 2017).”
Winning Isn't Everything: Training Human-Like Agents for Playtesting and Game AI (2019, background): “More important, MAL also suffers from non-convergence due to the breakdown of the Markovity of the decision process as the environment for each single agent is changing while the rest of the agents update their policies [55], [56].”
Revisiting Parameter Sharing in Multi-Agent Deep Reinforcement Learning (2020, background): “Virtually all cooperative multiagent reinforcement learning suffers from very slow convergence due to nonstationarity (Matignon et al., 2012; Hernandez-Leal et al., 2017; Papoudakis et al., 2019).”
Multi-agent deep reinforcement learning: a survey (2021, background): “As a result, the Markov assumption is violated, and the learning constitutes an inherently difficult problem (Hernandez-Leal et al. 2017; Laurent et al. 2011).”
Local Information Agent Modelling in Partially-Observable Environments (2021, methodology): “Multi-agent Reinforcement Learning (MARL): MARL algorithms are designed to train multiple agents to solve tasks in a shared environment [Hernandez-Leal et al., 2017, Papoudakis et al., 2019].”
On Multi-Agent Learning in Team Sports Games (2019, background): “See (Hernandez-Leal et al., 2017; 2018) for recent surveys on MAL and deep MARL advancements.”
Influencing Long-Term Behavior in Multiagent Reinforcement Learning (2022, unknown): “The standard approach for addressing the non-stationarity problem in MARL is to consider information about other agents and reason about joint action effects (Hernandez-Leal et al., 2017).”
Learning Against Non-Stationary Agents with Opponent Modelling and Deep Reinforcement Learning (2018, background): “However, the construction of these models is non-trivial as an agent’s behaviour is rarely stationary, thus requiring any learned opponent model to be continuously updated (Hernandez-Leal et al. 2017b).”
Autonomous agents modelling other agents: A comprehensive survey and open problems (2017, background): “Some methods attempt to address this issue by allowing for varying degrees of changing behaviours, such as that behaviours must converge in the limit (Conitzer and Sandholm, 2007), that agents may switch periodically between different stationary behaviours (Hernandez-Leal et al., 2017; Bard and Bowl”
Neural Replicator Dynamics (2019, background): “Most other works that focus on nonstationary multiagent learning are limited to repeated and stochastic games [1, 15, 24, 46, 47].”
Dealing with Non-Stationarity in MARL via Trust-Region Decomposition (2021, background): “Lemma 1 and Lemma 2 indicate that the δ-stationarity is a reasonable mathematical description of the non-stationarity problem (Hernandez-Leal et al., 2017; Papoudakis et al., 2019; Padakandla, 2021), which can measure the non-stationarity of the learning procedure.”
Deep Reinforcement Learning for Multiagent Systems: A Review of Challenges, Solutions, and Applications (2018, background): “The convergence theory of Q-learning applied in a single-agent setting is not guaranteed to most multiagent problems as the Markov property does not hold anymore in the nonstationary environment [47].”