Browse ORBi by ORBi project

- Background
- Content
- Benefits and challenges
- Legal aspects
- Functions and services
- Team
- Help and tutorials

Multistage stochastic programming: A scenario tree based approach to planning under uncertainty Defourny, Boris ; Ernst, Damien ; Wehenkel, Louis in Sucar, L. Enrique; Morales, Eduardo F.; Hoey, Jesse (Eds.) Decision Theory Models for Applications in Artificial Intelligence: Concepts and Solutions (2011) In this chapter, we present the multistage stochastic programming framework for sequential decision making under uncertainty. We discuss its differences with Markov Decision Processes, from the point of ... [more ▼] In this chapter, we present the multistage stochastic programming framework for sequential decision making under uncertainty. We discuss its differences with Markov Decision Processes, from the point of view of decision models and solution algorithms. We describe the standard technique for solving approximately multistage stochastic problems, which is based on a discretization of the disturbance space called scenario tree. We insist on a critical issue of the approach: the decisions can be very sensitive to the parameters of the scenario tree, whereas no efficient tool for checking the quality of approximate solutions exists. In this chapter, we show how supervised learning techniques can be used to evaluate reliably the quality of an approximation, and thus facilitate the selection of a good scenario tree. The framework and solution techniques presented in the chapter are explained and detailed on several examples. Along the way, we define notions from decision theory that can be used to quantify, for a particular problem, the advantage of switching to a more sophisticated decision model. [less ▲] Detailed reference viewed: 319 (45 ULg)Machine Learning Solution Methods for Multistage Stochastic Programming Defourny, Boris Doctoral thesis (2010) This thesis investigates the following question: Can supervised learning techniques be successfully used for finding better solutions to multistage stochastic programs? A similar question had already been ... [more ▼] This thesis investigates the following question: Can supervised learning techniques be successfully used for finding better solutions to multistage stochastic programs? A similar question had already been posed in the context of reinforcement learning, and had led to algorithmic and conceptual advances in the field of approximate value function methods over the years. This thesis identifies several ways to exploit the combination "multistage stochastic programming/supervised learning" for sequential decision making under uncertainty. Multistage stochastic programming is essentially the extension of stochastic programming to several recourse stages. After an introduction to multistage stochastic programming and a summary of existing approximation approaches based on scenario trees, this thesis mainly focusses on the use of supervised learning for building decision policies from scenario-tree approximations. Two ways of exploiting learned policies in the context of the practical issues posed by the multistage stochastic programming framework are explored: the fast evaluation of performance guarantees for a given approximation, and the selection of good scenario trees. The computational efficiency of the approach allows novel investigations relative to the construction of scenario trees, from which novel insights, solution approaches and algorithms are derived. For instance, we generate and select scenario trees with random branching structures for problems over large planning horizons. Our experiments on the empirical performances of learned policies, compared to golden-standard policies, suggest that the combination of stochastic programming and machine learning techniques could also constitute a method per se for sequential decision making under uncertainty, inasmuch as learned policies are simple to use, and come with performance guarantees that can actually be quite good. Finally, limitations of approaches that build an explicit model to represent an optimal solution mapping are studied in a simple parametric programming setting, and various insights regarding this issue are obtained. [less ▲] Detailed reference viewed: 162 (18 ULg)Large Margin Classification with the Progressive Hedging Algorithm Defourny, Boris ; Wehenkel, Louis Conference (2009, December) Several learning algorithms in classification and structured prediction are formulated as large scale optimization problems. We show that a generic iterative reformulation and resolving strategy based on ... [more ▼] Several learning algorithms in classification and structured prediction are formulated as large scale optimization problems. We show that a generic iterative reformulation and resolving strategy based on the progressive hedging algorithm from stochastic programming results in a highly parallel algorithm when applied to the large margin classification problem with nonlinear kernels. We also underline promising aspects of the available analysis of progressive hedging strategies. [less ▲] Detailed reference viewed: 53 (4 ULg)Planning under uncertainty, ensembles of disturbance trees and kernelized discrete action spaces Defourny, Boris ; Ernst, Damien ; Wehenkel, Louis in Proceedings of the IEEE International Symposium on Adaptive Dynamic Programming and Reinforcement Learning (ADPRL-09) (2009) Optimizing decisions on an ensemble of incomplete disturbance trees and aggregating their first stage decisions has been shown as a promising approach to (model-based) planning under uncertainty in large ... [more ▼] Optimizing decisions on an ensemble of incomplete disturbance trees and aggregating their first stage decisions has been shown as a promising approach to (model-based) planning under uncertainty in large continuous action spaces and in small discrete ones. The present paper extends this approach and deals with large but highly structured action spaces, through a kernel-based aggregation scheme. The technique is applied to a test problem with a discrete action space of 6561 elements adapted from the NIPS 2005 SensorNetwork benchmark. [less ▲] Detailed reference viewed: 30 (10 ULg)Supervised learning of intra-daily recourse strategies for generation management under uncertainties Cornélusse, Bertrand ; ; Defourny, Boris et al in PowerTech, 2009 IEEE Bucharest (2009) The aim of this work is to design intra-daily recourse strategies which may be used by operators to decide in real-time the modifications to bring to planned generation schedules of a set of units in ... [more ▼] The aim of this work is to design intra-daily recourse strategies which may be used by operators to decide in real-time the modifications to bring to planned generation schedules of a set of units in order to respond to deviations from the forecasted operating scenario. Our aim is to design strategies that are interpretable by human operators, that comply with real-time constraints and that cover the major disturbances that may appear during the next day. To this end we propose a new framework using supervised learning to infer such recourse strategies from simulations of the system under a sample of conditions representing possible deviations from the forecast. This framework is validated on a realistic generation system of medium size. [less ▲] Detailed reference viewed: 48 (21 ULg)Bounds for Multistage Stochastic Programs using Supervised Learning Strategies Defourny, Boris ; Ernst, Damien ; Wehenkel, Louis in Watanabe, Osamu; Zeugmann, Thomas (Eds.) Stochastic Algorithms: Foundations and Applications (2009) We propose a generic method for obtaining quickly good upper bounds on the minimal value of a multistage stochastic program. The method is based on the simulation of a feasible decision policy ... [more ▼] We propose a generic method for obtaining quickly good upper bounds on the minimal value of a multistage stochastic program. The method is based on the simulation of a feasible decision policy, synthesized by a strategy relying on any scenario tree approximation from stochastic programming and on supervised learning techniques from machine learning. [less ▲] Detailed reference viewed: 34 (18 ULg)Probability Density Estimation by Perturbing and Combining Tree Structured Markov Networks ; ; Defourny, Boris et al in Proc. of ECSQARU '09: 10th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (2009) Detailed reference viewed: 39 (12 ULg)Risk-aware decision making and dynamic programming Defourny, Boris ; Ernst, Damien ; Wehenkel, Louis Conference (2008) This paper considers sequential decision making problems under uncertainty, the tradeoff between the expected return and the risk of high loss, and methods that use dynamic programming to find optimal ... [more ▼] This paper considers sequential decision making problems under uncertainty, the tradeoff between the expected return and the risk of high loss, and methods that use dynamic programming to find optimal policies. It is argued that using Bellman's Principle determines how risk considerations on the return can be incorporated. The discussion centers around returns generated by Markov Decision Processes and conclusions concern a large class of methods in Reinforcement Learning. [less ▲] Detailed reference viewed: 155 (16 ULg)Lazy planning under uncertainty by optimizing decisions on an ensemble of incomplete disturbance trees Defourny, Boris ; Ernst, Damien ; Wehenkel, Louis in Defourny, Boris; Ernst, Damien; Wehenkel, Louis (Eds.) Recent Advances in Reinforcement Learning (2008) This paper addresses the problem of solving discrete-time optimal sequential decision making problems having a disturbance space W composed of a finite number of elements. In this context, the problem of ... [more ▼] This paper addresses the problem of solving discrete-time optimal sequential decision making problems having a disturbance space W composed of a finite number of elements. In this context, the problem of finding from an initial state x0 an optimal decision strategy can be stated as an optimization problem which aims at finding an optimal combination of decisions attached to the nodes of a disturbance tree modeling all possible sequences of disturbances w0, w1, . . ., w(T−1) in W^T over the optimization horizon T. A significant drawback of this approach is that the resulting optimization problem has a search space which is the Cartesian product of O(|W|^(T−1)) decision spaces U, which makes the approach computationally impractical as soon as the optimization horizon grows, even if W has just a handful of elements. To circumvent this difficulty, we propose to exploit an ensemble of randomly generated incomplete disturbance trees of controlled complexity, to solve their induced optimization problems in parallel, and to combine their predictions at time t = 0 to obtain a (near-)optimal first-stage decision. Because this approach postpones the determination of the decisions for subsequent stages until additional information about the realization of the uncertain process becomes available, we call it lazy. Simulations carried out on a robot corridor navigation problem show that even for small incomplete trees, this approach can lead to near-optimal decisions. [less ▲] Detailed reference viewed: 54 (3 ULg)High-dimensional probability density estimation with randomized ensembles of tree structured bayesian networks ; ; Defourny, Boris et al in Proc. of the 4th European Workshop on Probabilistic Graphical Models (PGM08) (2008) Detailed reference viewed: 30 (1 ULg)Projecting Generation Decisions Induced by a Stochastic Program on a Family of Supply Curve Functions Defourny, Boris ; Wehenkel, Louis Scientific conference (2007, March) We propose to post-process the results of a scenario based stochastic program by projecting its decisions on a parameterized space of policies. By doing so the risk of overfitting to the set of scenarios ... [more ▼] We propose to post-process the results of a scenario based stochastic program by projecting its decisions on a parameterized space of policies. By doing so the risk of overfitting to the set of scenarios used in the stochastic program is reduced. A proper choice of the structure of the space of policies allows one to exploit them in the context of novel scenarios, be it for Monte-Carlo based value estimation or for use in real-life conditions. These ideas are presented in the context of planning the exploitation of electric energy resources or for evaluating the economic value of a portfolio of assets. [less ▲] Detailed reference viewed: 17 (2 ULg) |
||