Sound Value Iteration for Simple Stochastic Games

AZEEM, Muqsit; Jan KŘETÍNSKÝ a Maximilian WEININGER. Sound Value Iteration for Simple Stochastic Games. Online. In ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE. SYDNEY: OPEN PUBL ASSOC, 2025, s. 29-44. ISSN 2075-2180. Dostupné z: https://doi.org/10.4204/EPTCS.428.4.

Základní údaje

Originální název

Sound Value Iteration for Simple Stochastic Games

Autoři

AZEEM, Muqsit; Jan KŘETÍNSKÝ a Maximilian WEININGER

Vydání

SYDNEY, ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE, od s. 29-44, 16 s. 2025

Nakladatel

OPEN PUBL ASSOC

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10200 1.2 Computer and information sciences

Utajení

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

Forma vydání

elektronická verze "online"

Označené pro přenos do RIV

Ano

Organizační jednotka

Fakulta informatiky

ISSN

DOI

https://doi.org/10.4204/EPTCS.428.4

UT WoS

001602118100002

EID Scopus

2-s2.0-105018803200

Klíčová slova anglicky

Computer Science; Theory&; Methods

---

Anotace

V originále

Algorithmic analysis of Markov decision processes (MDP) and stochastic games (SG) in practice relies on value-iteration (VI) algorithms. Since basic VI does not provide guarantees on the precision of the result, variants of VI have been proposed that offer such guarantees. In particular, sound value iteration (SVI) not only provides precise lower and upper bounds on the result, but also converges faster in the presence of probabilistic cycles. Unfortunately, it is neither applicable to SG, nor to MDP with end components. In this paper, we extend SVI and cover both cases. The technical challenge consists mainly in proper treatment of end components, which require different handling than in the literature. Moreover, we provide several optimizations of SVI. Finally, we evaluate our prototype implementation experimentally to demonstrate its potential on systems with probabilistic cycles.

---

Návaznosti

MUNI/I/1757/2021, interní kód MU	Název: MUNI Award in Science and Humanities (Akronym: Křetínský) Investor: Masarykova univerzita, MUNI Award in Science and Humanities, MASH - MUNI Award in Science and Humanities
101171844, interní kód MU	Název: Intelligence-Oriented Verification&Controller Synthesis Investor: Evropská unie, Intelligence-Oriented Verification&Controller Synthesis, Evropská rada pro výzkum (ERC)