Multi-Player Bandits Models Revisited

Résumé : Les bandits multi-joueurs multiarmes (MAB) ont fait l'objet d'études approfondies dans la littérature, motivés par des applications aux systèmes de radio intelligente. De telles applications motivent l'introduction de plusieurs niveaux d'informations pour les algorithmes MAB multi-joueurs. La plupart des travaux récents supposent que l'algorithme dispose d'informations de détection (sensing). Dans cette hypothèse, nous améliorons la meilleure borne inférieure connue pour le regret de tout algorithme décentralisé, et introduisons deux algorithmes, RandTopM et MCTopM, qui sont empiriquement meilleurs par rapport aux 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 des mauvais bras. Nous introduisons ensuite une heuristique prometteuse, appelée Selfish, qui peut fonctionner sans utiliser le sensing, ce qui est crucial pour les applications émergentes aux réseaux de type 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.
Type de document :
Pré-publication, Document de travail
2017
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01629733
Contributeur : Lilian Besson <>
Soumis le : lundi 6 novembre 2017 - 17:11:40
Dernière modification le : vendredi 17 novembre 2017 - 08:50:20

Fichiers

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

Licence


Distributed under a Creative Commons Paternité - Pas d'utilisation commerciale - Partage selon les Conditions Initiales 4.0 International License

Identifiants

  • HAL Id : hal-01629733, version 1
  • ARXIV : 1711.02317

Citation

Lilian Besson, Emilie Kaufmann. Multi-Player Bandits Models Revisited. 2017. 〈hal-01629733〉

Partager

Métriques

Consultations de
la notice

113

Téléchargements du document

20