A class of reasonably tractable partially observed discrete stochastic games

Stochastic games under partial information are typically computationally intractable even in the discrete-time/discrete-state case considered here. We consider a problem where one player has perfect information. The main problem is that the information state for the player with imperfect information is a function over the space of probability distributions (a function over a simplex), and so infinite-dimensional. However, in the problem form here, the payoff is only a function of the terminal state of the system, and the initial information state is either linear or a sum of max-plus delta functions. In this case, the information state and state-feedback value functions belong to finite-dimensional sets. Thus the computational tractability is greatly enhanced.