Multi-Player Bandits Revisited.

Résumé Les Bandits Multi-Armés (MAB) multi-joueurs ont été largement étudiés dans la littérature, motivés par des applications aux systèmes de Radio Cognitive. C'est également en raison de ces applications que nous motivons l'introduction de plusieurs niveaux de rétroaction pour les algorithmes MAB multi-joueurs. La plupart des travaux existants supposent que les informations de détection sont disponibles pour l'algorithme. Sous cette hypothèse, nous améliorons la limite inférieure de l'état de l'art pour le regret de tout algorithme décentralisé et nous introduisons deux algorithmes, RandTopM et MCTopM, dont on montre qu'ils surpassent empiriquement les algorithmes existants. De plus, nous fournissons de solides garanties théoriques pour ces algorithmes, y compris une notion d'optimalité asymptotique en termes de nombre de sélections de mauvais bras. Nous introduisons ensuite une heuristique prometteuse, appelée Selfish, qui peut fonctionner sans information de détection, ce qui est crucial pour les applications émergentes aux réseaux de l'Internet des objets. Nous étudions les performances empiriques de cet algorithme et fournissons quelques premiers éléments théoriques pour la compréhension de son comportement.