Multistage Conditional Compositional Optimization
2026-04-15 • Machine Learning
Machine Learning
AI summaryⓘ
The authors introduce a new method called Multistage Conditional Compositional Optimization (MCCO) to help make better decisions when there is uncertainty involved. MCCO handles problems that involve several steps and nested conditions, like deciding the best time to stop or managing risks dynamically. They point out that traditional ways to solve these problems become too complex very quickly as the problem size grows. To fix this, the authors develop improved sampling techniques that keep the complexity manageable and make the method more practical for real-world use.
Multistage stochastic programmingConditional stochastic optimizationConditional expectationsOptimal stoppingLinear-quadratic regulatorDistributionally robust optimizationContextual banditsDynamic risk measuresScenario complexityMultilevel Monte Carlo
Authors
Buse Şen, Yifan Hu, Daniel Kuhn
Abstract
We introduce Multistage Conditional Compositional Optimization (MCCO) as a new paradigm for decision-making under uncertainty that combines aspects of multistage stochastic programming and conditional stochastic optimization. MCCO minimizes a nest of conditional expectations and nonlinear cost functions. It has numerous applications and arises, for example, in optimal stopping, linear-quadratic regulator problems, distributionally robust contextual bandits, as well as in problems involving dynamic risk measures. The naïve nested sampling approach for MCCO suffers from the curse of dimensionality familiar from scenario tree-based multistage stochastic programming, that is, its scenario complexity grows exponentially with the number of nests. We develop new multilevel Monte Carlo techniques for MCCO whose scenario complexity grows only polynomially with the desired accuracy.