Dynamic Programming Approximations for Partially Observable Stochastic Games
Akshat Kumar, Shlomo Zilberstein · 2009
Partially observable stochastic games (POSGs) provide a rich mathematical framework for planning under uncertainty by a group of agents. However, this modeling advantage comes with a price, namely a high computational cost. Solving POSGs optimally quickly becomes intractable after a few de-cision cycles. Our main contribution is to provide bounded approximation techniques, which enable us to scale POSG al-gorithms by several orders of magnitude. We study both the POSG model and its cooperative counterpart, DEC-POMDP. Experiments on a number of problems confirm the scalability of our approach while still providing useful policies.