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

2018/05/08 by Křetínský, Jan, Meggendorfer, Tobias · 1 citation
#FOS: Computer and information sciences #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.1805.02946

Abstract

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.

Cited by

• Multi-Objective Statistical Model Checking using Lightweight Strategy Sampling (extended version)

Related

• Risk-Sensitive and Robust Decision-Making: a CVaR Optimization Approach
• Planning for Risk-Aversion and Expected Value in MDPs
• On Optimizing the Conditional Value-at-Risk of a Maximum Cost for Risk-Averse Safety Analysis
• On the Maximization of Long-Run Reward CVaR for Markov Decision Processes
• An Asymptotic CVaR Measure of Risk for Markov Chains