AAAI Publications, Twenty-Eighth AAAI Conference on Artificial Intelligence

Font Size: 
Evolutionary Dynamics of Q-Learning over the Sequence Form
Fabio Panozzo, Nicola Gatti, Marcello Restelli

Last modified: 2014-06-21

Abstract


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.

Keywords


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

Full Text: PDF