Convergence and No-Regret in Multiagent Learning

Michael Bowling. Convergence and No-Regret in Multiagent Learning. In Advances in Neural Information Processing Systems 17 (NIPS), pp. 209–216, 2005. A longer version is available as a University of Alberta Technical Report, TR04-11.

Download

[PDF] [gzipped postscript] 

Abstract

Learning in a multiagent system is a challenging problem due to two key factors. First, if other agents are simultaneously learning then the environment is no longer stationary, thus undermining convergence guarantees. Second, learning is often susceptible to deception, where the other agents may be able to exploit a learner's particular dynamics. In the worst case, this could result in poorer performance than if the agent was not learning at all. These challenges are identifiable in the two most common evaluation criteria for multiagent learning algorithms: convergence and regret. Algorithms focusing on convergence or regret in isolation are numerous. In this paper, we seek to address both criteria in a single algorithm by introducing GIGA-WoLF, a learning algorithm for normal-form games. We prove the algorithm guarantees at most zero average regret, while demonstrating the algorithm converges in many situations of self-play. We prove convergence in a limited setting and give empirical results in a wider variety of situations. These results also suggest a third new learning criterion combining convergence and regret, which we call negative non-convergence regret (NNR).

BibTeX

@InProceedings(04nips-w-tr,
  Author = "Michael Bowling",
  Title = "Convergence and No-Regret in Multiagent Learning",
  Booktitle = "Advances in Neural Information Processing Systems 17 (NIPS)",
  Year = "2005",
  Pages = "209--216",
  AcceptRate = "25\%",
  Note = "A longer version is available as a University of Alberta Technical Report, TR04-11."
)

Generated by bib2html.pl (written by Patrick Riley) on Fri Feb 13, 2015 15:54:29