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 π*(c). Working with the optimal concave and Lipschitz under only a feasible region value function v(c) = minz∈ Z c⊤ z, we show that regret always decomposes as Regret = −Cov(c,π*(c)) − R(c) for a residual R(c). We further show that R(c)=0 when π* 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 Regret ≤ D√(tr(Σ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.
Related
- Near-Optimal Regret Bounds for Monotone Stochastic Optimization under Semi-Bandit Feedback
- Sharp Regret Bounds and a Task-Covariance Correction for Spectral Representation Learning
- Regret-Based Scenario-Tree Construction for Multistage Stochastic Programs with Deterministic Constraints
- Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization
- Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization
BibTeX
@misc{aldridge2026regret,
title = {{Regret Equals Covariance: A Closed-Form Characterization for Stochastic Optimization}},
author = {Irene Aldridge},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2605.14019},
eprint = {2605.14019},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.14019},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Regret Equals Covariance: A Closed-Form Characterization for Stochastic Optimization
AU - Irene Aldridge
PY - 2026
DA - 2026/09/27
PB - arXiv
DO - 10.48550/arxiv.2605.14019
UR - https://arxiv.org/abs/2605.14019
AB - 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 π^*(c). Working with the optimal concave and Lipschitz under only a feasible region value function v(c) = min_z∈ Z c^⊤ z, we show that regret always decomposes as Regret = −Cov(c,π^*(c)) − R(c) for a residual R(c). We further show that R(c)=0 when π^* 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 Regret ≤ D√(tr(Σ_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.
ER -