EXPRESS: Tackling Decision Dependency in Contextual Stochastic Optimization

Abstract

In this paper, we study contextual stochastic optimization (CSO), where decisions are made under uncertainty and the distribution of random parameters can be partially inferred from covariates observed prior to decision-making. In many practical settings, these distributions also depend on the decisions themselves, a phenomenon known as the decision-dependent effect . Most existing studies address this issue by imposing structural assumptions on the relationship between decisions and the underlying distributions. However, such assumptions may lead to model misspecification when the true relationship deviates from the assumed form. A prominent alternative is the weighted sample average approximation (wSAA) method proposed by Bertsimas and Kallus (2019), which adapts sample weights based on their similarity to the current decision–context pair. Nevertheless, because these weights are typically computed using complex machine learning models and depend on the decision variables in decision-dependent settings, solving the resulting optimization problem becomes computationally challenging. To overcome this challenge, we extend the wSAA framework from the loss function to its gradient, leading to the notion of the contextual gradient . We show that the contextual gradient serves as a meaningful indicator of optimality and leverage this property to develop the contextual gradient descent (CGD) algorithm. Our analysis establishes that CGD converges to a neighborhood of the global optimum when the loss function exhibits sufficient strong convexity. Moreover, the derived bounds reveal a key insight: the strength of convexity in the loss function can compensate for the uncertainty introduced by decision-dependent effects. Extensive numerical experiments on both synthetic and real-world datasets demonstrate that CGD consistently outperforms existing methods for contextual optimization under decision-dependent uncertainty.