Regret and Covariance: A Characterization for Stochastic Optimization

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 exactly as $Regret=-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 $Regret\le D\sqrt{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.