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

  1. Sergey Levine
  2. Shimon Whiteson
  3. Pieter Abbeel
  4. Yoshua Bengio
  5. Mohit Bansal
  6. Jianfeng Gao
  7. Ruslan Salakhutdinov
  8. Kyunghyun Cho

In Computational Theory and Mathematics

  1. Shimon Whiteson
  2. Jakob N. Foerster
  3. Karl Tuyls
  4. Yi Wu
  5. Yaodong Yang
  6. Chris Amato
  7. Pablo Hernandez-Leal
  8. Rahul Savani

In Management Science and Operations Research

  1. Shimon Whiteson
  2. Karl Tuyls
  3. Jakob N. Foerster
  4. Marc Lanctot
  5. Pablo Hernandez-Leal
  6. Julien Pérolat
  7. Michael H. Bowling
  8. Neil Burch

In Reinforcement Learning

  1. Shimon Whiteson
  2. Sergey Levine
  3. Jakob N. Foerster
  4. Pieter Abbeel
  5. Karl Tuyls
  6. Chris Amato
  7. Pablo Hernandez-Leal
  8. Igor Mordatch

In Game & Decision Theory

  1. Karl Tuyls
  2. Shimon Whiteson
  3. Neil Burch
  4. Marc Lanctot
  5. Julien Pérolat
  6. Adam Lerer
  7. R´emi Munos
  8. Jakob N. Foerster

Citations in the corpus