A Multiagent Reinforcement Learning Algorithm with Non-linear Dynamics

By Sherief Abdallah, Victor R. Lesser. 2008

96 citations recorded by the source corpus.

Several multiagent reinforcement learning (MARL) algorithms have been proposed to optimize agents' decisions. Due to the complexity of the problem, the majority of the previously developed MARL algorithms assumed agents either had some knowledge of the underlying game (such as Nash equilibria) and/or observed other agents actions and the rewards they received. We introduce a new MARL algorithm called theWeighted Policy Learner (WPL), which allows agents to reach a Nash Equilibrium (NE) in benchmark 2-player-2-action games with minimum knowledge. Using WPL, the only feedback an agent needs is its own local reward (the agent does not observe other agents actions or rewards). Furthermore, WPL does not assume that agents know the underlying game or the corresponding Nash Equilibrium a priori. We experimentally show that our algorithm converges in benchmark two-player-two-action games. We also show that our algorithm converges in the challenging Shapley's game where previous MARL algorithms failed to converge without knowing the underlying game or the NE. Furthermore, we show that WPL outperforms the state-of-the-art algorithms in a more realistic setting of 100 agents interacting and learning concurrently. An important aspect of understanding the behavior of a MARL algorithm is analyzing the dynamics of the algorithm: how the policies of multiple learning agents evolve over time as agents interact with one another. Such an analysis not only verifies whether agents using a given MARL algorithm will eventually converge, but also reveals the behavior of the MARL algorithm prior to convergence. We analyze our algorithm in two-player-two-action games and show that symbolically proving WPL's convergence is difficult, because of the non-linear nature of WPL's dynamics, unlike previous MARL algorithms that had either linear or piece-wise-linear dynamics. Instead, we numerically solve WPL's dynamics differential equations and compare the solution to the dynamics of previous MARL algorithms.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Management Science and Operations Research, Reinforcement Learning

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 Computational Theory and Mathematics

In Management Science and Operations Research

In Reinforcement Learning

Citations in the corpus

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”
Multiagent Learning: Basics, Challenges, and Prospects (2012, methodology): “Related algorithms to infinitesimal gradient ascent have been devised to tackle this issue, such as for instance the weighted policy learner (WPL) algorithm of Abdallah and Lesser (2008).”
Independent reinforcement learners in cooperative Markov games: a survey regarding coordination problems (2012, background): “For instance, the presence of multiple concurrent learners makes the environment non-stationary from a single agent’s perspective, which is a commonly cited cause of difﬁculties in multiagent learning systems (Bowling & Veloso, 2000; Banerjee, Sen, & Peng, 2004; Abdallah & Lesser, 2008).”
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, methodology): “Evolutionary Dynamics of Multi-Agent Learning 0 0.5 1 0 0.5 1 x 1 y 1 0 0.5 1 0 0.5 1 x 1 y 1 0 0.5 1 0 0.5 1 x 1 y 1 IGA IGA-WoLF WPL 0 0.5 1 0 0.5 1 x 1 y 1 0 0.5 1 0 0.5 1 x 1 y 1 0 0.5 1 0 0.5 1 x 1 y 1 IGA WoLF WPL CL FAQ CL FAQ Traces Figure 7: Overview of the dynamics”
Distributed Machine Learning in Coalition Environments: Overview of Techniques (2018, background): “Some examples of gradient ascent algorithms are infenitesimal gradient ascent [33], generalized infinitesimal gradient ascent [34] and the more recent weighted policy learning [35].”
Lenient Learning in Independent-Learner Stochastic Cooperative Games (2016, background): “Other approaches, based on gradient descent, also try to converge to Nash Equilibria in self play (Abdallah and Lesser, 2008; Zhang and Lesser, 2010).”
A Deep Policy Inference Q-Network for Multi-Agent Systems (2017, background): “While approaches for eliminating the need of prior knowledge of the environment have been attempted [2, 22, 24, 36], they are still limited to simple grid-world settings, and are unable to be scaled”
Learning to compete, coordinate, and cooperate in repeated games using reinforcement learning (2011, background): “While many algorithms choose to do this by learning along the continuum of mixed strategies (Abdallah and Lesser 2008, Bowling and Veloso 2002, Zinkevich 2003), M-Qubed only considers playing its maximin strategy π MM i and each of its pure strategies a ∈ A i .”
Actor-Critic Policy Optimization in Partially Observable Multiagent Environments (2018, methodology): “These analyses are common in multiagent learning as they allow visual depiction of the policy changes and how different factors affect the (convergence) behavior [83, 92, 13, 91, 11, 94, 1, 99, 98, 8, 89].”
A Survey of Learning in Multiagent Environments: Dealing with Non-Stationarity (2017, methodology): “Repeated games It is common to use repeated games as a setting with non-stationary opponents (Suematsu and Hayashi, 2002; Bowling and Veloso, 2002; Tesauro, 2003; Weinberg and Rosenschein, 2004; Powers and Shoham, 2005; Conitzer and Sandholm, 2006; Abdallah and Lesser, 2008; Crandall and Goodrich, 2”