L’agriculture verticale permet de contrôler presque totalement les conditions pour croître des plantes, qu’il s’agisse des conditions météorologiques, des nutriments nécessaires à la croissance des plantes ou même de la lutte contre les parasites. Il est donc possible de trouver et de définir des paramètres susceptibles d’augmenter le rendement et la qualité des récoltes et de minimiser la consommation d’énergie dans la mesure du possible. À cette fin, ce mémoire présente des algorithmes d’optimisation tels qu’une version améliorée du recuit simulé qui peut être utilisée pour trouver et donner des lignes directrices pour les paramètres de l’agriculture verticale. Nous présentons égalementune contribution sur la façon dont les algorithmes de contrôle, p. ex. l’apprentissage par renforcement profond avec les méthodes critiques d’acteurs, peuvent être améliorés grâce à une exploration plus efficace en prenant en compte de l’incertitude épistémique lors de la sélection des actions. cette contribution peut profiter aux systèmes de contrôle conçus pour l’agriculture verticale. Nous montrons que notre travail est capable de surpasser certains algorithmes utilisés pour l’optimisation et le contrôle continu. / Vertical farming provides a way to have almost total control over agriculture, whether it be controlling weather conditions, nutrients necessary for plant growth, or even pest control. As such, it is possible to find and set parameters that can increase crop yield, and quality, and minimize energy consumption where possible. To that end, this thesis presents optimization algorithms such as an enhanced version of Simulated Annealing that can be used to find and give guidelines for those parameters. We also present work on how real-time control algorithms such as Actor-Critic methods can be made to perform better through more efficient exploration by taking into account epistemic uncertainty during action selection which can also benefit control systems made for vertical farming. We show that our work is able to outperform some algorithms used for optimization and continuous control.

L’efficacité des données est un défi clé pour l’apprentissage par renforcement profond (DRL), limitant souvent son utilisation aux environnements où des quantités illimitées de données simulées sont disponibles. J’envisage une gamme de solutions pour résoudre ce problème. Nous commençons par proposer une méthode permettant d’exploiter des données non étiquetées pour pré-entraîner des représentations qui sont ensuite affinées sur une petite quantité de données spécifiques à la tâche. Pour apprendre des représentations qui capturent divers aspects de la tâche sous-jacente, j’emploie une combinaison de modélisation des dynamiques latentes et de RL conditionné par objectif non supervisé. Cette approche surpasse nettement les travaux antérieurs combinant le pré-entraînement des représentations hors ligne avec l’affinement spécifique à la tâche, et se compare favorablement à d’autres méthodes de pré-entraînement nécessitant des ordres de grandeur plus de données. Nous identifions ensuite et discutons d’un défaut commun des algorithmes de DRL : une tendance à se fier aux interactions précoces et à ignorer les preuves utiles rencontrées plus tard. Les agents de DRL encourent un risque de surapprentissage par rapport aux expériences antérieures, affectant négativement le reste du processus d’apprentissage. Inspirés par les sciences cognitives, je fais référence à cet effet comme étant le biais de primauté. Nous proposons un mécanisme simple mais généralement applicable qui s’attaque au biais de primauté en réinitialisant périodiquement une partie de l’agent. Nous appliquons ce mécanisme aux algorithmes dans les domaines d’action discrets (Atari 100k) et continus (DeepMind Control Suite), améliorant constamment leurs performances. Nous démontrons ensuite que, poussée à l’extrême, cette approche basée sur la réinitialisation permet d’augmenter considérablement les ressources computationnelles même avec des données limitées, un phénomène que j’appelle franchir le mur du ratio de relecture. Les algorithmes basés sur cette stratégie sont capables d’exhiber un apprentissage beaucoup plus efficace que les travaux antérieurs, et permettent dans de nombreux cas un échange libre entre computation et données. Enfin, je conclue en démontrant qu’il est également possible de mettre à l’échelle les réseaux neuronaux utilisés dans le RL efficace en termes de données, simplement en modifiant certains hyperparamètres. En combinaison avec les autres avancées réalisées jusqu’à présent, cela nous permet d’atteindre une efficacité d’apprentissage surhumaine sur Atari 100k même en apprenant purement à partir de zéro et sans utiliser un modèle pour la planification. / Data efficiency is a key challenge for deep reinforcement learning (RL), often limiting its use to settings where unlimited quantities of simulated data are available. I consider a range of solutions to address this problem. I begin by proposing a method to leverage unlabeled data to pretrain representations that are then finetuned on a small amount of task-specific data. To learn representations that capture diverse aspects of the underlying task, I employ a combination of latent dynamics modeling and unsupervised goal-conditioned RL. This approach significantly surpasses prior work combining offline representation pretraining with task-specific finetuning and compares favorably with other pretraining methods that require orders of magnitude more data. I then identify and discuss a common flaw of deep RL algorithms: a tendency to rely on early interactions and ignore useful evidence encountered later. Deep RL agents incur a risk of overfitting to earlier experiences, negatively affecting the rest of the learning process. Inspired by cognitive science, I refer to this effect as the primacy bias. I propose a simple yet generally applicable mechanism that tackles the primacy bias by periodically resetting a part of the agent. I apply this mechanism to algorithms in both discrete (Atari 100k) and continuous action (DeepMind Control Suite) domains, consistently improving their performance. I then demonstrate that when taken to the extreme, this reset-based approach allows computational resources to be scaled up enormously even with limited data, a phenomenon which I call breaking the replay ratio barrier. Algorithms based on this strategy are able to exhibit far more efficient learning than prior work and allow computation and data to be freely exchanged in many cases. Finally, I conclude by demonstrating that it is also possible to scale up the neural networks used in sample-efficient RL, simply by changing certain hyperparameters. In combination with the other advances made so far, this allows us to achieve super-human learning efficiency on Atari 100k even when learning purely from scratch and not using a model for planning.

Cette thèse tente de construire de meilleurs agents d'apprentissage par renforcement (RL) en tirant parti de l'apprentissage auto-supervisé. Il se présente sous la forme d'une thèse par article qui contient trois travaux. Dans le premier article, nous construisons un benchmark basé sur les jeux Atari pour évaluer systématiquement les méthodes d'apprentissage auto-supervisé dans les environnements RL. Nous comparons un éventail de ces méthodes à travers une suite de tâches de sondage pour identifier leurs forces et leurs faiblesses. Nous montrons en outre qu'une nouvelle méthode contrastive ST-DIM excelle à capturer la plupart des facteurs génératifs dans les environnements étudiés, sans avoir besoin de s'appuyer sur des étiquettes ou des récompenses. Dans le deuxième article, nous proposons des représentations auto-prédictives (SPR) qui apprennent un modèle latent auto-supervisé de la dynamique de l'environnement parallèlement à la résolution de la tâche RL en cours. Nous montrons que SPR réalise des améliorations spectaculaires dans l'état de l'art sur le benchmark Atari 100k difficile où les agents n'ont droit qu'à 2 heures d'expérience en temps réel. Le troisième article étudie le rôle de la RL basée sur un modèle et de l'apprentissage auto-supervisé dans le contexte de la généralisation en RL. Grâce à des contrôles minutieux, nous montrons que la planification et l'apprentissage de représentation basé sur un modèle contribuent tous deux à une meilleure généralisation pour l'agent Muzero. Nous améliorons encore MuZero avec des objectifs d'apprentissage auto-supervisés auxiliaires, et montrons que cet agent MuZero++ obtient des résultats de pointe sur les benchmarks Procgen et Metaworld. / This thesis tries to build better Reinforcement Learning (RL) agents by leveraging self-supervised learning. It is presented as a thesis by article that contains three pieces of work. In the first article, we construct a benchmark based on Atari games to systematically evaluate self-supervised learning methods in RL environments. We compare an array of such methods across a suite of probing tasks to identify their strengths and weaknesses. We further show that a novel contrastive method ST-DIM excels at capturing most generative factors in the studied environments, without needing to rely on labels or rewards. In the second article, we propose Self-Predictive Representations (SPR) that learns a self-supervised latent model of the environment dynamics alongside solving the RL task at hand. We show that SPR achieves dramatic improvements in state-of-the-art on the challenging Atari 100k benchmark where agents are allowed only 2 hours of real-time experience. The third article studies the role of model-based RL and self-supervised learning in the context of generalization in RL. Through careful controls, we show that planning and model-based representation learning both contribute towards better generalization for the Muzero agent. We further improve MuZero with auxiliary self-supervised learning objectives, and show that this MuZero++ agent achieves state-of-the-art results on the Procgen and Metaworld benchmarks.

The primary goal of this work is to propose a methodology for discovering hyperparameters. Hyperparameters aid systems in convergence when well-tuned and handcrafted. However, to this end, poorly chosen hyperparameters leave practitioners in limbo, between concerns with implementation or improper choice in hyperparameter and system configuration. We specifically analyze the choice of learning rate in stochastic gradient descent (SGD), a popular algorithm. As a secondary goal, we attempt the discovery of fixed points using smoothing of the loss landscape by exploiting assumptions about its distribution to improve the update rule in SGD. Smoothing of the loss landscape has been shown to make convergence possible in large-scale systems and difficult black-box optimization problems. However, we use stochastic value gradients (SVG) to smooth the loss landscape by learning a surrogate model and then backpropagate through this model to discover fixed points on the real task SGD is trying to solve. Additionally, we construct a gym environment for testing model-free algorithms, such as Proximal Policy Optimization (PPO) as a hyperparameter optimizer for SGD. For tasks, we focus on a toy problem and analyze the convergence of SGD on MNIST using model-free and model-based reinforcement learning methods for control. The model is learned from the parameters of the true optimizer and used specifically for learning rates rather than for prediction. In experiments, we perform in an online and offline setting. In the online setting, we learn a surrogate model alongside the true optimizer, where hyperparameters are tuned in real-time for the true optimizer. In the offline setting, we show that there is more potential in the model-based learning methodology than in the model-free configuration due to this surrogate model that smooths out the loss landscape and makes for more helpful gradients during backpropagation. / L’objectif principal de ce travail est de proposer une méthodologie de découverte des hyperparamètres. Les hyperparamètres aident les systèmes à converger lorsqu’ils sont bien réglés et fabriqués à la main. Cependant, à cette fin, des hyperparamètres mal choisis laissent les praticiens dans l’incertitude, entre soucis de mise en oeuvre ou mauvais choix d’hyperparamètre et de configuration du système. Nous analysons spécifiquement le choix du taux d’apprentissage dans la descente de gradient stochastique (SGD), un algorithme populaire. Comme objectif secondaire, nous tentons de découvrir des points fixes en utilisant le lissage du paysage des pertes en exploitant des hypothèses sur sa distribution pour améliorer la règle de mise à jour dans SGD. Il a été démontré que le lissage du paysage des pertes rend la convergence possible dans les systèmes à grande échelle et les problèmes difficiles d’optimisation de la boîte noire. Cependant, nous utilisons des gradients de valeur stochastiques (SVG) pour lisser le paysage des pertes en apprenant un modèle de substitution, puis rétropropager à travers ce modèle pour découvrir des points fixes sur la tâche réelle que SGD essaie de résoudre. De plus, nous construisons un environnement de gym pour tester des algorithmes sans modèle, tels que Proximal Policy Optimization (PPO) en tant qu’optimiseur d’hyperparamètres pour SGD. Pour les tâches, nous nous concentrons sur un problème de jouet et analysons la convergence de SGD sur MNIST en utilisant des méthodes d’apprentissage par renforcement sans modèle et basées sur un modèle pour le contrôle. Le modèle est appris à partir des paramètres du véritable optimiseur et utilisé spécifiquement pour les taux d’apprentissage plutôt que pour la prédiction. Dans les expériences, nous effectuons dans un cadre en ligne et hors ligne. Dans le cadre en ligne, nous apprenons un modèle de substitution aux côtés du véritable optimiseur, où les hyperparamètres sont réglés en temps réel pour le véritable optimiseur. Dans le cadre hors ligne, nous montrons qu’il y a plus de potentiel dans la méthodologie d’apprentissage basée sur un modèle que dans la configuration sans modèle en raison de ce modèle de substitution qui lisse le paysage des pertes et crée des gradients plus utiles lors de la rétropropagation.

Dans cette thèse, nous avons étudié les problèmes de décisions séquentielles, avec comme application la gestion de stocks d'énergie. Traditionnellement, ces problèmes sont résolus par programmation dynamique stochastique. Mais la grande dimension, et la non convexité du problème, amènent à faire des simplifications sur le modèle pour pouvoir faire fonctionner ces méthodes. Nous avons donc étudié une méthode alternative, qui ne requiert pas de simplifications du modèle: Monte Carlo Tree Search (MCTS). Nous avons commencé par étendre le MCTS classique (qui s'applique aux domaines finis et déterministes) aux domaines continus et stochastiques. Pour cela, nous avons utilisé la méthode de Double Progressive Widening (DPW), qui permet de gérer le ratio entre largeur et profondeur de l'arbre, à l'aide de deux méta paramètres. Nous avons aussi proposé une heuristique nommée Blind Value (BV) pour améliorer la recherche de nouvelles actions, en utilisant l'information donnée par les simulations passées. D'autre part, nous avons étendu l'heuristique RAVE aux domaines continus. Enfin, nous avons proposé deux nouvelles méthodes pour faire remonter l'information dans l'arbre, qui ont beaucoup amélioré la vitesse de convergence sur deux cas tests. Une part importante de notre travail a été de proposer une façon de mêler MCTS avec des heuristiques rapides pré-existantes. C'est une idée particulièrement intéressante dans le cas de la gestion d'énergie, car ces problèmes sont pour le moment résolus de manière approchée. Nous avons montré comment utiliser Direct Policy Search (DPS) pour rechercher une politique par défaut efficace, qui est ensuite utilisée à l'intérieur de MCTS. Les résultats expérimentaux sont très encourageants. Nous avons aussi appliqué MCTS à des processus markoviens partiellement observables (POMDP), avec comme exemple le jeu de démineur. Dans ce cas, les algorithmes actuels ne sont pas optimaux, et notre approche l'est, en transformant le POMDP en MDP, par un changement de vecteur d'état. Enfin, nous avons utilisé MCTS dans un cadre de méta-bandit, pour résoudre des problèmes d'investissement. Le choix d'investissement est fait par des algorithmes de bandits à bras multiples, tandis que l'évaluation de chaque bras est faite par MCTS. Une des conclusions importantes de ces travaux est que MCTS en continu a besoin de très peu d'hypothèses (uniquement un modèle génératif du problème), converge vers l'optimum, et peut facilement améliorer des méthodes suboptimales existantes.

Une question fondamentale en neuroscience, ainsi que dans de nombreuses disciplines s’intéressant à la compréhension du comportement, telles que la psychologie, l’Economie, et la sociologie, concerne les processus décisionnels par lesquels les animaux et les humains sélectionnent des actions renforcées positivement ou négativement. Les processus décisionnels ainsi que leur base neuronale demeurent mal compris. D’autre part de nombreuses études ont révélé que les humains ainsi que les animaux prennent souvent des décisions sous-optimales. Notre principal objectif a été de comprendre la raison de ces comportements sous-optimaux. Par ailleurs, l’altération des processus sous-tendant la prise de décision, entraîne des pathologies. La compréhension des mécanismes décisionnels est essentielle au développement de stratégies de traitements plus efficaces. Dans cette étude nous avons proposé une nouvelle approche de l’étude des comportements décisionnels, basée sur l’hétérogénéité des préférences créées au cours de l’apprentissage du choix. Puis nous avons corrélé l’activité du putamen et du globus pallidus interne aux comportements préalablement décrits. Nos résultats montrent que bien que les primates apprennent à identifier la meilleure option et convergent vers une stratégie optimale dans un nombre important de sessions, ils n’arrivent pas en moyenne à optimiser leur comportement. Nous avons montré que ce comportement suboptimal des primates est caractérisé par la création de préférences irrationnelles par ces derniers pour des paramètres non pertinents de l’environnement. Nous avons finalement montré que bien qu’un faible nombre de neurones du putamen encode la valeur de l’action, leur contribution à l’activité de population est faible. L’activité du putamen reflète les futures performances des primates et prédit donc la formation des comportements irrationnels et rationnels. / A fundamental question in neuroscience, as well as in various fields such as economics, psychology and sociology, concerns the decision making processes by which animals and humans select actions based on reward and punishment. Both decision making processes and their neural basis are still poorly understood. Also, both human and animals often make suboptimal decisions in many tasks studied. Our first aim is to improve the understanding of why such sub-optimal decisions are made. Also, the alteration of decision making processes causes diseases, the understanding of whose mechanisms is essential in developing better treatment strategies. In this report, we propose a new approach which consists in extracting the neural substrates of choice behavior heterogeneity in between sessions. Our results show that although primates learn on average to identify the best option and converge to an optimal policy in a consequent number of sessions, they fail on average to optimize their behavior. We revealed that this suboptimal behavior was characterized by an unexpected high behavioral heterogeneity during the task that was due to the creation of irrelevant preferences by the monkeys. We finally show that although a few neurons of the putamen encode the action value, their contribution to the overall population activity is weak. Putamen activity rather reflects the futures performances and predicts the creation of rational and irrational behaviors.

Cette thèse aborde le problème de classification en apprentissage statistique sous un angle nouveau en rajoutant une dimension séquentielle au processus de classification. En particulier, nous nous intéressons au cas de l'apprentissage à contraintes de budget (ou apprentissage budgété) où l'objectif est de concevoir un classifieur qui, tout en apportant des prédictions correctes, doit gérer un budget computationnel, consommé au fur et à mesure que les différents attributs sont acquis ou évalués. Les attributs peuvent avoir des coûts d'acquisition différents et il arrive souvent que les attributs les plus discriminatifs soient les plus coûteux. Le diagnostic médical et le classement de pages web sont des exemples typiques d'applications de l'apprentissage budgété. Pour le premier, l'objectif est de limiter le nombre de tests médicaux que le patient doit endurer et, pour le second, le classement doit se faire dans un temps assez court pour ne pas faire fuir l'usager. Au cours de cette thèse, nous nous sommes intéressés à des contraintes de budget atypiques, que la conception de trigger nous a motivés à investiguer. Les triggers sont un type de classifieurs rapides, temps-réel et sensibles aux coûts qui ont pour objectif de filtrer les données massives que les accélérateurs de particules produisent et d'en retenir les événements les plus susceptibles de contenir le phénomène étudié, afin d'être enregistrés pour des analyses ultérieures. La conception de trigger impose des contraintes computationnelles strictes lors de la classification mais, surtout, exhibe des schémas complexes de calcul du coût de chaque attributs. Certains attributs sont dépendants d'autres attributs et nécessitent de calculer ces derniers en amont, ce qui a pour effet d'augmenter le coût de la classification. De plus, le coût des attributs peut directement dépendre de leur valeur concrète. On retrouve ce cas de figure lorsque les extracteurs d'attributs améliorent la qualité de leur sortie avec le temps mais peuvent toujours apporter des résultats préliminaires. Enfin, les observations sont regroupées en sacs et, au sein du même sac, certaines observations partagent le calcul d'un sous-ensemble d'attributs. Toutes ces contraintes nous ont amenés à formaliser la classification sous un angle séquentiel.Dans un premier temps, nous proposons un nouveau cadriciel pour la classification rapide en convertissant le problème initial de classification en un problème de prise décision. Cette reformulation permet d'un part d'aborder la séquentialité de manière explicite, ce qui a pour avantage de pouvoir aisément incorporer les différentes contraintes que l'on retrouve dans les applications réelles, mais aussi d'avoir à disposition toute une palette d'algorithmes d'apprentissage par renforcement pour résoudre le nouveau problème. Dans une seconde partie, nous appliquons notre modèle de classification séquentielle à un problème concret d'apprentissage à contraintes de budget et démontrant les bénéfices de notre approche sur des données simulées (à partir de distributions simplifiées) de l'expérience LHCb (CERN). / Classification in machine learning has been extensively studied during the pastdecades. Many solutions have been proposed to output accurate classifiers and toobtain statistical grantees on the unseen observations. However, when machinelearning algorithms meet concrete industrial or scientific applications, new computationalcriteria appear to be as important to satisfy as those of classificationaccuracy. In particular, when the output classifier must comply with a computationalbudget needed to obtain the features that are evaluated at test time, wetalk about “budgeted” learning. The features can have different acquisition costsand, often, the most discriminative features are the costlier. Medical diagnosis andweb-page ranking, for instance, are typical applications of budgeted learning. Inthe former, the goal is to limit the number of medical tests evaluate for patients,and in the latter, the ranker has limited time to order documents before the usergoes away.This thesis introduces a new way of tackling classification in general and budgetedlearning problems in particular, through a novel framework lying in theintersection of supervised learning and decision theory. We cast the classificationproblem as a sequential decision making procedure and show that this frameworkyields fast and accurate classifiers. Unlike classical classification algorithms thatoutput a “one-shot” answer, we show that considering the classification as a seriesof small steps wherein the information is gathered sequentially also providesa flexible framework that allows to accommodate different types of budget constraintsin a “natural” way. In particular, we apply our method to a novel type ofbudgeted learning problems motivated by particle physics experiments. The particularityof this problem lies in atypical budget constraints and complex cost calculationschemata where the calculation of the different features depends on manyfactors. We also review similar sequential approaches that have recently known aparticular interest and provide a global perspective on this new paradigm.

Depuis son introduction pour le jeu de Go, Monte Carlo Tree Search (MCTS) a été appliqué avec succès à d'autres jeux et a ouvert la voie à une famille de nouvelles méthodes comme Mutilple-MCTS ou Nested Monte Carlo. MCTS évalue un ensemble de situations de jeu à partir de milliers de fins de parties générées aléatoirement. À mesure que les simulations sont produites, le programme oriente dynamiquement sa recherche vers les coups les plus prometteurs. En particulier, MCTS a suscité l'intérêt de la communauté car elle obtient de remarquables performances sans avoir pour autant recours à de nombreuses connaissances expertes a priori. Dans cette thèse, nous avons choisi d'aborder MCTS comme un système apprenant à part entière. Les simulations sont alors autant d'expériences vécues par le système et les résultats sont autant de renforcements. L'apprentissage du système résulte alors de la complexe interaction entre deux composantes : l'acquisition progressive de représentations et la mobilisation de celles-ci lors des futures simulations. Dans cette optique, nous proposons deux approches indépendantes agissant sur chacune de ces composantes. La première approche accumule des représentations complémentaires pour améliorer la vraisemblance des simulations. La deuxième approche concentre la recherche autour d'objectifs intermédiaires afin de renforcer la qualité des représentations acquises. Les méthodes proposées ont été appliquées aux jeu de Go et du Clobber solitaire impartial. La dynamique acquise par le système lors des expérimentations illustre la relation entre ces deux composantes-clés de l'apprentissage / Monte Carlo Tree Search (MCTS) has been initially introduced for the game of Go but has now been applied successfully to other games and opens the way to a range of new methods such as Multiple-MCTS or Nested Monte Carlo. MCTS evaluates game states through thousands of random simulations. As the simulations are carried out, the program guides the search towards the most promising moves. MCTS achieves impressive results by this dynamic, without an extensive need for prior knowledge. In this thesis, we choose to tackle MCTS as a full learning system. As a consequence, each random simulation turns into a simulated experience and its outcome corresponds to the resulting reinforcement observed. Following this perspective, the learning of the system results from the complex interaction of two processes : the incremental acquisition of new representations and their exploitation in the consecutive simulations. From this point of view, we propose two different approaches to enhance both processes. The first approach gathers complementary representations in order to enhance the relevance of the simulations. The second approach focuses the search on local sub-goals in order to improve the quality of the representations acquired. The methods presented in this work have been applied to the games of Go and Impartial Solitaire Clobber. The results obtained in our experiments highlight the significance of these processes in the learning dynamic and draw up new perspectives to enhance further learning systems such as MCTS

Cette thèse s'intéresse aux méthodes d'itération sur les politiques dans l'apprentissage par renforcement à grand espace d'états avec approximation linéaire de la fonction de valeur. Nous proposons d'abord une unification des principaux algorithmes du contrôle optimal stochastique. Nous montrons la convergence de cette version unifiée vers la fonction de valeur optimale dans le cas tabulaire, ainsi qu'une garantie de performances dans le cas où la fonction de valeur est estimée de façon approximative. Nous étendons ensuite l'état de l'art des algorithmes d'approximation linéaire du second ordre en proposant une généralisation de Least-Squares Policy Iteration (LSPI) (Lagoudakis et Parr, 2003). Notre nouvel algorithme, Least-Squares [lambda] Policy Iteration (LS[lambda]PI), ajoute à LSPI un concept venant de [lambda]-Policy Iteration (Bertsekas et Ioffe, 1996) : l'évaluation amortie (ou optimiste) de la fonction de valeur, qui permet de réduire la variance de l'estimation afin d'améliorer l'efficacité de l'échantillonnage. LS[lambda]PI propose ainsi un compromis biais-variance réglable qui peut permettre d'améliorer l'estimation de la fonction de valeur et la qualité de la politique obtenue. Dans un second temps, nous nous intéressons en détail au jeu de Tetris, une application sur laquelle se sont penchés plusieurs travaux de la littérature. Tetris est un problème difficile en raison de sa structure et de son grand espace d'états. Nous proposons pour la première fois une revue complète de la littérature qui regroupe des travaux d'apprentissage par renforcement, mais aussi des techniques de type évolutionnaire qui explorent directement l'espace des politiques et des algorithmes réglés à la main. Nous constatons que les approches d'apprentissage par renforcement sont à l'heure actuelle moins performantes sur ce problème que des techniques de recherche directe de la politique telles que la méthode d'entropie croisée (Szita et Lorincz, 2006). Nous expliquons enfin comment nous avons mis au point un joueur de Tetris qui dépasse les performances des meilleurs algorithmes connus jusqu'ici et avec lequel nous avons remporté l'épreuve de Tetris de la Reinforcement Learning Competition 2008 / This thesis studies policy iteration methods with linear approximation of the value function for large state space problems in the reinforcement learning context. We first introduce a unified algorithm that generalizes the main stochastic optimal control methods. We show the convergence of this unified algorithm to the optimal value function in the tabular case, and a performance bound in the approximate case when the value function is estimated. We then extend the literature of second-order linear approximation algorithms by proposing a generalization of Least-Squares Policy Iteration (LSPI) (Lagoudakis and Parr, 2003). Our new algorithm, Least-Squares [lambda] Policy Iteration (LS[lambda]PI), adds to LSPI an idea of [lambda]-Policy Iteration (Bertsekas and Ioffe, 1996): the damped (or optimistic) evaluation of the value function, which allows to reduce the variance of the estimation to improve the sampling efficiency. Thus, LS[lambda]PI offers a bias-variance trade-off that may improve the estimation of the value function and the performance of the policy obtained. In a second part, we study in depth the game of Tetris, a benchmark application that several works from the literature attempt to solve. Tetris is a difficult problem because of its structure and its large state space. We provide the first full review of the literature that includes reinforcement learning works, evolutionary methods that directly explore the policy space and handwritten controllers. We observe that reinforcement learning is less successful on this problem than direct policy search approaches such as the cross-entropy method (Szita et Lorincz, 2006). We finally show how we built a controller that outperforms the previously known best controllers, and shortly discuss how it allowed us to win the Tetris event of the 2008 Reinforcement Learning Competition

Cette thèse s'intéresse à des problèmes de prise de décision séquentielle dans lesquels l'acquisition d'information est une fin en soi. Plus précisément, elle cherche d'abord à savoir comment modifier le formalisme des POMDP pour exprimer des problèmes de collecte d'information et à proposer des algorithmes pour résoudre ces problèmes. Cette approche est alors étendue à des tâches d'apprentissage par renforcement consistant à apprendre activement le modèle d'un système. De plus, cette thèse propose un nouvel algorithme d'apprentissage par renforcement bayésien, lequel utilise des transitions locales optimistes pour recueillir des informations de manière efficace tout en optimisant la performance escomptée. Grâce à une analyse de l'existant, des résultats théoriques et des études empiriques, cette thèse démontre que ces problèmes peuvent être résolus de façon optimale en théorie, que les méthodes proposées sont presque optimales, et que ces méthodes donnent des résultats comparables ou meilleurs que des approches de référence. Au-delà de ces résultats concrets, cette thèse ouvre la voie (1) à une meilleure compréhension de la relation entre la collecte d'informations et les politiques optimales dans les processus de prise de décision séquentielle, et (2) à une extension des très nombreux travaux traitant du contrôle de l'état d'un système à des problèmes de collecte d'informations / The purpose of this dissertation is to study sequential decision problems where acquiring information is an end in itself. More precisely, it first covers the question of how to modify the POMDP formalism to model information-gathering problems and which algorithms to use for solving them. This idea is then extended to reinforcement learning problems where the objective is to actively learn the model of the system. Also, this dissertation proposes a novel Bayesian reinforcement learning algorithm that uses optimistic local transitions to efficiently gather information while optimizing the expected return. Through bibliographic discussions, theoretical results and empirical studies, it is shown that these information-gathering problems are optimally solvable in theory, that the proposed methods are near-optimal solutions, and that these methods offer comparable or better results than reference approaches. Beyond these specific results, this dissertation paves the way (1) for understanding the relationship between information-gathering and optimal policies in sequential decision processes, and (2) for extending the large body of work about system state control to information-gathering problems