Empirically Evaluating Multiagent Learning Algorithms
  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 the other hand, little is known about the empirical performance
of these algorithms. Most such claims in the literature are 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 convergence. 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.
