Dynamic analysis of multiagent Q-learning with ε-greedy exploration

ABSTRACT

The development of mechanisms to understand and model the expected behaviour of multiagent learners is becoming increasingly important as the area rapidly find application in a variety of domains. In this paper we present a framework to model the behaviour of Q-learning agents using the ε-greedy exploration mechanism. For this, we analyse a continuous-time version of the Q-learning update rule and study how the presence of other agents and the ε-greedy mechanism affect it. We then model the problem as a system of difference equations which is used to theoretically analyse the expected behaviour of the agents. The applicability of the framework is tested through experiments in typical games selected from the literature.

REFERENCES

• 1: Sherief Abdallah , Victor Lesser, Non-linear dynamics in multiagent reinforcement learning algorithms, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 2: Borgers, T., & Sarin, R. (1997). Learning through reinforcement and replicator dynamics. Journal of Economic Theory, 77, 1--14.
• 3: V. S. Borkar , S. P. Meyn, The O.D. E. Method for Convergence of Stochastic Approximation and Reinforcement Learning, SIAM Journal on Control and Optimization, v.38 n.2, p.447-469, Jan. 2000 [doi>10.1137/S0363012997331639]
• 4: Bush, R. R., & Mosteller, F. (1955). Stochastic models for learning. New York: John Wiley and Sons.
• 5: 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
• 6: Fulda, N., & Ventura, D. (2007). Predicting and preventing coordination problems in cooperative Q-learning systems. Proceedings of the Twentieth International Joint Conference on Artificial Intelligence (IJCAI'07) (pp. 780--785).
• 7: Aram Galstyan , Karl Czajkowski , Kristina Lerman, Resource Allocation in the Grid Using Reinforcement Learning, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.1314-1315, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.232]
• 8: Eduardo Rodrigues Gomes , Ryszard Kowalczyk, Learning the IPA Market with Individual and Social Rewards, Proceedings of the 2007 IEEE/WIC/ACM International Conference on Intelligent Agent Technology, p.328-334, November 02-05, 2007 [doi>10.1109/IAT.2007.69]
• 9: Mehrtash T. Harandi , Majid Nili Ahmadabadi , Babak N. Araabi, Optimal Local Basis: A Reinforcement Learning Approach for Face Recognition, International Journal of Computer Vision, v.81 n.2, p.191-204, February 2009 [doi>10.1007/s11263-008-0161-5]
• 10: Hofbauer, J., & Sigmund, K. (1998). Evolutionary games and population dynamics. Cambridge University Press.
• 11: Iglesias, A., Martnez, P., Aler, R., & Fernndez, F. (2008). Learning teaching strategies in an adaptive and intelligent educational system through reinforcement learning. Applied Intelligence, in press.
• 12: David S. Leslie , E. J. Collins, Individual Q-Learning in Normal Form Games, SIAM Journal on Control and Optimization, v.44 n.2, p.495-514, 2005 [doi>10.1137/S0363012903437976]
• 13: Liviu Panait , Sean Luke, Cooperative Multi-Agent Learning: The State of the Art, Autonomous Agents and Multi-Agent Systems, v.11 n.3, p.387-434, November 2005 [doi>10.1007/s10458-005-2631-2]
• 14: Liviu Panait , Karl Tuyls , Sean Luke, Theoretical Advantages of Lenient Learners: An Evolutionary Game Theoretic Perspective, The Journal of Machine Learning Research, 9, p.423-457, 6/1/2008
• 15: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 16: Karl Tuyls , Katja Verbeeck , Tom Lenaerts, A selection-mutation model for q-learning in multi-agent systems, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860687]
• 17: José M. Vidal , Edmund H. Durfee, Predicting the Expected Behavior of Agents that Learn About Agents: The CLRI Framework, Autonomous Agents and Multi-Agent Systems, v.6 n.1, p.77-107, January 2003 [doi>10.1023/A:1021765422660]
• 18: Ziogos, N. P., Tellidou, A. C., Gountis, V. P., & Bakirtzis, A. G. (2007). A reinforcement learning algorithm for market participants in FTR auctions. Proceedings of the Seventh IEEE Power Tech (pp. 943--948). IEEE.

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
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory