Les problèmes d’investissements d’énergie sont difficiles à cause des incertitudes. Certaines incertitudes peuvent être modélisées par les probabilités. Mais il y a des problèmes difficiles tels que l'évolution de technologie et la pénalisation de CO2, délicats à modéliser par des probabilités. Aussi, les travaux sur l’optimisation des systèmes d’énergie est souvent déterministe. Cette thèse s’intéresse à appliquer l’optimisation bruitée aux systèmes d’énergie. Cette thèse se concentre sur trois parties principales: les études des méthodes pour gérer le bruit, y compris utiliser des méthodes de ré-échantillonnage pour améliorer la vitesse de convergence; les applications des méthodes de portefeuilles à l’optimisation bruitée dans le continu; les applications des méthodes de portefeuilles aux cas avec incertitudes pour la planification des investissements d’énergie et aux jeux, y compris l’utilisation de l’algorithme de bandit adversarial pour calculer l’équilibre de Nash d'un jeu matriciel à somme nulle et l’utilisation de “sparsity” pour accélérer le calcul de l’équilibre de Nash. / This manuscript concentrates in studying methods to handle the noise, including using resampling methods to improve the convergence rates and applying portfolio methods to cases with uncertainties (games, and noisy optimization in continuous domains).Part I will introduce the manuscript, then review the state of the art in noisy optimization, portfolio algorithm, multi-armed bandit algorithms and games.Part II concentrates on the work on noisy optimization:∙ Chapter 4 provides a generic algorithm for noisy optimization recovering most of the existing bounds in one single noisy optimization algorithm.∙ Chapter5 applies different resampling rules in evolution strategies for noisy optimization, without the assumption of variance vanishing in the neighborhood of the optimum, and shows mathematically log-log convergence results and studies experimentally the slope of this convergence.∙ Chapter 6 compares resampling rules used in the differential evolution algorithm for strongly noisy optimization. By mathematical analysis, a new rule is designed for choosing the number of resamplings, as a function of the dimension, and validate its efficiency compared to existing heuristics - though there is no clear improvement over other empirically derived rules.∙ Chapter 7 applies “common random numbers”, also known as pairing, to an intermediate case between black-box and white-box cases for improving the convergence.Part III is devoted to portfolio in adversarial problems:∙ Nash equilibria are cases in which combining pure strategies is necessary for designing optimal strategies. Two chapters are dedicated to the computation of Nash equilibria:– Chapter 9 investigates combinations of pure strategies, when a small set of pure strategies is concerned; basically, we get improved rates when the support of the Nash equilibrium is small.– Chapter 10 applies these results to a power system problem. This compares several bandit algorithms for Nash equilibria, defines parameter-free bandit algorithms, and shows the relevance of the sparsity approach dis- cussed in Chapter 9.∙ Then, two chapters are dedicated to portfolios of game methods:– Chapter 11 shows how to generate multiple policies, from a single one, when only one such policy is available. This kind of bootstrap (based on random seeds) generates many deterministic policies, and then combines them into one better policy. This has been tested on several games.– Chapter 12 extends chapter 11 by combining policies in a position-specific manner. In particular, we get a better asymptotic behavior than MCTS.Part IV is devoted to portfolios in noisy optimization:∙ Chapter 14 is devoted to portfolio of noisy optimization methods in continuous domains;∙ Chapter 15 proposed differential evolution as a tool for non- stationary bandit problems.

Cette thèse montre des contributions à l'analyse d'algorithmes pour l'optimisation de fonctions bruitées. Les taux de convergences (regret simple et regret cumulatif) sont analysés pour les algorithmes de recherche linéaire ainsi que pour les algorithmes de recherche aléatoires. Nous prouvons que les algorithmes basé sur la matrice hessienne peuvent atteindre le même résultat que certaines algorithmes optimaux, lorsque les paramètres sont bien choisis. De plus, nous analysons l'ordre de convergence des stratégies évolutionnistes pour des fonctions bruitées. Nous déduisons une convergence log-log. Nous prouvons aussi une borne basse pour le taux de convergence de stratégies évolutionnistes. Nous étendons le travail effectué sur les mécanismes de réévaluations en les appliquant au cas discret. Finalement, nous analysons la mesure de performance en elle-même et prouvons que l'utilisation d'une mauvaise mesure de performance peut mener à des résultats trompeurs lorsque différentes méthodes d'optimisation sont évaluées. / This thesis exposes contributions to the analysis of algorithms for noisy functions. It exposes convergence rates for linesearch algorithms as well as for random search algorithms. We prove in terms of Simple Regret and Cumulative Regret that a Hessian based algorithm can reach the same results as some optimal algorithms in the literature, when parameters are tuned correctly. On the other hand we analyse the convergence order of Evolution Strategies when solving noisy functions. We deduce log-log convergence. We also give a lower bound for the convergence rate of the Evolution Strategies. We extend the work on revaluation by applying it to a discrete settings. Finally we analyse the performance measure itself and prove that the use of an erroneus performance measure can lead to misleading results on the evaluation of different methods.

Dans ce manuscrit de thèse, mes travaux portent sur la combinaison de méthodes pour la prise de décision séquentielle (plusieurs étapes de décision corrélées) dans des environnements complexes et incertains. Les méthodes mises au point sont essentiellement appliquées à des problèmes de gestion et de production d'électricité tels que l'optimisation de la gestion des stocks d'énergie dans un parc de production pour anticiper au mieux la fluctuation de la consommation des clients.Le manuscrit comporte 7 chapitres regroupés en 4 parties : Partie I, « Introduction générale », Partie II, « État de l'art », Partie III, « Contributions » et Partie IV, « Conclusion générale ».Le premier chapitre (Partie I) introduit le contexte et les motivations de mes travaux, à savoir la résolution de problèmes d' « Unit commitment », c'est à dire l'optimisation des stratégies de gestion de stocks d'énergie dans les parcs de production d'énergie. Les particularités et les difficultés sous-jacentes à ces problèmes sont décrites ainsi que le cadre de travail et les notations utilisées dans la suite du manuscrit.Le second chapitre (Partie II) dresse un état de l'art des méthodes les plus classiques utilisées pour la résolution de problèmes de prise de décision séquentielle dans des environnements incertains. Ce chapitre introduit des concepts nécessaires à la bonne compréhension des chapitres suivants (notamment le chapitre 4). Les méthodes de programmation dynamique classiques et les méthodes de recherche de politique directe y sont présentées.Le 3e chapitre (Partie II) prolonge le précédent en dressant un état de l'art des principales méthodes d’optimisation spécifiquement adaptées à la gestion des parcs de production d'énergie et à leurs subtilités. Ce chapitre présente entre autre les méthodes MPC (Model Predictive Control), SDP (Stochastic Dynamic Programming) et SDDP (Stochastic Dual Dynamic Programming) avec pour chacune leurs particularités, leurs avantages et leurs limites. Ce chapitre complète le précédent en introduisant d'autres concepts nécessaires à la bonne compréhension de la suite du manuscrit.Le 4e chapitre (Partie III) contient la principale contribution de ma thèse : un nouvel algorithme appelé « Direct Value Search » (DVS) créé pour résoudre des problèmes de prise de décision séquentielle de grande échelle en milieu incertain avec une application directe aux problèmes d' « Unit commitment ». Ce chapitre décrit en quoi ce nouvel algorithme dépasse les méthodes classiques présentées dans le 3e chapitre. Cet algorithme innove notamment par sa capacité à traiter des grands espaces d'actions contraints dans un cadre non-linéaire, avec un grand nombre de variables d'état et sans hypothèse particulière quant aux aléas du système optimisé (c'est à dire applicable sur des problèmes où les aléas ne sont pas nécessairement Markovien).Le 5e chapitre (Partie III) est consacré à un concept clé de DVS : l'optimisation bruitée. Ce chapitre expose une nouvelle borne théorique sur la vitesse de convergence des algorithmes d'optimisation appliqués à des problèmes bruités vérifiant certaines hypothèses données. Des méthodes de réduction de variance sont également étudiées et appliquées à DVS pour accélérer sensiblement sa vitesse de convergence.Le 6e chapitre (Partie III) décrit un résultat mathématique sur la vitesse de convergence linéaire d’un algorithme évolutionnaire appliqué à une famille de fonctions non quasi-convexes. Dans ce chapitres, il est prouvé que sous certaines hypothèses peu restrictives sur la famille de fonctions considérée, l'algorithme présenté atteint une vitesse de convergence linéaire.Le 7e chapitre (Partie IV) conclut ce manuscrit en résumant mes contributions et en dressant quelques pistes de recherche intéressantes à explorer. / This thesis is dedicated to sequential decision making (also known as multistage optimization) in uncertain complex environments. Studied algorithms are essentially applied to electricity production ("Unit Commitment" problems) and energy stock management (hydropower), in front of stochastic demand and water inflows. The manuscript is divided in 7 chapters and 4 parts: Part I, "General Introduction", Part II, "Background Review", Part III, "Contributions" and Part IV, "General Conclusion". This first chapter (Part I) introduces the context and motivation of our work, namely energy stock management. "Unit Commitment" (UC) problems are a classical example of "Sequential Decision Making" problem (SDM) applied to energy stock management. They are the central application of our work and in this chapter we explain main challenges arising with them (e.g. stochasticity, constraints, curse of dimensionality, ...). Classical frameworks for SDM problems are also introduced and common mistakes arising with them are be discussed. We also emphasize the consequences of these - too often neglected - mistakes and the importance of not underestimating their effects. Along this chapter, fundamental definitions commonly used with SDM problems are described. An overview of our main contributions concludes this first chapter. The second chapter (Part II) is a background review of the most classical algorithms used to solve SDM problems. Since the applications we try to solve are stochastic, we there focus on resolution methods for stochastic problems. We begin our study with classical Dynamic Programming methods to solve "Markov Decision Processes" (a special kind of SDM problems with Markovian random processes). We then introduce "Direct Policy Search", a widely used method in the Reinforcement Learning community. A distinction is be made between "Value Based" and "Policy Based" exploration methods. The third chapter (Part II) extends the previous one by covering the most classical algorithms used to solve UC's subtleties. It contains a state of the art of algorithms commonly used for energy stock management, mainly "Model Predictive Control", "Stochastic Dynamic Programming" and "Stochastic Dual Dynamic Programming". We briefly overview distinctive features and limitations of these methods. The fourth chapter (Part III) presents our main contribution: a new algorithm named "Direct Value Search" (DVS), designed to solve large scale unit commitment problems. We describe how it outperforms classical methods presented in the third chapter. We show that DVS is an "anytime" algorithm (users immediately get approximate results) which can handle large state spaces and large action spaces with non convexity constraints, and without assumption on the random process. Moreover, we explain how DVS can reduce modelling errors and can tackle challenges described in the first chapter, working on the "real" detailed problem without "cast" into a simplified model. Noisy optimisation is a key component of DVS algorithm; the fifth chapter (Part III) is dedicated to it. In this chapter, some theoretical convergence rate are studied and new convergence bounds are proved - under some assumptions and for given families of objective functions. Some variance reduction techniques aimed at improving the convergence rate of graybox noisy optimization problems are studied too in the last part of this chapter. Chapter sixth (Part III) is devoted to non-quasi-convex optimization. We prove that a variant of evolution strategy can reach a log-linear convergence rate with non-quasi-convex objective functions. Finally, the seventh chapter (Part IV) concludes and suggests some directions for future work.