Convergence and No-Regret in Multiagent Learning

By Michael H. Bowling. 2004

265 citations recorded by the source corpus.

Subfields: Artificial Intelligence, 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

In Management Science and Operations Research

In Reinforcement Learning

In Game & Decision Theory

Citations in the corpus

Towards Continual Reinforcement Learning: A Review and Perspectives (2020, background): “In these settings, even the correct solution concept can be difficult to define (Kim et al., 2022; Littman, 2001; Wang and Sandholm, 2002; Bowling, 2004; Greenwald and Hall, 2003; Zinkevich, Greenwald, and Littman, 2006; Letcher, Foerster, Balduzzi, Rocktäschel, and Whiteson, 2019).”
Empirically Evaluating Multiagent Learning Algorithms (2014, methodology): “Our implementation of GIGA-WoLF follows the original pseudo-code and uses the learning rate and step size schedules from the original experiments by Bowling (2004a) as defaults; see Table VI.”
Multiagent Learning: Basics, Challenges, and Prospects (2012, methodology): “The GIGA-WoLF algorithm extended the GIGA algorithm with the WoLF principle (Bowling 2004), improving on its convergence properties.”
Continuous Adaptation via Meta-Learning in Nonstationary and Competitive Environments (2017, background): “Nonstationarity of multi-agent environments is a well known issue that has been extensively studied in the context of learning in simple multi-player iterated games (such as rock-paper-scissors) where each episode is one-shot interaction (Singh et al., 2000; Bowling, 2005; Conitzer & Sandholm, 2007)”
Independent reinforcement learners in cooperative Markov games: a survey regarding coordination problems (2012, background): “This approach and its variants (Banerjee & Peng, 2003; Bowling, 2005) have been designed for competitive games.”
The Mechanics of n-Player Differentiable Games (2018, background): “Extensions include weighted policy learning (Abdallah & Lesser, 2008) and GIGA-WoLF (Bowling, 2004).”
A survey and critique of multiagent deep reinforcement learning (2018, background): “Self-play is a cornerstone in MAL with impressive results [42,45,71,113,149].”
Multi-Agent Learning with Policy Prediction (2010, methodology): “Compared to state-of-the-art MARL algorithms, WPL (Abdallah and Lesser 2008), WoLF-PHC (Bowling and Veloso 2002) and GIGA-WoLF (Bowling 2005), it empirically converges faster and in a wider variety of situations.”
Evolutionary Dynamics of Multi-Agent Learning: A Survey (2015, background): “Both algorithms can be combined with the win or learn fast (WoLF) heuristic in order to improve convergence in stochastic games (Bowling & Veloso, 2002; Bowling, 2005).”
Cooperating with machines (2017, background): “gorithms are particularly ineffective in longer interactions, as they do not effectively adapt to their associate’s behavior. Additionally, algorithms that minimize regret (e.g., Exp3 [22], GIGA-WoLF [23], and WMA [24]), which is the central component of world-champion computer poker algorithms [9],”
Multiagent learning in the presence of memory-bounded agents (2013, unknown): “The most popular amongst such algorithms is GIGA-WoLF [6] that achieves at most zero regret on average against all other agents and converges to a NE in only certain restrictive settings of self-play (namely two player two action games).”
AWESOME: A general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents (2003, background): “is an admirable objective that has been pursued (and achieved) in a significant body of research (Littlestone & Warmuth, 1994; Auer et al., 1995; Fudenberg & Levine, 1995; Freund & Schapire, 1999; Hart & Mas-Colell, 2000; Jafari et al., 2001; Greenwald & Jafari, 2003; Zinkevich, 2003; Bowling, 2005”
A Comprehensive Survey of Multiagent Reinforcement Learning (2008, methodology): “An alternative to rationality is the concept of no-regret, which is defined as the requirement that the agent achieves a return that is at least as good as the return of any stationar y strategy, and this holds for any set of strategies of the othe r agents [57].”
Neural Replicator Dynamics (2019, methodology): “In this paper, we go beyond these simple settings and focus our analysis on the connections between EGT and Policy Gradient (PG) algorithms, which have been extensively applied to MARL [2, 7, 8, 18, 35, 55, 57].”
Probabilistic Recursive Reasoning for Multi-Agent Reinforcement Learning (2019, unknown): “Typical examples include the series of WoLF models (Bowling, 2005; Bowling & Veloso, 2001a; 2002) or the Nash-Q learning (Hu & Wellman, 2003), both of which require the Nash Equilibrium at each stage game to update the Q-function.”
Learning to compete, coordinate, and cooperate in repeated games using reinforcement learning (2011, background): “GIGA-WoLF (Bowling 2005) Yes No No Hyper-Q (Tesauro 2004) No No No”
A Survey of Learning in Multiagent Environments: Dealing with Non-Stationarity (2017, methodology): “actions and rewards Slow SG WOLF-PHC (Bowling and Veloso, 2002) Local rewards Slow SG GIGA-WOLF (Bowling, 2004) Local rewards Slow RG COLF (Munoz de Cote et al.”