Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
Rendered from LaTeX for readability, not typeset faithfully. Citation keys are highlighted; maths is left as source; figures, tables and equation environments are summarised rather than reproduced; unrecognised commands are greyed out so nothing is silently dropped. Email addresses are removed.
Optimizing Regret
abstractBuilding on the identity that expected regret equals the covariance between costs and decisions, this paper develops the complete derivative theory of the covariance regret functional. We derive the G\^ateaux derivative, showing that the universal steepest-descent direction is the contrarian
policy $-(c-\bar c)$, while ascent yields momentum. For linear policies $\hat\pi(c)=Ac+b$, the gradient is the cost covariance matrix $\Sigma_c$, with a zero Hessian implying boundary-optimal solutions such as the minimum-variance portfolio. We extend to constrained optimization, sign-gradient duality between regret minimization and alpha maximization, finite-sample
convergence bounds paralleling Thompson Sampling, and gradient-descent algorithms requiring only input observations.
Introduction and Motivation
aldridge2026 establishes that for linear optimization systems, the expected regret of any
policy $\hat\pi$ equals the covariance between uncertain costs and decisions:
equation[equation omitted — 97 chars of source]
This identity transforms performance measurement into a computable scalar. The natural next
question is: in which direction should the policy change to reduce regret? Answering it requires
differentiating the covariance functional with respect to the policy.
This paper derives the complete derivative theory for $\mathrm{Cov}(c,\hat\pi(c))$ as a functional of the policy mapping $\hat\pi:\mathcal{C}\to\mathcal{Z}$: Sections (ref)--(ref) derive its first- and second-order structure, constrained optima, and duality properties; Sections (ref) and (ref) give gradient-based algorithms and finite-sample guarantees; and Section (ref) presents financial applications.
Related Work
The covariance identity $\mathbb{E}[R(c)] = \mathrm{Cov}(c, \hat\pi(c))$ of aldridge2026 is a static optimization result, but the gradient algorithms and convergence guarantees we derive from it
(Sections (ref)--(ref)) connect to several strands of the no-regret learning literature.
Online convex optimization. Projected online gradient descent achieves $O(\sqrt{T})$ regret against an oblivious adversary zinkevich2003, with $O(\log T)$ rates for strongly convex or exp-concave losses HazanAgarwalKale2007,ShalevShwartz2007; see hazan2016 for a survey. Our covariance functional $C[A] = \mathrm{tr}(A\Sigma_c)$ is linear in $A$, so the projected gradient step $A_{k+1} = \Pi_{\mathcal{Z}}(A_k - \eta\hat\Sigma_c)$ attains a linear convergence rate (Theorem (ref)) rather than the generic $O(1/\sqrt{T})$ OCO
bound because the functional has zero curvature (Theorem (ref)) and the gradient is estimable from cost observations alone, without access to decision outputs.
Regret matching and CFR. Counterfactual regret minimization ZinkevichEtAl2007 builds on the Regret matching dynamics of HartMasColell2000, which converge to correlated equilibria by
weighting actions in proportion to cumulative regret. Our sign-gradient duality (Theorem (ref)) is structurally analogous: the regret-minimizing direction $-\Sigma_c$ and the alpha-maximizing direction $+\Sigma_c$ are opposite projections of the same gradient. Unlike RM/CFR,
however, our policy space is a function class evaluated under a fixed cost distribution, so our guarantee is a static convergence result rather than a per-round regret bound.
Thompson Sampling. AgrawalGoyal2013 establish matching problem-dependent and problem-independent finite-sample regret bounds for Thompson Sampling. Section (ref) derives direct analogs for our setting, with the cost covariance gaps $\Delta_{ij} = [\Sigma_c]_{ij}$ playing the role of the arm gaps $\Delta_i$.
Online portfolio selection. Universal portfolios cover1991 and related methods HelmboldEtAl1998 minimize worst-case regret against an adversarial return sequence on the probability simplex. Our framework instead minimizes expected regret under a fixed cost distribution over a general feasible set (long-short, leverage, and factor constraints).
The Derivative of the Covariance Functional
The functional and its domain
Let $c \in \mathcal{C} \subseteq \mathbb{R}^{d}$ be a random cost vector with
mean $\bar{c} = \mathbb{E}[c]$ and covariance matrix
$\Sigma_c = \operatorname{Cov}(c,c) \in \mathbb{R}^{d \times d}$. A policy
$\hat{\pi} \in \mathcal{P}$ is a measurable map from $\mathcal{C}$ to the feasible
set $\mathcal{Z} \subseteq \mathbb{R}^{n}$. The covariance functional is
equation[equation omitted — 229 chars of source]
By Aldridge (2026), $\mathbf{C}[\hat{\pi}] = \mathbb{E}[\mathcal{R}]$ whenever
$\mathbb{E}[\hat{\pi}(c)] = \pi^{*}$. We study $\mathbf{C}$ as an object to be
optimized over $\mathcal{P}$.
Gâteaux Derivative and the Universal Descent Direction
The Gâteaux derivative of $C$ at $\hat\pi$ in the direction of $\phi: \mathcal{C} \to \mathbb{R}^n$ is
equation[equation omitted — 115 chars of source]
theorem[Gâteaux derivative of covariance regret]
Let $\hat\pi \in \mathcal{P}$ be any policy with finite second moments. For any direction
$\phi: \mathcal{C} \to \mathbb{R}^n$,
\begin{equation}
D C[\hat\pi](\phi) = \mathrm{Cov}\big(c, \phi(c)\big).
\end{equation}
proofExpanding $C[\hat\pi + \epsilon\phi] = \mathbb{E}[(c-\bar c)^\top(\hat\pi(c) + \epsilon\phi(c) -
\mathbb{E}[\hat\pi(c)] - \epsilon\mathbb{E}[\phi(c)])] = C[\hat\pi] + \epsilon\,\mathrm{Cov}(c,\phi(c))$, since $\mathbb{E}[c-\bar c]=0$ kills the cross term. Subtract $C[\hat\pi]$, divide by $\epsilon$, and
take the limit.
Theorem (ref) shows the derivative of the covariance functional is itself a covariance functional: the regret identity is preserved under differentiation, and the result is independent of the current policy $\hat\pi$. The functional gradient (Riesz representer) is therefore
$g(c) = c - \bar c$, giving:
corollary[Universal steepest-descent direction]
The steepest-descent direction for $C$ in $L^2(P)$ is always $\phi^*(c) = -(c-\bar c)$, regardless of
$\hat\pi$; the steepest-ascent direction is $\phi^*(c) = +(c-\bar c)$.
proofBy Cauchy--Schwarz, $DC[\hat\pi](\phi) = \mathrm{Cov}(c,\phi) \geq -\|\phi\|_{L^2}\|c-\bar c\|_{L^2}$,
with equality when $\phi(c) \propto -(c-\bar c)$.
Economically, $\phi^*(c) = -(c-\bar c)$ is a contrarian/mean-reversion strategy (reduce the decision when costs are high), while $+(c-\bar c)$ is a momentum strategy — a first-principles derivation of why contrarian policies minimize regret and momentum policies maximize alpha.
The Linear Case: Matrix Gradient
For the finite-dimensional linear policy class $\hat\pi_\theta(c) = Ac+b$, $\theta=(A,b) \in
\mathbb{R}^{n\times d}\times\mathbb{R}^n$, Theorem (ref) specializes directly. Since
$\mathrm{Cov}(c,b)=0$,
equation[equation omitted — 72 chars of source]
corollary[Matrix gradient of covariance regret]
For linear policies, $\nabla_A C = \Sigma_c$, $\nabla_b C = 0_n$, and the Hessian with respect to
$\mathrm{vec}(A)$ is $H_A C = \Sigma_c \otimes I_n$.
proofImmediate from Theorem (ref) with $\phi(c) = \Delta A\, c$: $DC[\hat\pi](\Delta A\, c) =
\mathrm{Cov}(c, \Delta A\, c) = \mathrm{tr}(\Delta A\, \Sigma_c)$, identifying $\nabla_A C = \Sigma_c$.
The Hessian follows by vectorizing.
Since $\Sigma_c \succeq 0$, gradient descent always pulls $A$ toward zero — the minimum-variance
policy. At the per-entry level,
equation[equation omitted — 93 chars of source]
so regret is most sensitive along asset pairs with the largest cost covariance, and hedging those
pairs (driving the corresponding $A_{ij}$ toward zero) yields the greatest marginal regret reduction.
Second-Order Structure: Convexity, Concavity, and Saddle Points
theorem[Hessian of covariance regret]
For linear policies $\hat{\pi}(c) = Ac + b$, the covariance functional
is linear (and hence simultaneously convex and concave) in
$A$:
\begin{equation}
\mathbf{C}[\lambda A_1 + (1-\lambda)A_2, b]
\;=\; \lambda\mathbf{C}[A_1,b] + (1-\lambda)\mathbf{C}[A_2,b]
\quad\forall\,\lambda \in [0,1].
\end{equation}
Therefore $\mathbf{C}$ has no interior critical points in the
unconstrained linear-policy class: regret is minimized (or
maximized) on the boundary of the feasible set.
proof$\mathbf{C}[A,b] = \operatorname{tr}(A\Sigma_c)$ is linear in $A$, so it is both convex and
concave. All second derivatives are zero.
theorem[Nonlinear policies: second-order conditions]
For a general (possibly nonlinear) policy $\hat{\pi}$ parametrized by
$\theta \in \mathbb{R}^p$, the Hessian of $\mathbf{C}$ with respect to $\theta$
evaluated at $\theta_0$ is:
\begin{equation}
\mathbf{H}_\theta\mathbf{C}\big|_{\theta_0}
\;=\; \mathbb{E}\!\left[
(c - \bar{c})^{\top}
\frac{\partial^2\hat{\pi}}{\partial\theta\partial\theta^{\top}}
\right].
\end{equation}
A critical point $\theta^*$ (where $\nabla_\theta\mathbf{C} = 0$) is:
\begin{itemize}
• a local minimum (regret-minimizing policy) if
$\mathbf{H}_\theta\mathbf{C}\big|_{\theta^*} \succcurlyeq 0$;
• a local maximum (alpha-maximizing policy) if
$\mathbf{H}_\theta\mathbf{C}\big|_{\theta^*} \preccurlyeq 0$;
• a saddle point if the Hessian is indefinite.
\end{itemize}
proofDifferentiate $\nabla_\theta\mathbf{C} = \mathbb{E}[(c-\bar c)^{\top}
\partial\hat{\pi}/\partial\theta]$ again with respect to $\theta$,
exchanging differentiation and expectation by dominated convergence
(assuming the policy is twice differentiable with bounded second
derivatives). The result follows.
Constrained Optimization: The Regret Lagrangian
In portfolio optimization, the policy must satisfy feasibility
constraints. We derive the constrained gradient and the conditions
for an interior optimum.
General constrained problem
The regret minimization problem is:
equation[equation omitted — 164 chars of source]
The Lagrangian is:
equation[equation omitted — 163 chars of source]
KKT conditions: $D\mathcal{L}[\hat{\pi}^*, \lambda^*](\phi) = 0$ for all
feasible $\phi$, complementary slackness $\lambda_k^* g_k(\hat{\pi}^*) = 0$,
and dual feasibility $\lambda_k^* \geq 0$.
Budget and Return Constraints
We solve the general constrained problem for two practically important feasible sets: the minimum-variance portfolio (budget constraint alone) and
the return-targeted frontier (budget plus a return floor). Both follow from the same KKT system applied to the linear policy $w = Ac+b$.
For the budget constraint $\mathbf{1}^\top w = 1$ with non-negativity $w \geq 0$, introduce a multiplier $\mu$ for the budget and $\nu \geq 0$ for non-negativity:
equation[equation omitted — 122 chars of source]
Adding a return target $\bar r^\top(A\bar c+b)\geq\mu_0$ introduces a second multiplier $\kappa$, giving rise to the general stationarity conditions
equation[equation omitted — 167 chars of source]
corollary[Minimum-variance portfolio]
With $\kappa=0$ (no return constraint), (ref) reduces to $\Sigma_c=0$ unless the minimum is attained at the boundary $A^*=0$. For $\Sigma_c\succ0$, the budget-constrained regret minimum over linear policies is
\begin{equation}
A^*=0, \qquad b^* = \Sigma_c^{-1}\mathbf{1}\big/(\mathbf{1}^\top\Sigma_c^{-1}\mathbf{1}),
\end{equation}
the minimum-variance portfolio.
proof[Proof sketch]
$C[A,b]=\mathrm{tr}(A\Sigma_c)$ is linear and increasing along any direction where $\Sigma_c\succ0$, so the constrained minimum over the budget simplex sits at $A=0$; the resulting problem in $b$ subject to $\mathbf{1}^\top b=1$ is the standard MVP quadratic program.
corollary[Regret-return efficient frontier]
With $\kappa>0$, (ref) gives $A^* = \kappa\,\Sigma_c^{-1}\bar r\bar c^\top$, and the set of policies minimizing regret subject to a return target $\mu_0$ traces out a frontier
\begin{equation}
C^*(\mu_0) = \kappa^*\,\bar c^\top\Sigma_c^{-1}\bar r\cdot\mathrm{tr}(\Sigma_c),
\end{equation}
parameterized by $\kappa^*\geq0$ chosen so that the return constraint binds. This is the covariance-based analog of the Markowitz mean-variance frontier.
proof[Proof sketch]
Set $\nabla_A L = \Sigma_c - \kappa\bar r\bar c^\top = 0$ and solve for $A^*$; substitute into $C[A^*,b]$ and choose $\kappa$ so that the return constraint binds.
Sign-Gradient Duality: Minimizing Loss vs.\ Maximizing Alpha
theorem[Sign-gradient duality]
For a cost-minimization problem, the regret-minimizing gradient
direction is $-\Sigma_c$ (reduce cost sensitivity). For the
equivalent return-maximization problem with $r = -c$:
\begin{equation}
\nabla_A\operatorname{Cov}(r, \hat{\pi}(r))
\;=\; \Sigma_r \;=\; \Sigma_c.
\end{equation}
The alpha-maximizing gradient direction is $+\Sigma_c$
(increase return sensitivity). The identical gradient magnitude
with opposite signs reflects the sign-gradient duality:
\begin{equation}
\underbrace{minimize regret}_{subtract \eta\Sigma_c}
\;\longleftrightarrow\;
\underbrace{maximize alpha}_{add \eta\Sigma_c}.
\end{equation}
proofFor $r = -c$, $\operatorname{Cov}(r, Ar + b) = \operatorname{tr}(A\Sigma_r) = \operatorname{tr}(A\Sigma_c)$
(since $\Sigma_r = \Sigma_{-c} = \Sigma_c$). Maximizing this is
equivalent to following the gradient $+\Sigma_c$, while minimizing
regret follows $-\Sigma_c$.
Sensitivity Analysis: Cross-Derivatives
remark[Regret sensitivity to volatility and mean]
Since $C[A,b]=\mathrm{tr}(A\Sigma_c)$ depends on $\Sigma_c$ but not on $\bar c$, regret is insensitive to the cost mean ($\partial C/\partial\bar c=0$) and linearly sensitive to the cost covariance, with the sensitivity matrix $A$ itself, $\partial C/\partial\Sigma_c=A$; in the isotropic
case $\Sigma_c=\sigma_c^2 I$, this gives volatility elasticity $\partial C/\partial\sigma_c^2=\mathrm{tr}(A)$.
Gradient-Based Algorithms for Policy Optimization
Projected gradient descent for regret minimization
Given a step size $\eta>0$, an initial policy $A_0$, and a feasible set $\mathcal{Z}$, covariance gradient descent proceeds by observing $N$ cost realizations $c_1,\dots,c_N$, estimating $\hat\Sigma_c = \frac{1}{N-1}\sum_i (c_i-\bar c)(c_i-\bar c)^\top$, and updating
$A_{k+1}=\Pi_{\mathcal{Z}}(A_k-\eta\hat\Sigma_c)$ until $\|A_{k+1}-A_k\|<\varepsilon$. The gradient step $-\eta\hat\Sigma_c$ is computable from input data alone — no output observations are needed for
the gradient, only for estimating $\hat\Sigma_c$.
Variants: Natural and Confidence-Weighted Gradients
Two variants extend Algorithm (ref) along complementary axes: the natural policy gradient pre-multiplies the update by the inverse Fisher information metric, reducing to $A_{k+1}=A_k-\eta\Omega$ for linear Gaussian policies and yielding scale invariance across cost distributions, while the confidence-weighted gradient of ChenDidisheimSomoza2026 re-weights observations by an entropy-based confidence score to concentrate updates on the most reliable cost signals.
Convergence rate
theorem[Convergence of covariance gradient descent]
For the unconstrained linear-policy problem with step size
$\eta \leq 1/\left\lVert \Sigma_c \right\rVert_2$, the projected gradient descent
of Algorithm (ref) satisfies:
\begin{equation}
\mathbf{C}[A_k] - \mathbf{C}[A^*]
\;\leq\; (1 - \eta\lambda_{\min}(\Sigma_c))^k
(\mathbf{C}[A_0] - \mathbf{C}[A^*]).
\end{equation}
The convergence rate is determined by the condition number
$\kappa(\Sigma_c) = \lambda_{\max}(\Sigma_c)/\lambda_{\min}(\Sigma_c)$
of the cost covariance matrix. Ill-conditioned portfolios
(near-collinear assets) converge slowly; diversified portfolios
converge rapidly.
proofSince $\mathbf{C}[A,b] = \operatorname{tr}(A\Sigma_c)$ is linear in $A$ with
gradient $\Sigma_c$, the projected gradient step contracts the
distance to $A^*$ by factor $(1-\eta\lambda_{\min}(\Sigma_c))$
at each iteration, giving (ref) by induction.
Finite-Sample Regret Bounds
The convergence rate in Theorem (ref) is asymptotic. Practitioners need to know how many gradient steps and how many cost observations are required to bring regret below a target
tolerance. We answer both questions, in direct analogy with the finite-time analysis of Thompson Sampling by AgrawalGoyal2013, who bound cumulative bandit regret in terms of arm-gap parameters
$\Delta_i$.
Setup
Recall $C[A,b] = \mathrm{tr}(A\Sigma_c)$ and $\partial C/\partial A_{ij} = [\Sigma_c]_{ij}$
(Corollary (ref)). The optimum is $A^*=0$ (Theorem (ref)), giving
$C[A^*,b^*]=0$.
definition[Asset-pair gap]
For $i,j \in \{1,\dots,d\}$, define $\Delta_{ij} := [\Sigma_c]_{ij}$, with minimum and maximum eigenvalue gaps $\Delta_{\min} := \lambda_{\min}(\Sigma_c) > 0$, $\Delta_{\max} :=
\lambda_{\max}(\Sigma_c)$, and condition number $\kappa := \Delta_{\max}/\Delta_{\min}$.
The gaps $\Delta_{ij}$ play the role of the bandit arm gaps $\Delta_i$: they measure how much regret is generated per unit of allocation weight $A_{ij}$, with regret being most sensitive along the directions of the largest $|\Delta_{ij}|$.
Problem-Dependent Bound
We assume cost vectors are sub-Gaussian: $\mathbb{E}[e^{s^\top(c-\bar c)}] \leq e^{\sigma^2\|s\|^2/2}$ for some $\sigma>0$ and all $s \in \mathbb{R}^d$.
theorem[Problem-dependent finite-sample bound]
Let $\Sigma_c \succ 0$ with minimum eigenvalue $\Delta_{\min}$ and condition number $\kappa$. Run Algorithm (ref) with step size $\eta = 1/\|\Sigma_c\|$ and the true gradient $\Sigma_c$. After $K$ steps, starting from any $A_0$,
\begin{equation}
C[A_K] - C[A^*] \leq \left(1 - \tfrac{1}{\kappa}\right)^K C[A_0].
\end{equation}
To achieve excess regret of at most $\varepsilon$, it suffices to take
\begin{equation}
K(\varepsilon) = \kappa \ln\!\big(C[A_0]/\varepsilon\big)
\end{equation}
gradient steps.
proof[Proof sketch]
$C[A]=\mathrm{tr}(A\Sigma_c)$ is linear with a gradient $\Sigma_c$, so $\|A_{k+1}\| \leq
\|A_k\|(1-\eta\lambda_{\min}(\Sigma_c))$; setting $\eta=1/\Delta_{\max}$ gives the contraction factor $1-1/\kappa$. Since $C$ inherits the same geometric contraction, solving for $K$ gives the bound.
Sample Complexity
In practice, $\Sigma_c$ must be estimated from $N$ i.i.d. cost observations via $\hat\Sigma_c = \frac{1}{N-1}\sum_i (c_i-\bar c)(c_i-\bar c)^\top$.
theorem[Sample complexity for gradient estimation]
For sub-Gaussian costs with parameter $\sigma^2$, any $\delta \in (0,1)$, and target gradient error $\xi > 0$, a sample of size
\begin{equation}
N \geq C \,\frac{\sigma^4 d \ln(d/\delta)}{\xi^2}
\end{equation}
(universal constant $C>0$) guarantees $\|\hat\Sigma_c - \Sigma_c\| \leq \xi$ with probability of at least $1-\delta$. Running Algorithm (ref) with $\hat\Sigma_c$ and step size
$\eta = 1/(\|\Sigma_c\|+\xi)$, the stochastic iterates satisfy
\begin{equation}
\mathbb{E}\big[C[A_K]\big] - C[A^*] \leq \left(1 - \tfrac{\Delta_{\min}}{\Delta_{\max}+\xi}\right)^K
C[A_0] \;+\; \frac{\xi\|A_0\|_F}{\Delta_{\min}},
\end{equation}
where the first term decays geometrically and the second is a statistical bias vanishing as
$N \to \infty$.
proof[Proof sketch]
The spectral-norm bound follows from the matrix Bernstein inequality applied to the rank-1 summands
$(c_i-\bar c)(c_i-\bar c)^\top$ tropp2015. The convergence bound follows by bounding the
perturbation $\mathrm{tr}((\Sigma_c-\hat\Sigma_c)\Sigma_c)$ in the one-step update and applying a union bound over $K$ steps.
Financial Application: Optimal tilt away from the minimum-variance portfolio
The MVP has $A = 0$ and zero regret. An asset manager who wishes
to take active bets (tilt toward expected alpha) does so by adding
$\Delta A \neq 0$. The regret cost of a tilt $\Delta A$ is:
equation[equation omitted — 99 chars of source]
which is the trace of the product of the tilt matrix and the cost
covariance. The regret-optimal tilt toward a target
allocation $w_{\mathrm{target}}$ is:
equation[equation omitted — 172 chars of source]
whose solution is $\Delta A^* = (w_{\mathrm{target}} - w_{\mathrm{MVP}})\bar{c}^{\top}
(\bar{c}\bar{c}^{\top})^{-1}$, a rank-1 update.
Conclusion
The Gâteaux derivative of the covariance-based regret functional is itself a covariance, preserving the self-referential structure of the regret identity under differentiation. This yields a universal, policy-independent descent direction $\phi^*(c)=-(c-\bar c)$ — the contrarian/mean-reversion strategy, with the momentum strategy $+(c-\bar c)$ as its ascent
counterpart — and, for linear policies $\hat\pi=Ac+b$, a matrix gradient equal to the cost covariance $\Sigma_c$, with the minimum-variance portfolio ($A=0$) as the unique unconstrained minimizer and the maximum-leverage momentum policy as its maximizer. Minimizing loss and
maximizing alpha are gradient descent and ascent on the same functional, with the unified update $A \leftarrow A \mp \eta\Sigma_c$. Because the gradient $\hat\Sigma_c$ is estimable from input data alone, with no output observations required, gradient descent on regret is a zero-instrumentation
algorithm, consistent with the black-box evaluation framework of aldridge2026.