Les systèmes de dialogue homme machine actuellement utilisés dans l'industrie sont fortement limités par une forme de communication très rigide imposant à l'utilisateur de suivre la logique du concepteur du système. Cette limitation est en partie due à leur représentation de l'état de dialogue sous la forme de formulaires préétablis.Pour répondre à cette difficulté, nous proposons d'utiliser une représentation sémantique à structure plus riche et flexible visant à permettre à l'utilisateur de formuler librement sa demande.Une deuxième difficulté qui handicape grandement les systèmes de dialogue est le fort taux d'erreur du système de reconnaissance vocale. Afin de traiter ces erreurs de manière quantitative, la volonté de réaliser une planification de stratégie de dialogue en milieu incertain a conduit à utiliser des méthodes d'apprentissage par renforcement telles que les processus de décision de Markov partiellement observables (POMDP). Mais un inconvénient du paradigme POMDP est sa trop grande complexité algorithmique. Certaines propositions récentes permettent de réduire la complexité du modèle. Mais elles utilisent une représentation en formulaire et ne peuvent être appliqués directement à la représentation sémantique riche que nous proposons d'utiliser.Afin d'appliquer le modèle POMDP dans un système dont le modèle sémantique est complexe, nous proposons une nouvelle façon de contrôler sa complexité en introduisant un nouveau paradigme : le POMDP résumé à double suivi de la croyance. Dans notre proposition, le POMDP maitre, complexe, est transformé en un POMDP résumé, plus simple. Un premier suivi de croyance (belief update) est réalisé dans l'espace maitre (en intégrant des observations probabilistes sous forme de listes nbest). Et un second suivi de croyance est réalisé dans l'espace résumé, les stratégies obtenues sont ainsi optimisées sur un véritable POMDP.Nous proposons deux méthodes pour définir la projection du POMDP maitre en un POMDP résumé : par des règles manuelles et par regroupement automatique par k plus proches voisins. Pour cette dernière, nous proposons d'utiliser la distance d'édition entre graphes, que nous généralisons pour obtenir une distance entre listes nbest.En outre, le couplage entre un système résumé, reposant sur un modèle statistique par POMDP, et un système expert, reposant sur des règles ad hoc, fournit un meilleur contrôle sur la stratégie finale. Ce manque de contrôle est en effet une des faiblesses empêchant l'adoption des POMDP pour le dialogue dans l'industrie.Dans le domaine du renseignement d'informations touristiques et de la réservation de chambres d'hôtel, les résultats sur des dialogues simulés montrent l'efficacité de l'approche par renforcement associée à un système de règles pour s'adapter à un environnement bruité. Les tests réels sur des utilisateurs humains montrent qu'un système optimisé par renforcement obtient cependant de meilleures performances sur le critère pour lequel il a été optimisé.

Durant ce doctorat financé par l'observatoire B2V des mémoires, nous avons réalisé une modélisation mathématique du comportement dans trois tâches distinctes (avec des sujets humains, des sujets singes et des rongeurs), mais qui supposent toutes une coordination entre systèmes de mémoire. Dans la première expérience, nous avons reproduit le comportement de sujets humains (choix et temps de réaction) en combinant les modèles mathématiques d'une mémoire de travail et d'une mémoire inflexible. Nous avons associé pour un sujet son comportement au meilleur modèle possible en comparant des modèles génériques de coordination de ces deux mémoires issues de la littérature actuelle ainsi que notre propre proposition d'une interaction dynamique entre les mémoires. Au final, c'est notre proposition d'une interaction au lieu d'une séparation stricte qui s'est avérée la plus efficace dans la majorité des cas pour expliquer le comportement des sujets. Dans une deuxième expérience, les mêmes modèles de coordination ont été testés dans une tâche chez le singe. Considérée comme un test de transférabilité, cette expérience démontre principalement la nécessité de coordination de mémoires pour expliquer le comportement de certains singes. Dans une troisième expérience, nous avons modélisé le comportement d'un groupe de souris confronté à l'apprentissage d'une séquence d'action motrice dans un labyrinthe sans indices externes. En comparant avec deux autres stratégies d'apprentissages (intégration de chemin et planification dans un graphe), la combinaison d'une mémoire épisodique avec une mémoire inflexible s'est révélée être le meilleur modèle pour reproduire le comportement des souris. / During this PhD funded by the B2V Memories Observatory, we performed a mathematical modeling of behavior in three distinct tasks (with human subjects, monkeys and rodents), all involving coordination between memory systems. In the first experiment, we reproduced the behavior of human subjects (choice and reaction time) by combining the mathematical models of working memory and procedural memory. For each subject, we associated their behavior to the best possible model by comparing generic models of coordination of these two memories from the current literature as well as our own proposal of a dynamic interaction between memories. In the end, it was our proposal of an interaction instead of a strict separation which proved most effective in the majority of cases to explain the behavior of the subjects. In a second experiment, the same coordination models were tested in a monkey task. Considered as a transferability test, this experiment mainly demonstrates the need for coordination of memories to explain the behavior of certain monkeys. In a third experiment, we modeled the behavior of a group of mice confronted with the learning of a motor action sequence in a labyrinth without visual cues. Comparing with two other learning strategies (path integration and graph planning), the combination of an episodic memory with a procedural memory proved to be the best model to reproduce the behavior of mice.

Les systèmes de dialogue incrémentaux sont capables d’entamer le traitement des paroles de l’utilisateur au moment même où il les prononce (sans attendre de signal de fin de phrase tel un long silence par exemple). Ils peuvent ainsi prendre la parole à n’importe quel moment et l’utilisateur peut faire de même (et interrompre le système). De ce fait, ces systèmes permettent d’effectuer une plus large palette de comportements de prise de parole en comparaison avec les systèmes de dialogue traditionnels. Cette thèse s’articule autour de la problématique suivante : est-il possible pour un système de dialogue incrémental d’apprendre une stratégie optimale de prise de parole de façon autonome? Tout d’abord, une analyse des mécanismes sous-jacents à la dynamique de prise de parole dans une conversation homme-homme a permis d’établir une taxonomie de ces phénomènes. Ensuite, une nouvelle architecture permettant de doter les systèmes de dialogues conventionnels de capacités de traitement incrémentales de la parole, à moindre coût, a été proposée. Dans un premier temps, un simulateur de dialogue destiné à répliquer les comportements incrémentaux de l’utilisateur et de la reconnaissance vocale a été développé puis utilisé pour effectuer les premier tests de stratégies de dialogue incrémentales. Ces dernières ont été développées à base de règles issues de l’analyse effectuée lors de l’établissement de la taxonomie des phénomènes de prise de parole. Les résultats de la simulation montrent que le caractère incrémental permet d’obtenir des interactions plus efficaces. La meilleure stratégie à base de règles a été retenue comme référence pour la suite. Dans un second temps, une stratégie basée sur l’apprentissage par renforcement a été implémentée. Elle est capable d’apprendre à optimiser ses décisions de prise de parole de façon totalement autonome étant donnée une fonction de récompense. Une première comparaison, en simulation, a montré que cette stratégie engendre des résultats encore meilleurs par rapport à la stratégie à base de règles. En guise de validation, une expérience avec des utilisateurs réels a été menée (interactions avec une maison intelligente). Une amélioration significative du taux de complétion de tâche a été constatée dans le cas de la stratégie apprise par renforcement et ce, sans dégradation de l’appréciation globale par les utilisateurs de la qualité du dialogue (en réalité, une légère amélioration a été constatée). / Incremental dialogue systems are able to process the user’s speech as it is spoken (without waiting for the end of a sentence before starting to process it). This makes them able to take the floor whenever they decide to (the user can also speak whenever she wants, even if the system is still holding the floor). As a consequence, they are able to perform a richer set of turn-taking behaviours compared to traditional systems. Several contributions are described in this thesis with the aim of showing that dialogue systems’ turn-taking capabilities can be automatically improved from data. First, human-human dialogue is analysed and a new taxonomy of turn-taking phenomena in human conversation is established. Based on this work, the different phenomena are analysed and some of them are selected for replication in a human-machine context (the ones that are more likely to improve a dialogue system’s efficiency). Then, a new architecture for incremental dialogue systems is introduced with the aim of transforming a traditional dialogue system into an incremental one at a low cost (also separating the turn-taking manager from the dialogue manager). To be able to perform the first tests, a simulated environment has been designed and implemented. It is able to replicate user and ASR behaviour that are specific to incremental processing, unlike existing simulators. Combined together, these contributions led to the establishement of a rule-based incremental dialogue strategy that is shown to improve the dialogue efficiency in a task-oriented situation and in simulation. A new reinforcement learning strategy has also been proposed. It is able to autonomously learn optimal turn-taking behavious throughout the interactions. The simulated environment has been used for training and for a first evaluation, where the new data-driven strategy is shown to outperform both the non-incremental and rule-based incremental strategies. In order to validate these results in real dialogue conditions, a prototype through which the users can interact in order to control their smart home has been developed. At the beginning of each interaction, the turn-taking strategy is randomly chosen among the non-incremental, the rule-based incremental and the reinforcement learning strategy (learned in simulation). A corpus of 206 dialogues has been collected. The results show that the reinforcement learning strategy significantly improves the dialogue efficiency without hurting the user experience (slightly improving it, in fact).

Cette thèse porte sur la conception de contrôleurs pour robots explorateurs autonomes basée sur une approche en ligne (online) intégrée, ne nécessitant pas de vérité terrain ni d'intervention de l'expert humain au cours du processus d'entrainement.Le travail présenté se focalise sur le domaine de la robotique autonome et plus particulièrement la conception de controleurs robotiques pour les essaims de robots.Ce contexte présente deux difficultés spécifiques. Premièrement, les approches basées sur l'usage de simulateur sont d'efficacité limitée : d'une part, la précision du simulateur est limitée compte tenu de la variabilité des robots élémentaires; d'autre part, la complexité de la simulation est super-linéaire en fonction du nombre de robots de l'essaim. Deuxièmement, les approches guidées par le but se heurtent au fait que la fonction objectif n'est pas définie au niveau du robot individuel, mais au niveau de l'essaim.Une première étape vers la conception de contrôleur explorateur autonome est proposée dans cette thèse. L'approche proposée, appelée exploration robotique fondée sur l'évolution et l'information (Ev-ITER) se fonde sur l'hybridation de la robotique évolutionnaire et de l'apprentissage par renforcement utilisant l'entropie. Cette approche procède en deux phases: (i) dans une première phase l'évolution artificielle est utilisée pour générer des contrôleurs primaires (crawlers), dont les trajectoires sont d'entropie élevée dans l'espace sensori-moteur; (ii) dans une seconde phase, l'archive des trajectoires acquises par les controleurs primaires est exploitée pour définir les controleurs secondaires, inspirés de la motivation intrinsèque robuste et permettant l'exploration rigoureuse de l'environnement.Les contributions de cette thèse sont les suivantes. Premièrement, comme désiré Ev-ITER peut être lancé en ligne, et sans nécessiter de vérité terrain ou d'assistance. Deuxièmement, Ev-ITER surpasse les approches autonomes en robotique évolutionnaire en terme d'exploration de l'arène. Troisièmement, le contrôleur Ev-ITER est doté d'une certaine généralité, dans la mesure où il est capable d'explorer efficacement d'autres arènes que celle considérée pendant la première phase de l'évolution. Il est à souligner que la généralité du contrôleur appris vis-à-vis de l'environnement d'entrainement a rarement été considérée en apprentissage par renforcement ou en robotique évolutionnaire. / This thesis is concerned with building autonomous exploratory robotic controllers in an online, on-board approach, with no requirement for ground truth or human intervention in the experimental setting.This study is primarily motivated by autonomous robotics, specifically autonomous robot swarms. In this context, one faces two difficulties. Firstly, standard simulator-based approaches are hardly effective due to computational efficiency and accuracy reasons. On the one hand, the simulator accuracy is hindered by the variability of the hardware; on the other hand, this approach faces a super-linear computational complexity w.r.t. the number of robots in the swarm. Secondly, the standard goal-driven approach used for controller design does not apply as there is no explicit objective function at the individual level, since the objective is defined at the swarm level.A first step toward autonomous exploratory controllers is proposed in the thesis. The Evolution & Information Theory-based Exploratory Robotics (Ev-ITER) approach is based on the hybridization of two approaches stemming from Evolutionary Robotics and from Reinforcement Learning, with the goal of getting the best of both worlds: (i) primary controllers, or crawling controllers, are evolved in order to generate sensori-motor trajectories with high entropy; (ii) the data repository built from the crawling controllers is exploited, providing prior knowledge to secondary controllers, inspired from the intrinsic robust motivation setting and achieving the thorough exploration of the environment.The contributions of the thesis are threefold. Firstly, Ev-ITER fulfills the desired requirement: it runs online, on-board and without requiring any ground truth or support. Secondly, Ev-ITER outperforms both the evolutionary and the information theory-based approaches standalone, in terms of actual exploration of the arena. Thirdly and most importantly, the Ev-ITER controller features some generality property, being able to efficiently explore other arenas than the one considered during the first evolutionary phase. It must be emphasized that the generality of the learned controller with respect to the considered environment has rarely been considered, neither in the reinforcement learning, nor in evolutionary robotics.

L’optimisation de l’opération des réseaux mobiles a toujours été d'un très grand intérêt pour les opérateurs, surtout avec une augmentation rapide du trafic mobile, des attentes qualité de service encore plus élevées des utilisateurs, et l’émergence de nouveaux services requérant des contraintes spécifiques et différentes. Le concept de gestion autonome des réseaux (SON) a été introduit par la 3rd Generation Partnership Project comme étant une solution prometteuse pour simplifier l’opération et la gestion des réseaux complexes. Aujourd’hui, plusieurs fonctions SON sont déjà déployées dans les réseaux. Cependant, les actions conduites par les fonctions SON dans le réseau dépendent de la configuration de l’algorithme même de ces fonctions, et aussi du contexte du réseau et de l’environnement ou cette fonction est déployée. D’autre part, un réseau radio mobile auto-organisant serait idéalement un réseau où toutes les fonctions autonomes (SON) fonctionnent de manière coordonnée et cohérente pour répondre à des objectifs de haut niveau de l’opérateur. L’entité autonome serait donc le réseau capable de s’autogérer pour répondre à une stratégie globale de l’opérateur, exprimée en termes d’objectifs de haut niveau de l’opérateur. A cette fin, nous proposons dans cette thèse une approche qu'on appel « Cognitive Policy Based SON Management » (C-PBSM). Le C-PBSM est capable d’apprendre des configurations optimales des fonctions SON selon les exigences de l’opérateur. Il a également la capacité d’améliorer sa décision au cours du temps en apprenant de son expérience passée, et de s’adapter avec les changements de l’environnement. Nous étudions plusieurs approches pour mettre en place la boucle cognitive en se basant sur l’apprentissage par renforcement (RL). Nous analysons la convergence et la scalabilité de ces approches et proposons des solutions adaptées. Nous prenons en compte la non stationnarité des réseaux, notamment la variation de trafic. Nous proposons également des solutions pour mettre en œuvre un apprentissage collaboratif et un transfert des connaissances. Une architecture SDN (software defined networks) est proposée pour le déploiement des agents d’apprentissage dans le réseau. / The pressure on operators to improve the network management efficiency is constantly growing for many reasons: the user traffic that is increasing very fast, higher end users expectations, emerging services with very specific requirements. Self-Organizing Networks (SON) concept was introduced by the 3rd Generation Partnership Project as a promising solution to simplify the operation and management of complex networks. Many SON modules are already being deployed in today’s networks. Such networks are known as SON enabled networks, and they have proved to be useful in reducing the complexity of network management. However, SON enabled networks are still far from realizing a network that is autonomous and self-managed as a whole. In fact, the behavior of the SON functions depends on the parameters of their algorithm, as well as on the network environment where it is deployed. Besides, SON objectives and actions might be conflicting with each other, leading to incompatible parameter tuning in the network. Each SON function hence still needs to be itself manually configured, depending on the network environment and the objectives of the operator. In this thesis, we propose an approach for an integrated SON management system through a Cognitive Policy Based SON Management (C-PBSM) approach, based on Reinforcement Learning (RL). The C-PBSM translates autonomously high level operator objectives, formulated as target Key Performance Indicators (KPIs), into configurations of the SON functions. Furthermore, through its cognitive capabilities, the C-PBSM is able to build its knowledge by interacting with the real network. It is also capable of adapting with the environment changes. We investigate different RL approaches, we analyze the convergence time and the scalability and propose adapted solutions. We tackle the problem of non-stationarity in the network, notably the traffic variations, as well as the different contexts present in a network. We propose as well an approach for transfer learning and collaborative learning. Practical aspects of deploying RL agents in real networks are also investigated under Software Defined Network (SDN) architecture.

Les processus de décision markovien (MDP), le cadre mathématiques sous-jacent à la plupart des algorithmes de l'apprentissage par renforcement (RL) est souvent utilisé d'une manière qui suppose, à tort, que l'état de l'environnement d'un agent ne change pas pendant la sélection des actions. Puisque les systèmes RL basés sur les MDP classiques commencent à être appliqués dans les situations critiques pour la sécurité du monde réel, ce décalage entre les hypothèses sous-jacentes aux MDP classiques et la réalité du calcul en temps réel peut entraîner des résultats indésirables. Dans cette thèse, nous introduirons un nouveau cadre dans lequel les états et les actions évoluent simultanément, nous montrerons comment il est lié à la formulation MDP classique. Nous analyserons des algorithmes existants selon la nouvelle formulation en temps réel et montrerons pourquoi ils sont inférieurs, lorsqu'ils sont utilisés en temps réel. Par la suite, nous utiliserons ces perspectives pour créer un nouveau algorithme Real-Time Actor Critic qui est supérieur au Soft Actor Critic contrôle continu de l'état de l'art actuel, aussi bien en temps réel qu'en temps non réel. / Markov Decision Processes (MDPs), the mathematical framework underlying most algorithms in Reinforcement Learning (RL), are often used in a way that wrongfully assumes that the state of an agent's environment does not change during action selection. As RL systems based on MDPs begin to find application in real-world safety critical situations, this mismatch between the assumptions underlying classical MDPs and the reality of real-time computation may lead to undesirable outcomes. In this thesis, we introduce a new framework, in which states and actions evolve simultaneously, we show how it is related to the classical MDP formulation. We analyze existing algorithms under the new real-time formulation and show why they are suboptimal when used in real-time. We then use those insights to create a new algorithm, Real-Time Actor Critic (RTAC) that outperforms the existing state-of-the-art continuous control algorithm Soft Actor Critic both in real-time and non-real-time settings.

Le conditionnement Pavlovien, l'acquisition de réponses vers des stimuli neutres associés à des récompenses, et le conditionnement instrumental, l'expression de comportements pour atteindre des buts, sont au cœur de nos capacités d'apprentissage. Ils sont souvent étudiés séparément malgré les preuves de leur enchevêtrement. Les modèles de conditionnement instrumental reposent sur le formalisme de l'apprentissage par renforcement (RL), alors que les modèles du conditionnement Pavlovien reposent surtout sur des architectures dédiées souvent incompatibles avec ce formalisme, compliquant l'étude de leurs interactions.Notre objectif est de trouver des concepts, qui combinés à des modèles RL puissent offrir une architecture unifiée permettant une telle étude. Nous développons un modèle qui combine un système RL classique, qui apprend une valeur par état, avec un système RL révisé, évaluant les stimuli séparément et biaisant le comportement vers ceux associés aux récompenses. Le modèle explique certaines réponses inadaptées par l'interaction néfaste des systèmes, ainsi que certaines différences inter-individuelles par une simple variation au niveau de la population de la contribution de chaque système dans le comportement global.Il explique une activité inattendue de la dopamine, vis-à-vis de l'hypothèse qu'elle encode un signal d'erreur, par son calcul sur les stimuli et non les états. Il est aussi compatible avec une hypothèse alternative que la dopamine contribue aussi à rendre certains stimuli recherchés pour eux-mêmes. Le modèle présente des propriétés prometteuses pour l'étude du conditionnement Pavlovien,du conditionnement instrumental et de leurs interactions. / Pavlovian conditioning, the acquisition of responses to neutral stimuli previously paired with rewards, and instrumental conditioning, the acquisition of goal-oriented responses, are central to our learning capacities. However, despite some evidences of entanglement, they are mainly studied separately. Reinforcement learning (RL), learning by trials and errors to reach goals, is central to models of instrumental conditioning, while models of Pavlovian conditioning rely on more dedicated and often incompatible architectures. This complicates the study of their interactions. We aim at finding concepts which combined with RL models may provide a unifying architecture to allow such a study. We develop a model that combines a classical RL system, learning values over states, with a revised RL system, learning values over individual stimuli and biasing the behaviour towards reward-related ones. It explains maladaptive behaviours in pigeons by the detrimental interaction of systems, and inter-individual differences in rats by a simple variation at the population level in the contribution of each system to the overall behaviour. It explains unexpected dopaminergic patterns with regard to the dominant hypothesis that dopamine parallels a reward prediction error signal by computing such signal over features rather than states, and makes it compatible with an alternative hypothesis that dopamine also contributes to the acquisition of incentive salience, making reward-related stimuli wanted for themselves. The present model shows promising properties for the investigation of Pavlovian conditioning, instrumental conditioning and their interactions.

Les problèmes d’optimisation combinatoire (Constraint Optimization Problems – COP) sont souvent difficiles à résoudre et le choix de la stratégie de recherche a une influence importante sur la performance du solveur. Pour de résoudre un problème d’optimisation combinatoire en explorant un arbre de recherche, il faut choisir une heuristique de choix de variable (qui définit l’ordre dans lequel les variables vont être instanciées), une heuristique de choix de valeur (qui spécifie l’ordre dans lequel les valeurs seront essayées), et une stratégie de retour-arrière (qui détermine vers quel noeud effectuer les retours-arrière lorsqu’une feuille de l’arbre est rencontrée). Pour les stratégies de retour-arrière, il y a celles dont les retours-arrière sont totalement déterministes (e.g. Depth-First Search – DFS) et d’autres qui s’appuient sur des mécanismes d’évaluation de noeuds plus dynamiques (e.g. Best-First Search). Certaines (e.g. Limited Discrepancy Search – LDS) peuvent être implémentées soit comme un algorithme itératif déterministe ou un évaluateur de noeud. Une stratégie est dite adaptative quand elle s’adapte dynamiquement à la structure du problème et identifie les zones de l’espace de recherche qui contiennent les “bonnes” solutions. Dans ce contexte, des stratégies de branchement adaptatives ont été proposées (e.g. Impact-Based Search – IBS) ainsi qu’une stratégie de retour-arrière adaptative (e.g. Adaptive Discrepancy Search – ADS), proposée pour les problèmes d’optimisation distribués. À notre connaissance, aucune stratégie adaptative qui utilise l’apprentissage par renforcement (Reinforcement Learning – RL) pour supporter son mécanisme d’apprentissage n’a été proposée dans la littérature. Nous pensons que les techniques de RL permettront un apprentissage plus efficace et qu’une stratégie de retour-arrière munie de ces techniques aura le potentiel de résoudre les problèmes d’optimisation combinatoire plus rapidement. Dans ce mémoire, nous proposons un algorithme (RLBS) qui “apprend” à faire des retours-arrière de manière efficace lors de l’exploration d’arbres non-binaires. Plus précisément, il s’agit une stratégie de retour-arrière qui se base sur l’apprentissage automatique pour améliorer la performance du solveur. En fait, nous utilisons l’apprentissage par renforcement pour identifier les zones de l’espace de recherche qui contiennent les bonnes solutions. Cette approche a été développée pour les problèmes d’optimisation combinatoire dont l’espace de recherche est encodé dans un arbre non-binaire. Comme les arbres sont non-binaires, on a l’occasion d’effectuer plusieurs retours-arrière vers chaque noeud durant l’exploration. Ceci permet d’apprendre quels noeuds mènent vers les meilleures récompenses en général (c’est-à-dire, vers les feuilles les plus intéressantes). Le branchement est effectué en utilisant une stratégie de choix de variable/valeur quelconque. Toutefois, quand un retour-arrière est nécessaire, la sélection du noeud cible s’appuie sur l’apprentissage par renforcement. RLBS est évalué sur cinq instances industrielles du problème de la planification des opérations du rabotage du bois et a été comparé à ADS et à LDS sur cette même application. RLBS dépasse LDS et ADS, en termes de temps de calcul nécessaire à la résolution, sur chacune de ces instances-là et trouve la solution optimale plus rapidement. Les expérimentations ont montré que RLBS est en moyenne 4 fois plus rapide que ADS, et 6 fois plus rapide que LDS. RLBS a aussi été évalué sur une instance jouet du même problème et a été comparé à IBS. RLBS surpasse largement IBS. Il est capable de trouver une solution optimale en explorant beaucoup moins de noeuds que le nombre nécessaire à IBS pour trouver une telle solution. / Combinatorial optimization problems are often very difficult to solve and the choice of a search strategy has a tremendous influence over the solver’s performance. To solve a problem using search, one needs to choose a variable selection strategy (defining the order in which variables will be instantiated), a value selection strategy (that specifies the sequence in which we will try the variable possible values) and a backtracking strategy (that determines to which node we should backtrack/backjump, when a leaf is reached or a dead-end is encountered). When it comes to backtracking strategies, there are some that are encoded into full deterministic algorithms (e.g. Depth-First Search – DFS), and others that rely on more dynamic node evaluator mechanisms (e.g. Best-First Search). Others (e.g. Limited Discrepancy Search – LDS) can be implemented as a deterministic iterative algorithm or as a node evaluator. A strategy is said to be adaptive when it dynamically adapts to the structure of the problem and identifies the areas of the search space that contain good solutions. Some have proposed adaptive branching strategies (e.g. Impact-based Search – IBS) or a backtracking strategy (e.g. Adaptive Discrepancy Search – ADS) proposed for distributed optimization problems. To our current knowledge, no adaptive backtracking strategy that relies on Reinforcement Learning (RL) has been proposed yet. We believe that RL techniques could allow a more efficient learning process and that, provided with these techniques, a backtracking strategy has a great potential of solving combinatorial optimization problems in a faster way. In this thesis, we introduce an algorithm (RLBS) that learns to efficiently backtrack when searching non-binary trees. We consider a machine learning approach which improves the performance of the solver. More specifically, we use reinforcement learning to identify the areas of the search space that contain good solutions. The approach was developed for optimization problems for which the search space is encoded as a non-binary tree. Since the trees are non-binary, we have the opportunity to backtrack multiple times to each node during the search. This allows learning which nodes generally lead to the best rewards (that is, to the most interesting leaves). Branching can be carried on using any variable/value selection strategy. However, when backtracking is needed, the selection of the target node involves reinforcement learning. RLBS is evaluated on five instances of the lumber planing problem using real idustrial data, and it is compared to LDS and ADS. It outperforms classic (non-adaptive) search strategies (DFS, LDS), an adaptive branching strategy (IBS), and an adaptive backtracking strategy (ADS) on every instance of this problem. Experiments have shown that RLBS is on average 4 times faster than ADS, and 6 times faster than LDS. RLBS is also evaluated on a toy instance of the lumber planing problem and compared to IBS. RLBS substantially outperforms IBS by solving the problem to optimality much faster.

L'apprentissage par renforcement est une approche d'apprentissage automatique permettant de développer des systèmes s'améliorant à partir d'interactions avec un environnement. Les processus décisionnels de Markov partiellement observables (PDMPO) font partie des modèles mathématiques fréquemment utiliser pour résoudre ce type de problème d'apprentissage. Cependant, la majorité des méthodes de résolution utilisées dans les processus décisionnels de Markov partiellement observables nécessitent la connaissance du modèle. De plus, les recherches actuelles sur le PDMPO se restreignent principalement aux espaces d'états discrets, ce qui complique son application à certains problèmes naturellement modélisés par un espace d'état continu. Ce mémoire présente une vision des PDMPO basée sur les processus Gaussiens, une méthode d'apprentissage supervisée ayant comme propriété particulière d'être une distribution de probabilité dans l'espace des fonctions. Cette propriété est notamment très intéressante du fait qu'elle ouvre la porte à un traitement Bayésien de l'incertitude sur les fonctions inconnues d'un PDMPO continu. Les résultats obtenus avec l'approche d'apprentissage par processus Gaussien montrent qu'il est possible d'opérer dans un environnement tout en identifiant le modèle de ce celui-ci. À partir des conclusions tirées à la suite de nos travaux sur le PDMPO, nous avons observé un certain manque pour ce qui est de l'identification du modèle sous l'incertain. Ainsi, ce mémoire expose aussi un premier pas vers une extension de l'apprentissage de PDMPO continu utilisant des séquences d'états de croyances lors de l'identification du modèle. Plus précisément, nous proposons une méthode de régression par processus Gaussiens utilisant des ensembles d'entraînement incertain pour réaliser l'inférence dans l'espace des fonctions. La méthode proposée est particulièrement intéressante, du fait qu'elle s'applique exactement comme pour le cas des processus Gaussiens classiques et qu'elle n'augmente p±as la complexité de l'apprentissage.

Le temps de mélange de la chaîne de Markov induite par une politique limite ses performances dans les scénarios réels d'apprentissage continu. Pourtant, l'effet des temps de mélange sur l'apprentissage dans l'apprentissage par renforcement (RL) continu reste peu exploré. Dans cet article, nous caractérisons des problèmes qui sont d'un intérêt à long terme pour le développement de l'apprentissage continu, que nous appelons processus de décision markoviens (MDP) « extensibles » (scalable), à travers le prisme des temps de mélange. En particulier, nous établissons théoriquement que les MDP extensibles ont des temps de mélange qui varient de façon polynomiale avec la taille du problème. Nous démontrons ensuite que les temps de mélange polynomiaux présentent des difficultés importantes pour les approches existantes, qui souffrent d'un biais myope et d'estimations à base de ré-échantillonnage avec remise ensembliste (bootstrapping) périmées. Pour valider notre théorie, nous étudions la complexité des temps de mélange en fonction du nombre de tâches et de la durée des tâches pour des politiques très performantes déployées sur plusieurs jeux Atari. Notre analyse démontre à la fois que des temps de mélange polynomiaux apparaissent en pratique et que leur existence peut conduire à un comportement d'apprentissage instable, comme l'oubli catastrophique dans des contextes d'apprentissage continu. / The mixing time of the Markov chain induced by a policy limits performance in real-world continual learning scenarios. Yet, the effect of mixing times on learning in continual reinforcement learning (RL) remains underexplored. In this paper, we characterize problems that are of long-term interest to the development of continual RL, which we call scalable MDPs, through the lens of mixing times. In particular, we theoretically establish that scalable MDPs have mixing times that scale polynomially with the size of the problem. We go on to demonstrate that polynomial mixing times present significant difficulties for existing approaches, which suffer from myopic bias and stale bootstrapped estimates. To validate our theory, we study the empirical scaling behavior of mixing times with respect to the number of tasks and task duration for high performing policies deployed across multiple Atari games. Our analysis demonstrates both that polynomial mixing times do emerge in practice and how their existence may lead to unstable learning behavior like catastrophic forgetting in continual learning settings.