Fournir les infrastructures de calcul nécessaires à la résolution des problèmescom-plexes de la société moderne constitue un défistratégique. Lesorganisations y répondent classiquement en mettant en place de largesinfrastructures de calcul parallèle et distribué. Les vendeurs de systèmes deCalcul Hautes Performances sont incités par la compétition à produire toujoursplus de puissance de calcul et de stockage, ce qui mène à des plateformes”Petascale“ spécifiques et sophistiquées, et bientôt à des machines”Exascale“. Ces systèmes sont gérés de manière centralisée à l’aide desolutions logicielles de gestion de jobs et de resources dédiées. Un problèmecrucial auquel répondent ces logiciels est le problème d’ordonnancement, pourlequel le gestionnaire de resources doit choisir quand, et sur quellesresources exécuter quelle tache calculatoire. Cette thèse fournit des solutionsà ce problème. Toutes les plateformes sont différentes. En effet, leurinfrastructure, le comportement de leurs utilisateurs et les objectifs del’organisation hôte varient. Nous soutenons donc que les politiquesd’ordonnancement doivent s’adapter au comportement des systèmes. Dans cemanuscrit, nous présentons plusieurs manières d’obtenir cette adaptativité. Atravers une approche expérimentale, nous étudions plusieurs compromis entre lacomplexité de l’approche, le gain potentiel, et les risques pris. / Providing the computational infrastucture needed to solve complex problemsarising in modern society is a strategic challenge. Organisations usuallyadress this problem by building extreme-scale parallel and distributedplatforms. High Performance Computing (HPC) vendors race for more computingpower and storage capacity, leading to sophisticated specific Petascaleplatforms, soon to be Exascale platforms. These systems are centrally managedusing dedicated software solutions called Resource and Job Management Systems(RJMS). A crucial problem adressed by this software layer is the job schedulingproblem, where the RJMS chooses when and on which resources computational taskswill be executed. This manuscript provides ways to adress this schedulingproblem. No two platforms are identical. Indeed, the infrastructure, userbehavior and organization's goals all change from one system to the other. Wetherefore argue that scheduling policies should be adaptative to the system'sbehavior. In this manuscript, we provide multiple ways to achieve thisadaptativity. Through an experimental approach, we study various tradeoffsbetween the complexity of the approach, the potential gain, and the riskstaken.

Ce travail de thèse s'inscrit dans le domaine du machine learning et concerne plus particulièrement les sous-catégories de l'optimisation stochastique, du online learning et du clustering. Ces sous-domaines existent depuis plusieurs décennies mais ils ont tous reçu un éclairage différent au cours de ces dernières années. Notamment, les jeux de bandits offrent aujourd'huiun cadre commun pour l'optimisation stochastique et l'online learning. Ce point de vue conduit à de nombreuses extensions du jeu de base. C'est sur l'étude mathématique de ces jeux que se concentre la première partie de cette thèse. La seconde partie est quant à elle dédiée au clustering et plus particulièrement à deux notions importantes : la consistance asymptotique des algorithmes et la stabilité comme méthode de sélection de modèles. / This thesis takes place within the machine learning theory. In particular it focuses on three sub-domains, stochastic optimization, online learning and clustering. These subjects exist for decades, but all have been recently studied under a new perspective. For instance, bandits games now offer a unified framework for stochastic optimization and online learning. This point of view results in many new extensions of the basic game. In the first part of this thesis, we focus on the mathematical study of these extensions (as well as the classixcal game). On the order hand, in the second part we discuss two important theoretical concepts for clustering, namely the consistency of algorithms and the stability as a tool for model selection.

Dans cette thèse nous étudions des problèmes d'allocation de ressources dans des environnements incertains où un agent choisit ses actions séquentiellement. Après chaque pas, l'environnement fournit une observation bruitée sur la valeur de l'action choisie et l'agent doit utiliser ces observations pour allouer ses ressources de façon optimale. Dans le cadre le plus classique, dit modèle du bandit à plusieurs bras (MAB), on fait l'hypothèse que chaque observation est tirée aléatoirement d'une distribution de probabilité associée à l'action choisie et ne fournit aucune information sur les valeurs espérées des autres actions disponibles dans l'environnement. Ce modèle a été largement étudié dans la littérature et plusieurs stratégies optimales ont été proposées, notamment pour le cas où le but de l'agent est de maximiser la somme des observations. Ici, nous considérons une version du MAB où les actions ne sont plus indépendantes, mais chaque observation peut être utilisée pour estimer les valeurs de l'ensemble des actions de l'environnement. Plus précisément, nous proposons des stratégies d'allocation de ressources qui sont efficaces et adaptées à un environnement caractérisé par une structure linéaire globale. Nous étudions notamment les séquences d'actions qui mènent à : (i) identifier la meilleure action avec une précision donnée et en utilisant un nombre minimum d'observations, ou (ii) maximiser la précision d'estimation des valeurs de chaque action. De plus, nous étudions les cas où les observations provenant d'un algorithme de bandit dans un environnement donné peuvent améliorer par la suite la performance de l'agent dans d'autres environnements similaires. / This thesis is dedicated to the study of resource allocation problems in uncertain environments, where an agent can sequentially select which action to take. After each step, the environment returns a noisy observation of the value of the selected action. These observations guide the agent in adapting his resource allocation strategy towards reaching a given objective. In the most typical setting of this kind, the stochastic multi-armed bandit (MAB), it is assumed that each observation is drawn from an unknown probability distribution associated with the selected action and gives no information on the expected value of the other actions. This setting has been widely studied and optimal allocation strategies were proposed to solve various objectives under the MAB assumptions. Here, we consider a variant of the MAB setting where there exists a global linear structure in the environment and by selecting an action, the agent also gathers information on the value of the other actions. Therefore, the agent needs to adapt his resource allocation strategy to exploit the structure in the environment. In particular, we study the design of sequences of actions that the agent should take to reach objectives such as: (i) identifying the best value with a fixed confidence and using a minimum number of pulls, or (ii) minimizing the prediction error on the value of each action. In addition, we investigate how the knowledge gathered by a bandit algorithm in a given environment can be transferred to improve the performance in other similar environments.

Texte remanié de: Mémoire de DEA--Histoire--Paris 8. / Bibliogr. p. 141-151.

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.

Magisterarb.--[Universität Gießen], [1993?]. / Lieu de thèse probable d'aprés la préf. Bibliogr. p. 259-277.

Diss.--Fakultät für Geschichtswissenschaft und Philosophie--Universität Bielefeld, 1988. / Bibliogr. p. 325-366. Index.

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.

Texte remanié de: Thèse de doctorat--Histoire--Taipei, 2001. / Mention parallèle de titre ou de responsabilité : Disturbing between the "brigand region" and "administration district" : the transformation of the social order and local administration on the border region of Fujian, Guangdong, Jiangxi and Hunan during the Ming Dynasty. Bibliogr. p. 541-582.