Regret Equals Covariance: A Closed-Form Characterization for Stochastic Optimization

Abstract This paper proves that expected regret in any stochastic optimization problem decomposes exactly as $Regret(c) = \text{Cov}(c, \pi^*(c)) + R(c)$, where $c$ is a random cost vector, $\pi^*(c)$ is the optimal decision, and $R(c)$ is a residual bounded by the variance of $c$. For linear and quadratic programs — including the Markowitz portfolio optimization problem — the residual vanishes exactly, yielding the closed-form identity $Regret(c) = \text{Cov}(c, \pi^*(c))$. This characterization is distinct from the envelope theorem, which yields only a zero integral when applied distributionally, and from Sample Average Approximation, which produces a random variable rather than a deterministic function of the problem primitives. The result reduces the computational complexity from $O(Bn^2d^3)$ for SAA to $O(nd^2)$ for the covariance formula, completely eliminating the scenario-count factor. Simulations in 5,000 iterations confirm the exact convergence for LP and relative errors of 13.6\% and 31\% for constrained QP, both within theoretical limits. Applied to 4,487 U.S. equities from 2015–2024, covariance-predicted portfolio regret tracks realized regret closely over time.