Dynamic Programming for Partially Observable Stochastic Games
Eric A. Hansen
Daniel S. Bernstein
Shlomo Zilberstein
Abstract
We develop an exact dynamic programming algorithm for
partially observable stochastic games (POSGs). The algorithm
is a synthesis of dynamic programming for partially observable
Markov decision processes (POMDPs) and iterated
elimination of dominated strategies in normal form games.
We prove that when applied to finite-horizon POSGs, the algorithm
iteratively eliminates very weakly dominated strategies
without first forming a normal form representation of the
game. For the special case in which agents share the same
payoffs, the algorithm can be used to find an optimal solution.
We present preliminary empirical results and discuss
ways to further exploit POMDP theory in solving POSGs.
Download
[pdf]