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

Un nombre croissant de systèmes numériques font appel à des algortihmes 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épones ne variant pas au cours du temps. Pour les moteurs de recommandation, par exemple, il s'agit de limitations sévèers : de novueaux items à recommander apparaissent régulièrement, et les ancines 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. Sic es stratégies sont assez générlaes, elles ne sont pas forcément les plus efficaces dnas le cas où la forme de cette évolution temporelle est largement connue a priori.

Dans cet article, nous proposons deux nouvelles stratégies capabes de prendre en compte d'une part l'obsolescence progressive de chaque bars, et d'autre part l'arrivée de nouveaux brase : 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.