A Little Robustness Is All You Need: Leveraging Predictions for Contextual Optimization

A common approach for contextual optimization first trains a model to predict the unknown state from the context, and then takes the action that is optimal for the predicted state. We show that this follow-the-prediction policy can be brittle: for several standard problems, even a minimum-variance predictor with arbitrarily small RMSE can incur constant excess loss. We propose a simple policy that robustifies any black-box predictor by optimizing against the worst case in an $\varepsilon$-neighborhood of the prediction. We identify a problem-specific quantity, the \emph{robust optimization gap}, that captures the price of this hedging, and prove a general bound on the loss. We instantiate the framework for contextual posted pricing, ski rental, and house flipping, deriving closed-form robust policies and $O(\eta^{2/3})$ loss bounds in all three settings, where $\eta$ is the RMSE of the predictor. For posted pricing, this improves upon a result of Medina and Vassilvitskii (2017), and with a substantially simpler argument.