Complexity of solving finite stochastic games with imperfect information in extensive-form

In perfect information games such as Chess and Go, players observe everything. On the other hand, in games with imperfect information such as Bridge and Poker, players don't observe opponents' hands of cards and hence have partial knowledge while playing. Imperfect information makes the task of computing optimal strategies difficult : the problem is NP-hard in general, even for one-player games. However, there are tractable classes, such as perfect recall and Action-loss(A-loss) recall. In perfect recall, players fully remember their own past decisions; in A-loss recall, players may forget their past decisions but can remember the earliest decision point where they lost track of the exact decision made. One-player games with these kinds of recalls can be solved in polynomial time. Imperfect recall in general can capture stranger situations - players can even forget if they have encountered the same decision point before, also known as absentmindedness.

In this talk, we will take a tour of complexity of solving finite stochastic games in extensive-form with different degrees of imperfect information. We will discuss existing complexity bounds and also see new methods to transform non-absentminded games from "harder" classes to tractable classes that results in new polynomial time solvable classes of imperfect recall games.

This is based on joint work with Hugo Gimbert, Kristoffer Arnsfelt Hansen and B. Srivathsan.