Ce travail de thèse a été réalisé dans le contexte de la recommandation dynamique. La recommandation est l'action de fournir du contenu personnalisé à un utilisateur utilisant une application, dans le but d'améliorer son utilisation e.g. la recommandation d'un produit sur un site marchant ou d'un article sur un blog. La recommandation est considérée comme dynamique lorsque le contenu à recommander ou encore les goûts des utilisateurs évoluent rapidement e.g. la recommandation d'actualités. Beaucoup d'applications auxquelles nous nous intéressons génèrent d'énormes quantités de données grâce à leurs millions d'utilisateurs sur Internet. Néanmoins, l'utilisation de ces données pour évaluer une nouvelle technique de recommandation ou encore comparer deux algorithmes de recommandation est loin d'être triviale. C'est cette problématique que nous considérons ici. Certaines approches ont déjà été proposées. Néanmoins elles sont très peu étudiées autant théoriquement (biais non quantifié, borne de convergence assez large...) qu'empiriquement (expériences sur données privées). Dans ce travail nous commençons par combler de nombreuses lacunes de l'analyse théorique. Ensuite nous discutons les résultats très surprenants d'une expérience à très grande échelle : une compétition ouverte au public que nous avons organisée. Cette compétition nous a permis de mettre en évidence une source de biais considérable et constamment présente en pratique : l'accélération temporelle. La suite de ce travail s'attaque à ce problème. Nous montrons qu'une approche à base de bootstrap permet de réduire mais surtout de contrôler ce biais. / The context of this thesis work is dynamic recommendation. Recommendation is the action, for an intelligent system, to supply a user of an application with personalized content so as to enhance what is refered to as "user experience" e.g. recommending a product on a merchant website or even an article on a blog. Recommendation is considered dynamic when the content to recommend or user tastes evolve rapidly e.g. news recommendation. Many applications that are of interest to us generates a tremendous amount of data through the millions of online users they have. Nevertheless, using this data to evaluate a new recommendation technique or even compare two dynamic recommendation algorithms is far from trivial. This is the problem we consider here. Some approaches have already been proposed. Nonetheless they were not studied very thoroughly both from a theoretical point of view (unquantified bias, loose convergence bounds...) and from an empirical one (experiments on private data only). In this work we start by filling many blanks within the theoretical analysis. Then we comment on the result of an experiment of unprecedented scale in this area: a public challenge we organized. This challenge along with a some complementary experiments revealed a unexpected source of a huge bias: time acceleration. The rest of this work tackles this issue. We show that a bootstrap-based approach allows to significantly reduce this bias and more importantly to control it.

Les progrès récents en matière d'apprentissage automatique supposent généralement que les données d'apprentissage et de test proviennent de la même distribution de données. Cependant, dans la pratique, les données peuvent être collectées séparément comme des ensembles de données différents. Apprendre à partir de données provenant de plusieurs domaines sources et les généraliser à un autre domaine est un problème crucial de l'apprentissage automatique. Nous abordons ce type de problème dans le contexte de l'apprentissage par transfert (TL), notamment l'adaptation de domaine (DA), la généralisation de domaine (DG) et l'apprentissage multi-tâches (MTL), et ce dans le but de transférer les caractéristiques invariantes communes à de nouveaux domaines. Nous avons étudié ce type d'apprentissage par transfert sous différents aspects, y compris les problèmes liés au décalage conditionnel dans l'adaptation de domaine, les problèmes de désalignement sémantique et de décalage d'étiquettes dans la généralisation de domaine et l'apprentissage multi-tâches en parvenant à plusieurs résultats. Concrètement, nous explorons d'abord les problèmes de décalage conditionnel (DA) avec une stratégie d'apprentissage actif pour interroger les instances les plus informatives dans le domaine cible afin de faire migrer le terme de désaccord entre les fonctions d'étiquetage des domaines source et cible. Nous explorons ensuite les similitudes de catégories dans les problèmes liés à la généralisation de domaine (DG) via l'entraînement adversarial basé sur le transport optimal avec un objectif d'apprentissage de similarité métrique afin d'améliorer la correspondance au niveau du domaine et de la classe pour les problèmes DG. Nous étudions ensuite, plus en détail les relations entre les étiquettes et la sémantique dans le MTL, où nous fournissons une compréhension théorique de la manière de contrôler les divergences entre les étiquettes et la distribution sémantique. Enfin, nous étendons l'analyse théorique sur la façon d'exploiter les étiquettes et l'information sémantique dans la généralisation de domaine (DG), en fournissant une première analyse pour comprendre les propriétés de généralisation dans le contrôle des divergences de distribution des étiquettes et de la sémantique. Pour chaque travail reflété dans cette thèse, nous menons des expériences approfondies afin de démontrer l'efficacité et les objectifs d'apprentissage. Les résultats expérimentaux confirment que nos méthodes parviennent aux performances souhaitées et indiquées par les principes d'analyse et d'apprentissage, ce qui valide les contributions de cette thèse. / Recent machine learning progresses usually assume the data for training and testing are from the same data distribution. However, in practice, the data might be gathered separately as different datasets. To learn data from several source domains and generalize to another domain, is a crucial problem in machine learning. We tackle this kind of problem in the context of Transfer Learning (TL), including Domain Adaptation (DA), Domain Generalization (DG) and Multi-task Learning (MTL), with the sake of transferring the common invariant features to new domains. We have investigated this kind of transfer learning method in several different aspects, including the conditional shift problems in domain adaptation, semantic misalignment and label shift problems in domain generalization and multi-task learning problems with several accomplishments. Concretely, we first explore the conditional shift problems DA with an active learning strategy to query the most informative instances in the target domain to migrate the disagreement term between the source and target domain labelling functions. We then explore the category similarities in the DG problems via the optimal transport-based adversarial training with a metric similarity learning objective to enhance both the domain-level and class-level matching for DG problems. After that, we further investigate the label and semantic relations in MTL, where we provide the first theoretical understanding of how to control the label and semantic distribution divergences. Lastly, we extend the theoretical analysis on how to leverage the label and semantic information in DG, providing the first analysis to understand the generalization properties on controlling the label and semantic distribution divergences. For each work reflected in this thesis, we also conduct intensive experiments to demonstrate the effectiveness and learning objectives. The experimental results confirm that our methods achieve the desired performance indicated by the analysis and learning principles, which confirms the contributions of this thesis.

Cette these puise sa motivation d'un jeu qui apparait chez les insectes dits parasitoïdes, qui, dans le cadre d'une competition sans merci pour la conquete d'hôtes via lesquels se reproduire, s'en prennent directement a la descendance de leurs semblables. Il s'agit de superparasitisme.<br />Bien souvent, les hotes se presentent sous forme d'agregats epars dans l'environnement. Ainsi le cadre spatio-temporel de ce jeu est-il celui de l'agregat. Agregat dont la composition, en termes d'hotes sains et parasites, evolue au cours du jeu, d'ou son caractere dynamique.<br />En premier lieu, nous presentons ce que sont les jeux dynamiques au travers d'un resultat original qui traite du decouplage des equations d'Isaacs dans les jeux differentiels a deux joueurs et somme non-nulle. Il se trouve illustre par un exemple a propos du conflit que cree la question des soins parentaux chez les especes bi-parentales.<br />Dans un second temps, nous revisitons la theorie classique de la cueillette optimale, que nous etendons a la prise en compte d'une multitude de joueurs. Se succedent alors, lorsque la competition se fait vive, des episodes de guerre d'usure, entrecoupes parfois de quelque treve.<br />Vient enfin l'etude du superparasitisme tel un jeu differentiel. Nous montrons notamment que le superparasitisme n'implique cette fois pas necessairement de guerre d'usure. Cela ouvre des perspectives tant au plan mathematique (singularites en jeux differentiels a somme non nulle) que biologique (experiences de laboratoire).

Diss. -- Constance, 1966. / Includes bibliographical references.

Diss. -- Constance, 1966. / Includes bibliographical references.

Thèse (Ph. D.)--Université Laval, 2002. / Bibliogr.: f. 47-53. Publié aussi en version électronique.

Thèse (M.Ps.)--Université Laval, 2002. / Bibliogr.: p. 44-46. Publié aussi en version électronique.

Th.--Lett.--Paris 10, 1983.

Cette thèse traite des domaines suivant en Apprentissage Automatique: la théorie des Bandits, l'Apprentissage statistique et l'Apprentissage par renforcement. Son fil rouge est l'étude de plusieurs notions d'adaptation, d'un point de vue non asymptotique : à un environnement ou à un adversaire dans la partie I, à la structure d'un signal dans la partie II, à la structure de récompenses ou à un modèle des états du monde dans la partie III. Tout d'abord nous dérivons une analyse non asymptotique d'un algorithme de bandit à plusieurs bras utilisant la divergence de Kullback-Leibler. Celle-ci permet d'atteindre, dans le cas de distributions à support fini, la borne inférieure de performance asymptotique dépendante des distributions de probabilité connue pour ce problème. Puis, pour un bandit avec un adversaire possiblement adaptatif, nous introduisons des modèles dépendants de l'histoire et traduisant une possible faiblesse de l'adversaire et montrons comment en tirer parti pour concevoir des algorithmes adaptatifs à cette faiblesse. Nous contribuons au problème de la régression en montrant l'utilité des projections aléatoires, à la fois sur le plan théorique et pratique, lorsque l'espace d'hypothèses considéré est de dimension grande, voire infinie. Nous utilisons également des opérateurs d'échantillonnage aléatoires dans le cadre de la reconstruction parcimonieuse lorsque la base est loin d'être orthogonale. Enfin, nous combinons la partie I et II : pour fournir une analyse non-asymptotique d'algorithmes d'apprentissage par renforcement; puis, en amont du cadre des Processus Décisionnel de Markov, pour discuter du problème pratique du choix d'un bon modèle d'états. / This thesis studies the following topics in Machine Learning: Bandit theory, Statistical learning and Reinforcement learning. The common underlying thread is the non-asymptotic study of various notions of adaptation : to an environment or an opponent in part I about bandit theory, to the structure of a signal in part II about statistical theory, to the structure of states and rewards or to some state-model of the world in part III about reinforcement learning. First we derive a non-asymptotic analysis of a Kullback-Leibler-based algorithm for the stochastic multi-armed bandit that enables to match, in the case of distributions with finite support, the asymptotic distribution-dependent lower bound known for this problem. Now for a multi-armed bandit with a possibly adaptive opponent, we introduce history-based models to catch some weakness of the opponent, and show how one can benefit from such models to design algorithms adaptive to this weakness. Then we contribute to the regression setting and show how the use of random matrices can be beneficial both theoretically and numerically when the considered hypothesis space has a large, possibly infinite, dimension. We also use random matrices in the sparse recovery setting to build sensing operators that allow for recovery when the basis is far from being orthogonal. Finally we combine part I and II to first provide a non-asymptotic analysis of reinforcement learning algorithms such as Bellman-residual minimization and a version of Least-squares temporal-difference that uses random projections and then, upstream of the Markov Decision Problem setting, discuss the practical problem of choosing a good model of states.

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écompense associé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 certains problèmes très structurés tels que les systèmes de recommandations, la publicité en ligne, le routage de paquets, etc. Il paraît 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 nœuds représentent les actions. Dans un premier temps, nous étudierons le cas où les arêtes du graphe modélisent les similitudes entre actions. 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. 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. / This thesis studies several extensions of multi-armed bandit problem, where a learner sequentially selects an action and obtain the reward of the action. Traditionally, the only information the learner acquire 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 guaranties. We also introduce several novel quantities, to capture the difficulty of some problems, like effective dimension and effective independence number.