Regret Equals Integrated Covariance: Exact Identities for the Value of Information in Stochastic Optimization

원문 초록

For a stochastic program $\min_{z\in Z} c^T z + h(z)$ with a random cost vector $c$, regret, or the expected value of perfect information, is usually computed by re-solving the problem scenario by scenario. We show that regret is determined by the covariance between the cost vector and the optimal decision $\pi^s(c)$. The identity is exact and holds without regularity assumptions once the covariance is integrated along the path from the mean to each scenario. With $c_s=E[c]+s(c-E[c])$, $Reg=-\int_0^1 s^{-1} Cov(c_s,\pi^s(c_s))\,ds$. Three consequences follow. First, the plain covariance is always an upper bound: $0\le Reg\le-Cov(c,\pi^s(c))$. Second, when the optimal decision rule is affine, as in unconstrained and equality-constrained (e.g., budget-constrained Markowitz) quadratic programs, regret equals exactly one half of the covariance. For purely linear objectives, an affine rule forces zero regret. Third, the ratio of regret to covariance lies in $[0,1]$ and is governed by the shape of the covariance profile along the path. The noise level at which this profile first becomes positive is a decision-stability margin that tightens the bound. The identity also holds scenario by scenario for any predicted cost, so it applies to linear and combinatorial programs with discontinuous decision rules. We give dimension-free concentration bounds and a central limit theorem for the plug-in estimator. Across 7 problem classes, 8 cost distributions, and the shortest-path benchmark of Elmachtoub and Grigas (2022) with $10^6$ draws per configuration, the identities hold to within quadrature error, and the covariance bound holds in every scenario.