Stopping Criteria for Value Iteration on Concurrent Stochastic Reachability and Safety Games

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F25%3A00143614" target="_blank" >RIV/00216224:14330/25:00143614 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1109/LICS65433.2025.00049" target="_blank" >http://dx.doi.org/10.1109/LICS65433.2025.00049</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/LICS65433.2025.00049" target="_blank" >10.1109/LICS65433.2025.00049</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Stopping Criteria for Value Iteration on Concurrent Stochastic Reachability and Safety Games

Popis výsledku v původním jazyce

We consider two-player zero-sum concurrent stochastic games (CSGs) played on graphs with reachability and safety objectives. These include degenerate classes such as Markov decision processes or turn-based stochastic games, which can be solved by linear or quadratic programming; however, in practice, value iteration (VI) outperforms the other approaches and is the most implemented method. Similarly, for CSGs, this practical performance makes VI an attractive alternative to the standard theoretical solution via the existential theory of reals.VI starts with an under-approximation of the sought values for each state and iteratively updates them, traditionally terminating once two consecutive approximations are ε-close. However, this stopping criterion lacks guarantees on the precision of the approximation, which is the goal of this work. We provide bounded (a.k.a. interval) VI for CSGs: it complements standard VI with a converging sequence of over-approximations and terminates once the over- and under-approximations are ε-close.

Název v anglickém jazyce

Stopping Criteria for Value Iteration on Concurrent Stochastic Reachability and Safety Games

Popis výsledku anglicky

We consider two-player zero-sum concurrent stochastic games (CSGs) played on graphs with reachability and safety objectives. These include degenerate classes such as Markov decision processes or turn-based stochastic games, which can be solved by linear or quadratic programming; however, in practice, value iteration (VI) outperforms the other approaches and is the most implemented method. Similarly, for CSGs, this practical performance makes VI an attractive alternative to the standard theoretical solution via the existential theory of reals.VI starts with an under-approximation of the sought values for each state and iteratively updates them, traditionally terminating once two consecutive approximations are ε-close. However, this stopping criterion lacks guarantees on the precision of the approximation, which is the goal of this work. We provide bounded (a.k.a. interval) VI for CSGs: it complements standard VI with a converging sequence of over-approximations and terminates once the over- and under-approximations are ε-close.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

V - Vyzkumna aktivita podporovana z jinych verejnych zdroju

Rok uplatnění

2025

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Stopping Criteria for Value Iteration on Concurrent Stochastic Reachability and Safety Games

ISBN

9798331579005

ISSN

1043-6871

e-ISSN

—

Počet stran výsledku

13

Strana od-do

568-580

Název nakladatele

IEEE

Místo vydání

Singapore

Místo konání akce

Singapore

Datum konání akce

1. 1. 2025

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—