Approximate Solutions for Partially Observable Stochastic Games with Common Payoffs

Abstract

In partially observable team games with limited communication, agents receive different observations about the world state and must reason about the value of actions for all possible observation histories of their teammates in order to maximize a joint reward function. Extensive form games provide a theoretically sound, but computationally expensive, framework for decentralized action selection in these problems. We propose using Bayesian games, which model agents that have private information relevant to the decision making process of others, to approximate the full game tree as a series of smaller, related games. Policies are found by building a Bayesian game representation for each timestep, with heuristics such as QMDP used to provide the future discounted value of actions. This algorithm trades off limited look-ahead in uncertainty for computational feasibility, and results in policies that are locally optimal with respect to the selected heuristic. For a simple problem, we provide empirical comparisons of policies found by solving the full extensive form game to those found by our Bayesian game transformation. For more complex, robot-inspired problems, the performance of our algorithm is compared to approaches in which agents do not take differences in observations into account during policy construction.