Stopping Criteria for Value Iteration on Stochastic Games with
Quantitative Objectives

D 2023

Stopping Criteria for Value Iteration on Stochastic Games with Quantitative Objectives

KŘETÍNSKÝ, Jan; Tobias MEGGENDORFER a Maximilian WEININGER

Základní údaje

Originální název

Stopping Criteria for Value Iteration on Stochastic Games with Quantitative Objectives

Autoři

KŘETÍNSKÝ, Jan; Tobias MEGGENDORFER a Maximilian WEININGER

Vydání

Boston, 2023 38TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, LICS, od s. 1-14, 14 s. 2023

Nakladatel

IEEE

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í

tištěná verze "print"

Kód RIV

RIV/00216224:14330/23:00133936

Organizační jednotka

Fakulta informatiky

ISBN

979-8-3503-3587-3

ISSN

DOI

https://doi.org/10.1109/LICS56636.2023.10175771

UT WoS

001036707700042

EID Scopus

2-s2.0-85166017438

Klíčová slova anglicky

Stochastic games; value iteration

Štítky

core_A, firank_1

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 8. 4. 2024 05:49, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

A classic solution technique for Markov decision processes (MDP) and stochastic games (SG) is value iteration (VI). Due to its good practical performance, this approximative approach is typically preferred over exact techniques, even though no practical bounds on the imprecision of the result could be given until recently. As a consequence, even the most used model checkers could return arbitrarily wrong results. Over the past decade, different works derived stopping criteria, indicating when the precision reaches the desired level, for various settings, in particular MDP with reachability, total reward, and mean payoff, and SG with reachability.

Citovat

KŘETÍNSKÝ, Jan; Tobias MEGGENDORFER a Maximilian WEININGER. Stopping Criteria for Value Iteration on Stochastic Games with Quantitative Objectives. In 979-8-3503-3587-3. 2023 38TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, LICS. Boston: IEEE, 2023, s. 1-14. ISBN 979-8-3503-3587-3. Dostupné z: https://doi.org/10.1109/LICS56636.2023.10175771.

@inproceedings{2392227,
   author = {Křetínský, Jan and Meggendorfer, Tobias and Weininger, Maximilian},
   address = {Boston},
   booktitle = {2023 38TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, LICS},
   doi = {https://doi.org/10.1109/LICS56636.2023.10175771},
   editor = {979-8-3503-3587-3},
   keywords = {Stochastic games; value iteration},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Boston},
   isbn = {979-8-3503-3587-3},
   pages = {1-14},
   publisher = {IEEE},
   title = {Stopping Criteria for Value Iteration on Stochastic Games with Quantitative Objectives},
   year = {2023}
}

TY  - CONF
ID  - 2392227
AU  - Křetínský, Jan - Meggendorfer, Tobias - Weininger, Maximilian
PY  - 2023
TI  - Stopping Criteria for Value Iteration on Stochastic Games with Quantitative Objectives
PB  - IEEE
CY  - Boston
SN  - 9798350335873
KW  - Stochastic games
KW  - value iteration
N2  - A classic solution technique for Markov decision processes (MDP) and stochastic games (SG) is value iteration (VI). Due to its good practical performance, this approximative approach is typically preferred over exact techniques, even though no practical bounds on the imprecision of the result could be given until recently. As a consequence, even the most used model checkers could return arbitrarily wrong results. Over the past decade, different works derived stopping criteria, indicating when the precision reaches the desired level, for various settings, in particular MDP with reachability, total reward, and mean payoff, and SG with reachability.
ER  -

KŘETÍNSKÝ, Jan; Tobias MEGGENDORFER a Maximilian WEININGER. Stopping Criteria for Value Iteration on Stochastic Games with Quantitative Objectives. In 979-8-3503-3587-3. \textit{2023 38TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, LICS}. Boston: IEEE, 2023, s.~1-14. ISBN~979-8-3503-3587-3. Dostupné z: https://doi.org/10.1109/LICS56636.2023.10175771.

Přehled o publikaci