Theoretical Advantages of Lenient Learners: An Evolutionary Game Theoretic Perspective
Venue
Journal of Machine Learning Research (2008)
Publication Year
2008
Authors
Liviu Panait, Karl Tuyls, Sean Luke
BibTeX
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 convergenceguarantees for these algorithms, and
also to visualize the basins of attraction to optimal and suboptimal solutions in
two benchmark coordination problems. We demonstrate 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, our 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, our research supports the
strength and generality of evolutionary game theory as a backbone for multiagent
learning.
