Sound Value Iteration for Simple Stochastic Games
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911159666343936 |
|---|---|
| author | Azeem, Muqsit Kretinsky, Jan Weininger, Maximilian |
| author_facet | Azeem, Muqsit Kretinsky, Jan Weininger, Maximilian |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_14112 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sound Value Iteration for Simple Stochastic Games Azeem, Muqsit Kretinsky, Jan Weininger, Maximilian Computer Science and Game Theory Multiagent Systems 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. |
| title | Sound Value Iteration for Simple Stochastic Games |
| topic | Computer Science and Game Theory Multiagent Systems |
| url | https://arxiv.org/abs/2509.14112 |