Orateur
Description
This paper shifts focus from the typical approach of maximizing expected reward to minimizing expected regret, aiming to find a solution whose expected reward is close to the oracle. While these two approaches are equivalent when the uncertainty distribution is given, they diverge when accounting for distributional ambiguity, which is characterized by the Wasserstein distance, for enhanced robustness. This can be achieved by requiring the decision maker to specify their tolerance for expected regret under the nominal distribution and minimize the excess regret beyond this threshold across any other distribution. By exploring the entire range of this threshold parameter, our regret-based model encompasses both empirical optimization and worst-case regret minimization, the latter of which is NP-hard. When the reward function is represented by a linear program (possibly involving recourse decisions, a random technology matrix, and a random right-hand side), we propose two tractable safe approximations that preserve feasibility and empirical consistency of the original problem. The first approximation is formulated as a robust linear program with convex uncertainty sets, while the second tightens and improves upon the first using positive semidefinite constraints. Finally, we demonstrate the advantages of our tolerance-oriented regret-based model over a similar target-oriented reward-based model and empirical optimization in the context of supply chain procurement and portfolio selection.
