Data-driven Multistage Distributionally Robust Optimization with Nested Distance: Time Consistency and Tractable Dynamic Reformulations

We study multistage distributionally robust optimization in which the uncertainty set consists of stochastic processes that are close to a scenario tree in the nested distance (Pflug and Pichler (2012)). Compared to other choices such as Wasserstein distance between stochastic processes, the nested distance accounts for information evolution, making it hedge against a plausible family of data processes. Due to the non-convexity of the nested distance uncertainty set, the resulting minimax problem is notoriously difficult to solve. In spite of this challenge, in this paper, we develop an equivalent robust dynamic programming reformulation. This reformulation has two important implications: (1) Modeling-wise, it unveils that the considered single minimax multistage-static formulation based on the nested distance for stochastic processes is equivalent to a nested minimax multistage-dynamic formulation based on one-period nested Wasserstein distance (Shapiro and Pichler (2022)), thus both of which admit a time-consistent robust optimal policy. In the literature, both multistage-static and multistage-dynamic formulations are natural modeling approaches yet hard to reconcile with each other, and the only known cases where the two formulations coincide on generic multistage linear programs are defined via degenerate uncertainty sets (singleton or entirety). As such, our result provides the first non-trivial distributionally robust framework that unifies the two formulations. (2) Computation-wise, we identify conditions under which the robust Bellman recursion can be interpreted as norm-regularized sample average approximation and solved via tractable convex programs. We develop a stochastic dual dynamic programming algorithm and apply it to dynamic portfolio selection. Numerical experiments demonstrate the superior out-of-sample performance of our robust approach.

Article

Download

View Data-driven Multistage Distributionally Robust Optimization with Nested Distance: Time Consistency and Tractable Dynamic Reformulations