Apprentissage efficient dans les problèmes de semi-bandits stochastiques combinatoires

Les problemes de semi-banditsstochastiques combinatoires se presentent naturellement dans de nombreux contextes ou le dilemme exploration/exploitation se pose, tels que l’optimisation de contenu web (recommandation/publicite en ligne) ou encore les methodes de routage a trajet minimal. Ce probleme est formule de la maniere suivante : un agent optimise sequentiellement une fonction objectif inconnue et bruitee, definie sur un ensemble puissance $mathcal{P}([n])$. Pour chaque ensemble $A$ teste,l'agent subit une perte egale a l'ecart espere par rapport a la solution optimale tout en obtenant des observations lui permettant de reduire son incertitude sur les coordonnees de $A$.Notre objectif est d'etudier l'efficience des politiques pour ce probleme, en nous interessant notamment aux deux aspects suivants : l'efficience statistique, ou le critere considere est le regret subi par la politique (la perte cumulee) qui mesure la performance d'apprentissage ; et l'efficience computationnelle (i.e., de calcul). Il est parfois difficile de reunir ces deux aspects dans une seule politique. Dans cette these, nous proposons differentes directions pour ameliorer l'efficience statistique, tout en essayant de maintenir l'efficience computationnelle des politiques. Nous avons notamment ameliore les methodes optimistes en developpant des algorithmes d'approximation et en affinant les regions de confiance utilisees. Nous avons egalement explore une alternative aux methodes optimistes, a savoir les methodes randomisees, et avons constate qu'elles constituent un candidat serieux pour pouvoir reunir les deux types d'efficience.