State-coupled replicator dynamics

ABSTRACT

This paper introduces a new model, i.e. state-coupled replicator dynamics, expanding the link between evolutionary game theory and multiagent reinforcement learning to multistate games. More precisely, it extends and improves previous work on piecewise replicator dynamics, a combination of replicators and piecewise models. The contributions of the paper are twofold. One, we identify and explain the major shortcomings of piecewise replicators, i.e. discontinuities and occurrences of qualitative anomalies. Two, this analysis leads to the proposal of the new model for learning dynamics in stochastic games, named state-coupled replicator dynamics. The preceding formalization of piecewise replicators - general in the number of agents and states - is factored into the new approach. Finally, we deliver a comparative study of finite action-set learning automata to piecewise and state-coupled replicator dynamics. Results show that state-coupled replicators model learning dynamics in stochastic games more accurately than their predecessor, the piecewise approach.

REFERENCES

• 1: T. Börgers and R. Sarin. Learning through reinforcement and replicator dynamics. Journal of Econ. Theory, 77(1), 1997.
• 2: D. Hennes, K. Tuyls, and M. Rauterberg. Formalizing multi-state learning dynamics. In IAT, 2008.
• 3: Kumpati S. Narendra , Mandayam A. L. Thathachar, Learning automata: an introduction, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 4: 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
• 5: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 6: Karl Tuyls , Simon Parsons, What evolutionary game theory tells us about multiagent learning, Artificial Intelligence, v.171 n.7, p.406-416, May, 2007 [doi>10.1016/j.artint.2007.01.004]
• 7: 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]
• 8: K. Verbeeck, P. Vrancx, and A. Nowé. Networks of learning automata and limiting games. In ALAMAS, 2006.
• 9: Peter Vrancx , Karl Tuyls , Ronald Westra, Switching dynamics of multi-agent learning, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal

INDEX TERMS

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

General Terms:
Algorithms, Theory

Keywords:
evolutionary game theory, multi-agent learning, replicator dynamics, stochastic games