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

D 2018

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

KŘETÍNSKÝ, Jan a Tobias MEGGENDORFER

Základní údaje

Originální název

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

Autoři

KŘETÍNSKÝ, Jan (203 Česká republika, garant, domácí) a Tobias MEGGENDORFER (276 Německo)

Vydání

New York, NY, USA, Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS '18), od s. 609-618, 10 s. 2018

Nakladatel

ACM

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Kód RIV

RIV/00216224:14330/18:00108288

Organizační jednotka

Fakulta informatiky

ISBN

978-1-4503-5583-4

ISSN

DOI

http://dx.doi.org/10.1145/3209108.3209176

UT WoS

000545262800063

Klíčová slova anglicky

conditional value-at-risk; Markov chains; Markov decision processes; reachability; mean-payoff

Štítky

core_A, firank_1

Změněno: 31. 5. 2022 12:24, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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.

Návaznosti

GA18-11193S, projekt VaV

Název: Algoritmy pro diskrétní systémy a hry s nekonečně mnoha stavy

Investor: Grantová agentura ČR, Algoritmy pro diskrétní systémy a hry s nekonečně mnoha stavy

Citovat

KŘETÍNSKÝ, Jan a Tobias MEGGENDORFER. Conditional Value-at-Risk for Reachability and Mean Payoff in Markov Decision Processes. Online. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS '18). New York, NY, USA: ACM, 2018, s. 609-618. ISBN 978-1-4503-5583-4. Dostupné z: https://dx.doi.org/10.1145/3209108.3209176.

@inproceedings{1649039,
   author = {Křetínský, Jan and Meggendorfer, Tobias},
   address = {New York, NY, USA},
   booktitle = {Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS '18)},
   doi = {http://dx.doi.org/10.1145/3209108.3209176},
   keywords = {conditional value-at-risk; Markov chains; Markov decision processes; reachability; mean-payoff},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {New York, NY, USA},
   isbn = {978-1-4503-5583-4},
   pages = {609-618},
   publisher = {ACM},
   title = {Conditional Value-at-Risk for Reachability and Mean Payoff in Markov Decision Processes},
   year = {2018}
}

TY  - JOUR
ID  - 1649039
AU  - Křetínský, Jan - Meggendorfer, Tobias
PY  - 2018
TI  - Conditional Value-at-Risk for Reachability and Mean Payoff in Markov Decision Processes
PB  - ACM
CY  - New York, NY, USA
SN  - 9781450355834
KW  - conditional value-at-risk
KW  - Markov chains
KW  - Markov decision processes
KW  - reachability
KW  - mean-payoff
N2  - 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.
ER  -

KŘETÍNSKÝ, Jan a Tobias MEGGENDORFER. Conditional Value-at-Risk for Reachability and Mean Payoff in Markov Decision Processes. Online. In \textit{Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS '18)}. New York, NY, USA: ACM, 2018, s.~609-618. ISBN~978-1-4503-5583-4. Dostupné z: https://dx.doi.org/10.1145/3209108.3209176.

Podrobný výpis o publikaci