Algorithme de bandit et obsolescence : un modèle pour la recommandation

Abstract

Un nombre croissant de systèmes numériques font appel à des algorithmes de bandits pour combiner efficacement exploration de l'environnement et exploitation de l'information accumulée. Les modèles de bandits classiques sont toutefois assez naïfs : ils se bornent à un nombre fixé de choix disponibles (appelés bras), et à des réponses ne variant pas au cours du temps. Pour les moteurs de recommandation, par exemple, il s'agit de limitations sévères : de nouveaux items à recommander apparaissent régulièrement, et les anciens ont une tendance prévisible à perdre de l'attractivité. Pour faire face à ces problèmes, des stratégies capables de gérer l'évolution temporelle du gain moyen associé à chaque bras ont été proposées. Si ces stratégies sont assez générales, elles ne sont pas forcément les plus efficaces dans le cas où la forme de cette évolution temporelle est largement connue a priori. Dans cet article nous proposons deux nouvelles stratégies capables de prendre en compte d'une part l'obsolescence progressive de chaque bras, et d'autre part l'arrivée de nouveaux bras : Fading-UCB, pour laquelle nous fournissons une analyse détaillée de la borne supérieure de regret, et Trust and abandon. Nous montrons expérimentalement que les deux stratégies proposées permettent d'obtenir de meilleures performances que celles obtenues par les stratégies de l'état de l'art.