Seminar on Foundations of Computing

This research seminar provides a venue for presenting research results concerning algorithm design, discrete mathematics, formal methods, logic and related areas of theoretical computer science. The seminar is jointly organized by the research laboratories DIMEA, FORMELA, and LIVE. The seminar builds on the FMDSA seminar organized by the FORMELA laboratory in the past.

Time and place

The seminar usually takes place on Monday at 2PM term time in Room C123 in the building of the Faculty of Informatics on a (roughly) weekly schedule.

Spring 2026 – schedule overview

Speakers

2.2.

Marta Grobelna (TU Munich)

Stopping Criteria for Value Iteration on Concurrent Stochastic Reachability and Safety Games

Upcoming Speakers

	Gaurav Kucheriya (Charles university)
	Raju Gupta (SAV Bratislava)
	Ronen Wdowinski (TU Graz)

Marta Grobelna : Stopping Criteria for Value Iteration on Concurrent Stochastic Reachability and Safety Games

Monday, February 2, 14:00, room C117

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.