PaperlayerView exact revision on arXiv

Source-linked AI summary

Risk-Constrained Reinforcement Learning with Percentile Risk Criteria

Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, Marco Pavone

arXiv:1512.01629v3cs.AIcs.LGmath.OC

TL;DR

The paper targets risk-constrained MDPs, where expected cumulative cost must be optimized while controlling CVaR or chance-constrained risk. It derives Lagrangian gradients and develops policy-gradient and actor-critic algorithms with local-convergence guarantees. Experiments in optimal stopping and personalized advertising produce policies with lower cost-distribution right tails and can enforce a worst-case revenue target.

  • Problem

    Risk-constrained formulations are largely unaddressed in reinforcement learning, although such constraints arise naturally in engineering, finance, and logistics.

  • Method

    The paper derives Lagrangian gradients and develops policy-gradient and actor-critic algorithms for CVaR-constrained and chance-constrained MDPs.

  • Results

    The algorithms converge to locally optimal policies and, in optimal stopping and personalized advertising, produce lower right-tail cost distributions than risk-neutral counterparts.

  • Takeaways & Limitations

    The methods support risk-averse decision-making when catastrophic costs occupy the cost distribution’s right tail, including guaranteeing a specified worst-case revenue target in advertising.

  • Takeaways & Limitations

    The analysis focuses on discounted CVaR optimization with γ ∈(0, 1), although the authors state it can be generalized to γ = 1.

Abstract

from arXiv · show

In many sequential decision-making problems one is interested in minimizing an expected cumulative cost while taking into account \emph{risk}, i.e., increased awareness of events of small probability and high consequences. Accordingly, the objective of this paper is to present efficient reinforcement learning algorithms for risk-constrained Markov decision processes (MDPs), where risk is represented via a chance constraint or a constraint on the conditional value-at-risk (CVaR) of the cumulative cost. We collectively refer to such problems as percentile risk-constrained MDPs. Specifically, we first derive a formula for computing the gradient of the Lagrangian function for percentile risk-constrained MDPs. Then, we devise policy gradient and actor-critic algorithms that (1) estimate such gradient, (2) update the policy in the descent direction, and (3) update the Lagrange multiplier in the ascent direction. For these algorithms we prove convergence to locally optimal policies. Finally, we demonstrate the effectiveness of our algorithms in an optimal stopping problem and an online marketing application.

1. Introduction

The paper addresses the largely unaddressed problem of risk-constrained reinforcement learning, using CVaR or chance constraints to control cumulative-cost risk while optimizing policies. It develops policy-gradient and actor-critic methods with local-convergence guarantees and demonstrates them in stopping and advertising problems.

  • Risk-constrained formulations remain largely unaddressed despite extensive research on risk-sensitive MDPs and reinforcement learning.
  • The paper formulates MDPs with either a CVaR constraint or a chance constraint on cumulative cost.For CVaR constraints, both discrete and continuous cost distributions are considered.
  • The authors derive an augmented-MDP Bellman optimality condition by combining the original state with cumulative constraint-cost information.
  • A trajectory-based policy-gradient algorithm estimates an unbiased gradient under Monte Carlo sampling and converges to locally optimal policies.The convergence analysis uses an ordinary differential equation approach.
  • Actor-critic algorithms optimize policy and value-function parameters online and also converge to locally optimal solutions.
  • The algorithms are effective in optimal stopping and personalized advertisement recommendation, where CVaR constraints lower-bound worst-case revenue by a yearly company target.

2. Preliminaries

The paper studies finite, transient MDPs with bounded stopping times and parameterized stationary policies, defining discounted costs and percentile-risk constraints. It uses Lagrangian reformulations for CVaR and chance-constrained optimization under stated regularity and feasibility assumptions.

  • The model is a finite MDP with finite state and action spaces, a recurrent target state, bounded cost functions, and an initial state distribution.
  • Policies are stationary action distributions conditioned on the current state and represented in policy-gradient methods by a parameter vector θ.
  • The analysis assumes transience and a uniformly bounded first-hitting time for the target state under every stationary policy.A bounded stopping time can represent the time-out used in many reinforcement-learning trajectories.
  • The paper defines VaR as a percentile of cumulative cost and refers to a VaR constraint as a chance constraint.CVaR additionally captures costs in the tail beyond the VaR threshold.
  • CVaR-constrained optimization emphasizes discounted costs for γ ∈(0, 1), while chance-constrained optimization uses γ = 1 for stopping costs.The authors state that both analyses can be extended to the other discounting case.
  • The formulation assumes continuously differentiable policy probabilities and strict feasibility for the constrained problems.

3. A Trajectory-based Policy Gradient Algorithm

The trajectory-based policy-gradient method updates the policy and VaR parameters by descent and the Lagrange multiplier by ascent using gradients estimated from sampled trajectories. A three-timescale stochastic-approximation analysis establishes almost-sure convergence to a locally optimal CVaR-constrained policy.

  • The algorithm descends in θ and ν and ascends in λ using gradients of the Lagrangian.The VaR parameter is ν, the policy parameter is θ, and λ is the Lagrange multiplier.
  • Each iteration generates N trajectories under the current policy, estimates the gradients, and updates ν, θ, and λ.
  • Trajectory probabilities factor through policy action probabilities, yielding a log-gradient expressed as a sum of policy log-gradients.
  • Projection operators constrain policy and multiplier updates to compact parameter sets needed for convergence.The policy is projected onto Θ and the multiplier onto [0, λmax].
  • The three-timescale schedule makes the ν update fastest, the θ update intermediate, and the λ update slowest.
  • The policy-update sequence converges almost surely to a locally optimal policy for the CVaR-constrained optimization problem.

4. Actor-Critic Algorithms

The actor-critic methods reduce trajectory-gradient variance by approximating value functions incrementally in an augmented MDP, while updating policy, risk, and multiplier parameters on multiple timescales. Under stated assumptions, the critic and policy updates converge almost surely to their respective local targets.

  • Actor-critic design: The algorithms use temporal-difference learning to approximate the augmented-MDP value function with low-dimensional linear features.The augmented state tracks cumulative constraint cost, and the critic updates incrementally after state-action transitions.
  • Actor-critic design: The outer loop estimates Lagrangian gradients and updates the policy and VaR parameters by descent while updating the Lagrange multiplier by ascent.The SPSA-based variant updates all parameters incrementally; the semi-trajectory variant updates VaR and multiplier estimates at trajectory ends.
  • Convergence: Multiple stochastic-approximation timescales place the critic fastest, policy and VaR updates at intermediate speeds, and the multiplier update slowest.The step-size schedules are stated to ensure this ordering.
  • Gradient estimation: The critic uses a TD error whose likelihood-ratio product provides an unbiased policy-gradient estimate in the augmented MDP.The value approximation is Vθ(x,s) ≈ v^Tφ(x,s), with basis functions spanning a low-dimensional subspace.
  • Convergence: The critic update converges almost surely to the Bellman-residual minimizer under the stated feature and step-size assumptions.The result applies to the projected Bellman fixed point of the value function.
  • Convergence: The SPSA-based policy updates converge almost surely to a locally optimal CVaR-constrained policy under the stated technical assumptions.The SPSA policy step must satisfy εθk(vk)=o(Δk).

5. Extension to Chance-Constrained Optimization of MDPs

The paper extends its risk-constrained reinforcement-learning analysis from CVaR constraints to chance constraints using Lagrangian relaxation and augmented-state actor-critic methods. Under the stated assumptions, both policy-gradient and actor-critic policy updates converge almost surely to locally optimal policies.

  • Chance-constrained formulation: Chance-constrained MDPs are transformed into an unconstrained Lagrangian problem, with strict feasibility needed to guarantee a local saddle point.The chance constraint is handled analogously to the CVaR formulation.
  • Policy-gradient method: The chance-constrained policy-gradient algorithm omits VaR estimation and updates the policy and multiplier from trajectory-end estimates.Its θ update runs on the fast timescale, while the multiplier update runs on the slow timescale.
  • Policy-gradient method: The policy-gradient updates are unbiased estimates of the Lagrangian gradients and converge almost surely to a locally optimal chance-constrained policy.This follows under Assumptions 2–6.
  • Actor-critic method: The chance-constrained actor-critic method uses an augmented MDP whose state includes the original state and cumulative constraint-cost information.The augmented initial state sets the constraint-cost component to the chance threshold α.
  • Actor-critic method: The actor-critic critic converges almost surely to the Bellman-residual minimizer under its assumptions, and policy updates converge when value-function residuals vanish.The policy result requires εθk(vk)→0.
  • Actor-critic method: The chance-constrained actor-critic policy updates converge almost surely to a locally optimal policy under Assumptions 2–9 and vanishing critic residuals.The convergence proof replaces the critic iterate with its limiting value-function parameter on the faster timescale.

6. Examples

The experiments evaluate risk-constrained policy gradient and actor-critic methods in optimal stopping and personalized ad recommendation. Across comparisons with risk-neutral methods, risk-constrained policies reduce worst-case cost variability but can incur higher expected cost.

  • Examples: The experiments test risk-constrained and risk-neutral policy gradient and actor-critic algorithms on optimal stopping and personalized ad recommendation.The optimal stopping study includes CVaR- and chance-constrained methods; the ad-recommendation study uses CVaR-constrained and risk-neutral methods.
  • The Optimal Stopping Problem: The optimal stopping problem models purchasing decisions with state x = (c_k, k), where c_k is the current purchase cost and k is time.The cost evolves through a two-mode Markov chain with multiplicative appreciation or depreciation.
  • The Optimal Stopping Problem: The experiments use a tuning phase followed by a converged run that simulates 10,000 trajectories.The converged policy is obtained after the parameters converge, then evaluated by Monte Carlo averages.
  • The Optimal Stopping Problem: Risk-constrained algorithms produce higher expected cost but lower right-tail cost distributions than risk-neutral counterparts.This pattern is reported for the policy-gradient and actor-critic comparisons in the optimal stopping experiments.
  • A Personalized Ad-Recommendation System: The ad-recommendation study uses a simulator trained on real data, with 31 user features and four advertisement classes.The problem is formulated as return maximization using discounted total clicks, with tail risk representing the worst-case return distribution.

7. Conclusions and Future Work

The paper proposes and proves convergence for policy gradient and actor-critic algorithms for CVaR- and chance-constrained MDPs. Experiments in optimal stopping and personalized ad recommendation show lower cost-distribution right tails than risk-neutral counterparts, while future work targets sampling and broader applications.

  • Conclusions: The paper proposes policy gradient and actor-critic algorithms for CVaR-constrained and chance-constrained MDPs and proves their convergence.The algorithms address both risk formulations and are supported by convergence results.
  • Conclusions: In two applications, the algorithms produce policies with lower cost-distribution right tails than risk-neutral counterparts.The applications are optimal stopping and personalized ad recommendation.
  • Future Work: Future work includes on-policy actor-critic convergence proofs, importance sampling for rare right-tail events, and applications in operations research, robotics, and finance.These directions address convergence settings, gradient estimation in low-probability worst-case events, and broader application domains.

A.1 Computing the Gradients

This appendix derives the Lagrangian derivatives needed by the algorithms. It treats the policy parameter with a gradient, the auxiliary CVaR parameter with a sub-gradient, and the multiplier with a gradient.

  • Policy Parameter: The policy-parameter gradient is obtained by expanding the Lagrangian expectations and rewriting the result using trajectory log-probability derivatives.The expression specifies ∇θ log Pθ(ξ) when Pθ(ξ) ≠ 0.
  • CVaR Parameter: For fixed policy parameters, the Lagrangian is convex in ν, so its derivative with respect to ν is represented by a sub-gradient.The appendix characterizes sub-derivatives according to whether ν is below, equal to, or above J(ξ).
  • Lagrange Multiplier: Because the Lagrangian is linear in λ, its derivative with respect to λ has a direct gradient expression.The multiplier gradient completes the three derivative components used in the optimization updates.

A.2 Proof of Convergence of the Policy Gradient Algorithm

The proof analyzes policy-gradient convergence through multi-time-scale stochastic approximation, ODE dynamics, and Lyapunov stability. It concludes that, under the stated conditions, the iterates converge to a local saddle point yielding a locally optimal policy.

  • Convergence framework: The proof first establishes almost-sure convergence of each update to a stationary point of its corresponding continuous-time system.The step sizes impose the ordering ν fastest, θ next, and λ slowest.
  • Stability and saddle point: Lyapunov analysis shows that the continuous-time system is locally asymptotically stable at the stationary point.The Lagrangian serves as the Lyapunov function for the joint analysis.
  • λ-update and conclusion: The slow λ-update converges almost surely to λ∗ and, under λ∗∈[0, λmax), produces a local saddle point whose policy is locally optimal.The envelope theorem connects the λ dynamics to ascent of the optimized Lagrangian.
  • ν-update: The ν-update converges to ν∗ through a differential-inclusion analysis, with the Lagrangian nonincreasing along the resulting trajectories.The associated stochastic approximation converges almost surely to the stationary set.
  • θ-update: The θ-update converges locally to θ∗, and the resulting stationary point is a local minimum of the Lagrangian for fixed λ.The proof uses ODE stability and multi-time-scale stochastic approximation arguments.
  • λ-update and conclusion: The proof concludes that the local saddle point theorem makes θ∗ a locally optimal policy for the CVaR-constrained optimization problem.This conclusion follows after establishing local saddle-point structure for the Lagrangian.

B.1 Gradient with Respect to λ (Proof of Lemma 11)

This proof obtains the gradient with respect to λ by differentiating the value function and unrolling the resulting expression over trajectory states and actions.

  • Gradient derivation: The proof differentiates V^θ(x0,ν) with respect to λ while accounting for λ-dependent costs in the augmented MDP.Both V and Q depend on λ through the augmented cost function.
  • Gradient derivation: The resulting derivative is unrolled using the definition of ∇λV^θ(x,s).This transforms the recursive derivative into an expanded expression.
  • Gradient derivation: The expanded expression uses trajectory probabilities over states and auxiliary variables, weighted by the function h(x,s).The probability term conditions on the initial augmented state and policy parameter θ.

B.2 Proof of Convergence of the Actor-Critic Algorithms

The actor-critic convergence proof combines critic convergence with multi-time-scale stochastic approximation for the policy, auxiliary, and multiplier updates. It concludes convergence to a locally optimal CVaR-constrained policy.

  • Proof structure: The critic update converges almost surely on the fastest time scale to a fixed point of the projected Bellman equation on the augmented MDP.The critic estimates the value component before the slower updates are analyzed.
  • Proof structure: The ν, θ, and λ updates converge almost surely to a stationary point of their corresponding continuous-time system under the specified step-size rules.Their time scales are ordered after the critic update.
  • Proof structure: The convergence argument follows the policy-gradient analysis and identifies the stationary point as a local saddle point.The proof procedure is described as standard for stochastic approximation algorithms.
  • Conclusion: The local saddle point theorem yields a locally optimal solution for the CVaR-constrained MDP problem.The conclusion concerns the policy parameter θ∗.

B.2.1 PROOF OF THEOREM 10: CRITIC UPDATE (v-UPDATE)

The critic analysis models the update as a stochastic approximation with martingale noise and studies its limiting ODE. Under the stated conditions, critic iterates converge almost surely to a unique fixed point.

  • Critic update: The critic update operates on the fastest time scale, allowing ν, θ, and λ to be treated as fixed during its convergence analysis.This follows from the step-size conditions.
  • Critic update: The critic update is written as a stochastic approximation whose noise term is a square-integrable martingale difference.The conditional mean of the noise is zero under the sampling filtration.
  • Convergence conditions: The technical conditions include Lipschitz drift, suitable step sizes, martingale noise, uniform limiting behavior, and a stable limiting ODE.These properties are used to invoke stochastic-approximation convergence theory.
  • Convergence result: The critic iterates are bounded almost surely.Boundedness is established as part of the stochastic-approximation analysis.
  • Convergence result: The iterates converge almost surely to the unique fixed point v∗ satisfying Av∗=b.The limit depends on ν, θ, and λ.

B.2.2 PROOF OF THEOREM 12

The proof establishes convergence of the actor-critic updates through stochastic approximation, multi-timescale analysis, and vanishing estimation errors. Under the stated assumptions, the policy parameter converges almost surely to a local minimum of the Lagrangian objective.

  • Convergence of critic and ν updates: SPSA estimates the ν sub-gradient using two simulated value functions evaluated at perturbed parameters ν− and ν+.The perturbation Δ is nonnegative, random, and vanishes asymptotically.
  • Assumptions: The proof relies on bounded feature functions, assumptions ensuring asymptotically unbiased SPSA estimates, and Lipschitz continuity of the approximated policy gradient.The Lipschitz property follows from differentiability of the value approximation and occupation measure together with the policy assumptions.
  • Convergence of critic and ν updates: The critic and auxiliary ν updates are analyzed as stochastic approximations with martingale errors and vanishing disturbance bias.The ν-update follows an Euler discretization of a differential inclusion, while the critic converges using the cited theorem.
  • Convergence of θ update: The actor update converges almost surely to an equilibrium point when the gradient approximation is Lipschitz and the function-approximation error vanishes.The analysis treats faster-converging critic and ν sequences as having reached their limiting values and represents the update as stochastic approximation with vanishing bias.
  • Local optimality: The θ-limit θ∗ is a local minimum of L(ν∗(θ), θ, λ) for a fixed λ in [0, λmax].This conclusion is stated under vanishing function-approximation error as the critic parameter converges to its limit.
Loading 1512.01629v3…