Wasserstein Distributionally Robust Regret Minimization

We propose a decision-making model under uncertainty to minimize the ex-ante regret in a distributionally robust manner using the Wasserstein metric, where the regret is defined as the difference of the expected cost achieved and the best achievable expected cost for any given distribution of uncertainty. First, we formulate a minimization problem of the worst-case ex-ante regret over a Wasserstein ball. Subsequently, we derive its surrogate as the proposed model using the minimax inequality, whose objective function is above the worst-case ex-ante regret on the decision space. Our main contributions are to show that (i) the approximation error of our model is uniformly bounded, and it vanishes depending on the cost function, the uncertainty set, and the Wasserstein ball’s radius; (ii) our model provides a finite-sample performance guarantee and is asymptotically optimal; and (iii) an optimal solution of our model for a class of two-stage linear programs can be obtained using the cutting-plane method. Simulation results demonstrate the effectiveness of our model.