Les problèmes de semi-bandits stochastiques combinatoires se présentent naturellement dans de nombreux contextes où le dilemme exploration/exploitation se pose, tels que l’optimisation de contenu web (recommandation/publicité en ligne) ou encore les méthodes de routage à trajet minimal. Ce problème est formulé de la manière suivante : un agent optimise séquentiellement une fonction objectif inconnue et bruitée, définie sur un ensemble puissance $\mathcal{P}([n])$. Pour chaque ensemble $A$ testé, l'agent subit une perte égale à l'écart espéré par rapport à la solution optimale tout en obtenant des observations lui permettant de réduire son incertitude sur les coordonnées de $A$. Notre objectif est d'étudier l'efficience des politiques pour ce problème, en nous intéressant notamment aux deux aspects suivants : l'efficience statistique, où le critère considéré est le regret subi par la politique (la perte cumulée) qui mesure la performance d'apprentissage ; et l'efficience computationnelle (i.e., de calcul). Il est parfois difficile de réunir ces deux aspects dans une seule politique. Dans cette thèse, nous proposons différentes directions pour améliorer l'efficience statistique, tout en essayant de maintenir l'efficience computationnelle des politiques. Nous avons notamment amélioré les méthodes optimistes en développant des algorithmes d'approximation et en affinant les régions de confiance utilisées. Nous avons également exploré une alternative aux méthodes optimistes, à savoir les méthodes randomisées, et avons constaté qu'elles constituent un candidat sérieux pour pouvoir réunir les deux types d'efficience.
Directeurs : Michal VALKO (Université de Lille) et Vianney PERCHET (Université de Paris-Saclay) Rapporteurs : Alexandre PROUTIERE et Marc LELARGE Examinateurs : Claire VERNADE et Richard COMBES
Thèse de l'équipe SCOOL soutenue le 30/11/2020
français
English