# Conditional Value-at-Risk for Reachability and Mean Payoff in Markov Decision Processes

arXiv: https://arxiv.org/abs/1805.02946 · HTML: https://mlsanity.com/paper/1805.02946/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 May 2018.

## Built on by (most cited first, 4 of 4)

- [Risk-aware Stochastic Shortest Path](https://mlsanity.com/paper/2203.01640/) (2022)
- [Stopping Criteria for Value Iteration on Stochastic Games with Quantitative Objectives](https://mlsanity.com/paper/2304.09930/) (2023)
- [Threshold UCT: Cost-Constrained Monte Carlo Tree Search with Pareto Curves](https://mlsanity.com/paper/2412.13962/) (2024)
- [Risk-Sensitive Agent Compositions](https://mlsanity.com/paper/2506.04632/) (2025)

## Abstract (arXiv)

We present the conditional value-at-risk (CVaR) in the context of Markov chains and Markov decision processes with reachability and mean-payoff objectives. CVaR quantifies risk by means of the expectation of the worst p-quantile. As such it can be used to design risk-averse systems. We consider not only CVaR constraints, but also introduce their conjunction with expectation constraints and quantile constraints (value-at-risk, VaR). We derive lower and upper bounds on the computational complexity of the respective decision problems and characterize the structure of the strategies in terms of memory and randomization.