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

Jan Ketínský, Tobias Meggendorfer

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

8 Scopus citations

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.

Original languageEnglish
Title of host publicationProceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages609-618
Number of pages10
ISBN (Electronic)9781450355834, 9781450355834
DOIs
StatePublished - 9 Jul 2018
Event33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018 - Oxford, United Kingdom
Duration: 9 Jul 201812 Jul 2018

Publication series

NameProceedings - Symposium on Logic in Computer Science
ISSN (Print)1043-6871

Conference

Conference33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018
Country/TerritoryUnited Kingdom
CityOxford
Period9/07/1812/07/18

Fingerprint

Dive into the research topics of 'Conditional Value-at-Risk for Reachability and Mean Payoff in Markov Decision Processes'. Together they form a unique fingerprint.

Cite this