Competition and Coordination in Stochastic.pdf

Competition and Coordination in Stochastic Games Andriy Burkov, Abdeslam Boularias, and Brahim Chaib-draa DAMAS Laboratory Universite? Laval G1K 7P4, Quebec, Canada {burkov,boularia,chaib}@damas.ift.ulaval.ca Abstract. Agent competition and coordination are two classical and most important tasks in multiagent systems. In recent years, there was a number of learning algorithms proposed to resolve such type of problems. Among them, there is an important class of algorithms, called adaptive learning algorithms, that were shown to be able to converge in self-play to a solution in a wide variety of the repeated matrix games. Although cer- tain algorithms of this class, such as Infinitesimal Gradient Ascent (IGA), Policy Hill-Climbing (PHC) and Adaptive Play Q-learning (APQ), have been catholically studied in the recent literature, a question of how these algorithms perform versus each other in general form stochastic games is remaining little-studied. In this work we are trying to answer this question. To do that, we analyse these algorithms in detail and give a comparative analysis of their behavior on a set of competition and coor- dination stochastic games. Also, we introduce a new multiagent learning algorithm, called ModIGA. This is an extension of the IGA algorithm, which is able to estimate the strategy of its opponents in the cases when they do not explicitly play mixed strategies (e.g., APQ) and which can be applied to the games with more than two actions. 1 Introduction Competition and coordination between autonomous agents are two classical and most important tasks in multiagent systems. Coordination is especially impor- tant in multi-robotic systems where a number of non-adversarial robots (but not necessarily explicitly cooperative) are aimed to accomplish a task while being limited in communication and in knowledge about principles of rationality under- lying their counterparts. On the other hand, competition is a natural condition of most real life situati