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

Irene Aldridge

Papers from arXiv.org

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.

Date: 2026-05, Revised 2026-09
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://arxiv.org/pdf/2605.14019 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2605.14019

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().