Regret Equals Integrated Covariance: Exact Identities for the Value of Information in Stochastic Optimization
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 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-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. 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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.Where the paper says it
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 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.Where the paper says it
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 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.Where the paper says it
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 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. Consequently, the median-of-means auditor of Theorem 5. p. 9 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 6
is correct when dynamics are exogenous. Under endogenous dynamics it can be arbitrarily wrong. Under endogenous dynamics it can be arbitrarily wrong. Proposition 3. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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.Where the paper says it
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 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 ν. The last term is non-negative because z¯ ∈ Z by convexity. Corollary 3. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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.Where the paper says it
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 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/η)
. 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
.Where the paper says it
Where the paper says it
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 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. 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 µ.Where the paper says it
Where the paper says it
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 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.Where the paper says it
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 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). 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-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. 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. 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. Adaptivity gaps. The benefit of adaptivity is studied as a multiplicative ratio for stochastic
knapsack [10], stochastic probing [13] and submodular maximization [4]. Adaptivity gaps. The benefit of adaptivity is studied as a multiplicative ratio for stochastic
knapsack [10], stochastic probing [13] and submodular maximization [4]. 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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
-
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 - η.
-
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.
-
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/η).
-
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
- Evaluating AI Investment Strategies
- Regret Equals Covariance: A Closed-Form Characterization for Stochastic Optimization
Related papers
- Stationarity with Occasionally Binding Constraints
- Backtesting High-Dimensional Expected Shortfall
- Higher-Order Neyman Orthogonality in Moment-Condition Models
- Online Bayesian Inference for a Dirichlet Process Mixture of Binary Logit Models
- Debiased Conditional Independence Tests for Causal Effects
- Sharp Testable Implications of Encouragement Designs