L'informatique en périphérie (Fog Computing) étend le Cloud en fournissant des ressources distribuées à proximité des dispositifs IoT, soutenant les applications IoT en temps réel et sensibles aux délais. La charge de ces applications doit être intelligemment répartie à travers ces ressources limitées pour minimiser les délais d'attente dans les nœuds de périphérie, réduisant ainsi le délai d'exécution global et maximisant l'utilisation des ressources. Les solutions actuelles de répartition de charge sont souvent centralisées ou partiellement centralisées, ce qui va à l'encontre de l'objectif de l'informatique en périphérie de fournir des services distribués, entraînant des retards de décision, des points de défaillance uniques, des goulets d'étranglement et des problèmes de sécurité et de confidentialité. Ainsi, la conception d'une solution entièrement distribuée et efficace est essentielle pour les applications IoT en temps réel et sensibles aux délais dans des systèmes de périphérie complexes. Cette thèse apporte quatre contributions pour une solution efficace de répartition de charge en périphérie, évaluée sur un simulateur d'événements discrets avec des environnements réalistes et des architectures de périphérie hétérogènes. La première contribution est une solution de classement multicritère centralisée nécessitant des informations Fog en temps réel pour chaque décision d'attribution, surpassant les méthodes traditionnelles comme le Round-Robin. La deuxième contribution est un agent d'apprentissage par renforcement profond respectueux de la vie privée qui estime la charge dans chaque nœud sans la collecter, surpassant la première solution même dans des environnements partiellement observés. La troisième contribution est un cadre d'apprentissage continu pour cet agent, minimisant le délai de décision grâce à une inférence légère et ajusté par l'apprentissage par transfert, réduisant le temps d'entraînement par 5 et améliorant les performances par rapport à un agent formé à partir de zéro. La quatrième contribution déploie plusieurs instances indépendantes de l'agent aux passerelles IoT pour une solution évolutive, minimisant significativement le délai de décision et surpassant les solutions à agent unique, utilisant des protocoles de multidiffusion pour collecter les observations de l'environnement de manière réaliste. / Fog Computing extends the Cloud by providing distributed resources near IoT devices, supporting real-time and delay-sensitive IoT applications. The load of such applications must be intelligently distributed across these limited resources to minimize waiting delays in all Fog nodes, thereby reducing end-to-end execution delay and maximizing resource utilization. Existing load balancing solutions are either fully centralized or distributed with centralized components, which conflict with the aim of Fog Computing to provide distributed services, leading to decision delays, single points of failure, system bottlenecks, and security and privacy issues. Therefore, designing an efficient fully distributed solution is vital for real-time and delay-sensitive IoT applications in complex Fog systems. This thesis provides four contributions toward an efficient Fog load balancing solution for practical deployment, evaluated on a discrete-event simulator using realistic environments with heterogeneous and unbalanced Fog architectures serving heterogeneous workloads with variable generation rates. The first contribution is a centralized multi-criteria ranking solution requiring real-time Fog information for each assignment decision, outperforming traditional baseline methods like random, Round-Robin, nearest node selection, and fastest service selection methods. The second contribution is a privacy-aware Deep Reinforcement Learning agent that estimates the load in each Fog node instead of collecting it. This agent outperformed the first solution even with partially observed environments. The third contribution is a lifelong learning framework for the privacy-aware agent, minimizing decision delay using lightweight inference. To adapt to changes, the agent is fine-tuned using transfer learning instead of training from scratch, achieving a 5X reduction in training time, better generalization, and better performance than an agent trained from scratch. In the fourth contribution, multiple independent agent instances are deployed at IoT gateways for a scalable solution, outperforming single-agent solutions in minimizing decision delay. Additionally, interval-based multi-casting protocols are used to collect environment observations, unlike the common use of unrealistic instantaneous observations in the literature.

Les problèmes de prise de décisions séquentielles multiagents sont difficiles à résoudre surtout lorsque les agents n'observent pas parfaitement l'état de Y environnement. Les approches existantes pour résoudre ces problèmes utilisent souvent des approximations de la fonction de valeur ou se basent sur la structure pour simplifier la résolution. Dans cette thèse, nous proposons d'approximer un problème de décisions séquentielles multiagent à observation limitée, modélisé par un processus décisionnel markovien décentralisé (DEC-MDP) en utilisant deux hypothèses sur la structure du problème. La première hypothèse porte sur la structure de comportement optimal et suppose qu'il est possible d'approximer la politique optimale d'un agent en connaissant seulement les actions optimales au niveau d'un petit nombre de situations auxquelles l'agent peut faire face dans son environnement. La seconde hypothèse porte, quant à elle, sur la structure organisationnelle des agents et suppose que plus les agents sont éloignés les uns des autres, moins ils ont besoin de se coordonner. Ces deux hypothèses nous amènent à proposer deux approches d'approximation. La première approche, nommée Supervised Policy Reinforcement Learning, combine l'apprentissage par renforcement et l'apprentissage supervisé pour généraliser la politique optimale d'un agent. La second approche se base, quant à elle, sur la structure organisationnelle des agents pour apprendre une politique multiagent dans des problèmes où l'observation est limitée. Pour cela, nous présentons un modèle, le D O F - D E C - M DP (Distance-Observable Factored Decentralized Markov Décision Process) qui définit une distance d'observation pour les agents. A partir de ce modèle, nous proposons des bornes sur le gain de récompense que permet l'augmentation de la distance d'observation. Les résultats empiriques obtenus sur des problèmes classiques d'apprentissage par renforcement monoagents et multiagents montrent que nos approches d'approximation sont capables d'apprendre des politiques proches de l'optimale. Enfin, nous avons testé nos approches sur un problème de coordination de véhicules en proposant une méthode de synchronisation d'agents via la communication dans un cadre à observation limitée.

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.

La robotique ambiante s'intéresse à l'introduction de robots mobiles au sein d'environnements actifs où ces derniers fournissent des fonctionnalités alternatives ou complémentaires à celles embarquées par les robots mobiles. Cette thèse étudie la mise en concurrence des fonctionnalités internes et externes aux robots, qu'elle pose comme un problème de sélection de services logiciels. La sélection de services consiste à choisir un service ou une combinaison de services parmi un ensemble de candidats capables de réaliser une tâche requise. Pour cela, elle doit prédire et évaluer la performance des candidats. Ces performances reposent sur des critères non-fonctionnels comme la durée d'exécution, le coût ou le bruit. Ce domaine applicatif a pour particularité de nécessiter une coordination étroite entre certaines de ses fonctionnalités. Cette coordination se traduit par l'échange de flots de données entre les fonctionnalités durant leurs exécutions. Les fonctionnalités productrices de ces flots sont modélisées comme des services continus. Cette nouvelle catégorie de services logiciels impose que les compositions de services soient hiérarchiques et introduit des contraintes supplémentaires pour la sélection de services. Cette thèse met en évidence la présence d'un important couplage non-fonctionnel entre les performances des instances de services de différents niveaux, même lorsque les flots de données sont unidirectionnels. L'approche proposée se concentre sur la prédiction de la performance d'une instance de haut-niveau sachant son organigramme à l'issue de la sélection. Un organigramme regroupe l'ensemble des instances de services sollicitées pour réaliser une tâche de haut-niveau. L'étude s'appuie sur un scénario impliquant la sélection d'un service de positionnement en vue de permettre le déplacement d'un robot vers une destination requise. Pour un organigramme considéré, la prédiction de performance d'une instance de haut-niveau de ce scénario introduit les exigences suivantes : elle doit (i)être contextuelle en tenant compte, par exemple, du chemin suivi pour atteindre la destination requise, (ii) prendre en charge le remplacement d'une instance de sous-service suite à un échec ou, par extension, de façon opportuniste. En conséquence, cette sélection de services est posée comme un problème de prise de décision séquentielle formalisé à l'aide de processus de décision markoviens à horizon fini. La dimensionnalité importante du contexte en comparaison à la fréquence des déplacements du robot rend inadaptées les méthodes consistant à apprendre directement une fonction de valeur ou une fonction de transition. L'approche proposée repose sur des modèles de dynamique locaux et exploite le chemin de déplacement calculé par un sous-service pour estimer en ligne les valeurs des organigrammes disponibles dans l'état courant. Cette estimation est effectuée par l'intermédiaire d'une méthode de fouille stochastique d'arbre, Upper Confidence bounds applied to Trees

La robotique ambiante s'intéresse à l'introduction de robots mobiles au sein d'environnements actifs où ces derniers fournissent des fonctionnalités alternatives ou complémentaires à celles embarquées par les robots mobiles. Cette thèse étudie la mise en concurrence des fonctionnalités internes et externes aux robots, qu'elle pose comme un problème de sélection de services logiciels. La sélection de services consiste à choisir un service ou une combinaison de services parmi un ensemble de candidats capables de réaliser une tâche requise. Pour cela, elle doit prédire et évaluer la performance des candidats. Ces performances reposent sur des critères non-fonctionnels comme la durée d'exécution, le coût ou le bruit. Ce domaine applicatif a pour particularité de nécessiter une coordination étroite entre certaines de ses fonctionnalités. Cette coordination se traduit par l'échange de flots de données entre les fonctionnalités durant leurs exécutions. Les fonctionnalités productrices de ces flots sont modélisées comme des services continus. Cette nouvelle catégorie de services logiciels impose que les compositions de services soient hiérarchiques et introduit des contraintes supplémentaires pour la sélection de services. Cette thèse met en évidence la présence d'un important couplage non-fonctionnel entre les performances des instances de services de différents niveaux, même lorsque les flots de données sont unidirectionnels. L'approche proposée se concentre sur la prédiction de la performance d'une instance de haut-niveau sachant son organigramme à l'issue de la sélection. Un organigramme regroupe l'ensemble des instances de services sollicitées pour réaliser une tâche de haut-niveau. L'étude s'appuie sur un scénario impliquant la sélection d'un service de positionnement en vue de permettre le déplacement d'un robot vers une destination requise. Pour un organigramme considéré, la prédiction de performance d'une instance de haut-niveau de ce scénario introduit les exigences suivantes : elle doit (i)être contextuelle en tenant compte, par exemple, du chemin suivi pour atteindre la destination requise, (ii) prendre en charge le remplacement d'une instance de sous-service suite à un échec ou, par extension, de façon opportuniste. En conséquence, cette sélection de services est posée comme un problème de prise de décision séquentielle formalisé à l'aide de processus de décision markoviens à horizon fini. La dimensionnalité importante du contexte en comparaison à la fréquence des déplacements du robot rend inadaptées les méthodes consistant à apprendre directement une fonction de valeur ou une fonction de transition. L'approche proposée repose sur des modèles de dynamique locaux et exploite le chemin de déplacement calculé par un sous-service pour estimer en ligne les valeurs des organigrammes disponibles dans l'état courant. Cette estimation est effectuée par l'intermédiaire d'une méthode de fouille stochastique d'arbre, Upper Confidence bounds applied to Trees / Ambient robotics aims at introducing mobile robots in active environments where the latter provide new or alternative functionalities to those shipped by mobile robots. This thesis studies the competition between robot and external functionalities, which is set as a service selection problem. Service selection consists in choosing a service or a combination of services among a set of candidates able to fulfil a given request. To do this, it has to predict and evaluate candidate performances. These performances are based on non-functional requirements such as execution time, cost or noise. This application domain requires tight coordination between some of its functionalities. Tight coordination involves setting data streams between functionalities during their execution. In this proposal, functionalities producing data streams are modelled as continuous services. This new service category requires hierarchical service composition and adds some constraints to the service selection problem. This thesis shows that an important non-functional coupling appears between service instances at different levels, even when data streams are unidirectional. The proposed approach focuses on performance prediction of an high-level service instance given its organigram. This organigram gathers service instances involved in the high-level task processing. The scenario included in this study is the selection of a positioning service involved in a robot navigation high-level service. For a given organigram, performance prediction of an high-level service instance of this scenario has to: (i) be contextual by, for instance, considering moving path towards the required destination, (ii) support service instance replacement after a failure or in an opportunist manner. Consequently, this service selection is set as a sequential decision problem and is formalized as a finite-horizon Markov decision process. Its high contextual dimensionality with respect to robot moving frequency makes direct learning of Q-value functions or transition functions inadequate. The proposed approachre lies on local dynamic models and uses the planned moving path to estimate Q-values of organigrams available in the initial state. This estimation is done using a Monte-Carlo tree search method, Upper Confidence bounds applied to Trees

Le système online de l'expérience LHCb repose sur une large infrastructure informatique hétérogène, composée de milliers de serveurs sur lesquels de nombreuses applications différentes sont exécutées. Certaines applications sont critiques (prise de données, contrôle du détecteur), d'autres secondaires (serveurs web). Administrer un tel système et s'assurer de son bon fonctionnement représente une lourde charge de travail pour une petite équipe d'experts. Des recherches ont été menées afin d'automatiser certaines tâches d'administration système. En 2001, IBM définit les « self-objectives » sensés conduire à l' «autonomic computing» (informatique autonome). Dans ce contexte, nous présentons un framework basé sur l'intelligence artificielle et l'apprentissage par renforcement pour surveiller et diagnostiquer de manière non intrusive les systèmes et logiciels basés sur Linux. De plus, notre approche d’expérience partagée ainsi que notre architecture suivant le paradigme Objet permettent d'augmenter considérablement la vitesse d'apprentissage et de corréler les problèmes. / The LHCb online system relies on a large and heterogeneous IT infrastructure made from thousands of servers on which many different applications are running. They run a great variety of tasks : critical ones such as data taking and secondary ones like web servers. The administration of such a system and making sure it is working properly represents a very important workload for the small expert-operator team. Research has been performed to try to automatize (some) system administration tasks, starting in 2001 when IBM defined the so-called “self objectives” supposed to lead to “autonomic computing”. In this context, we present a framework that makes use of artificial intelligence and machine learning to monitor and diagnose at a low level and in a non intrusive way Linux-based systems and their interaction with software. Moreover, the shared experience approach we use, coupled with an "object oriented paradigm" architecture increases a lot our learning speed, and highlight relations between problems.

En recherche d'images aujourd'hui, nous manipulons souvent de grands volumes d'images, qui peuvent varier ou même arriver en continu. Dans une base d'images, on se retrouve ainsi avec certaines images anciennes et d'autres nouvelles, les premières déjà indexées et possiblement annotées et les secondes en attente d'indexation ou d'annotation. Comme la base n'est pas annotée uniformément, cela rend l'accès difficile par le biais de requêtes textuelles. Nous présentons dans ce travail différentes techniques pour interagir, naviguer et rechercher dans ce type de bases d'images. Premièrement, un modèle d'interaction à court terme est utilisé pour améliorer la précision du système. Deuxièmement, en se basant sur un modèle d'interaction à long terme, nous proposons d'associer mots textuels et caractéristiques visuelles pour la recherche d'images par le texte, par le contenu visuel, ou mixte texte/visuel. Ce modèle de recherche d'images permet de raffiner itérativement l'annotation et la connaissance des images. Nous identifions quatre contributions dans ce travail. La première contribution est un système de recherche multimodale d'images qui intègre différentes sources de données, comme le contenu de l'image et le texte. Ce système permet l'interrogation par l'image, l'interrogation par mot-clé ou encore l'utilisation de requêtes hybrides. La deuxième contribution est une nouvelle technique pour le retour de pertinence combinant deux techniques classiques utilisées largement dans la recherche d'information~: le mouvement du point de requête et l'extension de requêtes. En profitant des images non pertinentes et des avantages de ces deux techniques classiques, notre méthode donne de très bons résultats pour une recherche interactive d'images efficace. La troisième contribution est un modèle nommé "Sacs de KVR" (Keyword Visual Representation) créant des liens entre des concepts sémantiques et des représentations visuelles, en appui sur le modèle de Sac de Mots. Grâce à une stratégie d'apprentissage incrémental, ce modèle fournit l'association entre concepts sémantiques et caractéristiques visuelles, ce qui contribue à améliorer la précision de l'annotation sur l'image et la performance de recherche. La quatrième contribution est un mécanisme de construction incrémentale des connaissances à partir de zéro. Nous ne séparons pas les phases d'annotation et de recherche, et l'utilisateur peut ainsi faire des requêtes dès la mise en route du système, tout en laissant le système apprendre au fur et à mesure de son utilisation. Les contributions ci-dessus sont complétées par une interface permettant la visualisation et l'interrogation mixte textuelle/visuelle. Même si pour l'instant deux types d'informations seulement sont utilisées, soit le texte et le contenu visuel, la généricité du modèle proposé permet son extension vers d'autres types d'informations externes à l'image, comme la localisation (GPS) et le temps. / As regard image retrieval today, we often manipulate large volumes of images, which may vary or even update continuously. In an image database, we end up with both old and new images, the first possibly already indexed and annotated and the latter waiting for indexing or annotation. Since the database is not annotated consistently, it is difficult to use text queries. We present in this work different techniques to interact, navigate and search in this type of image databases. First, a model for short term interaction is used to improve the accuracy of the system. Second, based on a model of long terminteraction, we propose to combine semantic concepts and visual features to search for images by text, visual content or a mix between text and visual content. This model of image retrieval can iteratively refine the annotation of images.We identify four contributions in this work. The first contribution is a system for multimodal retrieval of images which includes different kinds of data, like visual content and text. This system can be queried by images, by keywords or by hybrid text/visual queries. The second contribution is a novel technique of relevance feedback combining 2 classic techniques: query point movement and query expansion. This technique profits for non-pertinent feedback and combines the advantages of both classic techniques and improve performance for interactive image retrieval. The third contribution is a model based on visual representations of keywords (KVR: Keyword Visual Representation) that create links between textand visual content, based on long term interaction. With the strategy of incremental learning, this model provides an association between semantic concepts and visual features that help improve the accuracy of image annotation and image retrieval. Moreover, the visual representation of textual concept gives users the ability to query the system by text queries or mixed queries text / images, even if the image database is only partially annotated. The fourth contribution, under the assumption that knowledge is not available early in most image retrieval systems, is a mechanism for incremental construction of knowledge from scratch. We do not separate phases of retrieval and annotation, and the user can makequeries from the start of the system, while allowing the system to learn incrementally when it is used. The contributions above are completed by an interface for viewing and querying mixing textual and visual content. Although at present only two types of information are used, the text and visual content, the genericity of the proposed model allows its extension to other types of external information, such as location (GPS) and time.

La présente thèse porte sur l'étude de prise de décisions séquentielles multi-Objectif (MOSDM). La motivation de ce travail est double. D'un côté, la prise de décision, par exemple, dans les domaines de robotique et de planification, concerne l'optimisation séquentielle. De l'autre côté, nombreuses applications dans le monde réel sont plus naturellement formulés en termes d'optimisation multi-Objectif (MOO). La méthode proposée dans la thèse adapte le cadre bien connue de recherche Monte-Carlo arborescente (MCTS) à l'optimisation multi-Objectif, dans lequel multiple séquences de décision optimales sont développées dans un seul arbre de recherche. Le principal défi est de proposer une nouvelle récompense, capable de guider l'exploration de l'arbre bien que le problème de MOO n'applique pas un ordre total entre les solutions. La contribution principale de cette thèse est de proposer et d'étudier expérimentalement ces deux récompenses : l'indicateur de hypervolume et la récompense de dominance Pareto, qui sont inspirées de la littérature de MOO et basés sur une archive de solutions antérieures (archives Pareto). L'étude montre la complémentarité de ces deux récompenses. L'indicateur de hypervolume souffre de sa complexité algorithmique. Cependant, cet indicateur fournit des informations à grains fins de la qualité des solutions à l'égard de l'archive actuelle. Bien au contraire, la complexité de la récompense de dominance Pareto est linéaire, mais cette récompense fournit des informations de plus en plus rare au long de la recherche. Les preuves de principe de l'approche sont donnés sur les problèmes articiaux et les défis internationaux, et confirment la valeur de l'approche. En particulier, MOMCTS est capable de découvrir les politiques se trouvant dans les régions non-Convexes du front Pareto, qui contraste avec l'état de l'art: les algorithmes d'apprentissage par renforcement multi-Objectif existants sont basés sur scalarization linéaire et donc ne sont pas capables de explorer ces régions non-Convexes. Enfin, MOMCTS a fait honorablement la concurrence avec l'état de l'art sur la compétition internationale de MOPTSP 2013. / This thesis is concerned with multi-Objective sequential decision making (MOSDM). The motivation is twofold. On the one hand, many decision problems in the domains of e.g., robotics, scheduling or games, involve the optimization of sequences of decisions. On the other hand, many real-World applications are most naturally formulated in terms of multi-Objective optimization (MOO). The proposed approach extends the well-Known Monte-Carlo tree search (MCTS) framework to the MOO setting, with the goal of discovering several optimal sequences of decisions through growing a single search tree. The main challenge is to propose a new reward, able to guide the exploration of the tree although the MOO setting does not enforce a total order among solutions. The main contribution of the thesis is to propose and experimentally study two such rewards, inspired from the MOO literature and assessing a solution with respect to the archive of previous solutions (Pareto archive): the hypervolume indicator and the Pareto dominance reward. The study shows the complementarity of these two criteria. The hypervolume indicator suffers from its known computational complexity; however the proposed extension thereof provides fine-Grained information about the quality of solutions with respect to the current archive. Quite the contrary, the Pareto-Dominance reward is linear but it provides increasingly rare information. Proofs of principle of the approach are given on artificial problems and challenges, and confirm the merits of the approach. In particular, MOMCTS is able to discover policies lying in non-Convex regions of the Pareto front, contrasting with the state of the art: existing Multi-Objective Reinforcement Learning algorithms are based on linear scalarization and thus fail to sample such non-Convex regions. Finally MOMCTS honorably competes with the state of the art on the 2013 MOPTSP competition.

Dans cette thèse, nous développons certaines techniques avancées d'apprentissage automatique dans le cadre de l'apprentissage en ligne et de l'apprentissage par renforcement (« reinforcement learning » en anglais -- RL). L'épine dorsale de nos approches est la programmation DC (Difference of Convex functions) et DCA (DC Algorithm), et leur version en ligne, qui sont reconnues comme de outils puissants d'optimisation non convexe, non différentiable. Cette thèse se compose de deux parties : la première partie étudie certaines techniques d'apprentissage automatique en mode en ligne et la deuxième partie concerne le RL en mode batch et mode en ligne. La première partie comprend deux chapitres correspondant à la classification en ligne (chapitre 2) et la prédiction avec des conseils d'experts (chapitre 3). Ces deux chapitres mentionnent une approche unifiée d'approximation DC pour différents problèmes d'optimisation en ligne dont les fonctions objectives sont des fonctions de perte 0-1. Nous étudions comment développer des algorithmes DCA en ligne efficaces en termes d'aspects théoriques et computationnels. La deuxième partie se compose de quatre chapitres (chapitres 4, 5, 6, 7). Après une brève introduction du RL et ses travaux connexes au chapitre 4, le chapitre 5 vise à fournir des techniques efficaces du RL en mode batch basées sur la programmation DC et DCA. Nous considérons quatre différentes formulations d'optimisation DC en RL pour lesquelles des algorithmes correspondants basés sur DCA sont développés. Nous traitons les problèmes clés de DCA et montrons l'efficacité de ces algorithmes au moyen de diverses expériences. En poursuivant cette étude, au chapitre 6, nous développons les techniques du RL basées sur DCA en mode en ligne et proposons leurs versions alternatives. Comme application, nous abordons le problème du plus court chemin stochastique (« stochastic shortest path » en anglais -- SSP) au chapitre 7. Nous étudions une classe particulière de problèmes de SSP qui peut être reformulée comme une formulation de minimisation de cardinalité et une formulation du RL. La première formulation implique la norme zéro et les variables binaires. Nous proposons un algorithme basé sur DCA en exploitant une approche d'approximation DC de la norme zéro et une technique de pénalité exacte pour les variables binaires. Pour la deuxième formulation, nous utilisons un algorithme batch RL basé sur DCA. Tous les algorithmes proposés sont testés sur des réseaux routiers artificiels / In this dissertation, we develop some advanced machine learning techniques in the framework of online learning and reinforcement learning (RL). The backbones of our approaches are DC (Difference of Convex functions) programming and DCA (DC Algorithm), and their online version that are best known as powerful nonsmooth, nonconvex optimization tools. This dissertation is composed of two parts: the first part studies some online machine learning techniques and the second part concerns RL in both batch and online modes. The first part includes two chapters corresponding to online classification (Chapter 2) and prediction with expert advice (Chapter 3). These two chapters mention a unified DC approximation approach to different online learning algorithms where the observed objective functions are 0-1 loss functions. We thoroughly study how to develop efficient online DCA algorithms in terms of theoretical and computational aspects. The second part consists of four chapters (Chapters 4, 5, 6, 7). After a brief introduction of RL and its related works in Chapter 4, Chapter 5 aims to provide effective RL techniques in batch mode based on DC programming and DCA. In particular, we first consider four different DC optimization formulations for which corresponding attractive DCA-based algorithms are developed, then carefully address the key issues of DCA, and finally, show the computational efficiency of these algorithms through various experiments. Continuing this study, in Chapter 6 we develop DCA-based RL techniques in online mode and propose their alternating versions. As an application, we tackle the stochastic shortest path (SSP) problem in Chapter 7. Especially, a particular class of SSP problems can be reformulated in two directions as a cardinality minimization formulation and an RL formulation. Firstly, the cardinality formulation involves the zero-norm in objective and the binary variables. We propose a DCA-based algorithm by exploiting a DC approximation approach for the zero-norm and an exact penalty technique for the binary variables. Secondly, we make use of the aforementioned DCA-based batch RL algorithm. All proposed algorithms are tested on some artificial road networks

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