A Data-Driven Approach to Multi-Stage Linear Optimization

We present a data-driven approach for solving multi-stage stochastic linear optimization problems in which uncertainty is correlated across stages. The proposed approach chooses decision rules which perform best when averaging over sample paths of a stochastic process; however, to avoid overfitting, we allow an adversary to slightly perturb each sample path. We show that this robust approach converges to the underlying stochastic problem as more data is obtained, even when the uncertainty is arbitrarily correlated across stages. Furthermore, we develop scalable approximation algorithms, which apply to problems with both continuous and integer decisions, by leveraging techniques from robust optimization. In computational experiments on stochastic inventory management problems, the proposed methods are practically tractable and produce decisions with near-optimal average performance. As a by-product of the aforementioned contributions, we also present new results in machine learning and distributionally robust optimization with Wasserstein ambiguity sets.