Wasserstein Distributionally Robust Regret Optimization

Distributionally robust optimization (DRO) is widely used for decision-making under uncertainty, but its adversarial focus on worst-case loss can lead to overly conservative policies.

To mitigate this, we study ex-ante Distributionally Robust Regret Optimization (DRRO) with Wasserstein ambiguity sets, designed to balance robustness with upside potential.

We develop a theory of Wasserstein DRRO (WDRRO) paralleling Wasserstein DRO.

Under smoothness and regularity, WDRRO selects among ERM optima by a first-order gradient-discrepancy rule.

If the ERM optimizer is unique, first-order sensitivity vanishes and a second-order expansion governs deviations.

For convex quadratics ERM and DRRO coincide for any radius.

We then study regimes where these assumptions fail: nondifferentiable max-affine losses, discrete references, and larger radii, where WDRRO can differ from ERM and WDRO.

We show that computing WDRRO regret is NP-hard even without bilinear terms.

Nevertheless, we develop exact algorithms, a tractable convex relaxation with guarantees, and experiments showing tightness and loss-dependent behavior.