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

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.

Econometrics (econ.EM); Machine Learning (cs.LG); Statistics Theory (math.ST); Computation (stat.CO)

arXiv:2605.14019 [econ.EM]

(or arXiv:2605.14019v2 [econ.EM] for this version)

https://doi.org/10.48550/arXiv.2605.14019 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.