Multiagent reinforcement learning: algorithm converging to Nash equilibrium in general-sum discounted stochastic games

ABSTRACT

This paper introduces a multiagent reinforcement learning algorithm that converges with a given accuracy to stationary Nash equilibria in general-sum discounted stochastic games. Under some assumptions we formally prove its convergence to Nash equilibrium in self-play. We claim that it is the first algorithm that converges to stationary Nash equilibrium in the general case.

REFERENCES

• 1: Multiagent learning using a variable learning rate, Artificial Intelligence, v.136 n.2, p.215-250, April 2002 [doi>10.1016/S0004-3702(02)00121-2]
• 2: Caroline Claus , Craig Boutilier, The dynamics of reinforcement learning in cooperative multiagent systems, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.746-752, July 1998, Madison, Wisconsin, United States
• 3: Jerzy Filar , Koos Vrieze, Competitive Markov decision processes, Springer-Verlag New York, Inc., New York, NY, 1996
• 4: A. Greenwald and K. Hall. Correlated-q learning. In Proceedings of the Twentieth International Conference on Machine Learning, pages 242--249, 2003.
• 5: Junling Hu , Michael P. Wellman, Multiagent Reinforcement Learning: Theoretical Framework and an Algorithm, Proceedings of the Fifteenth International Conference on Machine Learning, p.242-250, July 24-27, 1998
• 6: M. L. Littman. Markov games as a framework for multi-agent reinforcement learning. In ICML, pages 157--163, 1994.
• 7: Michael L. Littman, Friend-or-Foe Q-learning in General-Sum Games, Proceedings of the Eighteenth International Conference on Machine Learning, p.322-328, June 28-July 01, 2001
• 8: G. Tesauro. Extending q-learning to general adaptive multi-agent systems. In S. Thrun, L. K. Saul, and B. Schölkopf, editors, NIPS. MIT Press, 2003.
• 9: M. Zinkevich, A. R. Greenwald, and M. L. Littman. Cyclic equilibria in markov games. In NIPS, 2005.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

General Terms:
Algorithms, Theory

Keywords:
algorithmic game theory, computation of equilibria, multiagent reinforcement learning, stochastic games