Sound Value Iteration for Simple Stochastic Games

V alue iteration (VI) [4] is the practically most used method for reliable analysis of probabilistic systems, in particular Markov decision processes (MDPs) [21] and stochastic games (SGs) [8]. It is used in the state-of-the-art model checkers such as Prism [18] and Storm [11] as the default method due to its better practical scalability, compared to strategy iteration or linear/quadratic programming [14, 19]. The price to pay are issues with precision. Firstly, while other methods yield precise results in theory (omitting floating-point issues), VI converges to the exact result only in the limit. Secondly, the precision of the intermediate iterations was until recently an open question. Given the importance of reliable precision in verification, many recent works focused on modifying VI so that the imprecision can be bounded, yielding a stopping criterion. Consequently, (i) the computed result is reliable, and (ii) the procedure can even terminate earlier whenever the desired precision is achieved.