Ordonnancement d'objets par bandits unimodaux sur des graphes paramétriques

International audience; Nous cherchons à résoudre le problème du placement optimal (ordonnancement), en ligne, de K objets à L positions pré-déterminées sur une page web de manière à maximiser le nombre de clics des utilisateurs.Nous proposons un algorithme original, facile à implémenter et ayant des garanties théoriques fortes fonctionnant pour un modèle utilisateur basé positions(PBM) qui est bien adapté à un contexte dans lequel les objets sont placés sur une grille où aucune position n’est à priori meilleure. Notre algorithme propose une recommandation optimale à travers l’apprentissage d’un graphe compacte représentant les différentes permutations de L items parmi les K positions. La borne logarithmique de regret de notre algorithme de bandit est une conséquence directe de la propriété uni-modale de ce bandit par rapport au graphe appris.Des expérimentations comparant notre méthode à l’ état de l’art des algorithmes fonctionnant sur ce même modèle utilisateur, montrent que notre méthode est beaucoup plus efficace tout en fournissant des performances de regret du même niveau que les meilleurs algorithmes connus et ce sur des données synthétiques ou des données réelles.