Regret Equals Covariance: A Closed-Form Characterization for Stochastic Optimization
TL;DR
A distribution-free bound is given that depends only on the radius of the feasible region and the cost covariance of regret that holds for unconstrained and equality-constrained quadratic programs and many, but not all, linear programs.
Abstract
Quantifying regret typically involves repeatedly re-solving a stochastic optimization problem across simulated scenarios. Such an approach is costly: the cost scales with the number of scenarios and the cost of each solve. We propose that regret can instead be measured using the joint moments of the cost vector $c$ and the optimal decision $\pi^*(c)$. Working with the optimal concave and Lipschitz under only a feasible region value function $v(c) = \min_{z\in Z} c^\top z$, we show that regret always decomposes as $\mathrm{Regret} = -\mathrm{Cov}(c,\pi^*(c)) - R(c)$ for a residual $R(c)$. We further show that $R(c)=0$ when $\pi^*$ is affine in $c$, which holds for unconstrained and equality-constrained (e.g., budget-constrained Markowitz) quadratic programs and many, but not all, linear programs. For all cases, we give a distribution-free bound $\mathrm{Regret} \le D\sqrt{\mathrm{tr}(\Sigma_c)}$ that depends only on the radius of the feasible region and the cost covariance. We also derive concentration and asymptotic-normality results for the empirical regret, the latter under an explicit and checkable non-degeneracy condition.
