Exploration aléatoire dans les bandits linéaires généralisés

Résumé

Nous étudions deux algorithmes randomisés pour les bandits linéaires généralisés. Le premier, GLM-TSL, échantillonne un modèle linéaire généralisé (GLM) à partir de l'approximation de Laplace de la distribution postérieure. Le second, GLM-FPL, ajuste un GLM à un historique aléatoirement perturbé des récompenses passées. Nous analysons les deux algorithmes et déduisons 𝑂̃ (𝑑𝑛log𝐾‾‾‾‾‾‾‾√)O~(dnlogK) limites supérieures de leur regret à 𝑛n tours, où 𝑑d est le nombre de caractéristiques et 𝐾K est le nombre de bras. Le premier améliore les travaux antérieurs tandis que le second est le premier pour les perturbations de bruit gaussien dans les modèles non linéaires. Nous évaluons empiriquement le GLM-TSL et le GLM-FPL dans les bandits logistiques, et nous appliquons le GLM-FPL aux bandits à réseaux neuronaux. Notre travail met en évidence le rôle de la randomisation, au-delà de l'échantillonnage postérieur, dans l'exploration.