Optimizing the CVaR via Sampling

Aviv Tamar; Yonatan Glassner; Shie Mannor

Source-linked AI summary

Optimizing the CVaR via Sampling

Aviv Tamar, Yonatan Glassner, Shie Mannor

arXiv:1404.3862v4Apr 15, 2014stat.MLcs.AIcs.LG

TL;DR

Existing CVaR optimization methods are limited when parameters also control the distribution of random outcomes, motivating a more general approach. The paper derives a conditional-expectation, likelihood-ratio-style gradient, builds a sampling estimator with stochastic-gradient optimization, and evaluates it in risk-sensitive Tetris control. The authors report useful risk-sensitive policies and faster convergence with importance sampling at α = 0.01.

Problem
Existing CVaR optimization methods are not suitable when parameters control the distribution of random outcomes, although such settings include reinforcement learning and other important domains.
Method
The paper derives a conditional-expectation CVaR gradient formula, proposes a sampling-based likelihood-ratio estimator, and uses stochastic gradient descent for optimization.
Results
Optimizing CVaR produced useful risk-sensitive Tetris policies, while importance sampling improved convergence by more than a factor of 2 for α = 0.01 and N = 200.
Takeaways & Limitations
The method extends CVaR optimization to new domains and supports simulation-based risk-sensitive decision making in reinforcement learning.
Takeaways & Limitations
For very low α, the estimator has high variance because averaging effectively uses only αN samples; in CVaR reinforcement learning, a Markov policy is not necessarily optimal.

Abstract

from arXiv · show

Conditional Value at Risk (CVaR) is a prominent risk measure that is being used extensively in various domains. We develop a new formula for the gradient of the CVaR in the form of a conditional expectation. Based on this formula, we propose a novel sampling-based estimator for the CVaR gradient, in the spirit of the likelihood-ratio method. We analyze the bias of the estimator, and prove the convergence of a corresponding stochastic gradient descent algorithm to a local CVaR optimum. Our method allows to consider CVaR optimization in new domains. As an example, we consider a reinforcement learning application, and learn a risk-sensitive controller for the game of Tetris.

1 Introduction

The paper targets CVaR optimization when parameters control both payoff values and the distribution of random outcomes, a setting existing methods do not handle. It derives a conditional-expectation gradient formula, develops a sampling estimator and stochastic-gradient procedure, and applies them to risk-sensitive Tetris control.

Motivation: Existing CVaR methods handle payoffs R = f_θ(X) when X does not depend on θ, but not domains where θ controls outcome distributions.The latter setting arises in queueing systems, resource allocation, and reinforcement learning.
Contribution: The paper proposes a CVaR optimization approach for parameters that also control the distribution of X.
Method: A new CVaR gradient formula expresses the gradient as a conditional expectation, enabling a sampling-based likelihood-ratio estimator.
Guarantees: The estimator is analyzed for bias, and the associated stochastic-gradient-descent algorithm is proved to converge to a local CVaR optimum.
Application: The method is applied to reinforcement learning by learning a risk-sensitive controller for Tetris.The authors report that Tetris enables interpretation of the learned policies as sensible.
Extensions: The estimator can also support CVaR-constrained objectives through penalty methods and naturally incorporate importance sampling for small α and rare events.

2 A CVaR Gradient Formula

This section develops an LR-style CVaR gradient formula under regularity assumptions, first for a one-dimensional parameterized distribution and then for general rewards generated from multidimensional random variables and discrete variables.

2 A CVaR Gradient Formula: The section introduces a new likelihood-ratio-style CVaR gradient formula and extends the result from one-dimensional to multidimensional cases.
2 A CVaR Gradient Formula: CVaR is defined from the α fraction of worst outcomes, while VaR is the corresponding α-quantile of a continuous bounded random variable.
2.1 CVaR Gradient of a 1-Dimensional Variable: The derivation studies how CVaR changes when the distribution function changes, then parameterizes the density by θ.
2.1 CVaR Gradient of a 1-Dimensional Variable: The one-dimensional result expresses the CVaR gradient as a conditional expectation and supplies the basis for a sampling algorithm.
2.1 CVaR Gradient of a 1-Dimensional Variable: The derivation assumes continuous bounded outcomes, smooth VaR and CVaR gradients, and standard boundedness conditions for likelihood-ratio estimates.The paper notes that relaxing these assumptions is possible but technically involved.
2.1 CVaR Gradient of a 1-Dimensional Variable: The proof differentiates the lower-tail level set using the Leibniz rule and identifies the VaR as the specific baseline in the likelihood-ratio formula.
2.2 CVaR Gradient Formula – General Case: For the general case, reward R is generated by a bounded function of a finite-support multidimensional X and a discrete variable Y, with parameterized distributions.
2.2 CVaR Gradient Formula – General Case: The multidimensional proposition requires continuous rewards, bounded well-defined gradients, and level sets expressible as finite sums of disjoint closed connected components.Its proof requires additional multidimensional Leibniz-rule arguments, and relaxing the assumptions is left for future work.

3 A CVaR Gradient Estimation Algorithm

The paper introduces GCVaR, a Monte Carlo estimator for CVaR gradients based on an empirical quantile and sampled likelihood-ratio terms. The estimator is consistent with bias O(N^-1/2), while naive likelihood-ratio estimation on worst samples is inconsistent.

Monte Carlo estimator: GCVaR estimates the CVaR gradient from i.i.d. samples by first estimating VaR with the empirical α-quantile and then applying the sampling formula.The empirical quantile is obtained by sorting sampled rewards and selecting the ⌈αN⌉ term.
Bias and consistency: The empirical α-quantile is biased, so the resulting gradient estimator is biased before its asymptotic behavior is analyzed.
Monte Carlo estimator: The estimator requires derivatives of both fY(y;θ) and fX∣Y(x∣y;θ) with respect to each parameter component.
Bias and consistency: The gradient-estimator bias is O(N^-1/2), under continuity and positive-density conditions at VaR.
Comparison with standard likelihood-ratio estimation: Applying a standard likelihood-ratio estimator to only the α% worst samples, without subtracting the estimated VaR baseline, is inconsistent and can have arbitrarily large gradient error.
Variance reduction: For α close to 0, GCVaR has high variance because averaging effectively uses only αN samples; importance sampling can reduce this variance.

4 CVaR Optimization

The paper uses GCVaR within CVaRSGD to optimize CVaR by iteratively sampling, estimating the gradient, and projecting parameter updates into a compact set. Under stated regularity and bias conditions, the algorithm converges almost surely to asymptotically stable equilibria.

Algorithm: CVaRSGD combines the GCVaR gradient estimator with stochastic gradient descent to solve the CVaR optimization problem.
Algorithm: At each iteration, CVaRSGD samples from the current parameterized distribution, computes a GCVaR gradient estimate, and updates the parameters.
Projection: Projection onto a compact parameter set keeps iterates bounded and is intended to have negligible practical effect when the set contains the local optima.
Projected dynamics: The projected update is analyzed through an ordinary differential equation whose direction operator keeps parameters within the constraint set.
Convergence: Under Assumptions 4–6, continuous differentiability, and a summable gradient-bias condition, CVaRSGD converges almost surely to the set of asymptotically stable equilibria.
Convergence: The sample size must increase over iterations, although the required rate can be slow; one stated choice is ϵi = 1/i and ni = (log i)^4.

5 Application to Reinforcement Learning

The paper applies CVaRSGD to risk-sensitive reinforcement learning by estimating CVaR gradients from simulated trajectories and updating policy parameters. In Tetris, the method produces policies with higher CVaR, although average return is compromised, and importance sampling accelerates optimization when α is small.

Risk-sensitive policy-gradient approach: CVaRSGD estimates gradients of the CVaR of total return from simulated trajectories and updates the policy through stochastic gradient descent.The formulation decomposes trajectories into discrete state-action sequences and continuous rewards; only policy-dependent terms are required in the estimator.
Risk-sensitive policy-gradient approach: For CVaR optimization, a Markov policy may not guarantee optimality, although the simulations still produced useful and sensible results.Under certain conditions, augmenting the current state with a function of accumulated reward suffices for optimality.
Tetris experiment: In Tetris, CVaRSGD compromised average return for a higher CVaR value compared with standard policy gradient.The experiment used α = 0.05, a 10 × 20 board, seven tetrominos, a 1000-step limit, and a warm-started softmax policy.
Tetris experiment: The CVaR policy had a significantly lower left-tail reward distribution than the standard policy, indicating more risk-sensitive behavior.Its Board Well parameter differed substantially, repressing actions that create deep wells because they can heighten the board despite potentially producing high rewards.
Tetris experiment: More than 2× faster convergence was achieved by importance-sampled CVaRSGD when α = 0.01 and N = 200.The comparison used CVaRSGD and its importance-sampling version under a small-tail-probability setting.

6 Conclusion and Future Work

The paper concludes that its likelihood-ratio formulation enables sampling-based CVaR optimization with convergence to a local optimum. An RL experiment on Tetris demonstrates risk-sensitive policy learning in a domain the authors describe as beyond existing CVaR optimization approaches.

Conclusion: The paper introduces an LR-style CVaR gradient formula, a sampling-based estimator, and stochastic gradient descent guaranteed to converge to a local optimum.The authors present this as an extension of likelihood-ratio methods to the CVaR performance criterion.
Conclusion: In Tetris, optimizing CVaR produced useful risk-sensitive policies in an RL domain described as beyond existing CVaR optimization approaches.The authors use the experiment to motivate simulation-based optimization for risk-sensitive decision making.

A Proof of Proposition 2

The proof extends the CVaR-gradient argument to a multidimensional, parameter-dependent integration domain. It uses geometric differentiation of the domain and likelihood-ratio manipulations to obtain the required expectation.

Boundary differentiation: The argument partitions level sets, tracks how their boundaries change with parameters, and applies a multidimensional Leibniz rule.The proof uses normal and tangent boundary velocities and differentiates integrals over the resulting domains.
Proof setup: The proof handles a parameter-dependent n-dimensional integration domain and a parameter-dependent differential form.This is the multidimensional setting needed for the proposition.
Likelihood-ratio form: A final likelihood-ratio transformation converts the differentiated sums and integrals into the required expectation.The transformation multiplies and divides by the relevant marginal and conditional densities.

B Proof of Theorem 3

The proof establishes consistency of the CVaR-gradient estimator despite the bias of the empirical quantile. It bounds the estimator’s components and shows that the additional error terms vanish asymptotically.

Bias control: The proof defines a bounded auxiliary quantity D(x,y) and uses the strong law of large numbers to control estimator components.Additional terms are treated separately using Hölder’s inequality and boundedness assumptions.
Bias control: The remaining terms vanish as sample size increases, yielding the stated estimator result.The conclusion follows after substituting the intermediate propositions into the target expression.

C Proof of Theorem 4

The proof establishes that the CVaR gradient estimator’s bias decreases asymptotically faster than N^-1/2, using quantile and empirical-CDF error bounds.

Quantile bound: The boundedness of R implies boundedness and uniform integrability of the estimated quantile error.These properties allow convergence in probability to yield the corresponding expected absolute-error rate.
Quantile bound: The empirical α-quantile differs from the true quantile by O(N^-1/2) in expectation.This follows by combining the empirical-quantile representation with bounds on the empirical C.D.F. deviation.
Conclusion: The resulting quantile-error estimate completes the proof of the stated convergence bound.The final step uses the empirical C.D.F. deviation bound to conclude E[|ν − ˜v|] is O(N^-1/2).

D Example: the Importance of the VaR Baseline in GCVaR

The VaR baseline is essential in GCVaR: omitting it can make the gradient-estimation error arbitrarily large, while importance sampling addresses high variance for very low quantiles.

VaR baseline: The VaR baseline is crucial because removing it can make the gradient-estimation error arbitrarily large.The example analyzes Z ∼ Normal(θ,1) with α = 0.5, where the baseline-related term is unbounded in θ.
VaR baseline: Without the baseline, the naive estimator may even point in the opposite direction.The example’s baseline term can dominate the true CVaR gradient as θ changes.
Importance sampling: For α close to 0, GCVaR has high variance because averaging effectively uses only αN samples.The paper introduces importance sampling to mitigate this low-quantile variance.
Importance sampling: Importance sampling estimates expectations under an alternative distribution g using the likelihood ratio f(x)/g(x).The sampling distribution must dominate the original distribution, and its choice determines whether variance is reduced.
Importance sampling: The proposed importance-sampling distribution is selected by approximately minimizing an estimated variance objective over a parameterized family.The procedure uses sampled average approximation and deterministic gradient descent to obtain the distribution parameter.

E.2 IS Estimate for CVaR Sensitivity

The IS CVaR-sensitivity procedure selects a sampling distribution, estimates the VaR under importance sampling, and then computes a weighted gradient estimate; its application requires domain-specific distribution design.

IS quantile: The CVaR quantile must also be estimated under importance sampling because the ordinary empirical quantile uses samples from the original distribution.The method uses an IS empirical C.D.F. for this quantile estimate.
IS distribution: The procedure first fits a parameterized importance-sampling distribution by solving a sampled variance-minimization problem.The objective aggregates squared gradient components, assuming independence between them.
Gradient estimation: IS GCVaR draws trajectories from the fitted distribution and uses the resulting weighted samples to estimate the CVaR gradient.The gradient estimate uses the IS quantile and replaces the ordinary gradient estimate in the parameter update.
Implementation choices: The IS estimate of the CVaR quantile can be updated separately, so a large sample size is affordable when the importance distribution is updated intermittently.The paper therefore does not require importance sampling for that auxiliary estimate in its typical stochastic-gradient setting.
RL implementation: Selecting and sampling the RL importance distribution requires access to the MDP transition probabilities and domain knowledge.The paper presents a heuristic for reinforcement learning rather than restricting the method to one value-function approximation technique.
RL implementation: The importance-sampling distribution is adapted in reinforcement learning by modifying MDP transition probabilities to favor bad trajectories.Increasing ω encourages transitions to low-value states, increasing the probability of bad trajectories.

E.4 Empirical Results with Importance Sampling

The importance-sampling experiment evaluates CVaR optimization at α = 0.01 and reports substantially faster convergence for IS GCVaR than for naive GCVaR.

Experimental setup: The RL value-function approximation exploits the soft-max policy’s feature representation.The approximation uses the policy’s φ(s,a)^⊺θ structure to construct state-action values.
Importance-sampling results: At α = 0.01 with N = 200, IS GCVaR converges significantly faster than GCVaR.The comparison tracks CVaR of the return against iteration.
Importance-sampling results: The reported speedup is attributed to lower variance in the gradient estimation.The experiment uses trajectories from the initial policy to choose ω through sampled average approximation.