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

arXiv:2611.05227 · econ.EM, cs.IT, cs.LG, math.IT · Submitted 2026-11-03 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Economics. The day in economics: theory, mechanisms and the evidence beneath them.

Ruth: I'm Ruth.

Warren: And I'm Warren, here with Iris.

Ruth: We're looking at the paper: "Regret Equals Integrated Covariance".

Warren: Here's the gist of the paper. A policy can earn its performance by where it locates on average or by reacting to information<ref:2611.05227#pg2> For any Markov policy π in a finite-horizon MDP, let ν be its open-loop marginal, which plays π’s average action distribution at each step<ref:2611.05227#pg4> We show that J(π) − J(ν) equals Pt tr Cov(Qνt, πt) under endogenous dynamics<ref:2611.05227#pg5> Audits based on immediate costs alone can have the wrong P sign<ref:2611.05227#pg9> Writing the covariance as a joint-versus-product gap gives the bound J(π) − J(ν) ≤ t spant p I(st; at)/2, with a sharp constant Hence, an MDP’s adaptivity gap is bounded by the information that its optimal policy uses Estimating J(π) − J(ν) from π’s own bandit feedback logs takes Θ(χ¯2 log(1/η)/δ2) rounds, where χ¯2 is an average χ2-divergence At the same time, deterministic non-constant policies cannot be audited at all.

Ruth: Exact Characterization of Adaptivity The exact characterization of the performance difference between a policy and its open-loop marginal is given by an identity involving a covariance term Specifically, for every finite-horizon MDP and every Markov policy π, J(π) − J(ν) = X H t=1 tr Covst∼d πt Q νt (st, ·), πt(· st) This identity holds under fully endogenous dynamics.

Warren: The identity is invariant to adding any function of the state to Qνt, and choosing the per-state midpoint replaces the global oscillation of Qνt by the much smaller per-state action range.

Ruth: Information Theoretic Limits The right-hand form of the exact characterization compares a joint law to the product of its marginals, and their KL divergence is related to mutual information I(st; at) Pinsker’s inequality yields an informal statement that J(π) − J(ν) ≤ P t spant p I(st; at)/2 This leads to the conclusion that the additive adaptivity gap of an MDP is at most P t spant p It/2 evaluated at any optimal policy.

Paper summary: Ruth: So looking at this paper, "Regret Equals Integrated Covariance: Exact Identities for the Value of Information in Stochastic Optimization", it’s really about moving beyond simple regret bounds and giving us an exact mathematical structure for the difference between a policy and its baseline.

Warren: The authors show that this performance difference is exactly equal to that integral of the covariance term, which links it directly to how much information the policy is using across time, under fully endogenous dynamics.

Iris: What this means in practice is that we don't just need to watch immediate rewards; we need a way to look at the structure of state and action interaction over time, which they’ve managed to do mathematically. They also provide an important sample complexity result for episodic MDPs using an importance-sampling auditor.

Ruth: The implication for us is that when we try to evaluate complex adaptive systems, understanding the information flow between what's happening in the world and what your system does is a direct path to bounding the error you make in estimating its true value. It connects optimization directly to information theory.

Warren: And they confirm that while this identity is powerful, their method for auditing still requires a certain amount of data, which scales with that chi squared term, so we have to be mindful of the cost if we want a precise measurement.

Iris: The limitation they point out is that this characterization relies on fully endogenous dynamics and their specific auditor needs an importance-sampling approach for episodic MDPs, which means you’re dealing with a whole trajectory at once.

Conclusion: Ruth: So we’ve seen how this paper gives us an exact mathematical way to measure how much performance you lose when your policy isn't using all the information available, which is what they call the adaptivity gap.

Warren: Yeah, and that gap isn't just some loose estimate anymore; it's tied directly to the integral of a covariance term over time. That’s what they call integrated covariance.

Iris: From my side, I see them tying this performance difference to mutual information between the state and the action over time. It makes sense because that’s fundamentally how much a policy can actually learn from experience.

Ruth: Exactly, and it suggests that if you want to improve a policy's value without just tinkering with immediate costs, you need to figure out exactly what information it’s missing or using inefficiently.

Warren: The authors show this relationship holds under fully endogenous dynamics, meaning the system is reacting in a way that depends on its own history, which is the tricky part for traders because things don't stay fixed.

Iris: And they give us a bound based on that information, saying the gap is at most proportional to mutual information between state and action over time. That’s actually really helpful for setting expectations about how much better a smarter policy can do than a baseline one.

Ruth: So, looking at the title 'Regret Equals Integrated Covariance', it tells us that regret in this context isn't just about short-term mistakes, it’s fundamentally about the accumulated correlation between what’s happening and what we choose to do.

Warren: It means if you want to minimize long-term losses, you have to optimize for the structure of that covariance term itself. If that term is small, your policy is already pretty good without needing super complex information gathering.

Iris: The main implication for us as researchers is that this gives us a concrete quantity—that integrated covariance—to measure adaptivity instead of just relying on vague notions of learning speed.

Ruth: And it opens up a new way to think about how much value is actually hidden in the data you collect when you’re trying to make decisions in a complex system.

econ.EM, cs.IT, cs.LG, math.IT

Submitted: 2026-11-03

Updated: 2026-11-07

Comments: 13 pages

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 92/100

The gist: A policy can earn its performance by where it locates on average or by reacting to information<ref:2611.05227#pg2> For any Markov policy π in a finite-horizon MDP…

Key concepts

Open-loop Marginal ($ u$)
This is the average action distribution a policy takes at each step without considering future consequences. It represents what the policy *would* do if it didn't react to new information, serving as a baseline for comparison against an adaptive policy.
Adaptivity Gap ($J(\pi) - J(\nu)$)
This measures the performance difference between a reactive policy ($\pi$) and its open-loop counterpart ($ u$). It quantifies the benefit gained by using information to adjust actions based on observed states, which is central to understanding how much information improves outcomes.
Covariance Term ($tr Cov(Q_{\nu t}, \pi_t)$)
This term represents the core mathematical link between the policy's performance and its adaptability. It shows that the performance difference is exactly equal to this covariance term under endogenous dynamics, linking adaptation directly to how state and action distributions vary together.

Terminology

Summary

A policy can earn its performance by where it locates on average or by reacting to information<ref:2611. p. 0

Where the paper says it

Regret-based Characterization, Information Limits, and the Sample Complexity of Auditing Adaptive Policies Irene Aldridge∗ Abstract A policy can earn its performance by where it locates on average or by reacting to information. For any Markov policy π in a finite-horizon MDP, let ν be its open-loop marginal, which plays π’s average action distribution at each step.

05227#pg2> For any Markov policy π in a finite-horizon MDP, let ν be its open-loop marginal, which plays π’s average action distribution at each step<ref:2611. p. 0
Where the paper says it

Regret-based Characterization, Information Limits, and the Sample Complexity of Auditing Adaptive Policies Irene Aldridge∗ Abstract A policy can earn its performance by where it locates on average or by reacting to information. For any Markov policy π in a finite-horizon MDP, let ν be its open-loop marginal, which plays π’s average action distribution at each step.

05227#pg4> We show that J(π) − J(ν) equals Pt tr Cov(Qνt, πt) under endogenous dynamics<ref:2611. p. 0
Where the paper says it

For any Markov policy π in a finite-horizon MDP, let ν be its open-loop marginal, which plays π’s average action distribution at each step. We show that J(π) − J(ν) equals P t tr Cov(Qν t , πt) under endogenous dynamics.

05227#pg5> Audits based on immediate costs alone can have the wrong P sign<ref:2611. p. 0
Where the paper says it

We show that J(π) − J(ν) equals P t tr Cov(Qν t , πt) under endogenous dynamics. Audits based on immediate costs alone can have the wrong P sign.

05227#pg9> Writing the covariance as a joint-versus-product gap gives the bound J(π) − J(ν) ≤ t spant p I(st; at)/2, with a sharp constant Hence, an MDP’s adaptivity gap is bounded by the information that its optimal policy uses Estimating J(π) − J(ν) from π’s own bandit feedback logs takes Θ(χ¯2 log(1/η)/δ2) rounds, where χ¯2 is an average χ2-divergence At the same time, deterministic non-constant policies cannot be audited at all. p. 0
Where the paper says it

Writing the covariance as a joint-versus-product gap gives the bound |J(π) − J(ν)| ≤ t spant p I(st; at)/2, with a sharp constant. Hence, an MDP’s adaptivity gap is bounded by the information that its optimal policy uses.

Exact Characterization of Adaptivity

The exact characterization of the performance difference between a policy and its open-loop marginal is given by an identity involving a covariance term Specifically, for every finite-horizon MDP and every Markov policy π, J(π) − J(ν) = X H t=1 tr Covst∼d πt Q νt (st, ·), πt(· st) This identity holds under fully endogenous dynamics. The identity is invariant to adding any function of the state to Qνt, and choosing the per-state midpoint replaces the global oscillation of Qνt by the much smaller per-state action range. p. 2

Where the paper says it

Second, a covariance between a function of the state and a function of the action is EP f − EP S⊗P A f, so any divergence bound between a joint law and its product applies. The identity is invariant to adding any function of the state to Qν t , and choosing the per-state midpoint replaces the global oscillation of Qν t by the much smaller per-state action range.

Information Theoretic Limits

The right-hand form of the exact characterization compares a joint law to the product of its marginals, and their KL divergence is related to mutual information I(st; at) Pinsker’s inequality yields an informal statement that J(π) − J(ν) ≤ P t spant p I(st; at)/2 This leads to the conclusion that the additive adaptivity gap of an MDP is at most P t spant p It/2 evaluated at any optimal policy. Furthermore, a policy whose actions carry at most R units of mutual information between state and action per step cannot beat the best open-loop policy by more than H(H+1) 2 p R/2. p. 1

Where the paper says it

And with costs in [0, 1], a policy whose actions carry at most R units of mutual information between state and action per step (a. R ”nats”) cannot beat the best open-loop policy by more than H(H+1) 2 p R/2 (Theorem 4.

Sample Complexity of Auditing

Estimating the adaptivity cost ∆(π) from bandit feedback logs reduces to off-policy evaluation of the open-loop marginal ν π, and the right complexity parameter is χ¯2(π):= Ex h χ2¯ π(· x) A median-of-means IPW auditor estimates ∆(π) within ±δ with probability 1 − η from O(χ¯2 log(1/η)/δ2) logged rounds, for every policy and instance. Conversely, for every value Γ ≥ 1/3 there is a policy with χ¯2 = Γ and two instances on which every auditor needs Ω(Γ log(1/η)/δ2) rounds. p. 1

Where the paper says it

A median-of-means IPW auditor estimates ∆(π) within ±δ with probability 1 − η from O(χ¯ 2 log(1/η)/δ2 ) logged rounds, for every policy and instance. Conversely, for every value Γ ≥ 1/3 there is a policy with χ¯ 2 = Γ and two instances on which every auditor needs Ω(Γ log(1/η)/δ2 ) rounds.

Episodic MDP Auditing

For episodic MDPs, an importance-sampling auditor over whole trajectories needs a number of episodes n = O H2χ2(Pν∥Pπ) log(1/η)/δ2, where 1 + χ2(Pν∥Pπ) ≤ Q t 1 + max s∈supp d πt χ2¯ πt(· s). The median-of-means auditor of Theorem 5. p. 9

Where the paper says it

Moreover 1 + χ 2 (P ν ∥P π ) ≤ Y H t=1 1 + max s∈supp d π t χ 2 p¯t ∥ πt(· | s) . Consequently, the median-of-means auditor of Theorem 5.

3 applied to Y is (δ, η)-accurate after n =⌈4H2χ2(Pν∥Pπ)/δ2⌉⌈8 ln(1/η)⌉ episodes. p. 9
Where the paper says it

Consequently, the median-of-means auditor of Theorem 5. p. 9

Where the paper says it

Moreover 1 + χ 2 (P ν ∥P π ) ≤ Y H t=1 1 + max s∈supp d π t χ 2 p¯t ∥ πt(· | s) . Consequently, the median-of-means auditor of Theorem 5.

3 applied to Y is (δ, η)-accurate after n = ⌈4H2χ 2 (P ν∥P π )/δ2 ⌉⌈8 ln(1/η)⌉ episodes.

p. 9
Where the paper says it

Consequently, the median-of-means auditor of Theorem 5. 3 applied to Y is (δ, η)-accurate after n = ⌈4H2χ 2 (P ν∥P π )/δ2 ⌉⌈8 ln(1/η)⌉ episodes.

Myopic Audits Fail

A tempting shortcut is to audit with immediate costs, P t tr Cov(lt(st, ·), zt), which by Theorem 3.6 is correct when dynamics are exogenous Under endogenous dynamics it can be arbitrarily wrong. p. 5

Where the paper says it

6 is correct when dynamics are exogenous. Under endogenous dynamics it can be arbitrarily wrong.

Proposition 3. p. 5
Where the paper says it

Under endogenous dynamics it can be arbitrarily wrong. Proposition 3.

8 shows that for every m > 1 there is a two-step MDP with two states and two actions, and a deterministic policy π, such that X t tr Cov lt(st, ·), zt = 1/4 > 0 while J(π) − J(ν π) = 1−m/4 < 0. p. 5
Where the paper says it

8 (Sign reversal). For every m > 1 there is a two-step MDP with two states and two actions, and a deterministic policy π, such that X t tr Cov ℓt(st , ·), zt = 1 4 > 0 while J(π) − J(ν π ) = 1−m 4 < 0.

Decomposition of Regret

The three-part decomposition shows that for every Markov policy π, J(π) − J(π∗) = X t tr Cov(qt, zt) z adaptivity cost ∆(π) + J(ν π) − J(ν ∗) static allocation ≥0 + Gap(M) z≥0. Consequently, Gap(M) = −∆(π∗) − J(ν π∗) − J(ν ∗) ≤ −∆(π∗). p. 5

Where the paper says it

For every Markov policy π, J(π) − J(π ∗ ) = X t tr Cov(qt , zt) | {z } adaptivity cost ∆(π) + J(ν π ) − J(ν ∗ ) | {z } static allocation ≥0 + Gap(M) | {z } ≥0 . Consequently Gap(M) = −∆(π ∗ ) − J(ν π ∗ ) − J(ν ∗ ) ≤ −∆(π ∗ ) for every optimal π ∗ , with equality if and only if the open-loop marginal of π ∗ is an optimal open-loop policy.

Information Bound on Adaptivity Gap

Theorem 4.2 states that for every finite-horizon MDP and every Markov policy π, J(π) − J(ν π) ≤ X H t=1 spant p I(st; at)/2. p. 1

Where the paper says it

In every finite-horizon MDP and for every Markov policy π, J(π) − J(ν) = X H t=1 tr Covst∼d π t Q ν t (st , ·), πt(· | st) (1) J(π) − J(ν) = X H t=1 EPt Q ν t − EP S t ⊗P A t Q ν t , (2) where Pt is the joint law of (st , at) under π and P S t ⊗P A t is the product of its marginals (Theorem 3. The identity holds under fully endogenous dynamics; the feedback from actions to states is absorbed by evaluating the covariance under π’s state distribution and pairing actions with the Q-function of ν.

Corollary 4. p. 4
Where the paper says it

The last term is non-negative because z¯ ∈ Z by convexity. Corollary 3.

4 then shows that the adaptivity gap is bounded by the information used by an optimal policy. p. 0
Where the paper says it

Writing the covariance as a joint-versus-product gap gives the bound |J(π) − J(ν)| ≤ t spant p I(st; at)/2, with a sharp constant. Hence, an MDP’s adaptivity gap is bounded by the information that its optimal policy uses.

Rate-Value Tradeoff

If a Markov policy π satisfies I(st; at) ≤ Rt for every t, then J(π) ≥ J(ν∗) − X H t=1 (H − t + 1)p Rt/2. In particular, with a constant budget R, J(ν∗) − J(π) ≤ H(H+1) 2 p R/2. p. 6

Where the paper says it

If a Markov policy π satisfies I(st ; at) ≤ Rt for every t, then J(π) ≥ J(ν ∗ ) − X H t=1 (H − t + 1)p Rt/2. In particular, with a constant budget R, J(ν ∗ ) − J(π) ≤ H(H+1) 2 p R/2.

Sample Complexity in Contextual Bandits

The complexity parameter χ¯2(π) is the right complexity parameter for auditing contextual bandits Theorem 5.3 shows that if χ¯2(π) < ∞, this auditor is (δ, η)-accurate on every instance once T ≥ l 4 χ¯2(π) δ2/m · 8 ln(1/η). p. 7

Where the paper says it

Split T rounds into k = ⌈8 ln(1/η)⌉ blocks of m = ⌈4χ¯ 2 (π)/δ2 ⌉ rounds each, and output the median of the block means. If χ¯ 2 (π) < ∞, this auditor is (δ, η)-accurate on every instance once T ≥ l 4 ¯χ 2 (π) δ 2 m · 8 ln(1/η) .

Theorem 5.4 establishes a lower bound on the required sample size for every Γ ≥ 1/3. p. 8
Where the paper says it

4 (Lower bound). For every Γ ≥ 1/3, δ ∈ (0, 1/32] and η ∈ (0, 1/8], there is a context distribution D and a policy π with χ¯ 2 (π) = Γ, together with two cost models, such that every auditor that is (δ, η)-accurate on both instances requires T ≥ 9 2048 · (Γ + 1) ln1/(4η) δ 2 .

Episodic MDP Auditing Summary

Under Assumption 5.5, let W(τ) = Q H t=1 p¯t(at)/πt(at P st), L(τ) = t lt, and Y = L(τ)(1 − W(τ)). p. 0

Where the paper says it

For any Markov policy π in a finite-horizon MDP, let ν be its open-loop marginal, which plays π’s average action distribution at each step. We show that J(π) − J(ν) equals P t tr Cov(Qν t , πt) under endogenous dynamics.

Then EπY = J(π) − J(ν π) and Varπ(Y) ≤ H2χ2(Pν∥Pπ). p. 9
Where the paper says it

5, let W(τ ) = QH t=1 p¯t(at)/πt(at P | st), L(τ ) = t ℓt, and Y = L(τ )(1 − W(τ )). Then EπY = J(π) − J(ν π ) and Varπ(Y ) ≤ H2χ 2 (P ν∥P π ), where P µ denotes the trajectory law under µ.

Consequently, the median-of-means auditor of Theorem 5.3 applied to Y is (δ, η)-accurate after n =⌈4H2χ2(Pν∥Pπ)/δ2⌉⌈8 ln(1/η)⌉ episodes.

Numerical Illustration

Table 1 reports a 20-step lost-sales inventory MDP, exact computation. The myopic audit understates adaptive value by 22–78%, and the information bound holds with slack, as expected of a worst-case bound when I(st; at) is large. p. 9

Where the paper says it

The covariance identity holds to 10−13. The myopic audit understates adaptive value by 22–78%, and the information bound holds with slack, as expected of a worst-case bound when I(st ; at) is large.

References

[1] Shipra Agrawal and Navin Goyal. Near-optimal regret bounds for Thompson sampling [9] Kent Daniel, Mark Grinblatt, Sheridan Titman, and Russ Wermers. p. 2

Where the paper says it

1 is an elementary identity, but it provides a structural reading of regret: negative regret (beating the best fixed action) is possible only with negative sample covariance, and every no-regret algorithm has sample covariance of at most its regret. Applied to stochastic bandit algorithms such as Thompson sampling, whose regret is near-optimal [1], the decomposition separates an algorithm’s static exposure to suboptimal arms (the static gap) from the timing of its exploration (the covariance).

Measuring mutual fund performance with characteristic-based benchmarks [3] Irene Aldridge. p. 0
Where the paper says it

Regret-based Characterization, Information Limits, and the Sample Complexity of Auditing Adaptive Policies Irene Aldridge∗ Abstract A policy can earn its performance by where it locates on average or by reacting to information. For any Markov policy π in a finite-horizon MDP, let ν be its open-loop marginal, which plays π’s average action distribution at each step.

p. 0
Where the paper says it

Regret-based Characterization, Information Limits, and the Sample Complexity of Auditing Adaptive Policies Irene Aldridge∗ Abstract A policy can earn its performance by where it locates on average or by reacting to information. For any Markov policy π in a finite-horizon MDP, let ν be its open-loop marginal, which plays π’s average action distribution at each step.

Regret equals covariance: A closed-form characterization for stochastic optimization [4] Arash Asadpour and Hamid Nazerzadeh. p. 0
Where the paper says it

In finance, this is the classical split of active returns into a ”timing” (covariance) component and a ”static allocation” (means) component [9, 19]; in stochastic optimization, minν J(ν) − minπ J(π) is the additive adaptivity gap [10, 13]. Recent work by Aldridge [2, 3] observed that, for stochastic linear programs and portfolio policies, expected regret equals the covariance between costs and decisions when the policy is mean-unbiased.

p. 0
Where the paper says it

In finance, this is the classical split of active returns into a ”timing” (covariance) component and a ”static allocation” (means) component [9, 19]; in stochastic optimization, minν J(ν) − minπ J(π) is the additive adaptivity gap [10, 13]. Recent work by Aldridge [2, 3] observed that, for stochastic linear programs and portfolio policies, expected regret equals the covariance between costs and decisions when the policy is mean-unbiased.

Maximizing stochastic monotone submodular functions [7] Nicolò Cesa-Bianchi and Gábor Lugosi. p. 2
Where the paper says it

Adaptivity gaps. The benefit of adaptivity is studied as a multiplicative ratio for stochastic knapsack [10], stochastic probing [13] and submodular maximization [4].

p. 2
Where the paper says it

Adaptivity gaps. The benefit of adaptivity is studied as a multiplicative ratio for stochastic knapsack [10], stochastic probing [13] and submodular maximization [4].

Prediction, Learning, and Games [8] Thomas M. p. 2
Where the paper says it

The lower bound plants a cost perturbation on the context–action pair that π plays with probability p but ν π plays with probability 1/2, and applies the Bretagnolle–Huber inequality. 3 Related work Online learning and regret.

p. 2
Where the paper says it

The lower bound plants a cost perturbation on the context–action pair that π plays with probability p but ν π plays with probability 1/2, and applies the Bretagnolle–Huber inequality. 3 Related work Online learning and regret.

Cover and Joy A. Thomas. Elements of Information Theory [9] Kent Daniel, Mark Grinblatt, Sheridan Titman, and Russ Wermers. p. 3
Where the paper says it

Aldridge [2, 3] uses it as a regret characterization for stochastic linear programs and AI investment strategies under a mean-unbiasedness condition. The present paper removes that condition, extends the identity to endogenous dynamics, and supplies information and sample-complexity theory.

Measuring mutual fund performance with characteristic-based benchmarks [3] Irene Aldridge. Regret equals covariance: A closed-form characterization for stochastic optimization [4] Arash Asadpour and Hamid Nazerzadeh. Maximizing stochastic monotone submodular functions [7] Nicolò Cesa-Bianchi and Gábor Lugosi. Prediction, Learning, and Games [8] Thomas M. Cover and Joy A. Thomas.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improve auditing accuracy by using an importance-sampling auditor that requires n episodes for episodic MDPs, specifically using a number of episodes n = O(H2χ2(Pν∥Pπ) log(1/η)/δ2). This allows for estimation of the adaptivity cost ∆(π) with high probability 1 - η.

  2. Implement a rate-value tradeoff in decision-making by constraining the mutual information between state and action, I(st; at), to a budget Rt. A policy satisfying this constraint can be guaranteed to have J(π) >= J(ν∗) - X H t=1 (H − t + 1)p Rt/2.

  3. Design agent evaluation systems that utilize logged propensities and states to estimate adaptive value against the open-loop marginal using a median-of-means IPW auditor, achieving an accuracy of ±δ with probability 1 - η after T >= l 4 χ¯2(π) δ squared m ln(1/η).

  4. Develop a mechanism to detect deterministic non-constant policies that cannot be audited from their own logs by leveraging the non-identifiability results, stating that a deterministic non-constant policy cannot be audited from its own logs (Theorem 5.2).

Abstract

For a stochastic program 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 π 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=-integral 0 1 s-1 Cov(c s,π s(c s)),ds. Three consequences follow. First, the plain covariance is always an upper bound: 0 at most Reg at most-Cov(c,π 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.

Sources

Related papers