AWESOME: A general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents

By Vincent Conitzer, Tuomas Sandholm. 2003

299 citations recorded by the source corpus.

Two minimal requirements for a satisfactory multiagent learning algorithm are that it 1. learns to play optimally against stationary opponents and 2. converges to a Nash equilibrium in self-play. The previous algorithm that has come closest, WoLF-IGA, has been proven to have these two properties in 2-player 2-action (repeated) games—assuming that the opponent’s mixed strategy is observable. Another algorithm, ReDVaLeR (which was introduced after the algorithm described in this paper), achieves the two properties in games with arbitrary numbers of actions and players, but still requires that the opponents' mixed strategies are observable. In this paper we present AWESOME, the first algorithm that is guaranteed to have the two properties in games with arbitrary numbers of actions and players. It is still the only algorithm that does so while only relying on observing the other players' actual actions (not their mixed strategies). It also learns to play optimally against opponents that eventually become stationary. The basic idea behind AWESOME (Adapt When Everybody is Stationary, Otherwise Move to Equilibrium) is to try to adapt to the others' strategies when they appear stationary, but otherwise to retreat to a precomputed equilibrium strategy. We provide experimental results that suggest that AWESOME converges fast in practice. The techniques used to prove the properties of AWESOME are fundamentally different from those used for previous algorithms, and may help in analyzing future multiagent learning algorithms as well.

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

Stabilising Experience Replay for Deep Multi-Agent Reinforcement Learning (2017, background): “Methods like hyper Q-learning (Tesauro, 2003) - which we also discuss in Section 3.2 - and AWESOME (Conitzer & Sandholm, 2007) try to tackle the nonstationarity by tracking and conditioning each agents’ learning process on their teammates’ current policy, while Da Silva et al. (2006) propose…”
Empirically Evaluating Multiagent Learning Algorithms (2014, background): “AWESOME (Conitzer and Sandholm, 2003; Conitzer and Sandholm, 2007) tracks the opponent’s behavior in different periods of play and tries to maintain hypotheses about its play.”
Learning with Opponent-Learning Awareness (2017, background): “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].”
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 [26–28].”
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, background): “…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 received (Hu and Wellman 2003; Conitzer and Sandholm 2007).”
Evolutionary Dynamics of Multi-Agent Learning: A Survey (2015, background): “Examples of joint action learners are minimax-Q (Littman, 1994), fictitious play and AWESOME (Brown, 1951; Conitzer & Sandholm, 2007), hyper-Q (Tesauro, 2003), and Nash-Q (Hu & Wellman, 2003).”
Learning against multiple opponents (2006, background): “Conitzer and Sandholm[7] then proposed a new algorithm that achieved the above criteria for arbitrary repeated games, but only when all the opponents were of the same type (either all stationary or all self-play).”
Making friends on the fly: Cooperating with new teammates (2017, unknown): “An algorithm that shows this reasoning is the AWESOME algorithm [23].”
Optimizing for the Future in Non-Stationary MDPs (2020, background): “Non-stationarity also occurs in multi-player games, like rock-paper-scissors, where each episode is a single one-step interaction (Singh et al., 2000; Bowling, 2005; Conitzer and Sandholm, 2007).”
A Multiagent Reinforcement Learning Algorithm with Non-linear Dynamics (2008, methodology): “An alternative goal that we pursue here is converging to the Nash Equilibrium (NE) (Bowling, 2005; Conitzer & Sandholm, 2007; Banerjee & Peng, 2007), which is by deﬁnition a local maximum across agents (no agent can do better by deviating unilaterally from the NE).”
Interactive POMDPs with finite-state models of other agents (2017, background): “However, there has been considerable effort in multiagent learning towards algorithms that model the opponents implicitly [4,10,36].”
Performance Bounded Reinforcement Learning in Strategic Interactions (2004, background): “3. that the agents are given at the start, their portions of an equilibrium policy profile which they converge to if all the agents are following the same prescribed algorithm (similar to WoLF-IGA and AWESOME).”
Learning against sequential opponents in repeated stochastic games (2017, background): “…to act in multiagent systems has received attention mainly from game theory, focused on algorithms that converge to the Nash equilibrium [2, 6, 7]; and from reinforcement learning, focused on acting optimally in stochastic scenarios with limited a priori information but online observations…”