Multiagent learning using a variable learning rate

By Michael H. Bowling, Manuela M. Veloso. 2002

872 citations recorded by the source corpus.

Abstract Learning to act in a multiagent environment is a difficult problem since the normal definition of an optimal policy no longer applies. The optimal policy at any moment depends on the policies of the other agents. This creates a situation of learning a moving target. Previous learning algorithms have one of two shortcomings depending on their approach. They either converge to a policy that may not be optimal against the specific opponents' policies, or they may not converge at all. In this article we examine this learning problem in the framework of stochastic games. We look at a number of previous learning algorithms showing how they fail at one of the above criteria. We then contribute a new reinforcement learning technique using a variable learning rate to overcome these shortcomings. Specifically, we introduce the WoLF principle, “Win or Learn Fast”, for varying the learning rate. We examine this technique theoretically, proving convergence in self-play on a restricted class of iterated matrix games. We also present empirical results on a variety of more general stochastic games, in situations of self-play and otherwise, demonstrating the wide applicability of this method.

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning, Optimization & Training

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 Optimization & Training

Citations in the corpus

Unrolled Generative Adversarial Networks (2016, neutral): “This is similar to the situation in simple matrix games like rock-paper-scissors and matching pennies, where alternating gradient descent (ascent) with a ﬁxed learning rate is known not to converge (Singh et al., 2000; Bowling & Veloso, 2002).”
OpenSpiel: A Framework for Reinforcement Learning in Games (2019, background): “Visualization of Evolutionary and Policy Learning Dynamics One common visualization tool in the multiagent learning literature (especially in games) is a phase portrait that shows a vector field and/or trajectories of particle the depict local changes to the policy under specific update dynamics [64”
Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observability (2017, background): “Bowling & Veloso (2002) conduct Policy Hill Climbing us-ing the Win-or-Learn Fast heuristic to decrease (increase) each agent’s learning rate when it performs well (poorly).”
Empirically Evaluating Multiagent Learning Algorithms (2014, background): “While four of the eleven algorithms tested in this study were simple stationary-strategy baselines, the remaining seven were MAL algorithms including Hyper-Q (Tesauro, 2004), WoLF-PHC (Bowling and Veloso, 2002), and a joint action learner (Claus and Boutilier, 1997).”
Learning with Opponent-Learning Awareness (2017, methodology): “Seminal work includes the family of WoLF algorithms [3], which uses different learning rates depending on whether an agent is winning or losing, joint-action-learners (JAL), and AWESOME [9].”
Decentralized Likelihood Quantile Networks for Improving Performance in Deep Multi-Agent Reinforcement Learning (2018, background): “Even with perfect observability, ILs are non-Markovian due to unpredictable and unobservable teammates’ actions, hence the environment non-stationary problem (Bowling & Veloso, 2002).”
Negative Update Intervals in Deep Multi-Agent Reinforcement Learning (2018, background): “When multiple ILs update policies in parallel an environment can no longer be considered Markovian, thereby losing the property that guarantees convergence for a large number of single-agent learning algorithms [1, 25].”
Mean Field Multi-Agent Reinforcement Learning (2018, methodology): “Our work follows the same direction as Littman (1994); Hu & Wellman (2003); Bowling & Veloso (2002) on adapting a Stochastic Game (van der Wal et al., 1981) into the MARL formulation.”
Multiagent Learning: Basics, Challenges, and Prospects (2012, methodology): “Another well known gradient-ascent type algorithm is the policy hill climber (PHC) explained in Bowling and Veloso (2002).”
Independent reinforcement learners in cooperative Markov games: a survey regarding coordination problems (2012, methodology): “The WoLF PHC convergence to optimal policies has been demonstrated empirically on a number of zero-sum and general-sum stochastic games (Bowling & Veloso, 2002).”
A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning (2017, background): “use adaptive learning rates [12], adjust the frequencies of updates [48, 81], or dynamically respond to the other agents actions online [63, 50].”
The Mechanics of n-Player Differentiable Games (2018, background): “WoLF (Win or Learn Fast) converges to Nash equilibria in two-player two-action games (Bowling & Veloso, 2002).”
Multi-Agent Learning with Policy Prediction (2010, methodology): “…each algorithm has its own additional assumptions, such as requiring an agent to know a Nash Equilibrium (NE) and the strategy of the other players(Bowling and Veloso 2002; Banerjee and Peng 2007; Conitzer and Sandholm 2007), or observe what actions other agents executed and what re-wards they…”
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).”
Correlated Q-Learning (2003, methodology): “In 1994, the field was launched with Littman’s (1994) seminal paper on minimax Q-learning. The proof of convergence of this algorithm to a minimax equilibrium policy appeared subsequently in Littman and Szepesvári (1996). This algorithm computes the value of a state as the value to one player of the”
AWESOME: A general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents (2003, methodology): “The algorithm that has come closest to satisfying both of the properties in general repeated games is WoLFIGA (Bowling & Veloso, 2002).”
Autonomous agents modelling other agents: A comprehensive survey and open problems (2017, background): “[9,49,133]) and learning based on communication.”
Convergence and No-Regret in Multiagent Learning (2004, methodology): “Like WoLF-IGA, though, it does not have any known regret guarantees, but more importantly requires the other players’ payoffs to be known. to step (1).”