  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.
