为随机博弈值迭代提供可保证精度的停止准则
Stopping Criteria for Value Iteration on Concurrent Stochastic Reachability and Safety Games
- 引入上下界同步迭代，确保逼近值始终夹在真实值区间内
- 当上下界差距小于ε时终止，保证结果精度不超过ε
- 适合需要严格误差控制的博弈决策场景
我们研究在图上进行的双人零和并发随机博弈（CSGs），其目标为到达或安全。这类博弈包括马尔可夫决策过程或轮流博弈等退化情形，可通过线性或二次规划求解；但实践中，值迭代（VI）性能更优，是主流实现方法。传统VI以状态值的下界近似开始，迭代更新直至连续两次近似值相差小于ε，但此准则无法保证最终结果的精度。本文提出针对CSGs的有界（即区间）值迭代：在标准VI基础上增加一个收敛的上界序列，当上下界间距小于ε时终止，从而确保近似值与真实值之差不超过ε。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。