Constant or logarithmic regret in asynchronous multiplayer bandits - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2023

Constant or logarithmic regret in asynchronous multiplayer bandits

Résumé

Multiplayer bandits have recently been extensively studied because of their application to cognitive radio networks. While the literature mostly considers synchronous players, radio networks (e.g. for IoT) tend to have asynchronous devices. This motivates the harder, asynchronous multiplayer bandits problem, which was first tackled with an explore-then-commit (ETC) algorithm (see Dakdouk, 2022), with a regret upper-bound in O(T 2 3). Before even considering decentralization, understanding the centralized case was still a challenge as it was unknown whether getting a regret smaller than Ω(T 2 3) was possible. We answer positively this question, as a natural extension of UCB exhibits a O(T log(T)) minimax regret. More importantly, we introduce Cautious Greedy, a centralized algorithm that yields constant instance-dependent regret if the optimal policy assigns at least one player on each arm (a situation that is proved to occur when arm means are close enough). Otherwise, its regret increases as the sum of log(T) over some sub-optimality gaps. We provide lower bounds showing that Cautious Greedy is optimal in the data-dependent terms. Therefore, we set up a strong baseline for asynchronous multiplayer bandits and suggest that learning the optimal policy in this problem might be easier than thought, at least with centralization.
Fichier principal
Vignette du fichier
2305.19691.pdf (1.02 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-04273108 , version 1 (07-11-2023)

Identifiants

Citer

Hugo Richard, Etienne Boursier, Vianney Perchet. Constant or logarithmic regret in asynchronous multiplayer bandits. 2023. ⟨hal-04273108⟩
28 Consultations
17 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More