Empirically Evaluating Multiagent Learning Algorithms

By Erik Zawadzki, Asher Lipson, Kevin Leyton-Brown. 2014

29 citations recorded by the source corpus.

There exist many algorithms for learning how to play repeated bimatrix games. Most of these algorithms are justified in terms of some sort of theoretical guarantee. On t he other hand, little is known about the empirical performance of these algorithms. Most such claims in the literature are been based on small experiments, which has hampered understanding as well as the development of new multiagent learning (MAL) algorithms. We have developed a new suite of tools for running multiagent experiments: the MultiAgent Learning Testbed (MALT). These tools are designed to facilitate larger and more comprehensive experiments by removing the need to build one-off experimental code. MALT also provides baseline implementations of many MAL algorithms, hopefully eliminating or reducing differences between algorithm implementations and increasing the reproducibility of results. Using this test suite, we ran an experiment unprecedented in size. We analyzed the results according to a variety of performance metrics including reward, maxmin distance, regret, and several notions of equilibrium conve rgence. We confirmed several pieces of conventional wisdom, but also discovered some surprising results. For example, we found that single-agent Q-learning outperformed many more complicated and more modern MAL algorithms.

Subfields: Artificial Intelligence, 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 Management Science and Operations Research

In Reinforcement Learning

Citations in the corpus

Counterfactual Multi-Agent Policy Gradients (2017, neutral): “Tampuu et al. (2015) use a combination of DQN with independent Q -learning (Tan, 1993; Shoham & Leyton-Brown, 2009; Zawadzki et al., 2014) to learn how to play two-player pong.”
Learning to Communicate with Deep Multi-Agent Reinforcement Learning (2016, neutral): “While independent Q-learning can in principle lead to convergence problems (since one agent’s learning makes the environment appear non-stationary to other agents), it has a strong empirical track record [15, 16], and was successfully applied to two-player pong.”
Stabilising Experience Replay for Deep Multi-Agent Reinforcement Learning (2017, methodology): “The most commonly used method is independent Qlearning(Tan, 1993; Shoham & Leyton-Brown, 2009; Zawadzki et al., 2014), which we discuss further in Section 3.”
Multi-agent Reinforcement Learning in Sequential Social Dilemmas (2017, background): “…cooperation can be stabilized, e.g., direct reciprocity [4, 5, 6, 7], indirect reciprocity [8], norm enforcement [9, 10], simple reinforcement learning variants [3], multiagent reinforcement learning [11, 12, 13, 14, 15], spatial structure [16], emotions [17], and social network eﬀects [18, 19].”
Learning to Communicate to Solve Riddles with Deep Distributed Recurrent Q-Networks (2016, methodology): “While independent Q-learning can in principle lead to convergence problems (since one agent’s learning makes the environment appear non-stationary to other agents), it has a strong empirical track record (Shoham et al., 2007; Shoham & Leyton-Brown, 2009; Zawadzki et al., 2014).”
A review of cooperative multi-agent deep reinforcement learning (2019, background): “The tabular IQL usually works well in practice for small size problems [131, 250]; however, in the case of function approximation, especially deep neural network (DNN), it may not work very well.”