Independent reinforcement learners in cooperative Markov games: a survey regarding coordination problems
By Laëtitia Matignon, Guillaume J. Laurent, Nadine Le Fort-Piat. 2012
482 citations recorded by the source corpus.
Abstract In the framework of fully cooperative multi-agent systems, independent (non-communicative) agents that learn by reinforcement must overcome several difficulties to manage to coordinate. This paper identifies several challenges responsible for the non-coordination of independent agents: Pareto-selection, non-stationarity, stochasticity, alter-exploration and shadowed equilibria. A selection of multi-agent domains is classified according to those challenges: matrix games, Boutilier's coordination game, predators pursuit domains and a special multi-state game. Moreover, the performance of a range of algorithms for independent reinforcement learners is evaluated empirically. Those algorithms are Q-learning variants: decentralized Q-learning, distributed Q-learning, hysteretic Q-learning, recursive frequency maximum Q-value and win-or-learn fast policy hill climbing. An overview of the learning algorithms’ strengths and weaknesses against each challenge concludes the paper and can serve as a basis for choosing the appropriate algorithm for a new domain. Furthermore, the distilled challenges may assist in the design of new learning algorithms that overcome these problems and achieve higher performance in multi-agent applications.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Management Science and Operations Research, Reinforcement Learning, Game & Decision Theory
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
- Sergey Levine
- Shimon Whiteson
- Pieter Abbeel
- Yoshua Bengio
- Mohit Bansal
- Jianfeng Gao
- Ruslan Salakhutdinov
- Kyunghyun Cho
In Computational Theory and Mathematics
- Shimon Whiteson
- Jakob N. Foerster
- Karl Tuyls
- Yi Wu
- Yaodong Yang
- Chris Amato
- Pablo Hernandez-Leal
- Rahul Savani
In Management Science and Operations Research
- Shimon Whiteson
- Karl Tuyls
- Jakob N. Foerster
- Marc Lanctot
- Pablo Hernandez-Leal
- Julien Pérolat
- Michael H. Bowling
- Neil Burch
In Reinforcement Learning
- Shimon Whiteson
- Sergey Levine
- Jakob N. Foerster
- Pieter Abbeel
- Karl Tuyls
- Chris Amato
- Pablo Hernandez-Leal
- Igor Mordatch
In Game & Decision Theory
- Karl Tuyls
- Shimon Whiteson
- Neil Burch
- Marc Lanctot
- Julien Pérolat
- Adam Lerer
- R´emi Munos
- Jakob N. Foerster
Citations in the corpus
- Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments (2017, methodology): “This was attempted with Q-learning in [34], but does not perform well in practice [22].”
- Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observability (2017, methodology): “Matignon et al. (2012) survey these approaches, the most straightforward being Decentralized Q-learning (Tan, 1993), where each agent performs independent Q-learning.”
- Stabilising Experience Replay for Deep Multi-Agent Reinforcement Learning (2017, background): “On the one hand, the conventional wisdom is that this problem is not severe in practice, and substantial empirical results have demonstrated success with IQL (Matignon et al., 2012).”
- The Hanabi Challenge: A New Frontier for AI Research (2019, background): “[58] L.”
- The Representational Capacity of Action-Value Networks for Multi-Agent Reinforcement Learning (2019, background): “Current deep MARL approaches are either based on the assumption that the joint-action value function Q(s,a) can be represented efficiently by neural networks (when, in fact, the exponential number of joint actions usually makes a good approximation hard to learn), or that it suffices to represent (a”
- Decentralized Likelihood Quantile Networks for Improving Performance in Deep Multi-Agent Reinforcement Learning (2018, methodology): “The alter-exploration problem amplifies the issue of shadowed equilibria (Matignon et al., 2012).”
- Mean Field Multi-Agent Reinforcement Learning (2018, background): “…IL which increases the Q -values of actions that frequently produced good rewards in the past; (3) Recursive Frequency Maximum Q -value (Rec-FMQ) (Matignon et al., 2012), an improved version of FMQ that recursively computes the occurrence frequency to evaluate and then choose actions; (4)…”
- Lenient Multi-Agent Deep Reinforcement Learning (2017, methodology): “To answer this question we plan to test our LDQN within a hunter prey scenario where each episode runs for a fixed number of time-steps, with the prey being re-inserted at a random position each time it is caught [18].”
- A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning (2017, background): “These coordination problems have been well-studied in the fully-observable cooperative case [70]: we observe similar problems in a partially-observed mixed cooperative/competitive setting and, and we show that the severity increases as the environment becomes more partially-observed.”
- Emergent Complexity via Multi-Agent Competition (2017, background): “This was further explored by Matignon et al. [2012] again in the cooperative setting.”
- Human-level performance in 3D multiplayer games with population-based reinforcement learning (2018, critical): “End-to-end reinforcement learning methods (45, 46) have so far not succeeded in training agents in multi-agent games that combine team and competitive play due to the high complexity of the learning problem (7, 43) that arises from the concurrent adaptation of other learning agents in the environmen”
- A survey and critique of multiagent deep reinforcement learning (2018, methodology): “Here, the authors took inspiration from Hysteretic Q-learning [8], originally presented in MAL, where two”
- Qatten: A General Framework for Cooperative Multiagent Reinforcement Learning (2020, background): “If all agents receive the same rewards ( R 1 = ... = R N = R ), Markov games becomes fully-cooperative: a best-interest action of one agent is also a best-interest action of others (Matignon et al., 2012).”
- Arena: A General Evaluation Platform and Building Toolkit for Multi-Agent Intelligence (2019, background): “The simplest way to deploy multi-agent collaborative systems is to make each agent have a completely independent learning process (fully decentralized) [1, 37, 48, 59, 67, 68, 90].”
- Neural Replicator Dynamics (2019, background): “The associated core challenge is that the agents’ concurrent learning implies that they each perceive the environment as nonstationary [37, 62].”
- A review of cooperative multi-agent deep reinforcement learning (2019, methodology): “The tabular IQL usually works well in practice for small size problems [88, 88]; however, in the case of function approximation, especially deep neural network (DNN) it fails.”
- Action Branching Architectures for Deep Reinforcement Learning (2017, methodology): “This could be due to any of the several well-known issues for independent fully-cooperative learning agents: Pareto-selection, non-stationarity, stochasticity, alter-exploration, and shadowed equilibria [Matignon et al., 2012, Wei and Luke, 2016].”
- Prosocial learning agents solve generalized Stag Hunts better than selfish ones (2017, background): “lenient learning (Panait et al., 2008; Matignon et al., 2012) or Frequency Maximum Q-learning (Kapetanakis and Kudenko, 2002), while another has focused on potential-based reward shaping (Babes et al.”