Session: Certified Data-Driven Optimization via the Scenario Approach
Chair: Simone Garatti
Cluster: Optimization Under Uncertainty and Data-driven Optimization
Talk 1: Scenario Optimization: Data-Driven Goal-Oriented Designs with Certified Reliability
Speaker: Marco C. Campi
Abstract: The utilization of data is becoming paramount in addressing modern optimization problems characterized by increasing complexity. However, for a true science of data-driven optimization to emerge, fundamental questions need to be addressed: (i) should data be used to reconstruct the unknown distribution of uncertainty, or should we rather directly optimize to achieve the final design? (ii) is it possible to endow data-driven, optimization-based designs with certifications of quality that hold beyond any assumed characteristics of the underlying distribution? In this presentation, we introduce "Scenario Optimization", a collection of data-driven optimization techniques that provide algorithmic and theoretical responses to the questions posed above. After introducing robust data-driven techniques, we move toward relaxed schemes, showing how each plays a prominent role in specific application domains. The algorithmic methods will be accompanied by results certifying their reliability, providing users with a comprehensive suite of data-driven optimization techniques.
Talk 2: Expanding the Scope of the Scenario Approach with the Pick-to-Learn (P2L) Algorithm
Speaker: Simone Garatti
Abstract: The scenario approach is a powerful and widely-used framework in data-driven optimization and decision-making, also offering a rigorous methodology to evaluate the risk of solutions derived from data. This makes it a pivotal tool for decision-making under uncertainty. On the other hand, the scenario approach relies on structural assumptions that are not always met in applications. A notable example is the minimization of mean error cost functions, which is frequently used in machine learning, particularly in the training of neural networks. In this talk, we delve into the deeper theoretical foundations behind the scenario approach, and present the powerful framework of preferent sample compression. By leveraging this deeper understanding of the method, a meta-algorithm, the Pick-to-Learn (P2L) algorithm, is introduced to broaden the applicability of the scenario approach. P2L builds upon any learning-based decision scheme as a black-box to create a new scheme that conform to the theory of preferent sample compression, while maintaining the design goals of the original scheme. This makes the reach of the theory of preferent compression virtually infinite, and licenses the utilization of the powerful risk evaluation results of the scenario approach to a wide range of problems of great interest that would otherwise fall outside its traditional scope.
Talk 3: Randomized Algorithms and PAC Bounds for Inverse Reinforcement Learning in Continuous Spaces
Speaker: Tobias Sutter
Abstract: This work studies discrete-time discounted Markov decision processes with continuous state and action spaces and addresses the inverse problem of inferring a cost function from observed optimal behavior. We first consider the case in which we have access to the entire expert policy and characterize the set of solutions to the inverse problem by using occupation measures, linear duality, and complementary slackness conditions. To avoid trivial solutions and ill-posedness, we introduce a natural linear normalization constraint. This results in an infinite-dimensional linear feasibility problem, prompting a thorough analysis of its properties. Next, we use linear function approximators and adopt a randomized approach, namely the scenario approach and related probabilistic feasibility guarantees, to derive epsilon-optimal solutions for the inverse problem. We further discuss the sample complexity for a desired approximation accuracy. Finally, we deal with the more realistic case where we only have access to a finite set of expert demonstrations and a generative model and provide bounds on the error made when working with samples.
