Regret Equals Covariance: A Closed-Form 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 π^*(c). Working with the optimal concave and Lipschitz under only a feasible region value function v(c) = minz∈ Z c^top z, we show that regret always decomposes as Regret = -Cov(c,π^*(c)) - R(c) for a residual R(c). We further show that R(c)=0 when π^* 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 ≤ D√tr(Sigmac) 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.