| Title: |
Multi-Player Bandits Revisited ; Modèles de Bandits Multi-Joueurs Revisités |
| Authors: |
Besson, Lilian; Kaufmann, Emilie |
| Contributors: |
Institut d'Électronique et des Technologies du numéRique (IETR); Université de Nantes (UN)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes); Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS); SUPELEC-Campus Rennes; Ecole Supérieure d'Electricité - SUPELEC (FRANCE); Sequential Learning (SEQUEL); Inria Lille - Nord Europe; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL); Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS); CentraleSupélec; Signal, Communication et Electronique Embarquée (SCEE); Institut d'Electronique et de Télécommunications de Rennes (IETR); Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes); Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Ecole Supérieure d'Electricité - SUPELEC (FRANCE)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes); Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Ecole Supérieure d'Electricité - SUPELEC (FRANCE)-Centre National de la Recherche Scientifique (CNRS); Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL); Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS); Centre National de la Recherche Scientifique (CNRS); CNRS, projet PEPS BIO; Mehryar Mohri; Karthik Sridharan; ANR-16-CE40-0002,BADASS,BANDITS MANCHOTS POUR SIGNAUX NON-STATIONNAIRES ET STRUCTURES(2016) |
| Source: |
Algorithmic Learning Theory ; https://inria.hal.science/hal-01629733 ; Algorithmic Learning Theory, Mehryar Mohri; Karthik Sridharan, Apr 2018, Lanzarote, Spain ; http://www.cs.cornell.edu/conferences/alt2018/ |
| Publisher Information: |
HAL CCSD |
| Publication Year: |
2018 |
| Collection: |
Université de Rennes 1: Publications scientifiques (HAL) |
| Subject Terms: |
Multi-Armed Bandits; Cognitive Radio; Opportunistic Spectrum Access; Reinforcement learning; Decentralized algorithms; [STAT.ML]Statistics [stat]/Machine Learning [stat.ML] |
| Subject Geographic: |
Lanzarote; Spain |
| Description: |
International audience ; Multi-player Multi-Armed Bandits (MAB) have been extensively studied in the literature, motivated by applications to Cognitive Radio systems. Driven by such applications as well, we motivate the introduction of several levels of feedback for multi-player MAB algorithms. Most existing work assume that sensing information is available to the algorithm. Under this assumption, we improve the state-of-the-art lower bound for the regret of any decentralized algorithms and introduce two algorithms, RandTopM and MCTopM, that are shown to empirically outperform existing algorithms. Moreover, we provide strong theoretical guarantees for these algorithms, including a notion of asymptotic optimality in terms of the number of selections of bad arms. We then introduce a promising heuristic, called Selfish, that can operate without sensing information, which is crucial for emerging applications to Internet of Things networks. We investigate the empirical performance of this algorithm and provide some first theoretical elements for the understanding of its behavior. ; 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 ... |
| Document Type: |
conference object |
| Language: |
English |
| Relation: |
info:eu-repo/semantics/altIdentifier/arxiv/1711.02317; ARXIV: 1711.02317 |
| Availability: |
https://inria.hal.science/hal-01629733; https://inria.hal.science/hal-01629733v2/document; https://inria.hal.science/hal-01629733v2/file/BK__ALT_2018.pdf |
| Rights: |
http://creativecommons.org/licenses/by-nc-sa/ ; info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.1DF6762B |
| Database: |
BASE |