Abstract:Regret is the cost of uncertainty in algorithmic decision-making. Quantifying regret typically requires computationally expensive simulation via Sample Average Approximation (SAA), with complexity $\mathcal{O}(Bn^{2}d^{3})$ in the number of scenarios $B$, variables $n$, and constraints $d$. % This paper proves that expected regret in any stochastic optimization problem admits the exact decomposition % \begin{equation*}
\mathrm{Regret}(c)
= \mathrm{Cov}(c,\,\pi^{*}(c)) + R(c), \end{equation*} % where $c$ is the vector of uncertain parameters, $\pi^{*}(c)$ is the optimal decision, and $R(c)$ is a residual whose magnitude we bound explicitly under Lipschitz, smooth, and strongly convex conditions. % For linear programs and unconstrained quadratic programs, including the classical Markowitz portfolio problem, we prove $R(c)=0$ exactly, so that $\mathrm{Regret}(c) = \mathrm{Cov}(c,\pi^{*}(c))$ holds without approximation. % When historical cost-decision pairs $\{(c_i, \pi^*(c_i))\}$ are available, the covariance can be estimated in $\mathcal{O}(nd^{2})$ time, which is orders of magnitude faster than SAA. The estimation is performed by a single pass through the data. % We derive concentration bounds, a central limit theorem, and an asymptotically unbiased residual estimator, and we validate all results on synthetic LP, QP, and integer programming instances and on a rolling-window portfolio experiment using ten years of CRSP equity data.
| Comments: | 33 pages |
| Subjects: | Econometrics (econ.EM); Machine Learning (cs.LG); Statistics Theory (math.ST); Computation (stat.CO) |
| Cite as: | arXiv:2605.14019 [econ.EM] |
| (or arXiv:2605.14019v1 [econ.EM] for this version) | |
| https://doi.org/10.48550/arXiv.2605.14019 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Irene Aldridge [view email]
[v1]
Wed, 13 May 2026 18:32:44 UTC (260 KB)