一句话：为并发随机博弈的值迭代提出带上/下界的停止准则，保证近似精度。
本文研究图上带可达性与安全性目标的二人零和并发随机博弈（CSG），其中也包含马尔可夫决策过程与回合制随机博弈等退化情形。此类问题理论上可用线性/二次规划或实数存在理论求解，但实践中值迭代（VI）因性能优势而最常被实现。传统 VI 从目标值的下近似出发迭代更新，并以连续两次近似 ε-接近作为停止条件，但该条件无法保证最终近似的精度。本文为此类 CSG 提出有界（又称区间）VI：在标准下近似序列之外，额外构造收敛的上近似序列，并在上、下近似 ε-接近时终止。由此为停止准则提供了精度保证，弥补了传统 VI 停止条件缺乏理论保障的不足。
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.
DOI 原文 ·
@inproceedings{paperbot8658,
title = {Stopping Criteria for Value Iteration on Concurrent Stochastic Reachability and Safety Games},
author = {Marta Grobelna and Jan Křetínský and Maximilian Weininger},
booktitle = {LICS},
year = {2025},
doi = {10.1109/lics65433.2025.00049}
}