PaperlayerView exact revision on arXiv

Source-linked AI summary

A Survey of Contextual Optimization Methods for Decision Making under Uncertainty

Utsav Sadana, Abhilash Chenreddy, Erick Delage, Alexandre Forel, Emma Frejinger, Thibaut Vidal

arXiv:2306.10374v2math.OCcs.LG

TL;DR

Contextual optimization addresses decision-making under uncertainty by combining machine learning with optimization. This survey organizes methods for learning policies in stochastic programming into three frameworks and identifies methodological challenges, especially for ILO.

  • Problem

    Combining prediction and optimization for uncertain decisions has produced methods that may be suboptimal and, in some cases, infeasible.

  • Method

    The survey develops a taxonomy of contextual optimization methods based on training procedures, covering three frameworks for learning policies.

  • Results

    The contextual optimization literature is categorized into decision rule optimization, sequential learning, and optimization-based learning frameworks.

  • Takeaways & Limitations

    The taxonomy provides a uniform way to organize contextual optimization methods and their training procedures.

  • Takeaways & Limitations

    The survey identifies specific methodological challenges, especially for ILO, whose appropriate treatment is a priori unclear.

Abstract

from arXiv · show

Recently there has been a surge of interest in operations research (OR) and the machine learning (ML) community in combining prediction algorithms and optimization techniques to solve decision-making problems in the face of uncertainty. This gave rise to the field of contextual optimization, under which data-driven procedures are developed to prescribe actions to the decision-maker that make the best use of the most recently updated information. A large variety of models and methods have been presented in both OR and ML literature under a variety of names, including data-driven optimization, prescriptive optimization, predictive stochastic programming, policy optimization, (smart) predict/estimate-then-optimize, decision-focused learning, (task-based) end-to-end learning/forecasting/optimization, etc. Focusing on single and two-stage stochastic programming problems, this review article identifies three main frameworks for learning policies from data and discusses their strengths and limitations. We present the existing models and methods under a uniform notation and terminology and classify them according to the three main frameworks identified. Our objective with this survey is to both strengthen the general understanding of this active field of research and stimulate further theoretical and algorithmic advancements in integrating ML and stochastic programming.

1. Introduction

Contextual optimization uses covariates and uncertain-parameter data to learn decision rules for stochastic programs. This survey organizes the literature into decision rule optimization, sequential learning and optimization, and integrated learning and optimization.

  • Motivation: Contextual optimization maps observed covariates to actions when objective and constraint uncertainty is unknown.Data-driven methods estimate the uncertain parameter’s conditional distribution or a sufficient statistic from covariates.
  • Motivation: Traditional stochastic optimization uses unconditional uncertainty distributions, which may produce suboptimal or infeasible decisions.
  • Motivation: 13?
  • Frameworks: The survey identifies three frameworks for learning covariate-to-action mappings: decision rule optimization, SLO, and ILO.
  • Decision rule optimization: Decision rule optimization directly parameterizes a policy and fits it for empirical performance, using linear covariate functions or deep neural networks.
  • Sequential learning and optimization: SLO first predicts a conditional distribution and then solves a contextual stochastic optimization problem, with robustification addressing overfitting or misspecification.
  • Integrated learning and optimization: ILO trains predictive models toward better-performing decisions rather than prioritizing prediction precision, under names including smart predict-then-optimize and decision-focused learning.
  • Survey scope and contribution: The survey extends ILO coverage beyond expected value-based models, links regret minimization with end-to-end and imitation-based approaches, and classifies training procedures.

2. Contextual optimization: An overview

Contextual optimization chooses actions from covariates when uncertain parameters are unknown, and learns policies from historical data to minimize expected costs. The survey organizes these approaches into decision rule optimization, sequential learning and optimization, and integrated learning and optimization.

  • Contextual stochastic optimization: Contextual optimization selects a feasible action z after observing covariates x correlated with uncertain parameters y, whose distribution is unknown at decision time.The cost function may contain uncertainty in objectives or constraints.
  • Contextual stochastic optimization: The contextual stochastic optimization problem minimizes expected cost conditioned on the observed covariate under the joint distribution of covariates and uncertain parameters.The formulation assumes a risk-neutral decision-maker in the main discussion and conditions on P(y|x).
  • Learning policies: Because the joint distribution is generally unknown, the decision-maker uses historical data to learn a policy mapping covariates directly to feasible actions.Parameterized policies πθ form decision rules and are fitted using the empirical distribution of observed data.
  • Three frameworks: The survey identifies three frameworks for finding effective approximate covariate-to-action policies: decision rule optimization, sequential learning and optimization, and integrated learning and optimization.The latter two combine a predictive component with an optimization component, while differing in how the predictor is trained.
  • Framework comparison: Decision rule optimization minimizes empirical expected costs over a restricted policy class, while learning-and-optimization pipelines optimize under a predicted distribution that approximates P(y|x).If the predictive component perfectly predicts P(y|x), the pipeline recovers the optimal policy.
  • Framework comparison: Sequential learning and optimization trains the predictor by minimizing estimation error, whereas integrated learning and optimization trains it to minimize average historical costs through the induced policy.The SLO predictor may be parametric or non-parametric, with complexity controlled by regularization or hyperparameter selection.

3. Decision rule optimization

Decision rule optimization learns a parameterized policy that maps covariates directly to decisions, avoiding optimization at decision time. The literature spans linear, kernel-based, tree-based, neural, and piecewise-affine rules, with trade-offs between flexibility, interpretability, feasibility, and generalization.

  • Policy-based approaches: Policy-based approaches learn a parameterized mapping πθ(x) and evaluate it directly at decision time, without solving a new optimization problem.Examples include linear policies and neural networks.
  • Linear decision rules: Linear decision rules are widely used because neural-network policies lack interpretability, although LDRs may not be asymptotically optimal in general.Regularization introduces a trade-off between generalization error and bias.
  • RKHS-based decision rules: RKHS-based policies lift covariates into richer function spaces; results establish out-of-sample bounds and, in some settings, asymptotic optimality.Gaussian-kernel RKHS policies are one prominent construction.
  • Non-linear decision rules: Nonlinear rules include decision trees, neural networks, and piecewise-affine policies, with feasibility handled through constructions such as softmax layers or differentiable repair.Piecewise-affine rules have non-asymptotic and asymptotic consistency results for unconstrained and constrained problems.

4. Sequential learning and optimization

Sequential learning and optimization methods estimate conditional outcome distributions or assign data-dependent weights before solving stochastic optimization problems. The surveyed approaches include residual-based, proximity-based, kernel, random-forest, expected-value, and distributionally robust models, each with statistical and computational considerations.

  • Frameworks: Sequential learning and optimization distinguishes direct conditional-distribution learning from approaches designed to be robust to model misspecification.The survey presents these settings as two main SLO categories.
  • Residual-based distributions: Residual-based methods construct conditional distributions from regression errors and can be combined with any trained regression model.Using the same historical data for fitting and residual measurement can underestimate residual-error distributions.
  • Weight-based distributions: Weight-based methods solve weighted SAA problems using observation weights derived from proximity, kernels, or random forests.kNN assigns equal weight to the k closest samples and zero weight to the others; decision trees weight samples sharing a leaf.
  • Guarantees and robustness: 64? No, kNN, NW, and local-weight prescriptions have conditions for asymptotic optimality and consistency, while DRO reformulations can yield convex programs and out-of-sample guarantees.The surveyed results also include bootstrap-robustness guarantees under KL divergence.

5. Integrated learning and optimization

Integrated learning and optimization trains prediction components using downstream decision performance, linking prediction, optimization, and task-specific loss functions. The surveyed methods include conditional-distribution, regret-based, and surrogate-loss or optimizer approaches, with reported computational and performance differences across problems.

  • Integrated learning and optimization: The ILO training pipeline combines a prediction model, an optimization model, and a task-based loss that represents the downstream problem.Prediction parameters are trained using the loss of the induced policy rather than prediction error alone.
  • Training methods: Differentiating integrated losses is challenging because they may be non-convex, while LP solution gradients can be null or nonexistent at transitions between extreme points.These issues motivate training procedures based on implicit differentiation, surrogate differentiable losses, and surrogate differentiable optimizers.
  • Models: Conditional-distribution ILO models estimate uncertain parameters with parametric distributions and prescribe actions using conditional expected-value optimization.For the newsvendor problem, ILO outperforms decision-rule optimization with neural networks and SLO using maximum likelihood estimation when the model is misspecified.
  • Models: Regret minimization trains a contextual point predictor by minimizing the regret of acting on its estimate rather than on realized parameters.The expected-regret objective has the same optimal parameter vectors and minimizers as the corresponding ILO objective.
  • Empirical findings: Reported experiments find that several integrated methods improve convergence, computational time, or task loss relative to alternatives, but outcomes vary by problem and comparator.Examples include up to two orders of magnitude improvement in expected regret over SPO+, nearly fivefold computational reduction for ADMM-FP versus OptNet, and faster convergence than QPTL for SPO-relax.
  • Theory and comparisons: The literature also reports theoretical trade-offs: SLO can converge faster under low-noise assumptions, whereas ILO outperforms SLO asymptotically in a general nonlinear setting.Other results include Fisher consistency for SPO+ under stated conditions and comparable performance between a simple algorithm and SPO+.

6. Active research directions

The survey identifies active directions involving uncertain constraints, risk, software and benchmarking, endogenous uncertainty, privacy, interpretability, and fairness. These directions broaden contextual optimization beyond its common assumptions while exposing data, modeling, and evaluation challenges.

  • Uncertainty in constraints: Most contextual optimization studies assume deterministic constraints, while uncertain constraints can make solutions that ignore covariates infeasible.Learning an uncertainty set that minimizes downstream cost is identified as a challenging problem.
  • Risk aversion: Risk-averse contextual optimization replaces risk-neutral expectations with risk measures such as value-at-risk and uses conditional uncertainty sets.The uncertainty set must capture relevant scenarios while balancing risk avoidance and returns.
  • Toolboxes and benchmarking: Toolboxes including cvxpylayers and PyEPO support differentiable decision pipelines, but comparable evaluations on fixed settings and real-world data remain scarce.Existing benchmarking includes a meta-analysis reporting no single method clearly outperforming all others across four newsvendor datasets.
  • Endogenous uncertainty: Decision-dependent uncertainty with covariates remains sparse, including settings where facility locations or prices change demand.The causal relationship between demand and prices is unknown, motivating methods that isolate causal price effects from covariate effects.
  • Data privacy: Privacy-preserving obfuscation can protect sensitive multi-source data but may reduce predictive and prescriptive performance.Differential privacy is identified as one approach, with data quality and decision value studied using distributionally robust optimization.
  • Interpretability and explainability: Interpretability and explainability are important because decision pipelines must be trusted and may need to provide meaningful information about automated decisions.Proposed directions include transparent tree or rule models, feature-importance analysis, and counterfactual explanations.
  • Fairness: Fairness concerns arise when contextual decisions use protected attributes, with pricing research seeking to limit differences between customer groups.This creates a need to incorporate fairness considerations into contextual decision-making.

7. Conclusions

The survey organizes contextual optimization for single- and two-stage stochastic programming into three frameworks for learning policies from covariate data. It standardizes their description and identifies active research directions.

  • Contextual optimization uses covariates revealed before decisions, together with historical covariate and uncertainty data, to prescribe decisions.
  • The survey categorizes contextual optimization methods into decision rule optimization, sequential learning and optimization, and integrated learning and optimization.
  • Decision rule optimization parameterizes the policy directly as a function of the covariates, whereas learning-and-optimization frameworks estimate conditional distributions or sufficient statistics.
  • The survey gives the three frameworks parametric descriptions and introduces uniform notation and terminology for analyzing different methods.
  • For integrated learning and optimization, the survey describes both the training pipeline and modeling choice, emphasizing that these aspects are intertwined.
  • The survey also provides a list of active research fields in contextual stochastic optimization problems.

Appendix A: Theoretical guarantees

The appendix summarizes theoretical guarantees for contextual optimization policies and surrogate losses. It covers asymptotic optimality, consistency, Fisher consistency, and calibration conditions.

  • The appendix distinguishes asymptotic optimality from consistency as theoretical guarantees for policies obtained from samples.
  • A policy is defined as consistent when its distance from the optimal solution set converges to zero almost everywhere.
  • As the sample size tends to infinity, the policy performance under almost all covariates matches the optimal conditional cost.
  • Fisher consistency requires complete knowledge of the joint distribution P.
  • A central calibration question is whether low surrogate excess risk translates into small excess true SPO risk.
  • For polyhedral Z, the reported calibration function is O(ǫ2), while it is O(ǫ) when Z is a level set of a strongly convex and smooth function.

Appendix B: List of abbreviations

Appendix B lists abbreviations used throughout the survey, including terms for contextual optimization, learning, optimization, statistical methods, and mathematical tools.

  • CSO denotes contextual stochastic optimization, while SLO and ILO denote sequential learning and optimization and integrated learning and optimization.
  • DRO, CVaR, ERM, and SAA denote distributionally robust optimization, conditional value at risk, empirical risk minimization, and sample average approximation.
  • ML, MLE, and DNN denote machine learning, maximum likelihood estimation, and deep neural network.
  • MILP, NW, kNN, and LDR denote mixed-integer linear program, Nadaraya-Watson, k-nearest neighbor, and linear decision rule.
  • RKHS, ADMM, IFT, FP, and KKT denote reproducing kernel Hilbert space, alternating direction method of multipliers, implicit function theorem, fixed point, and Karush–Kuhn–Tucker.
Loading 2306.10374v2…