Conditional value-at-risk for reachability and mean payoff in Markov decision processes

DOI10.1145/3209108.3209176MaRDI QIDQ5145337zbMATH OpenOpenAlexFDO

Authors Jan Křetínský, Tobias Meggendorfer

Publication date 20 January 2021

Published in Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.02946

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) Markov and semi-Markov decision processes (90C40)

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.

Recommendations

• Markov decision processes with average-value-at-risk criteria
• A convex analytic approach to risk-aware Markov decision processes
• Conditional value-at-risk: structure and complexity of equilibria
• Conditional value-at-risk: structure and complexity of equilibria
• An average-value-at-risk criterion for Markov decision processes with unbounded costs

Cited in

(13)

• Policy gradients for CVaR-constrained MDPs
• Maximizing the conditional expected reward for reaching the goal
• Multi-weighted Markov decision processes with reachability objectives
• Conditional value-at-risk: structure and complexity of equilibria
• Conditional value-at-risk: structure and complexity of equilibria
• On Optimizing the Conditional Value-at-Risk of a Maximum Cost for Risk-Averse Safety Analysis
• MDPs as distribution transformers: affine invariant synthesis for safety objectives
• Positivity-hardness results on Markov decision processes
• Entropic risk for turn-based stochastic games
• On Skolem-hardness and saturation points in Markov decision processes
• Risk-averse optimization of total rewards in Markovian models using deviation measures
• Demonic variance and a non-determinism score for Markov decision processes
• Finding equilibria: simpler for pessimists, simplest for optimists

This page was built for publication: Conditional value-at-risk for reachability and mean payoff in Markov decision processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5145337)