The Generalized Likelihood Ratio Test meets klUCB: an Improved Algorithm for Piece-Wise Non-Stationary Bandits

Résumé : Nous proposons un nouvel algorithme pour le problème du bandit non stationnaire i.i.d. avec des récompenses bornées. Notre proposition, GLR-klUCB, combine un algorithme de bandit efficace, klUCB, avec un détecteur de points de changement efficace et sans paramètre, le test du rapport de vraisemblance généralisé, dans sa variante de Bernoulli. Nous fournissons de nouvelles garanties théoriques d'intérêt indépendant pour ce test (GLRT). Nous analysons deux variantes de notre stratégie, basées sur les redémarrages locaux et les redémarrages globaux, et montrons que leur regret est limité par $O(\Upsilon_T \sqrt{T \log(T)})$ si le nombre de points de changement $Υ_T$ est inconnu, et par $O(\sqrt{\Upsilon_T T \log(T)})$ si $\Upsilon_T$ est connu. Ces résultats améliorent les bornes de l'état de l'art actuel, car notre algorithme ne nécessite aucun réglage basé sur la connaissance de la complexité du problème autre que $Υ_T$. Nous présentons des expériences numériques montrant que GLR-klUCB surpasse les algorithmes passivement et activement adaptatifs de la littérature, et soulignons les avantages de l'utilisation de redémarrages locaux.
Type de document :
Pré-publication, Document de travail
2019
Liste complète des métadonnées

https://hal.inria.fr/hal-02006471
Contributeur : Lilian Besson <>
Soumis le : lundi 4 février 2019 - 16:08:13
Dernière modification le : vendredi 8 février 2019 - 01:24:37

Fichiers

The-Generalized-Likelihood-Rat...
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-02006471, version 1
  • ARXIV : 1902.01575

Citation

Lilian Besson, Emilie Kaufmann. The Generalized Likelihood Ratio Test meets klUCB: an Improved Algorithm for Piece-Wise Non-Stationary Bandits. 2019. 〈hal-02006471〉

Partager

Métriques

Consultations de la notice

60

Téléchargements de fichiers

33