Hedging Algorithms and Repeated Matrix Games

Abstract : Playing repeated matrix games (RMG) while maximizing the cumulative returns is a basic method to evaluate multi-agent learning (MAL) algorithms. Previous work has shown that UCB, M3, S or Exp3 algorithms have good behaviors on average in RMG. Besides, hedging algorithms have been shown to be effective on prediction problems. An hedging algorithm is made up with a top-level algorithm and a set of basic algorithms. To make its decision, an hedging algorithm uses its top-level algorithm to choose a basic algorithm, and the chosen algorithm makes the decision. This paper experimentally shows that well-selected hedging algorithms are better on average than all previous MAL algorithms on the task of playing RMG against various players. S is a very good top-level algorithm, and UCB and M3 are very good basic algorithms. Furthermore, two-level hedging algorithms are more effective than one-level hedging algorithms, and three levels are not better than two levels.
Type de document :
Communication dans un congrès
Workshop on Machine Learning and Data Mining in and around Games (ECML-PKDD), Sep 2011, Athens, Greece. 2011
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00975943
Contributeur : Damien Pellier <>
Soumis le : mercredi 9 avril 2014 - 13:29:22
Dernière modification le : mercredi 29 novembre 2017 - 14:49:54
Document(s) archivé(s) le : mercredi 9 juillet 2014 - 12:11:11

Fichier

bouzy11.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00975943, version 1

Collections

Citation

Bruno Bouzy, Marc Métivier, Damien Pellier. Hedging Algorithms and Repeated Matrix Games. Workshop on Machine Learning and Data Mining in and around Games (ECML-PKDD), Sep 2011, Athens, Greece. 2011. 〈hal-00975943〉

Partager

Métriques

Consultations de la notice

92

Téléchargements de fichiers

130