En Europe, la présence de grands carnivores dans des paysages anthropisés entraîne une forte compétition avec l'homme et alimente d'importantes polémiques concernant leur protection légale. La perception antagoniste de ces espèces à la fois emblématiques pour certains et sources de conflits pour d'autres, rend la gestion de leurs populations très délicate. Depuis la recolonisation spontanée du loup (Canis lupus) dans les Alpes françaises au début des années 1990, la population s'est accrue numériquement et spatialement. Parallèlement, les dégâts occasionnés par le loup sur la filière élevage ont suivi la même tendance. L'Etat met en place aujourd'hui un contrôle raisonné de la population, sous réserve que les objectifs de conservation, exigés par la Directive Habitat, soient respectés. En s'inspirant du cas d'étude du loup en France, nous proposons dans cette thèse un cadre de prise de décision structurée adapté pour la gestion et la conservation d'espèces rares et difficilement observables, protégées par des accords législatifs mais qui, dans un contexte social conflictuel, peuvent être régulées. La modélisation séquentielle du processus décisionnel s'est déroulée dans un contexte de forte incertitude selon plusieurs étapes : 1) appréhender les objectifs de conservation et/ou contrôle du loup en France pour les formaliser sous forme mathématique via une fonction d'utilité, 2) suivre la population par une méthode non-invasive pour définir des indicateurs de gestion fiables et évaluer le statut de conservation de la population, 3) coupler les mesures létales adoptées actuellement à un modèle démographique décrivant la dynamique du loup et intégrant sa structure sociale, 4) et déterminer la décision. Cette dernière étape est réalisée à l'aide d'une méthode d'optimisation qui calcule la stratégie optimale de gestion en fonction de la structure sociale de la population et des différentes sources d'incertitude accumulées à chaque étape du processus décisionnel. Nous avons choisi comme indicateur de gestion le taux de croissance, à partir duquel nous avons défini l'utilité. Cet indicateur était robuste à l'incertitude d'échantillonnage émergeant de la détection partielle et hétérogène des individus. Des analyses de sensibilité de la décision ont montré une forte influence de la fonction d'utilité sur la stratégie optimale, soulignant ainsi l'importance de définir correctement les objectifs. Nous avons également montré que la stratégie optimale était sensible aux variations des paramètres démographiques, montrant ainsi l'intérêt des méthodes de capture-marquage-recapture pour les estimer correctement. Nous discutons enfin de l'extension de notre approche à un cadre décisionnel de gestion adaptative pour traiter des problèmes de conservation dans un contexte conflictuel. / Large carnivore management in Europe is controversial because of conflictive objectives arising from the legal protection of threatened species vs. the possible necessity of culling individuals to prevent severe damages on human activities. Since the wolf recovery in the French Alps in the early 90's, the population has been numerically and spatially increasing. In parallel, livestock depredations have been following the same trend. As an EU member state, France is bound to the European Habitat Directive, which provides full protection of wolf populations and their habitat. Nevertheless, derogatory killings are allowed for individuals causing problems on livestock and some lethal control is now incorporated into the national management plan, as long as the population growth and its distribution range are not being threatened. Illustrating with the case study of the wolf in France, my dissertation proposes a structured decision making framework for the management and the conservation of elusive species that are legally protected but, in a conflictive context, are subject to population control. The sequential modeling of our decision process occurred in the following steps: 1) define the multiple objectives and formulate them in terms of a utility function, 2) monitor the population through a non-invasive approach in order to define the population conservation status, 3) build a demographic model to predict the consequences of harvesting on population dynamics and social structure, 4) obtain optimal state-dependent decisions. The last step is done with stochastic dynamic programming (SDP), acknowledged to be one of the most useful optimization methods in decision making. We provide an optimal solution for wolf management that gives the highest chance of meeting objectives, defined on population growth rate. This demographic indicator was found to be robust to sampling uncertainty arising from partial and heterogeneous detection of individuals. We ran decision sensibility analyses and found a strong effect of the utility function on the optimal strategy, highlighting the importance of defining explicit objectives. We also found that the optimal strategy was sensitive to demographic parameters, which demonstrate the general need of using solid statistical approaches to estimate them properly. This structured decision making framework can further be extended to adaptive management, acknowledged as being a convenient framework for wildlife management.

En planification théorique de la décision, le cadre des Processus Décisionnels Markoviens Factorisés (Factored Markov Decision Process, FMDP) a produit des algorithmes efficaces de résolution des problèmes de décisions séquentielles dans l'incertain. L'efficacité de ces algorithmes repose sur des structures de données telles que les Arbres de Décision ou les Diagrammes de Décision Algébriques (ADDs). Ces techniques de planification sont utilisées en Apprentissage par Renforcement par l'architecture SDYNA afin de résoudre des problèmes inconnus de grandes tailles. Toutefois, l'état-de-l'art des algorithmes d'apprentissage, de programmation dynamique et d'apprentissage par renforcement utilisés par SDYNA, requière que le problème soit spécifié uniquement à l'aide de variables binaires et/ou utilise des structures améliorables en termes de compacité. Dans ce manuscrit, nous présentons nos travaux de recherche visant à élaborer et à utiliser une structure de donnée plus efficace et moins contraignante, et à l'intégrer dans une nouvelle instance de l'architecture SDYNA. Dans une première partie, nous présentons l'état-de-l'art de la modélisation de problèmes de décisions séquentielles dans l'incertain à l'aide de FMDP. Nous abordons en détail la modélisation à l'aide d'DT et d'ADDs.Puis nous présentons les ORFGs, nouvelle structure de données que nous proposons dans cette thèse pour résoudre les problèmes inhérents aux ADDs. Nous démontrons ainsi que les ORFGs s'avèrent plus efficaces que les ADDs pour modéliser les problèmes de grandes tailles. Dans une seconde partie, nous nous intéressons à la résolution des problèmes de décision dans l'incertain par Programmation Dynamique. Après avoir introduit les principaux algorithmes de résolution, nous nous attardons sur leurs variantes dans le domaine factorisé. Nous précisons les points de ces variantes factorisées qui sont améliorables. Nous décrivons alors une nouvelle version de ces algorithmes qui améliore ces aspects et utilise les ORFGs précédemment introduits. Dans une dernière partie, nous abordons l'utilisation des FMDPs en Apprentissage par Renforcement. Puis nous présentons un nouvel algorithme d'apprentissage dédié à la nouvelle structure que nous proposons. Grâce à ce nouvel algorithme, une nouvelle instance de l'architecture SDYNA est proposée, se basant sur les ORFGs ~:~l'instance SPIMDDI. Nous testons son efficacité sur quelques problèmes standards de la littérature. Enfin nous présentons quelques travaux de recherche autour de cette nouvelle instance. Nous évoquons d'abord un nouvel algorithme de gestion du compromis exploration-exploitation destiné à simplifier l'algorithme F-RMax. Puis nous détaillons une application de l'instance SPIMDDI à la gestion d'unités dans un jeu vidéo de stratégie en temps réel. / In decision theoretic planning, the factored framework (Factored Markovian Decision Process, FMDP) has produced several efficient algorithms in order to resolve large sequential decision making under uncertainty problems. The efficiency of this algorithms relies on data structures such as decision trees or algebraïc decision diagrams (ADDs). These planification technics are exploited in Reinforcement Learning by the architecture SDyna in order to resolve large and unknown problems. However, state-of-the-art learning and planning algorithms used in SDyna require the problem to be specified uniquely using binary variables and/or to use improvable data structure in term of compactness. In this book, we present our research works that seek to elaborate and to use a new data structure more efficient and less restrictive, and to integrate it in a new instance of the SDyna architecture. In a first part, we present the state-of-the-art modeling tools used in the algorithms that tackle large sequential decision making under uncertainty problems. We detail the modeling using decision trees and ADDs. Then we introduce the Ordered and Reduced Graphical Representation of Function, a new data structure that we propose in this thesis to deal with the various problems concerning the ADDs. We demonstrate that ORGRFs improve on ADDs to model large problems. In a second part, we go over the resolution of large sequential decision under uncertainty problems using Dynamic Programming. After the introduction of the main algorithms, we see in details the factored alternative. We indicate the improvable points of these factored versions. We describe our new algorithm that improve on these points and exploit the ORGRFs previously introduced. In a last part, we speak about the use of FMDPs in Reinforcement Learning. Then we introduce a new algorithm to learn the new datastrcture we propose. Thanks to this new algorithm, a new instance of the SDyna architecture is proposed, based on the ORGRFs : the SPIMDDI instance. We test its efficiency on several standard problems from the litterature. Finally, we present some works around this new instance. We detail a new algorithm for efficient exploration-exploitation compromise management, aiming to simplify F-RMax. Then we speak about an application of SPIMDDI to the managements of units in a strategic real time video game.

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. / In this thesis, we study sequential decision making problems, with a focus on the unit commitment problem. Traditionally solved by dynamic programming methods, this problem is still a challenge, due to its high dimension and to the sacrifices made on the accuracy of the model to apply state of the art methods. We investigate on the applicability of Monte Carlo Tree Search methods for this problem, and other problems that are single player, stochastic and continuous sequential decision making problems. We started by extending the traditional finite state MCTS to continuous domains, with a method called Double Progressive Widening (DPW). This method relies on two hyper parameters, and determines the ratio between width and depth in the nodes of the tree. We developed a heuristic called Blind Value (BV) to improve the exploration of new actions, using the information from past simulations. We also extended the RAVE heuristic to continuous domain. Finally, we proposed two new ways of backing up information through the tree, that improved the convergence speed considerably on two test cases.An important part of our work was to propose a way to mix MCTS with existing powerful heuristics, with the application to energy management in mind. We did so by proposing a framework that allows to learn a good default policy by Direct Policy Search (DPS), and to include it in MCTS. The experimental results are very positive.To extend the reach of MCTS, we showed how it could be used to solve Partially Observable Markovian Decision Processes, with an application to game of Mine Sweeper, for which no consistent method had been proposed before.Finally, we used MCTS in a meta-bandit framework to solve energy investment problems: the investment decision was handled by classical bandit algorithms, while the evaluation of each investment was done by MCTS.The most important take away is that continuous MCTS has almost no assumption (besides the need for a generative model), is consistent, and can easily improve existing suboptimal solvers by using a method similar to what we proposed with DPS.