Apprentissage séquentiel avec similitudes

Dans cette these nous etudions differentes generalisations du probleme dit « du bandit manchot ». Le probleme du bandit manchot est un probleme de decision sequentiel au cours duquel un agent selectionne successivement des actions et obtient une recompense pour chacune d'elles. On fait generalement l'hypothese que seule la recompense associee a l'action choisie est observee par l'agent, ce dernier ne recoit aucune information sur les actions non choisies. Cette hypothese s'avere parfois tres restrictive pour certains problemes tres structures tels que les systemes de recommandations, la publicite en ligne, le routage de paquets, etc. Il parait assez naturel de tenir compte de la connaissance de la structure du probleme pour ameliorer les performances des algorithmes d'apprentissage usuels. Dans cette these, nous nous focalisons sur les problemes de bandits presentant une structure pouvant etre modelisee par un graphe dont les nœuds representent les actions. Dans un premier temps, nous etudierons le cas ou les aretes du graphe modelisent les similitudes entre actions. Dans un second temps, nous analyserons le cas ou l'agent observe les recompenses de toutes les actions adjacentes a l'action choisie dans le graphe. Notre contribution principale a ete d'elaborer de nouveaux algorithmes permettant de traiter efficacement les problemes evoques precedemment, et de demontrer theoriquement et empiriquement le bon fonctionnement de ces algorithmes. Nos travaux nous ont egalement amenes a introduire de nouvelles grandeurs, telles que la dimension effective et le nombre d'independance effectif, afin de caracteriser la difficulte des differents problemes.