Distributionally Robust Regret Minimization

We consider decision-making problems involving the optimization of linear objective functions with uncertain coefficients. The probability distribution of the coefficients--which are assumed to be stochastic in nature--is unknown to the decision maker but is assumed to lie within a given ambiguity set, defined as a type-1 Wasserstein ball centered at a given nominal distribution. To account for this uncertainty, we minimize the worst-case expected regret over all distributions in the ambiguity set. Here, the (ex post) regret experienced by the decision maker is defined as the difference between the cost incurred by a chosen decision given a particular realization of the objective coefficients and the minimum achievable cost with perfect knowledge of the coefficients at the outset. For this class of ambiguity sets, the worst-case expected regret is shown to equal the expected regret under the nominal distribution plus a regularization term that has the effect of drawing optimal solutions toward the "center" of the feasible region as the radius of the ambiguity set increases. This novel form of regularization is also shown to arise when minimizing the worst-case conditional value-at-risk (CVaR) of regret. We show that, under certain conditions, distributionally robust regret minimization problems over type-1 Wasserstein balls can be recast as tractable finite-dimensional convex programs.