PaperlayerView exact revision on arXiv

Source-linked AI summary

Algorithms for CVaR Optimization in MDPs

Yinlam Chow, Mohammad Ghavamzadeh

arXiv:1406.3339v3cs.AImath.OC

TL;DR

The paper addresses mean-CVaR optimization in MDPs, where minimizing expected cost alone does not control risk from cost variability and tail losses. It derives gradient estimators and develops policy-gradient and actor-critic algorithms, proving convergence to locally risk-sensitive optima and demonstrating lower loss-distribution right tails in optimal stopping. The authors also identify unresolved convergence, sampling, and evaluation challenges.

  • Problem

    MDP optimization often minimizes expected discounted cost without accounting for policy-induced variability, while constructing tractable risk-sensitive criteria remains unresolved.

  • Method

    The paper derives gradients for a mean-CVaR objective and uses trajectory-based and incremental estimates in policy-gradient and actor-critic algorithms.

  • Results

    The algorithms are proved to converge to locally risk-sensitive optimal policies and, in optimal stopping, produce lower loss-distribution right tails than risk-neutral methods.

  • Takeaways & Limitations

    Mean-CVaR policy-gradient and actor-critic methods provide a way to seek policies with reduced tail losses in the studied MDP setting.

  • Takeaways & Limitations

    The paper leaves open convergence proofs for on-policy actor-critic sampling, finite-time solution-quality bounds, improved right-tail sampling, and evaluation on more challenging problems.

Abstract

from arXiv · show

In many sequential decision-making problems we may want to manage risk by minimizing some measure of variability in costs in addition to minimizing a standard criterion. Conditional value-at-risk (CVaR) is a relatively new risk measure that addresses some of the shortcomings of the well-known variance-related risk measures, and because of its computational efficiencies has gained popularity in finance and operations research. In this paper, we consider the mean-CVaR optimization problem in MDPs. We first derive a formula for computing the gradient of this risk-sensitive objective function. We then devise policy gradient and actor-critic algorithms that each uses a specific method to estimate this gradient and updates the policy parameters in the descent direction. We establish the convergence of our algorithms to locally risk-sensitive optimal policies. Finally, we demonstrate the usefulness of our algorithms in an optimal stopping problem.

1 Introduction

The paper motivates risk-sensitive MDP optimization beyond expected discounted cost and focuses on mean-CVaR objectives, developing policy-gradient and actor-critic methods with convergence guarantees and an optimal-stopping demonstration.

  • Motivation: Risk-sensitive MDPs seek to penalize policy-induced cost variability in addition to minimizing expected discounted costs.The paper identifies expected exponential utility, variance-related measures, and percentile performance as existing criteria, while criterion construction remains open.
  • Motivation: CVaR measures expected loss in the tail beyond a specified confidence-level VaR and offers computational advantages over VaR.CVaR optimization has been applied to portfolio optimization and option hedging, motivating its use here.
  • Contributions: The paper develops policy-gradient and actor-critic algorithms for mean-CVaR optimization in MDPs.The algorithms use several gradient-estimation methods, including incremental and trajectory-based updates.
  • Contributions: The proposed algorithms are shown to converge asymptotically to locally risk-sensitive optimal policies.The convergence result is established using an ordinary differential equations approach.
  • Contributions: An optimal stopping problem demonstrates the usefulness of the proposed algorithms.The paper compares risk-sensitive methods with risk-neutral counterparts in this setting.

2 Preliminaries

The preliminaries define the MDP, parameterized policies, policy-gradient updates, and VaR-related risk concepts used to formulate CVaR optimization.

  • MDP model: The environment is modeled as an MDP with state and action spaces, bounded random costs, transition probabilities, and an initial-state distribution.For simplicity, the paper assumes a single initial state, while noting that results extend to multiple initial states.
  • Policies: A stationary policy assigns a probability distribution over actions conditional on the current state.The paper uses parameterized stochastic policies in its policy-gradient and actor-critic methods.
  • Policy optimization: Policy-gradient methods estimate a performance gradient with respect to policy parameters from observed trajectories and adjust parameters in the gradient direction.The paper represents policies through a parameter vector θ and uses µ and θ interchangeably.
  • Risk measures: VaR is defined at confidence level α, while CVaR concerns expected losses at or beyond the VaR threshold.The paper notes that VaR can be unstable and numerically difficult for fat-tailed or empirically discrete loss distributions.

3 CVaR Optimization in MDPs

The paper formulates CVaR optimization over discounted MDP losses, converts the constrained problem into a Lagrangian saddle-point problem, and specifies gradient-based policy optimization.

  • Loss formulation: The discounted loss Dθ(x) is the sum of costs encountered from state x while following policy µ.The corresponding expected loss functions are the value and action-value functions.
  • Optimization objective: Standard discounted optimization seeks a policy θ* minimizing the value function at the initial state.The CVaR formulation extends this setting with a confidence level α and loss tolerance β.
  • Optimization objective: The CVaR-constrained problem is transformed into an equivalent formulation and then relaxed into an unconstrained Lagrangian problem.The Lagrangian introduces multiplier λ and supports saddle-point optimization.
  • Optimization procedure: The saddle point is sought by descending in policy and auxiliary parameters while ascending in the Lagrange multiplier.The saddle-point inequalities define the target of this min-max procedure.
  • Assumptions: A feasibility assumption requires that the loss tolerance β be achievable by some policy.The paper also notes that an optimal CVaR policy can depend on current time, state, and accumulated discounted cost.

4 A Trajectory-based Policy Gradient Algorithm

The trajectory-based policy-gradient algorithm estimates Lagrangian gradients from sampled system trajectories and updates policy, VaR, and multiplier parameters with projected stochastic approximation.

  • Algorithm: Each iteration generates N trajectories under the current policy to estimate gradients and update θ, ν, and λ.The trajectory is the algorithm’s unit of observation.
  • Trajectory model: A trajectory records states, actions, costs, and a stopping time before entering a zero-cost recurring sink state.The paper assumes a proper policy so transient states are exited and the terminal state is reached in finite time with probability one.
  • Gradient estimation: The trajectory log-probability gradient decomposes into the sum of policy log-probability gradients across time steps.This identity supports likelihood-ratio gradient estimation from sampled trajectories.
  • Stochastic approximation: Projection operators constrain θ, ν, and λ to specified compact or bounded sets needed for convergence.The step sizes assign the VaR update the fastest time scale, the policy update the intermediate scale, and the multiplier update the slowest scale.
  • Convergence: The policy-gradient algorithm converges to a local saddle point of the risk-sensitive Lagrangian.The result follows from the paper’s convergence analysis for the three-time-scale stochastic approximation algorithm.

5 Incremental Actor-Critic Algorithms

The paper develops incremental actor-critic algorithms for mean-CVaR optimization, using gradient estimators based on an augmented MDP and alternative trajectory or SPSA procedures. Under stated stochastic-approximation conditions, the algorithms converge to locally risk-sensitive optima.

  • Motivation: Actor-critic methods address the high variance of trajectory-based policy-gradient estimates by using linear value-function approximation and incremental updates.The trajectory-based method can have high-variance gradient estimates, especially for long trajectories.
  • Augmented MDP: The algorithms operate on an augmented MDP whose state includes the original state and an auxiliary variable used to represent the CVaR objective.The augmented cost assigns a terminal penalty involving the positive part of the auxiliary state.
  • Gradient estimation: The policy-gradient component uses an unbiased temporal-difference estimate involving ∇log µ and a critic approximation to the value function.The critic approximates V θ(x, s) with v^Tφ(x, s), using a low-dimensional feature vector.
  • Gradient estimation: SPSA estimates the VaR sub-gradient incrementally from perturbed values ν− = ν − ∆ and ν+ = ν + ∆.This provides a fully incremental alternative to an estimator applicable only at trajectory termination.
  • Algorithms: The paper presents fully incremental SPSA-based and semi trajectory-based actor-critic algorithms with different update frequencies for θ, ν, and λ.The SPSA-based algorithm updates all parameters at each time step, whereas the semi trajectory-based method updates ν and λ at trajectory end.
  • Convergence: The convergence analysis establishes that the actor-critic algorithms converge to a local saddle point of L(θ, ν, λ).The algorithms use multiple stochastic-approximation time scales, with the critic on the fastest time scale.

6 Experimental Results

The experiments evaluate risk-sensitive policy-gradient and actor-critic algorithms against risk-neutral counterparts in an optimal stopping problem. Risk-sensitive policies accept higher expected loss in exchange for lower variance and lower right-tail losses.

  • Optimal stopping problem: The optimal stopping problem asks an agent to accept the current cost or wait for a stochastic future cost until a stopping horizon T.The state contains the current cost and time, and accepting or reaching T terminates the process.
  • Experimental setup: The evaluation compares PG-CVaR, AC-CVaR-SPSA, and AC-CVaR-Semi-Traj with risk-neutral PG and AC algorithms.Figure 1 presents discounted cumulative-cost distributions, while Table 1 summarizes performance.
  • Results: Risk-sensitive algorithms produce higher expected loss but lower variance than risk-neutral methods.The comparison is reported for the policies learned in the optimal stopping experiment.
  • Results: Risk-sensitive algorithms have lower right-tail loss distributions than their risk-neutral counterparts.The paper identifies this as the principal distributional difference between the two classes of policies.

7 Conclusions and Future Work

The paper concludes that its policy-gradient and actor-critic algorithms provide convergent approaches to CVaR optimization, with lower right-tail losses observed in an optimal stopping problem. It identifies convergence rates, sampling, and broader evaluation as open directions.

  • Conclusions: The paper proposes policy-gradient and actor-critic algorithms for CVaR optimization in MDPs.The contribution includes both trajectory-based and incremental algorithmic approaches.
  • Conclusions: The algorithms are proved to converge to locally risk-sensitive optimal policies.The convergence proofs are provided in the appendix.
  • Conclusions: In the optimal stopping experiment, the learned policies have lower right-tail loss distributions than risk-neutral counterparts.The paper notes the relevance of this outcome when the right tail contains catastrophic losses.
  • Future work: Future work includes convergence proofs for on-policy samples rather than samples from the discounted visiting distribution.The paper states that the latter sampling approach can be wasteful in terms of samples.
  • Future work: Finite-time quality bounds remain unavailable for the multi-timescale stochastic-approximation and actor-critic algorithms discussed.The paper specifically contrasts these open bounds with the asymptotic limits established here.
  • Future work: More accurate gradient estimates may require additional samples from the low-probability right tail, while the choice of importance-sampling distribution remains unresolved.The paper also calls for evaluation in more challenging problems.

A.3 Proof of Convergence of the Policy Gradient Algorithm

The policy-gradient convergence proof models the projected multi-timescale updates through differential equations and directional derivatives. Under the stated assumptions, the updates converge almost surely to a local saddle point when λ∗<λmax.

  • Main convergence result: Algorithm 1’s policy-gradient updates converge almost surely to a local saddle point (θ∗, ν∗, λ∗) when λ∗∈[0, λmax).The saddle inequalities hold over the policy and VaR variables locally and the multiplier variable over [0, λmax].
  • Projected dynamics: Projected directional derivatives keep ν, θ, and λ updates moving in descent or ascent directions when iterates reach their constraint boundaries.ΓΘ and ΓΛ project onto the feasible sets, while the left directional derivatives characterize boundary behavior.
  • λ-update: The λ-value function L∗(λ) is absolutely continuous, and the envelope theorem identifies its derivative with the partial λ-derivative at local optima.Concavity additionally gives continuity and directional differentiability properties used in the λ-update convergence argument.
  • Timescale decomposition: The proof separates ν, θ, and λ updates across faster-to-slower timescales, treating slower variables as fixed during each faster update.The ν-update is analyzed first, followed by θ with ν at equilibrium, and λ using converged θ∗(λ) and ν∗(λ).
  • ν-update: The ν-update is a stochastic approximation of a differential inclusion with martingale-difference error, using subgradients because the objective may be nondifferentiable in ν.The proof verifies boundedness, compactness, upper semicontinuity, step-size, and noise conditions for the subgradient analysis.

B.4 Convergence of the Actor Critic Algorithms

The actor-critic convergence analysis covers algorithms using learned value functions and multiple update mechanisms. Under approximation and stationarity conditions, the joint updates converge almost surely to a local saddle point.

  • Algorithm inputs: The critic uses projected value-function approximation, with feature vectors and parameters initialized alongside θ, ν, λ, u, and v.Algorithm 3 operates on an augmented MDP and observes both original and augmented costs and transitions.
  • Convergence result: Algorithm 2’s actor-critic updates converge almost surely to a local saddle point (θ∗, ν∗, λ∗) when λ∗∈[0, λmax).The result assumes vanishing actor approximation error and uses a γ-stationary distribution to generate samples.
  • Gradient estimation: The analysis includes multi-loop, SPSA-based, and alternative actor-critic procedures for estimating the VaR subgradient and updating the policy.The SPSA update uses two perturbed value functions at ν−=ν−∆ and ν+=ν+∆, with the perturbation vanishing asymptotically.

B.4.1 Proof of Theorem 6: TD(0) Critic Update (v−update)

The TD(0) critic proof establishes stability of the linear stochastic approximation underlying the actor-critic algorithms. It concludes that the critic iterates converge almost surely to a unique fixed point for fixed policy-related parameters.

  • Matrix stability: Every eigenvalue of A has positive real part, ensuring stability of the limiting ODE for the critic update.The proof derives positive definiteness of A+A^⊤ and uses an eigenvalue contradiction argument.
  • Stochastic approximation conditions: The critic analysis verifies Lipschitz continuity, step-size conditions, martingale-difference noise, uniform convergence, and global asymptotic stability of the limiting ODE.These properties imply boundedness of the TD iterates almost surely before applying the stochastic-approximation convergence theorem.
  • Fixed-point convergence: The TD(0) iterates converge almost surely to the unique fixed point v∗ satisfying h(v∗)=0, equivalently Av∗=b.The limit depends on the fixed values of θ, ν, and λ.

B.4.2 Proof of Theorem 7

Theorem 7’s proof extends convergence from the critic to the SPSA-based actor-critic updates. It controls perturbation bias, establishes convergence of ν and θ, and then applies the slow λ-update analysis to obtain a local saddle point.

  • Critic timescale: The critic parameter v converges almost surely before the slower ν, θ, and λ updates are analyzed.This faster timescale permits replacing v with its limiting value in subsequent convergence arguments.
  • ν-update: SPSA estimates the ν subgradient using value functions at ν−=ν−∆ and ν+=ν+∆, with asymptotic unbiasedness requiring controlled perturbation error.The proof assumes εθk(vk)E[1/∆k]→0 so the perturbation-related bias vanishes.
  • ν-update: The ν-update is treated as an Euler discretization of a differential inclusion with martingale-difference noise and vanishing disturbance bias.This yields ν-convergence by arguments analogous to the policy-gradient proof.
  • θ-update: The actor update uses converged v∗(θ) and ν∗(θ), while its gradient approximation has a vanishing bias and martingale-difference error.Lipschitz continuity of the gradient approximation supports the stochastic-approximation convergence argument for θ.
  • λ-update: The λ-update operates on the slowest timescale using converged v∗(λ), θ∗(λ), and ν∗(λ), and its noise term is a martingale difference.The subsequent λ-convergence and saddle-point analysis follows the policy-gradient proof.

C Experimental Results

The experiments compare trajectory-based and incremental policy-learning algorithms, including risk-neutral and CVaR-constrained variants, using specified policy parameterizations and two evaluation phases.

  • Experimental setting: The house-purchasing MDP uses x0 = [1; 0], ph = 0.1, T = 20, γ = 0.95, fu = 1.5, fd = 0.8, and p = 0.65.The passage lists these as the experimental MDP parameters.
  • Implemented algorithms: The study implements risk-neutral policy gradient and actor-critic algorithms alongside CVaR-constrained policy gradient and actor-critic variants.The incremental methods include semi-trajectory and SPSA CVaR actor-critic algorithms.
  • Policy parametrization: The trajectory-based experiments use a two-dimensional radial basis function feature map with Boltzmann policy parametrization.The risk-neutral policy is obtained using LSPI, while the evaluated methods use the specified RBF features and policy family.
  • Evaluation protocol: Each trajectory-based experiment has a tuning phase followed by a converged run phase.Tuning runs for up to 1000 iterations until parameters converge; the converged policy is then simulated for 1000 runs.
  • Evaluation protocol: The incremental experiments likewise obtain converged parameters during tuning and simulate the resulting policy for 1000 runs.These experiments use augmented-state Boltzmann policies with RBF features for [x; s].

D.1 Bellman Operator for Expected Utility Functions

This section establishes Bellman-operator properties for the augmented expected-utility MDP and proves existence and uniqueness of its fixed point. It then extends the analysis to projected linear value-function approximation.

  • Bellman-operator properties: The Bellman operator is monotone and respects constant shifts, with Tθ[V + K](x, s) = Tθ[V](x, s) + γK.These properties support the contraction-based fixed-point analysis.
  • Fixed-point interpretation: Under transient policies and bounded initial value functions, the limiting iterates recover the infinite-horizon value function.The argument controls the remaining tail contribution using transience and discounting.
  • Fixed-point result: The operator has a unique fixed-point solution V* on the augmented space X × R, and iterating it from any bounded initial function converges to that solution.The fixed point equals the expected-utility value function.
  • Fixed-point result: The fixed-point proof uses contraction to show that successive iterates form a Cauchy sequence in the complete bounded-function space.Uniqueness follows because any two fixed points must have zero sup-norm distance under the contraction argument.
  • Projected approximation: The projected Bellman operator has a unique fixed point when the value function is approximated linearly as φ(x, s)^T v under a full-rank feature assumption.The corresponding projected equation yields a unique value-function estimate and weight vector.
  • Projected approximation: The approximation scheme projects with respect to an occupation-measure-weighted norm, and the projected Bellman operator is contractive.The contraction follows from non-expansive projection and the stated operator properties.
  • Projected approximation: The projected solution ˜V* is the best linear approximation of Vθ in the feature subspace, with an error bound relative to the exact fixed point.The bound is stated in Lemma 17, and equality holds when V* lies in the approximation subspace.
Loading 1406.3339v3…