Evolutionary Dynamics of Q-Learning over the Sequence Form


  • Fabio Panozzo Politecnico di Milano
  • Nicola Gatti Politecnico di Milano
  • Marcello Restelli Politecnico di Milano




replicator dynamics, multi-agent learning, reinforcement learning, extensive-form games


Multi-agent learning is a challenging open task in artificial intelligence. It is known an interesting connection between multi-agent learning algorithms and evolutionary game theory, showing that the learning dynamics of some algorithms can be modeled as replicator dynamics with a mutation term. Inspired by the recent sequence-form replicator dynamics, we develop a new version of the Q-learning algorithm working on the sequence form of an extensive-form game allowing thus an exponential reduction of the dynamics length w.r.t. those of the normal form. The dynamics of the proposed algorithm can be modeled by using the sequence-form replicator dynamics with a mutation term. We show that, although sequence-form and normal-form replicator dynamics are realization equivalent, the Q-learning algorithm applied to the two forms have non-realization equivalent dynamics. Originally from the previous works on evolutionary game theory models form multi-agent learning, we produce an experimental evaluation to show the accuracy of the model.




How to Cite

Panozzo, F., Gatti, N., & Restelli, M. (2014). Evolutionary Dynamics of Q-Learning over the Sequence Form. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1). https://doi.org/10.1609/aaai.v28i1.9012



Main Track: Novel Machine Learning Algorithms