Certainty equivalence for imperfect information finite state-space stochastic games

摘要

Stochastic games under imperfect 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. A function of a conditional probability distribution is proposed as an information state. 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. When the initial information state belongs to these classes, its propagation is finite-dimensional. The state feedback value function is also finite-dimensional, and obtained via dynamic programming, but has a nonstandard form due to the necessity of an expanded state variable. Under a saddle point assumption, certainty equivalence is obtained and the proposed function is indeed an information state.