Le test du rapport de vraisemblance généralisé rencontre klUCB : un algorithme amélioré pour les bandits non stationnaires.

Résumé Nous proposons un nouvel algorithme pour le problème de bandit non stationnaire i.i.d. par morceaux avec 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ètres, le test du rapport de vraisemblance généralisé de Bernoulli, pour lequel nous fournissons de nouvelles garanties théoriques d'intérêt indépendant. Nous analysons deux variantes de notre stratégie, basées sur des redémarrages locaux et des 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. Ceci améliore les limites actuelles de l'état de l'art, 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 passifs et activement adaptatifs de la littérature, et nous soulignons l'avantage d'utiliser des redémarrages locaux.