Theoretical advantages of lenient learners : an evolutionary game theoretic perspective

L. Panait, K.P. Tuyls, S. Luke

    Research output: Contribution to journalArticleAcademicpeer-review

    63 Citations (Scopus)
    73 Downloads (Pure)

    Abstract

    This paper presents the dynamics of multiple learning agents from an evolutionary game theoretic perspective. We provide replicator dynamics models for cooperative coevolutionary algorithms and for traditional multiagent Q-learning, and we extend these differential equations to account for lenient learners: agents that forgive possible mismatched teammate actions that resulted in low rewards. We use these extended formal models to study the convergence guarantees for these algorithms, and also to visualize the basins of attraction to optimal and suboptimal solutions in two benchmark coordination problems. The paper demonstrates that lenience provides learners with more accurate information about the benefits of performing their actions, resulting in higher likelihood of convergence to the globally optimal solution. In addition, the analysis indicates that the choice of learning algorithm has an insignificant impact on the overall performance of multiagent learning algorithms; rather, the performance of these algorithms depends primarily on the level of lenience that the agents exhibit to one another. Finally, the research herein supports the strength and generality of evolutionary game theory as a backbone for multiagent learning.
    Original languageEnglish
    Pages (from-to)423-457
    Number of pages34
    JournalJournal of Machine Learning Research
    Volume9
    Publication statusPublished - 2008

    Fingerprint Dive into the research topics of 'Theoretical advantages of lenient learners : an evolutionary game theoretic perspective'. Together they form a unique fingerprint.

    Cite this