Apprentissage séquentiel avec similitudes

Autor: Kocák , Tomáš
Přispěvatelé: Sequential Learning ( SEQUEL ), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189 ( CRIStAL ), Ecole Centrale de Lille-Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut Mines-Télécom [Paris]-Université de Lille-Centre National de la Recherche Scientifique ( CNRS ) -Ecole Centrale de Lille-Institut Mines-Télécom [Paris]-Université de Lille-Centre National de la Recherche Scientifique ( CNRS ), Inria Lille Nord Europe - Laboratoire CRIStAL - Université de Lille, Michal Valko, Rémi Munos, Sequential Learning (SEQUEL), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)
Jazyk: angličtina
Rok vydání: 2016
Předmět:
Zdroj: Machine Learning [cs.LG]. Inria Lille Nord Europe-Laboratoire CRIStAL-Université de Lille, 2016. English
Machine Learning [cs.LG]. Inria Lille Nord Europe-Laboratoire CRIStAL-Université de Lille, 2016. English. ⟨NNT : ⟩
Popis: This thesis studies several extensions of multi-armed bandit problem, where a learner sequentially selects an action and obtains the reward of the action. Traditionally, the only information the learner acquires is about the obtained reward while information about other actions is hidden from the learner. This limited feedback can be restrictive in some applications like recommender systems, internet advertising, packet routing, etc. Usually, these problems come with structure, similarities between users or actions, additional observations, or any additional assumptions. Therefore, it is natural to incorporate these assumptions to the algorithms to improve their performance. This thesis focuses on multi-armed bandit problem with some underlying structure usually represented by a graph with actions as vertices. First, we study a problem where the graph captures similarities between actions; connected actions tend to grand similar rewards. Second, we study a problem where the learner observes rewards of all the neighbors of the selected action. We study these problems under several additional assumptions on rewards (stochastic, adversarial), side observations (adversarial, stochastic, noisy), actions (one node at the time, several nodes forming a combinatorial structure in the graph). The main contribution of this thesis is to design algorithms for previously mentioned problems together with theoretical and empirical guarantees. We also introduce several novel quantities, to capture the difficulty of some problems, like effective dimension and effective independence number.; Dans cette thèse nous étudions différentes généralisations du problème dit « du bandit manchot ». Le problème du bandit manchot est un problème de décision séquentiel au cours duquel un agent sélectionne successivement des actions et obtient une récompense pour chacune d’elles. On fait généralement l’hypothèse que seule la récompenseassociée à l’action choisie est observée par l’agent, ce dernier ne reçoit aucune information sur les actions non choisies. Cette hypothèse s’avère parfois très restrictive pour certaines applications telles que les systèmes de recommandations, la publicité en ligne, le routage de paquets, etc. Ces types de problèmes sont en effet souvent très structurés : les utilisateurs et/ou les actions disponibles peuvent par exemple présenter certaines similitudes, ou l’agent peut parfois recevoir davantage d’information de l’environnement, etc. Il paraît dès lors assez naturel de tenir compte de la connaissance de la structure du problème pour améliorer les performances des algorithmes d’apprentissage usuels. Dans cette thèse, nous nous focalisons sur les problèmes de bandits présentant une structure pouvant être modélisée par un graphe dont les noeuds représentent les actions. Dans un premier temps, nous étudierons le cas où les arêtes du graphe modélisent les similitudes entre actions : deux actions connectées auront tendance à fournir des récompenses similaires. Dans un second temps, nous analyserons le cas où l’agent observe les récompenses de toutes les actions adjacentes à l’action choisie dans le graphe. Pour les deux cas précédents, nous dissocierons plusieurs sous-cas : récompenses stochastiques ou adversariales, informations additionnelles stochastiques adversariales ou bruitée, une ou plusieurs actions sélectionnées simultanément. Notre contribution principale a été d’élaborer de nouveaux algorithmes permettant de traiter efficacement les problèmes évoqués précédemment, et de démontrer théoriquement et empiriquement le bon fonctionnement de ces algorithmes. Nos travaux nous ont également amenés à introduire de nouvelles grandeurs, telles que la dimension effective et le nombre d’indépendance effectif, afin de caractériser la difficulté des différents problèmes.
Databáze: OpenAIRE
Externí odkaz: