Blind Stochastic Games: From nonexistence, through undecidability, to subclasses

25^th November 2025, 13:00
Raimundo Saona Urmeneta
LSE

Abstract

Stochastic Games are dynamic games between two opponents with stochastic transitions.
In the blind model, players observes their actions but not the next state.
A game has a uniform value if each player can approximately guarantee to obtain it in average, for all sufficiently large time horizons.
Prior work has shown that: (1) the uniform value may not exist in general; and (2) it is undecidable to approximate the value in the single-player case (probabilistic automata).
Therefore, we introduce the subclass of ergodic games, restricting the state transitions.
For ergodic blind stochastic games, we prove the existence of the uniform value and provide an algorithm to approximate it, which is novel even in the single-player setting.
Our results are tight because we show that no algorithm can compute the uniform value of ergodic blind single-player stochastic games.

Biography

Rai is a Fellow at London School of Economics and Political Science (LSE). His research involves Mathematics, Game Theory, and Computer Science. He works with continuous and discrete models, and with both dynamic online and static offline settings.