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.

L'apprentissage par renforcement est la réponse du domaine de l'apprentissage numérique au problème du contrôle optimal. Dans ce paradigme, un agent informatique apprend à contrôler un environnement en interagissant avec ce dernier. Il reçoit régulièrement une information locale de la qualité du contrôle effectué sous la forme d'une récompense numérique (ou signal de renforcement), et son objectif est de maximiser une fonction cumulante de ces récompenses sur le long terme, généralement modélisée par une fonction dite de valeur. Le choix des actions appliquées à l'environnement en fonction de sa configuration est appelé une politique, et la fonction de valeur quantifie donc la qualité de cette politique. Ce parangon est très général, et permet de s'intéresser à un grand nombre d'applications, comme la gestion des flux de gaz dans un complexe sidérurgique, que nous abordons dans ce manuscrit. Cependant, sa mise en application pratique peut être difficile. Notamment, lorsque la description de l'environnement à contrôler est trop grande, une représentation exacte de la fonction de valeur (ou de la politique) n'est pas possible. Dans ce cas se pose le problème de la généralisation (ou de l'approximation de fonction de valeur) : il faut d'une part concevoir des algorithmes dont la complexité algorithmique ne soit pas trop grande, et d'autre part être capable d'inférer le comportement à suivre pour une configuration de l'environnement inconnue lorsque des situations proches ont déjà été expérimentées. C'est le problème principal que nous traitons dans ce manuscrit, en proposant une approche inspirée du filtrage de Kalman.

Cette thèse étudie une classe d'algorithmes d'apprentissage par renforcement (RL), appelée « itération sur les politiques obtenues par classification » (CBPI). Contrairement aux méthodes standards de RL, CBPI n'utilise pas de représentation explicite de la fonction valeur. CBPI réalise des déroulés (des trajectoires) et estime la fonction action-valeur de la politique courante pour un nombre limité d'états et d'actions. En utilisant un ensemble d'apprentissage construit à partir de ces estimations, la politique gloutonne est apprise comme le produit d'un classificateur. La politique ainsi produite à chaque itération de l'algorithme, n'est plus définie par une fonction valeur (approximée), mais par un classificateur. Dans cette thèse, nous proposons de nouveaux algorithmes qui améliorent les performances des méthodes CBPI existantes, spécialement lorsque le nombre d’interactions avec l’environnement est limité. Nos améliorations se portent sur les deux limitations de CBPI suivantes : 1) les déroulés utilisés pour estimer les fonctions action-valeur doivent être tronqués et leur nombre est limité, créant un compromis entre le biais et la variance dans ces estimations, et 2) les déroulés sont répartis de manière uniforme entre les états déroulés et les actions disponibles, alors qu'une stratégie plus évoluée pourrait garantir un ensemble d'apprentissage plus précis. Nous proposons des algorithmes CBPI qui répondent à ces limitations, respectivement : 1) en utilisant une approximation de la fonction valeur pour améliorer la précision (en équilibrant biais et variance) des estimations, et 2) en échantillonnant de manière adaptative les déroulés parmi les paires d'état-action. / This dissertation is motivated by the study of a class of reinforcement learning (RL) algorithms, called classification-based policy iteration (CBPI). Contrary to the standard RL methods, CBPI do not use an explicit representation for value function. Instead, they use rollouts and estimate the action-value function of the current policy at a collection of states. Using a training set built from these rollout estimates, the greedy policy is learned as the output of a classifier. Thus, the policy generated at each iteration of the algorithm, is no longer defined by a (approximated) value function, but instead by a classifier. In this thesis, we propose new algorithms that improve the performance of the existing CBPI methods, especially when they have a fixed budget of interaction with the environment. Our improvements are based on the following two shortcomings of the existing CBPI algorithms: 1) The rollouts that are used to estimate the action-value functions should be truncated and their number is limited, and thus, we have to deal with bias-variance tradeoff in estimating the rollouts, and 2) The rollouts are allocated uniformly over the states in the rollout set and the available actions, while a smarter allocation strategy could guarantee a more accurate training set for the classifier. We propose CBPI algorithms that address these issues, respectively, by: 1) the use of a value function approximation to improve the accuracy (balancing the bias and variance) of the rollout estimates, and 2) adaptively sampling the rollouts over the state-action pairs.

Ce mémoire aborde l'utilisation des méthodes par bandit pour résoudre la problématique de l'entraînement de modèles de générations de résumés extractifs. Les modèles extractifs, qui bâtissent des résumés en sélectionnant des phrases d'un document original, sont difficiles à entraîner car le résumé cible correspondant à un document n'est habituellement pas constitué de manière extractive. C'est à cet effet que l'on propose de voir la production de résumés extractifs comme différents problèmes de bandit, lesquels sont accompagnés d'algorithmes pouvant être utilisés pour l'entraînement. On commence ce document en présentant BanditSum, une approche tirée de la litérature et qui voit la génération des résumés d'un ensemble de documents comme un problème de bandit contextuel. Ensuite, on introduit CombiSum, un nouvel algorithme qui formule la génération du résumé d'un seul document comme un bandit combinatoire. En exploitant la formule combinatoire, CombiSum réussit à incorporer la notion du potentiel extractif de chaque phrase à son entraînement. Enfin, on propose LinCombiSum, la variante linéaire de CombiSum qui exploite les similarités entre les phrases d'un document et emploie plutôt la formulation en bandit linéaire combinatoire. / This thesis discusses the use of bandit methods to solve the problem of training extractive abstract generation models. The extractive models, which build summaries by selecting sentences from an original document, are difficult to train because the target summary of a document is usually not built in an extractive way. It is for this purpose that we propose to see the production of extractive summaries as different bandit problems, for which there exist algorithms that can be leveraged for training summarization models.In this paper, BanditSum is first presented, an approach drawn from the literature that sees the generation of the summaries of a set of documents as a contextual bandit problem. Next,we introduce CombiSum, a new algorithm which formulates the generation of the summary of a single document as a combinatorial bandit. By exploiting the combinatorial formulation,CombiSum manages to incorporate the notion of the extractive potential of each sentence of a document in its training. Finally, we propose LinCombiSum, the linear variant of Com-biSum which exploits the similarities between sentences in a document and uses the linear combinatorial bandit formulation instead

Dans le domaine de l'apprentissage par renforcement, la planification dans le cas de systèmes déterministes consiste à effectuer une recherche avant grâce à un modèle génératif du système considéré et ce pour trouver l'action à appliquer dans son état courant. Dans notre cas, cette recherche avant conduira à la construction d'un arbre des possibilités, sa racine correspondant à l'état courant du système. Dans le cas où les ressources computationnelles sont limitées et inconnues, il convient d'utiliser un algorithme cherchant à minimiser son regret. Autrement dit, un algorithme retournant une action à effectuer qui soit la plus proche possible de l'optimale en terme de qualité et en fonction des ressources computationnelles. Nous présentons l'algorithme de planification optimiste dans le cas où l'espace d'action est discret. Nous prouvons une borne inférieure et supérieure sur son regret dans le pire des cas ainsi que dans une classe particulière de problèmes. Nous présentons ensuite deux autres algorithmes inspirés de l'approche optimiste dans le cas où l'espace d'action est continu. / In the field of reinforcement learning, planning in the case of deterministic systems consists of doing a forward search using a generative model of the system so as to find the action to apply in its current state. In our case, the forward search leads us to build a look-ahead tree, its root being the current state of the system. If the computational resources are limited and unknown, we have to use an algorithm which tries to minimize its regret. In other words, an algorithm returning an action to apply which is as close as possible to the optimal one in term of quality and with respect to the computational resources used. We present the optimistic planing algorithm in the case of a discrete action space. We prove a lower and upper bound in the worst case and in a particular class of problems. Also we present two algorithms using the optimistic approach but in the case of a continuous action space.

L'apprentissage par renforcement est la réponse du domaine de l'apprentissage numérique au problème du contrôle optimal. Dans ce paradigme, un agent informatique apprend à contrôler un environnement en interagissant avec ce dernier. Il reçoit régulièrement une information locale de la qualité du contrôle effectué sous la forme d'une récompense numérique (ou signal de renforcement), et son objectif est de maximiser une fonction cumulante de ces récompenses sur le long terme, généralement modélisée par une fonction dite de valeur. Le choix des actions appliquées à l'environnement en fonction de sa configuration est appelé une politique, et la fonction de valeur quantifie donc la qualité de cette politique donc la qualité de cette politique. Ce parangon est très général, et permet de s'intéresser à un grand nombre d'applications, comme la gestion des flux de gaz dans un complexe sidérurgique, que nous abordons dans ce manuscrit. Cependant, sa mise en application pratique peut être difficile. Notamment, lorsque la description de l'environnement à contrôler est trop grande, une représentation exacte de la fonction de la valeur (ou de la politique) n'est pas possible. Dans ce cas se pose le problème de la généralisation (ou de l'approximation de fonction de valeur) : il faut d'une part concevoir des algorithmes dont la complexité algorithmique ne soit pas trop grande, et d'autre part être capable d'interférer le comportement à suivre pour une configuration de l'environnement inconnue lorsque des situations proches ont déjà été expérimentées. C'est le problème principal que nous traitons dans ce manuscrit, en proposant une approche inspirée du filtrage de Kalman / Reinforcement learning is the response of machine learning to the problem of optimal control. In this paradigm, an agent learns do control an environment by interacting with it. It receives evenly a numeric reward (or reinforcement signal), which is a local information about the quality of the control. The agent objective is to maximize a cumulative function of these rewards, generally modelled as a so-called value function. A policy specifies the action to be chosen in a particular configuration of the environment to be controlled, and thus the value function quantifies the quality of yhis policy. This paragon is very general, and it allows taking into account many applications. In this manuscript, we apply it to a gas flow management problem in the iron and steel industry. However, its application can be quite difficult. Notably, if the environment description is too large, an exact representation of the value function (or of the policy) is not possible. This problem is known as generalization (or value function approximation) : on the one hand, one has to design algorithms with low computational complexity, and on the other hand, one has to infer the behaviour the agent should have in an unknown configuration of the environment when close configurations have been experimented. This is the main problem we address in this manuscript, by introducing a family of algorithms inspired from Kalman filtering

Thèse (de maîtrise)--Université Laval, 2009. / Titre de l'écran-titre (visionné le 16 juin 2009). Bibliogr.

Malgré leurs excellentes performances, les exigences élevées des réseaux de neurones artificiels en terme de volume de données et de puissance de calcul limitent leur adoption dans plusieurs domaines. C'est pourquoi il reste important de développer de nouvelles architectures moins voraces. Ce mémoire cherche à produire une architecture plus flexible et moins vorace en s'appuyant sur la théorie de l'apprentissage par renforcement. En considérant le réseau comme un agent suivant une politique, on réalise que cette politique est beaucoup plus rigide que celle suivie habituellement par les agents d'apprentissage par renforcement. Nous posons l'hypothèse qu'une architecture capable de formuler une politique plus flexible pourrait atteindre des performances similaires tout en limitant son utilisation de ressources. L'architecture que nous proposons s'inspire de la recherche faite en prédiction de paramètres, particulièrement de l'architecture hypernetwork, que nous utilisons comme base de référence. Nos résultats montrent que l'apprentissage d'une politique dynamique aussi performante que les politiques statiques suivies par les réseaux conventionnels n'est pas une tâche triviale. Nos meilleurs résultats indiquent une diminution du nombre de paramètres de 33%, une diminution des calculs de 12% au prix d'une baisse de l'exactitude des prédictions de 2%. Malgré ces résultats, nous croyons que notre architecture est un point de départ pouvant être amélioré de plusieurs manières que nous explorons rapidement en conclusion. / Despite their excellent performances, artificial neural networks high demand of both data and computational power limit their adoption in many domains. Developing less demanding architecture thus remain an important endeavor. This thesis seeks to produce a more flexible and less resource-intensive architecture by using reinforcement learning theory. When considering a network as an agent instead of a function approximator, one realize that the implicit policy followed by popular feed forward networks is extremely simple. We hypothesize that an architecture able to learn a more flexible policy could reach similar performances while reducing its resource footprint. The architecture we propose is inspired by research done in weight prediction, particularly by the hypernetwork architecture, which we use as a baseline model.Our results show that learning a dynamic policy achieving similar results to the static policies of conventional networks is not a trivial task. Our proposed architecture succeeds in limiting its parameter space by 20%, but does so at the cost of a 24% computation increase and loss of5% accuracy. Despite those results, we believe that this architecture provides a baseline that can be improved in multiple ways that we describe in the conclusion.

Les récents progrès dans le domaine du traitement du langage ont apporté un intérêt significatif à la mise en oeuvre de systèmes de dialogue parlé. Ces derniers sont des interfaces utilisant le langage naturel comme medium d'interaction entre le système et l'utilisateur. Le module de gestion de dialogue choisit le moment auquel l'information qu'il choisit doit être échangée avec l'utilisateur. Ces dernières années, l'optimisation de dialogue parlé en utilisant l'apprentissage par renforcement est devenue la référence. Cependant, une grande partie des algorithmes utilisés nécessite une importante quantité de données pour être efficace. Pour gérer ce problème, des simulations d'utilisateurs ont été introduites. Cependant, ces modèles introduisent des erreurs. Par un choix judicieux d'algorithmes, la quantité de données d'entraînement peut être réduite et ainsi la modélisation de l'utilisateur évitée. Ces travaux concernent une partie des contributions présentées. L'autre partie des travaux consiste à proposer une modélisation à partir de données réelles des utilisateurs au moyen de l'apprentissage par renforcement inverse / Recent advancements in the area of spoken language processing and the wide acceptance of portable devices, have attracted signicant interest in spoken dialogue systems.These conversational systems are man-machine interfaces which use natural language (speech) as the medium of interaction.In order to conduct dialogues, computers must have the ability to decide when and what information has to be exchanged with the users. The dialogue management module is responsible to make these decisions so that the intended task (such as ticket booking or appointment scheduling) can be achieved.Thus learning a good strategy for dialogue management is a critical task.In recent years reinforcement learning-based dialogue management optimization has evolved to be the state-of-the-art. A majority of the algorithms used for this purpose needs vast amounts of training data.However, data generation in the dialogue domain is an expensive and time consuming process. In order to cope with this and also to evaluatethe learnt dialogue strategies, user modelling in dialogue systems was introduced. These models simulate real users in order to generate synthetic data.Being computational models, they introduce some degree of modelling errors. In spite of this, system designers are forced to employ user models due to the data requirement of conventional reinforcement learning algorithms can learn optimal dialogue strategies from limited amount of training data when compared to the conventional algorithms. As a consequence of this, user models are no longer required for the purpose of optimization, yet they continue to provide a fast and easy means for quantifying the quality of dialogue strategies. Since existing methods for user modelling are relatively less realistic compared to real user behaviors, the focus is shifted towards user modelling by means of inverse reinforcement learning. Using experimental results, the proposed method's ability to learn a computational models with real user like qualities is showcased as part of this work.

Au fil des dernières années les robots ont fait partie de notre quotidien. Même si nous ne les voyons pas, nous dépendons d'eux pour construire nos ordinateurs, téléphones mobiles, voitures, etcetera. Les robots sont utilisés aussi pour l'organisation des produits dans les usines. Un autre domaine de croissance est la robotique sociale. Nous pouvons voir des études tel que des robots d'aide aux enfants autistes. Il y a aussi des robots qui sont utilisés pour accueillir des personnes dans des hôtels ou dans centres commerciaux pour interagir avec les gens. Ainsi, le robot doit comprendre le comportement des personnes. Et, pour les robots mobiles, il faut savoir comment naviguer dans l'environnement humain. En ce qui concerne les environnements humains, ce travail explore la navigation acceptable socialement des robots en direction de personnes. Pour donner un exemple, quand un robot s'approche d'une personne, il ne doit pas traiter la personne comme un obstacle. Car si cette dernière est traitée comme un obstacle, le robot s'approcherait d'elle sans prendre en compte son espace personnel, ce qui la gênerait. Une personne est une entité qui doit être pris en compte sur la base des normes sociales que nous (en tant que personnes) utilisons tous les jours. Dans cette thèse, nous explorons comment un robot s'approche d'une personne. Celle-ci peut-être gênée si quelque chose ou quelqu'un envahit son espace personnel. La personne se sentira aussi menacée si elle est approchée par derrière. Ces normes sociales doivent être respectées par le robot. C'est pour cela que nous modélisons le comportement du robot à travers des algorithmes d'apprentissage. Nous faisons approcher (manuellement) un robot d'un personne plusieurs fois et le robot apprend à reproduire ce comportement. Un autre travail de cette thèse est la compréhension d'un groupe de personnes. Nous, en tant que humains, avons la capacité de le faire intuitivement. Toutefois, un robot nécessite impérativement un modèle mathématique. Enfin, nous abordons le sujet d'un robot qui s'approche d'un groupe de personnes. Nous utilisons des démonstrations pour faire apprendre le robot. Nous évaluons le bon déroulement du comportement du robot comme par exemple, en observant combien de fois le robot envahit l'espace personnel des personnes pendant la navigation. / In the past years, robots have been a part of our every day lives. Even when we do not see them, we depend on them to build our computers, mobile phones, cars and more. They are also been used for organizing stocks in warehouses. And, with the growth of autonomous cars, we see them driving autonomously on highways and cities. Another area of growth is social robotics. We can see a lot of studies such as robots helping children with autism. Other robots are being used to receive people in hotels or to interact with people in shopping centers. In the latter examples, robots need to understand people behavior. In addition, in the case of mobile robots, they need to know how to navigate in human environments. In the context of human environments, this thesis explores socially acceptable navigation of robots towards people. To give an example, when a robot approaches one person, the robot shall by no means treat people as an obstacle because the robot get really close to the human and interfere with her personal space. The human is an entity that needs to be considered based on social norms that we (humans) use on a daily basis. In a first time, we explore how a robot can approach one person. A person is an entity that can be bothered if someone or something approaches invading her personal space. The person also will feel distressed when she is approached from behind. These social norms have to be respected by the robot. For this reason, we decided to model the behavior of the robot through learning algorithms. We manually approach a robot to a person several times and the robot learns how to reproduce this behavior. In a second time, we present how a robot can understand what is a group of people. We, humans, have the ability to do this intuitively. However, for a robot, a mathematical model is essential. Lastly, we address how a robot can approach a group of people. We use exemplary demonstrations to teach this behavior to the robot. We evaluate then the robot's movements by for example, observing if the robot invades people's personal space during the trajectory.