CGO seminar at LSE

I presented my latest work on Partially Observable Stochastic Games on the existence and approximability of the uniform value in the blind case.

Title

Taming Partial Observation in Stochastic Games: the blind case

Abstract

Consider dynamic games between two opponents with both stochastic transitions and partial observation of the 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 the uniform value may not exist in general.  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.  Notably, this result is novel even in the single-player setting. Our results are tight because we show that no algorithm can compute the uniform value exactly.

Here is the presentation: