Auswahl der wissenschaftlichen Literatur zum Thema „Apprentissage par reinforcement“

International audience Reinforcement learning algorithms have succeeded over the years in achieving impressive results in a variety of fields. However, these algorithms suffer from certain weaknesses highlighted by Refael Vivanti and al. that may explain the regression of even well-trained agents in certain environments : the difference in variance on rewards between areas of the environment. This difference in variance leads to two problems : Boring Area Trap and Manipulative consultant. We note that the Adaptive Symmetric Reward Noising (ASRN) algorithm proposed by Refael Vivanti and al. has limitations for environments with the following characteristics : long game times and multiple boring area environments. To overcome these problems, we propose three algorithms derived from the ASRN algorithm called Rebooted Adaptive Symmetric Reward Noising (RASRN) : Continuous ε decay RASRN, Full RASRN and Stepwise α decay RASRN. Thanks to two series of experiments carried out on the k-armed bandit problem, we show that our algorithms can better correct the Boring Area Trap problem. Les algorithmes d'apprentissage par renforcement ont réussi au fil des années à obtenir des résultats impressionnants dans divers domaines. Cependant, ces algorithmes souffrent de certaines faiblesses mises en évidence par Refael Vivanti et al. qui peuvent expliquer la régression des agents même bien entraînés dans certains environnements : la différence de variance sur les récompenses entre les zones de l'environnement. Cette différence de variance conduit à deux problèmes : le Piège de la Zone Ennuyeuse (Boring Area Trap) et le Consultant Manipulateur. Nous observons que l'algorithme Adaptive Symmetric Reward Noising (ASRN) proposé par Refael Vivanti et al. présente des limites pour des environnements ayant les caractéristiques suivantes : longues durées de jeu et environnement à zones ennuyeuses multiples. Pour pallier ces problèmes, nous proposons trois algorithmes dérivés de l'algorithme ASRN nommés Rebooted Adaptive Symmetric Reward Noi-sing (RASRN) : Continuous ε decay RASRN, Full RASRN et Stepwise α decay RASRN. Grâce à deux séries d'expérimentations menées sur le problème du bandit à k bras, nous montrons que ces algorithmes permettent de mieux corriger le problème du piège de la zone ennuyeuse.

Les systèmes d’intelligence artificielle les plus puissants utilisent désormais des modèles statistiques. Afin de construire des modèles efficaces, ces systèmes doivent collecter une quantité substantielle de données issues de l’environnement. Les assistants personnels, maisons connectées, serveurs vocaux et autres systèmes de dialogue ne font pas exception. Ces systèmes ont pour vocation d’interagir avec des humains, et pour cela, leurs données d’apprentissage se doivent d’être collectées avec ces mêmes humains. Parce que le nombre d’interactions avec une seule personne est assez faible, l’approche usuelle pour augmenter le jeu de données consiste à agréger les données de tous les utilisateurs.Une des limitations de cette approche vient du fait que, par construction, les modèles entraînés ainsi ne sont efficaces qu’avec un humain "moyen" et n’incluent pas de système d’adaptation ; cette faiblesse entraîne la restriction du service à certains groupes de personnes; Par conséquent, cela réduit l’ensemble des utilisateurs et provoque des problèmes d’inclusion. La présente thèse propose des solutions impliquant la construction de systèmes de dialogue combinant l’apprentissage par transfert et l’apprentissage parrenforcement. La thèse explore deux pistes de recherche : La première consiste à inclure un mécanisme d’adaptation dès les premières interactions avec un nouvel utilisateur. Pour ce faire, nous utilisons la connaissance accumulée avec des utilisateurs déjà connus du système. La question sous-jacente est la suivante : comment gérer l’évolution du système suite à une croissance interrompue d’utilisateurs et donc de connaissance? La première approche implique le clustering des systèmes de dialogue (chacun étant spécialisé pour un utilisateur) en fonction de leurs stratégies. Nous démontrons que la méthode améliore la qualité des dialogues en interagissant avec des modèles à base de règles et des modèles d’humains. La seconde approche propose d’inclure un mécanisme d’apprentissage par transfert dans l’exécution d’un algorithme d’apprentissage profond par renforcement, Deep Q-learning. La seconde piste avance l’idée selon laquelle les premières interactions avec un nouvel utilisateur devraient être gérées par un système de dialogue sécurisé et précautionneux avant d’utiliser un système de dialogue spécialisé. L’approche se divise en deux étapes. La première étape consiste à apprendre une stratégie sécurisée avec de l’apprentissage par renforcement. À cet effet, nous proposons un nouveau framework d’apprentissage par renforcement sous contrainte en états continus ainsi que des algorithmes les solutionnant. En particulier, nous validons, en termes de sécurité et d’efficacité, une extension de Fitted-Q pour les deux applications sous contraintes : les systèmes de dialogue et la conduite autonome. La deuxième étape implique l’utilisation de ces stratégies sécurisées lors des premières interactions avec un nouvel utilisateur ; cette méthode est une extension de l’algorithme classique d’exploration, ε-greedy
The most powerful artificial intelligence systems are now based on learned statistical models. In order to build efficient models, these systems must collect a huge amount of data on their environment. Personal assistants, smart-homes, voice-servers and other dialogue applications are no exceptions to this statement. A specificity of those systems is that they are designed to interact with humans, and as a consequence, their training data has to be collected from interactions with these humans. As the number of interactions with a single person is often too scarce to train a proper model, the usual approach to maximise the amount of data consists in mixing data collected with different users into a single corpus. However, one limitation of this approach is that, by construction, the trained models are only efficient with an "average" human and do not include any sort of adaptation; this lack of adaptation makes the service unusable for some specific group of persons and leads to a restricted customers base and inclusiveness problems. This thesis proposes solutions to construct Dialogue Systems that are robust to this problem by combining Transfer Learning and Reinforcement Learning. It explores two main ideas: The first idea of this thesis consists in incorporating adaptation in the very first dialogues with a new user. To that extend, we use the knowledge gathered with previous users. But how to scale such systems with a growing database of user interactions? The first proposed approach involves clustering of Dialogue Systems (tailored for their respective user) based on their behaviours. We demonstrated through handcrafted and real user-models experiments how this method improves the dialogue quality for new and unknown users. The second approach extends the Deep Q-learning algorithm with a continuous transfer process.The second idea states that before using a dedicated Dialogue System, the first interactions with a user should be handled carefully by a safe Dialogue System common to all users. The underlying approach is divided in two steps. The first step consists in learning a safe strategy through Reinforcement Learning. To that extent, we introduced a budgeted Reinforcement Learning framework for continuous state space and the underlying extensions of classic Reinforcement Learning algorithms. In particular, the safe version of the Fitted-Q algorithm has been validated, in term of safety and efficiency, on a dialogue system tasks and an autonomous driving problem. The second step consists in using those safe strategies when facing new users; this method is an extension of the classic ε-greedy algorithm

Les contributions de la thèse sont centrées sur la prise de décisions séquentielles et plus spécialement sur l'Apprentissage par Renforcement (AR). Prenant sa source de l'apprentissage statistique au même titre que l'apprentissage supervisé et non-supervisé, l'AR a gagné en popularité ces deux dernières décennies en raisons de percées aussi bien applicatives que théoriques. L'AR suppose que l'agent (apprenant) ainsi que son environnement suivent un processus de décision stochastique Markovien sur un espace d'états et d'actions. Le processus est dit de décision parce que l'agent est appelé à choisir à chaque pas de temps du processus l'action à prendre. Il est dit stochastique parce que le choix d'une action donnée en un état donné n'implique pas le passage systématique à un état particulier mais définit plutôt une distribution sur l'espace d'états. Il est dit Markovien parce que cette distribution ne dépend que de l'état et de l'action courante. En conséquence d'un choix d'action, l'agent reçoit une récompense. Le but de l'AR est alors de résoudre le problème d'optimisation retournant le comportement qui assure à l'agent une récompense maximale tout au long de son interaction avec l'environnement. D'un point de vue pratique, un large éventail de problèmes peuvent être transformés en un problème d'AR, du Backgammon (cf. TD-Gammon, l'une des premières grandes réussites de l'AR et de l'apprentissage statistique en général, donnant lieu à un joueur expert de classe internationale) à des problèmes de décision dans le monde industriel ou médical. Seulement, le problème d'optimisation résolu par l'AR dépend de la définition préalable d'une fonction de récompense adéquate nécessitant une expertise certaine du domaine d'intérêt mais aussi du fonctionnement interne des algorithmes d'AR. En ce sens, la première contribution de la thèse a été de proposer un nouveau cadre d'apprentissage, allégeant les prérequis exigés à l'utilisateur. Ainsi, ce dernier n'a plus besoin de connaître la solution exacte du problème mais seulement de pouvoir désigner entre deux comportements, celui qui s'approche le plus de la solution. L'apprentissage se déroule en interaction entre l'utilisateur et l'agent. Cette interaction s'articule autour des trois points suivants : i) L'agent exhibe un nouveau comportement ii) l'expert le compare au meilleur comportement jusqu'à présent iii) l'agent utilise ce retour pour mettre à jour son modèle des préférences puis choisit le prochain comportement à démontrer. Afin de réduire le nombre d'interactions nécessaires entre l'utilisateur et l'agent pour que ce dernier trouve le comportement optimal, la seconde contribution de la thèse a été de définir un critère théoriquement justifié faisant le compromis entre les désirs parfois contradictoires de prendre en compte les préférences de l'utilisateur tout en exhibant des comportements suffisamment différents de ceux déjà proposés. La dernière contribution de la thèse est d'assurer la robustesse de l'algorithme face aux éventuelles erreurs d'appréciation de l'utilisateur. Ce qui arrive souvent en pratique, spécialement au début de l'interaction, quand tous les comportements proposés par l'agent sont loin de la solution attendue
The thesis contributions resolves around sequential decision taking and more precisely Reinforcement Learning (RL). Taking its root in Machine Learning in the same way as supervised and unsupervised learning, RL quickly grow in popularity within the last two decades due to a handful of achievements on both the theoretical and applicative front. RL supposes that the learning agent and its environment follow a stochastic Markovian decision process over a state and action space. The process is said of decision as the agent is asked to choose at each time step an action to take. It is said stochastic as the effect of selecting a given action in a given state does not systematically yield the same state but rather defines a distribution over the state space. It is said to be Markovian as this distribution only depends on the current state-action pair. Consequently to the choice of an action, the agent receives a reward. The RL goal is then to solve the underlying optimization problem of finding the behaviour that maximizes the sum of rewards all along the interaction of the agent with its environment. From an applicative point of view, a large spectrum of problems can be cast onto an RL one, from Backgammon (TD-Gammon, was one of Machine Learning first success giving rise to a world class player of advanced level) to decision problems in the industrial and medical world. However, the optimization problem solved by RL depends on the prevous definition of a reward function that requires a certain level of domain expertise and also knowledge of the internal quirks of RL algorithms. As such, the first contribution of the thesis was to propose a learning framework that lightens the requirements made to the user. The latter does not need anymore to know the exact solution of the problem but to only be able to choose between two behaviours exhibited by the agent, the one that matches more closely the solution. Learning is interactive between the agent and the user and resolves around the three main following points: i) The agent demonstrates a behaviour ii) The user compares it w.r.t. to the current best one iii) The agent uses this feedback to update its preference model of the user and uses it to find the next behaviour to demonstrate. To reduce the number of required interactions before finding the optimal behaviour, the second contribution of the thesis was to define a theoretically sound criterion making the trade-off between the sometimes contradicting desires of complying with the user's preferences and demonstrating sufficiently different behaviours. The last contribution was to ensure the robustness of the algorithm w.r.t. the feedback errors that the user might make. Which happens more often than not in practice, especially at the initial phase of the interaction, when all the behaviours are far from the expected solution

L'apprentissage par renforcement est aujourd'hui plus populaire que jamais, mais plusieurs compétences simples lui restent hors de portée: manipulation d'objets, contrôle sensorimoteur, interaction naturelle avec d'autres agents. Une approche possible pour aborder ces défis consiste à s'inspirer du développement humain, voire de tenter de le reproduire. Dans cette thèse, nous étudions l'intersection de deux sujets cruciaux en sciences du développement, et leur application à l'apprentissage par renforcement dans le but d'aborder ces défis: l'apprentissage social et la motivation intrinsèque. L'interaction et la motivation intrinsèque ont déjà été étudiées, séparément, en combinaison avec l'apprentissage par renforcement, mais avec l'objectif d'améliorer les performances d'agents existants plutôt que d'apprendre de manière développementale. Nous concentrons donc à l'inverse notre étude sur l'aspect développemental de ces deux sujets. Nos travaux de thèse abordent en particulier l'auto-organisation de l'apprentissage en trajectoires développementale par recherche intrinsèquement motivée du progrès d'apprentissage, et l'interaction de cette organisation avec l'apprentissage dirigé vers des buts et l'apprentissage par imitation. Nous montrons que ces différents mécanismes, lorsqu'ils sont mis en place dans des environnements ouverts sans tâche prédéfinie, peuvent interagir pour produire des comportements d'apprentissage satisfaisants d'un point de vue développemental, et plus riches que ceux produits par chaque mécanisme séparément: génération automatique de curriculum, imitation sélective, suivi non-supervisé de démonstrations
Reinforcement learning (RL) is today more popular than ever, but certain basic skills are still out of reach of this paradigm: object manipulation, sensorimotor control, natural interaction with other agents. A possible approach to address these challenges consist in taking inspiration from human development, or even trying to reproduce it. In this thesis, we study the intersection of two crucial topics in developmental sciences and how to apply them to RL in order to tackle the aforementioned challenges: interactive learning and intrinsic motivation. Interactive learning and intrinsic motivation have already been studied, separately, in combination with RL, but in order to improve quantitatively existing agents performances, rather than to learn in a developmental fashion. We thus focus our efforts on the developmental aspect of these subjects. Our work touches the self-organisation of learning in developmental trajectories through an intrinsically motivated for learning progress, and the interaction of this organisation with goal-directed learning and imitation learning. We show that these mechanisms, when implemented in open-ended environments with no task predefined, can interact to produce learning behaviors that are sound from a developmental standpoint, and richer than those produced by each mechanism separately

Cette thèse développe et étudie certaines méthodes de principe pour l'apprentissage profond (DL) et l'apprentissage par renforcement (RL).Dans la partie II, nous étudions le DL selon le point de vue du “Minimum Description Length” principe, qui formalise le rasoir d'Occam, et postule qu'un bon modèle prédictif est un modèle capable de compresser sans perte les données (en prenant en compte le coût de la description du modèle lui-même). Les modèles de DL, par le nombre de paramètres à encoder, semblent aller à l'encontre de ce principe. Nous démontrons expérimentalement la capacité de compression des modèles de DL, même en tenant compte de l'encodage des paramètres, montrant ainsi que ces approches sont bien fondées du point de vue de la théorie de l'information.Dans la partie III, nous étudions deux limitations des approches standard de DL et RL, et nous développons des méthodes mathématiquement bien fondées pour les dépasser;La première concerne l'optimisation des modèles de DL avec SGD, et le coût important du choix d'un bon taux d'apprentissage. Nous introduisons la méthode Alrao (All learning rates at once) : chaque unité (ou neurone) du réseau obtient son propre taux d'apprentissage tiré aléatoirement à partir d'une distribution couvrant de nombreux ordres de grandeur. De façon surprenante, Alrao obtient des résultats proches de ceux de SGD avec un taux d'apprentissage optimal, et ce pour diverses architectures et problèmes.Le second aborde les environnements de RL en temps quasi continu (robotique, contrôle, jeux vidéos,…) : nous montrons que la discrétisation temporelle (nombre d'actions par seconde) est un facteur critique, et empiriquement que les approches basées sur Q-learning ne peuvent plus apprendre quand le nombre d'action par seconde devient grand. Formellement, nous prouvons que le Q-learning n'existe pas en temps continu. Nous détaillons une méthode mathématiquement bien fondée pour construire un algorithme RL invariant à la discrétisation temporelle, et confirmons cette approche empiriquement.La partie principale de cette thèse, (Partie IV), étudie l'opérateur des états successeurs en RL, et comment il peut améliorer l'efficacité de l'apprentissage de la fonction valeur.Dans un environnement où la récompense n'est reçue que très rarement, l'apprentissage de la fonction valeur est un problème difficile. L'opérateur des états successeurs est un objet mathématique qui exprime les fonctions valeur de toutes les fonctions de récompense possibles pour une politique fixe. L'apprentissage de cet opérateur peut se faire sans signaux de récompense et peut extraire des informations de chaque transition observée, illustrant une approche de RL non supervisé.Nous proposons un traitement formel de cet objet dans des espaces finis et continus avec des approximateurs de fonctions, comme les réseaux de neurones. Nous présentons plusieurs algorithmes d'apprentissage et les résultats associés. De même que la fonction valeur, l'opérateur des états successeurs satisfait une équation de Bellman. De plus, il satisfait également deux autres équations à point fixe : une équation de Bellman en arrière et une équation de Bellman-Newton, exprimant la compositionalité des chemins dans le processus de Markov. Ces nouvelles relations nous permettent de généraliser à partir des trajectoires observées de plusieurs façons, ce qui peut conduire à une plus grande efficacité en pratique.Enfin, (partie V), l'étude de l'opérateur des états successeurs et de ses algorithmes nous permet de dériver des méthodes non biaisées dans le cadre d'un RL à buts multiples. Nous montrons en outre que l'algorithme Hindsight Experience Replay, populaire dans ce cadre mais connu pour être biaisé, est en fait non biaisé dans la classe importante des environnements déterministes
This thesis develops and studies some principled methods for Deep Learning (DL) and deep Reinforcement Learning (RL).In Part II, we study the efficiency of DL models from the context of the Minimum Description Length principle, which formalize Occam's razor, and holds that a good model of data is a model that is good at losslessly compressing the data, including the cost of describing the model itself. Deep neural networks might seem to go against this principle given the large number of parameters to be encoded. Surprisingly, we demonstrate experimentally the ability of deep neural networks to compress the training data even when accounting for parameter encoding, hence showing that DL approaches are well principled from this information theory viewpoint.In Part III, we tackle two limitations of standard approaches in DL and RL, and develop principled methods, improving robustness empirically.The first one concerns optimisation of deep learning models with SGD, and the cost of finding the optimal learning rate, which prevents using a new method out of the box without hyperparameter tuning. When design a principled optimisation method for DL, 'All Learning Rates At Once' : each unit or feature in the network gets its own learning rate sampled from a random distribution spanning several orders of magnitude. Perhaps surprisingly, Alrao performs close to SGD with an optimally tuned learning rate, for various architectures and problems.The second one tackles near continuous-time RL environments (such as robotics, control environment, …) : we show that time discretization (number of action per second) in as a critical factor, and that empirically, Q-learning-based approaches collapse with small time steps. Formally, we prove that Q-learning does not exist in continuous time. We detail a principled way to build an off-policy RL algorithm that yields similar performances over a wide range of time discretizations, and confirm this robustness empirically.The main part of this thesis, (Part IV), studies the Successor States Operator in RL, and how it can improve sample efficiency of policy evaluation. In an environment with a very sparse reward, learning the value function is a hard problem. At the beginning of training, no learning will occur until a reward is observed. This highlight the fact that not all the observed information is used. Leveraging this information might lead to better sample efficiency. The Successor State Operator is an object that expresses the value functions of all possible reward functions for a given, fixed policy. Learning the successor state operator can be done without reward signals, and can extract information from every observed transition, illustrating an unsupervised reinforcement learning approach.We offer a formal treatment of these objects in both finite and continuous spaces with function approximators. We present several learning algorithms and associated results. Similarly to the value function, the successor states operator satisfies a Bellman equation. Additionally, it also satisfies two other fixed point equations: a backward Bellman equation and a Bellman-Newton equation, expressing path compositionality in the Markov process. These new relation allow us to generalize from observed trajectories in several ways, potentially leading to more sample efficiency. Every of these equations lead to corresponding algorithms for any function approximators such as neural networks.Finally, (Part V) the study of the successor states operator and its algorithms allow us to derive unbiased methods in the setting of multi-goal RL, dealing with the issue of extremely sparse rewards. We additionally show that the popular Hindsight Experience Replay algorithm, known to be biased, is actually unbiased in the large class of deterministic environments

Les robots opèrent dans le monde réel, dans lequel essayer quelque chose prend beaucoup de temps. Pourtant, les methodes d’apprentissage par renforcement actuels (par exemple, deep reinforcement learning) nécessitent de longues périodes d’interaction pour trouver des politiques efficaces. Dans cette thèse, nous avons exploré des algorithmes qui abordent le défi de l’apprentissage par essai-erreur en quelques minutes sur des robots physiques. Nous appelons ce défi “Apprentissage par renforcement micro-data”. Dans la première contribution, nous avons proposé un nouvel algorithme d’apprentissage appelé “Reset-free Trial-and-Error” qui permet aux robots complexes de s’adapter rapidement dans des circonstances inconnues (par exemple, des dommages) tout en accomplissant leurs tâches; en particulier, un robot hexapode endommagé a retrouvé la plupart de ses capacités de marche dans un environnement avec des obstacles, et sans aucune intervention humaine. Dans la deuxième contribution, nous avons proposé un nouvel algorithme de recherche de politique “basé modèle”, appelé Black-DROPS, qui: (1) n’impose aucune contrainte à la fonction de récompense ou à la politique, (2) est aussi efficace que les algorithmes de l’état de l’art, et (3) est aussi rapide que les approches analytiques lorsque plusieurs processeurs sont disponibles. Nous avons aussi proposé Multi-DEX, une extension qui s’inspire de l’algorithme “Novelty Search” et permet de résoudre plusieurs scénarios où les récompenses sont rares. Dans la troisième contribution, nous avons introduit une nouvelle procédure d’apprentissage du modèle dans Black-DROPS qui exploite un simulateur paramétré pour permettre d’apprendre des politiques sur des systèmes avec des espaces d’état de grande taille; par exemple, cette extension a trouvé des politiques performantes pour un robot hexapode (espace d’état 48D et d’action 18D) en moins d’une minute d’interaction. Enfin, nous avons exploré comment intégrer les contraintes de sécurité, améliorer la robustesse et tirer parti des multiple a priori en optimisation bayésienne. L'objectif de la thèse était de concevoir des méthodes qui fonctionnent sur des robots physiques (pas seulement en simulation). Par conséquent, tous nos approches ont été évaluées sur au moins un robot physique. Dans l’ensemble, nous proposons des méthodes qui permettre aux robots d’être plus autonomes et de pouvoir apprendre en poignée d’essais
Robots have to face the real world, in which trying something might take seconds, hours, or even days. Unfortunately, the current state-of-the-art reinforcement learning algorithms (e.g., deep reinforcement learning) require big interaction times to find effective policies. In this thesis, we explored approaches that tackle the challenge of learning by trial-and-error in a few minutes on physical robots. We call this challenge “micro-data reinforcement learning”. In our first contribution, we introduced a novel learning algorithm called “Reset-free Trial-and-Error” that allows complex robots to quickly recover from unknown circumstances (e.g., damages or different terrain) while completing their tasks and taking the environment into account; in particular, a physical damaged hexapod robot recovered most of its locomotion abilities in an environment with obstacles, and without any human intervention. In our second contribution, we introduced a novel model-based reinforcement learning algorithm, called Black-DROPS that: (1) does not impose any constraint on the reward function or the policy (they are treated as black-boxes), (2) is as data-efficient as the state-of-the-art algorithm for data-efficient RL in robotics, and (3) is as fast (or faster) than analytical approaches when several cores are available. We additionally proposed Multi-DEX, a model-based policy search approach, that takes inspiration from novelty-based ideas and effectively solved several sparse reward scenarios. In our third contribution, we introduced a new model learning procedure in Black-DROPS (we call it GP-MI) that leverages parameterized black-box priors to scale up to high-dimensional systems; for instance, it found high-performing walking policies for a physical damaged hexapod robot (48D state and 18D action space) in less than 1 minute of interaction time. Finally, in the last part of the thesis, we explored a few ideas on how to incorporate safety constraints, robustness and leverage multiple priors in Bayesian optimization in order to tackle the micro-data reinforcement learning challenge. Throughout this thesis, our goal was to design algorithms that work on physical robots, and not only in simulation. Consequently, all the proposed approaches have been evaluated on at least one physical robot. Overall, this thesis aimed at providing methods and algorithms that will allow physical robots to be more autonomous and be able to learn in a handful of trials

Les travaux de cette thèse se situent à l’interface de deux thématiques de l'apprentissage automatique : l’apprentissage de préférences d'une part, et l’apprentissage par renforcement de l'autre. La première consiste à percoler différents classements d’un même ensemble d’objets afin d’en extraire un ordre général, la seconde à identifier séquentiellement une stratégie optimale en observant des récompenses sanctionnant chaque action essayée. La structure de la thèse suit ce découpage thématique. En première partie, le paradigme de minimisation du risque empirique est utilisé à des fins d'ordonnancement. Partant du problème d’apprentissage supervisé de règles d’ordonnancement à partir de données étiquetées de façon binaire, une extension est proposée au cas où les étiquettes prennent des valeurs continues. Les critères de performance usuels dans le cas binaire, à savoir la courbe caractéristique de l’opérateur de réception (COR) et l’aire sous la courbe COR (ASC), sont étendus au cas continu : les métriques COR intégrée (CORI) et ASC intégrée (ASCI) sont introduites à cet effet. Le second problème d'ordonnancement étudié est celui de l'agrégation de classements à travers l'identification du consensus de Kemeny. En particulier, une relaxation au problème plus général de la réduction de la dimensionnalité dans l'espace des distributions sur le groupe symétrique est formulée à l'aide d'outils mathématiques empruntés à la théorie du transport optimal. La seconde partie de cette thèse s'intéresse à l'apprentissage par renforcement. Des problèmes de bandit manchot sont analysés dans des contextes où la performance moyenne n'est pas pertinente et où la gestion du risque prévaut. Enfin, le problème plus général de l'apprentissage par renforcement distributionnel, dans lequel le décideur cherche à connaître l'entière distribution de sa performance et non pas uniquement sa valeur moyenne, est considéré. De nouveaux opérateurs de programmation dynamique ainsi que leurs pendants atomiques mènent à de nouveaux algorithmes stochastiques distributionnels
This thesis divides into two parts: the first part is on ranking and the second on risk-aware reinforcement learning. While binary classification is the flagship application of empirical risk minimization (ERM), the main paradigm of machine learning, more challenging problems such as bipartite ranking can also be expressed through that setup. In bipartite ranking, the goal is to order, by means of scoring methods, all the elements of some feature space based on a training dataset composed of feature vectors with their binary labels. This thesis extends this setting to the continuous ranking problem, a variant where the labels are taking continuous values instead of being simply binary. The analysis of ranking data, initiated in the 18th century in the context of elections, has led to another ranking problem using ERM, namely ranking aggregation and more precisely the Kemeny's consensus approach. From a training dataset made of ranking data, such as permutations or pairwise comparisons, the goal is to find the single "median permutation" that best corresponds to a consensus order. We present a less drastic dimensionality reduction approach where a distribution on rankings is approximated by a simpler distribution, which is not necessarily reduced to a Dirac mass as in ranking aggregation.For that purpose, we rely on mathematical tools from the theory of optimal transport such as Wasserstein metrics. The second part of this thesis focuses on risk-aware versions of the stochastic multi-armed bandit problem and of reinforcement learning (RL), where an agent is interacting with a dynamic environment by taking actions and receiving rewards, the objective being to maximize the total payoff. In particular, a novel atomic distributional RL approach is provided: the distribution of the total payoff is approximated by particles that correspond to trimmed means

L'apprentissage par renforcement permet à un agent d'apprendre un comportement qui n'a jamais été préalablement défini par l'homme. L'agent découvre l'environnement et les différentes conséquences de ses actions à travers des interactions avec celui-ci : il apprend de sa propre expérience, sans avoir de connaissances préétablies des buts ni des effets de ses actions. Cette thèse s'intéresse à la façon dont l'apprentissage profond peut aider l'apprentissage par renforcement à gérer des espaces continus et des environnements ayant de nombreux degrés de liberté dans l'optique de résoudre des problèmes plus proches de la réalité. En effet, les réseaux de neurones ont une bonne capacité de mise à l'échelle et un large pouvoir de représentation. Ils rendent possible l'approximation de fonctions sur un espace continu et permettent de s'inscrire dans une approche développementale nécessitant peu de connaissances a priori sur le domaine. Nous cherchons comment réduire l'expérience nécessaire à l'agent pour atteindre un comportement acceptable. Pour ce faire, nous avons proposé le cadre Neural Fitted Actor-Critic qui définit plusieurs algorithmes acteur-critique efficaces en données. Nous examinons par quels moyens l'agent peut exploiter pleinement les transitions générées par des comportements précédents en intégrant des données off-policy dans le cadre proposé. Finalement, nous étudions de quelle manière l'agent peut apprendre plus rapidement en tirant parti du développement de son corps, en particulier, en procédant par une augmentation progressive de la dimensionnalité de son espace sensorimoteur
Reinforcement learning allows an agent to learn a behavior that has never been previously defined by humans. The agent discovers the environment and the different consequences of its actions through its interaction: it learns from its own experience, without having pre-established knowledge of the goals or effects of its actions. This thesis tackles how deep learning can help reinforcement learning to handle continuous spaces and environments with many degrees of freedom in order to solve problems closer to reality. Indeed, neural networks have a good scalability and representativeness. They make possible to approximate functions on continuous spaces and allow a developmental approach, because they require little a priori knowledge on the domain. We seek to reduce the amount of necessary interaction of the agent to achieve acceptable behavior. To do so, we proposed the Neural Fitted Actor-Critic framework that defines several data efficient actor-critic algorithms. We examine how the agent can fully exploit the transitions generated by previous behaviors by integrating off-policy data into the proposed framework. Finally, we study how the agent can learn faster by taking advantage of the development of his body, in particular, by proceeding with a gradual increase in the dimensionality of its sensorimotor space

Ces travaux de thèse étudient en détail la problématique d'optimisation du trafic par le biais du contrôle des feux de signalisation d'un réseau routier. Cette optimisation passe par l'utilisation de techniques d'apprentissage par renforcement, branche du machine learning permettant à un agent de résoudre une tâche dans un environment en maximisant ses signaux de récompenses.Dans un premier temps, les champs respectifs du contrôle de feux et de l'apprentissage par renforcement sont présentés, permettant ensuite d'introduire le domaine du contrôle de feu par apprentissage par renforcement. Dans un second temps, nous définissons un modèle mathématique du trafic utilisant des notions de théorie des graphes, ainsi que le modèle d'apprentissage, le simulateur de trafic et la librairie d'apprentissage par renforcement spécialement définie pour nos expérimentations. Dans un troisième et dernier temps, ces définitions nous permettent de construire une méthode d'optimisation du trafic performante.Nous étudions premièrement différentes méthodes d'apprentissage par renforcement sur une intersection isolée. Plusieurs grandes familles d'algorithmes (Q-learning, LRP, acteur-critique) sont comparés à des méthodes deterministes. Nous introduisons ensuite des méthodes d'approximation par réseau de neurones profonds, permettant d'augmenter sensiblement la performance de ces méthodes sur une intersection seule. Ces expérimentations nous permettent alors d'isoler le double deep Q-learning (DDQN) comme la méthode la plus adaptée pour le contrôle de feux.Sur cette base, nous introduisons ensuite le concept de coordination dans un système multi-agents d'apprentissage par renforcement (MARL). Là encore, plusieurs modes de coordination sont comparées à la méthode isolée définie précédemment. Plus particulièrement, nous définissons une nouvelle méthode, DEC-DQN, qui permet à plusieurs agents d'une POMDP de communiquer afin de mieux optimiser le trafic routier. DEC-DQN utilise un réseau de neurone commun à tous les agents du système, ce qui leur permet d'apprendre eux-même la meilleure façon de communiquer. Afin de correctement récompenser les actions de communication de chaque agent, qui sont distinctes de leurs actions d'optimisation du trafic par le contrôle de feux, DEC-DQN définit une fonction de récompense qui permet à chaque agent d'estimer l'effet de son action de communication sur les agents voisins. Cette estimation se fait directement à l'aide des réseaux de neurones servant au choix d'actions d'optimisation des intersections voisines.Cette nouvelle méthode de coordination est finalement comparée à d'autres méthodes de coordination phares de la litérature. La méthode DEC-DQN permet un apprentissage accéleré du routage de trafic par les agents, tout en montrant des performances et stabilité supérieures aux autres méthodes testées
This thesis studies the problem of traffic optimization through traffic light signals on road networks. Traffic optimization is achieved in our case through the use of reinforcement learning, a branch of machine learning in which an agent solves a given task in an environment by maximizing its reward signals.First, we present the fields of traffic signal control (TSC) and reinforcement learning (RL) separately, before presenting how the latter is applied on the former (RL-TSC). Then, we define a mathematical model of traffic based on graph theory, before introducing the reinforcement learning model, traffic simulator and deep reinforcement learning library created for our research work.Finally, these definitions allow us to build an efficient traffic signal control method based on reinforcement learning.We first study multiple classical reinforcement learning techniques on an isolated traffic intersection. Multiple classes of RL algorithms are compared (e.g. Q-learning, LRP, actor-critic) to deterministic TSC methods used as a baseline. We then introduce function approximation methods using deep neural networks, allowing for significant performance improvement on isolated intersections. These experiments allow us to single out dueling deep Q-learning as the best isolated RL-TSC method for out model.On this basis, we introduce the concept of agent coordination in multi-agent reinforcement learning systems (MARL). We compare multiple modes of coordinaiton to the isolated baseline that we previously defined. These experiments allow us to define the DEC-DQN coordination method, which allows for multiple agents of a POMDP to communicate in order to better optimize traffic. DEC-DQN uses a deep neural network shared by all agents of the network, allowing them to learn a common communication protocol from scratch. In order to correctly reward communication actions, which are entirely distinct from traffic optimization actions taken by agents, DEC-DQN defines a special reward function allowing each agent to directly estimate the impact of its communications on neighboring agents of the network. Communicaiton action rewards are directly estimated on the traffic optimization neural networks of neighboring intersections.Finally, this novel cooridnation method is compared to other methods of the literature on a large-scale simulation. The DEC-DQN algorithm results in faster agent learning, as well as increased performance and stability thanks to agent coordination

Apprendre à atteindre des buts est une compétence à acquérir à grande pertinence pratique pour des agents intelligents. Par exemple, ceci englobe de nombreux problèmes de navigation (se diriger vers telle destination), de manipulation robotique (atteindre telle position du bras robotique) ou encore certains jeux (gagner en accomplissant tel objectif). En tant qu'être vivant interagissant avec le monde, je suis constamment motivé par l'atteinte de buts, qui varient en portée et difficulté.L'Apprentissage par Renforcement (AR) est un paradigme prometteur pour formaliser et apprendre des comportements d'atteinte de buts. Un but peut être modélisé comme une configuration spécifique d'états de l'environnement qui doit être atteinte par interaction séquentielle et exploration de l'environnement inconnu. Bien que divers algorithmes en AR dit "profond" aient été proposés pour ce modèle d'apprentissage conditionné par des états buts, les méthodes existantes manquent de compréhension rigoureuse, d'efficacité d'échantillonnage et de capacités polyvalentes. Il s'avère que l'analyse théorique de l'AR conditionné par des états buts demeurait très limitée, même dans le scénario basique d'un nombre fini d'états et d'actions.Premièrement, nous nous concentrons sur le scénario supervisé, où un état but qui doit être atteint en minimisant l'espérance des coûts cumulés est fourni dans la définition du problème. Après avoir formalisé le problème d'apprentissage incrémental (ou ``online'') de ce modèle souvent appelé Plus Court Chemin Stochastique, nous introduisons deux algorithmes au regret sous-linéaire (l'un est le premier disponible dans la littérature, l'autre est quasi-optimal).Au delà d'entraîner l'agent d'AR à résoudre une seule tâche, nous aspirons ensuite qu'il apprenne de manière autonome à résoudre une grande variété de tâches, dans l'absence de toute forme de supervision en matière de récompense. Dans ce scénario non-supervisé, nous préconisons que l'agent sélectionne lui-même et cherche à atteindre ses propres états buts. Nous dérivons des garanties non-asymptotiques de cette heuristique populaire dans plusieurs cadres, chacun avec son propre objectif d'exploration et ses propres difficultés techniques. En guise d'illustration, nous proposons une analyse rigoureuse du principe algorithmique de viser des états buts "incertains", que nous ancrons également dans le cadre de l'AR profond.L'objectif et les contributions de cette thèse sont d'améliorer notre compréhension formelle de l'exploration d'états buts pour l'AR, dans les scénarios supervisés et non-supervisés. Nous espérons qu'elle peut aider à suggérer de nouvelles directions de recherche pour améliorer l'efficacité d'échantillonnage et l'interprétabilité d'algorithmes d'AR basés sur la sélection et/ou l'atteinte d'états buts dans des applications pratiques
Learning to reach goals is a competence of high practical relevance to acquire for intelligent agents. For instance, this encompasses many navigation tasks ("go to target X"), robotic manipulation ("attain position Y of the robotic arm"), or game-playing scenarios ("win the game by fulfilling objective Z"). As a living being interacting with the world, I am constantly driven by goals to reach, varying in scope and difficulty.Reinforcement Learning (RL) holds the promise to frame and learn goal-oriented behavior. Goals can be modeled as specific configurations of the environment that must be attained via sequential interaction and exploration of the unknown environment. Although various deep RL algorithms have been proposed for goal-oriented RL, existing methods often lack principled understanding, sample efficiency and general-purpose effectiveness. In fact, very limited theoretical analysis of goal-oriented RL was available, even in the basic scenario of finitely many states and actions.We first focus on a supervised scenario of goal-oriented RL, where a goal state to be reached in minimum total expected cost is provided as part of the problem definition. After formalizing the online learning problem in this setting often known as Stochastic Shortest Path (SSP), we introduce two no-regret algorithms (one is the first available in the literature, the other attains nearly optimal guarantees).Beyond training our RL agent to solve only one task, we then aspire that it learns to autonomously solve a wide variety of tasks, in the absence of any reward supervision. In this challenging unsupervised RL scenario, we advocate to "Set Your Own Goals" (SYOG), which suggests the agent to learn the ability to intrinsically select and reach its own goal states. We derive finite-time guarantees of this popular heuristic in various settings, each with its specific learning objective and technical challenges. As an illustration, we propose a rigorous analysis of the algorithmic principle of targeting "uncertain" goals which we also anchor in deep RL.The main focus and contribution of this thesis are to instigate a principled analysis of goal-oriented exploration in RL, both in the supervised and unsupervised scenarios. We hope that it helps suggest promising research directions to improve the interpretability and sample efficiency of goal-oriented RL algorithms in practical applications

Le sentiment d’agentivité est défini comme le sentiment de contrôler nos actions, et à travers elles, les évènements du monde extérieur. Cet ensemble phénoménologique dépend de notre capacité d’apprendre les contingences entre nos actions et leurs résultats, et un algorithme classique pour modéliser cela vient du domaine de l’apprentissage par renforcement. Dans cette thèse, nous avons utilisé l’approche de modélisation cognitive pour étudier l’interaction entre agentivité et apprentissage par renforcement. Tout d’abord, les participants réalisant une tâche d’apprentissage par renforcement tendent à avoir plus d’agentivité. Cet effet est logique, étant donné que l’apprentissage par renforcement consiste à associer une action volontaire et sa conséquence. Mais nous avons aussi découvert que l’agentivité influence l’apprentissage de deux manières. Le mode par défaut pour apprendre des contingences action-conséquence est que nos actions ont toujours un pouvoir causal. De plus, simplement choisir une action change l’apprentissage de sa conséquence. En conclusion, l’agentivité et l’apprentissage par renforcement, deux piliers de la psychologie humaine, sont fortement liés. Contrairement à des ordinateurs, les humains veulent être en contrôle, et faire les bons choix, ce qui biaise notre aquisition d’information
Sense of agency or subjective control can be defined by the feeling that we control our actions, and through them effects in the outside world. This cluster of experiences depend on the ability to learn action-outcome contingencies and a more classical algorithm to model this originates in the field of human reinforcementlearning. In this PhD thesis, we used the cognitive modeling approach to investigate further the interaction between perceived control and reinforcement learning. First, we saw that participants undergoing a reinforcement-learning task experienced higher agency; this influence of reinforcement learning on agency comes as no surprise, because reinforcement learning relies on linking a voluntary action and its outcome. But our results also suggest that agency influences reinforcement learning in two ways. We found that people learn actionoutcome contingencies based on a default assumption: their actions make a difference to the world. Finally, we also found that the mere fact of choosing freely shapes the learning processes following that decision. Our general conclusion is that agency and reinforcement learning, two fundamental fields of human psychology, are deeply intertwined. Contrary to machines, humans do care about being in control, or about making the right choice, and this results in integrating information in a one-sided way