Tuesday, May 23, 2017
Venue: IST Austria
Every day, we make sequences of decisions to accomplish our goals, and we attempt to achieve these goals in the most favorable way. In many aspects of life, such as in security or economy, the optimality of these decisions is critical, and a computational support for decision making is thus needed. Sequential decision making is, however, computationally challenging in the presence of uncertainty (partially observable Markov decision processes) or even adversaries (partially observable stochastic games). We provide a game theoretic model of one-sided partially observable stochastic games which is motivated by problems arising mainly in security. It captures both the uncertainty of the decision maker and the adversarial nature of the problem into account. Our framework assumes two players where one player is given the advantage of having perfect information. We show that we can solve such games in the similar fashion as one solves POMDPs using the value iteration algorithm, including its more practical approximate variants based on point-based updates of the value function.