stat.MLAug 7, 2026

Optimized Certainty Equivalent Risk Minimization Using Samples: Algorithms, Convergence Rates, and Applications

Authors: Sumedh Gupte, Prashanth L. A., Sanjay P. Bhat

Abstract

We consider the optimization of the Optimized Certainty Equivalent (OCE) risk, with applications including portfolio optimization in finance, and uncertainty quantification, classification, and regression in machine learning. Our contributions cover popular special cases of OCE, such as entropic risk, mean-variance risk, and smooth variants of Conditional Value-at-Risk. Our treatment sets out the conditions that facilitate the extension of OCE to unbounded r.v.s.. We provide a useful characterization of OCE that links OCE to utility-based shortfall risk (UBSR). Our characterization enables us to form an OCE estimator from the classic sample-average approximation (SAA) of UBSR. We derive mean-squared error (MSE) bounds for our proposed OCE estimator. For OCE optimization, we first derive an expression for the OCE gradient using the characterization linking OCE to UBSR. This expression serves as the basis for a gradient estimator for the OCE. We derive non-asymptotic bounds on the MSE for the proposed OCE gradient estimator. We incorporate the aforementioned gradient estimator into a stochastic gradient (SG) algorithm to optimize OCE and quantify its convergence rate using non-asymptotic bounds that we derive. Finally, we present three experiments that use our OCE optimization algorithm to solve portfolio optimization and uncertainty quantification problems.

Explore similar work

CardsList
May 13, 2026econ.EM

Regret Equals Covariance: A Closed-Form Characterization for Stochastic Optimization

Regret is the cost of uncertainty in algorithmic decision-making. Quantifying regret typically requires computationally expensive simulation via Sample Average Approximation (SAA), with complexity O(Bn2d3)\mathcal{O}(Bn^{2}d^{3}) in the number of scenarios BB, variables nn, and constraints dd. % This paper proves that expected regret in any stochastic optimization problem admits the exact decomposition % \begin{equation*} \mathrm{Regret}(c) = \mathrm{Cov}(c,,π^{}(c)) + R(c), \end{equation} % where cc is the vector of uncertain parameters, π∗(c)π^{*}(c) is the optimal decision, and R(c)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)=0R(c)=0 exactly, so that Regret(c)=Cov(c,π∗(c))\mathrm{Regret}(c) = \mathrm{Cov}(c,π^{*}(c)) holds without approximation. % When historical cost-decision pairs {(ci,π∗(ci))}\{(c_i, π^*(c_i))\} are available, the covariance can be estimated in O(nd2)\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.
Irene Aldridge
RegretStochastic OptimizationCovariance EstimationPortfolio OptimizationQuadratic ProgramsClosed-Form
AskPDF
Jul 21, 2026econ.EM

Optimizing Regret

Building on the identity that expected regret equals the covariance between costs and decisions, this paper develops a derivative theory of the covariance regret functional. We derive the Gâteaux derivative, showing that the universal steepest-descent direction is the contrarian policy −(c−cˉ)-(c-\bar c), while ascent yields momentum. For linear policies π^(c)=Ac+b\hatπ(c)=Ac+b, the gradient is the cost covariance matrix ΣcΣ_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.
Irene Aldridge
Dynamic Regret BoundsRegretStochastic OptimizationOptimal PoliciesGradient DescentPolicy Gradient
AskPDF
May 20, 2026cs.LG

On the Sample Complexity of Discounted Reinforcement Learning with Optimized Certainty Equivalents

We study risk-sensitive reinforcement learning in finite discounted MDPs, where a generative model of the MDP is assumed to be available. We consider a family or risk measures called the optimized certainty equivalent (OCE), which includes important risk measures such as entropic risk, CVaR, and mean-variance. Our focus is on the sample complexities of learning the optimal state-action value function (value learning) and an optimal policy (policy learning) under recursive OCE. We provide an exact characterization of utility functions uu for which the corresponding OCE defines an objective that is PAC-learnable. We analyze a simple model-based approach and derive PAC sample complexity bounds. We establish that whenever uu does not have full domain dom(u)≠R\text{dom}(u)\neq \mathbb{R}, the corresponding problem is not PAC-learnable. Finally, we establish corresponding lower bounds for both value and policy learning, demonstrating tightness in the size SASA of state-action space, and for a more restricted class of utilities, we derive lower bounds that makes the dependence on the effective horizon 11−γ\frac{1}{1-γ} explicit. Specifically, for CVaRτ\text{CVaR}_τ we show that the correct dependence on ττ is 1τ2\frac{1}{τ^2}, thus improving by a factor of 1τ\frac{1}τ over state-of-the-art although our bound has a suboptimal dependence on 11−γ\frac{1}{1-γ}.
Oliver Mortensen, Mohammad Sadegh Talebi
Value FunctionsMarkov Decision ProcessesOptimal Sample ComplexitySample Complexity
AskPDF