Approximate Sufficient Statistics for Team Decision Problems

摘要

Team decision problems are one of the fundamental problems in decentralized decision making. Because team decision problems are NP-hard, it is important to find methods for reducing their complexity. Wu and Lall gave a definition of sufficient statistics for team decision problems, and demonstrated that these statistics are sufficient for optimality, and possess other desirable properties such as being readily updated when additional information becomes available. More recently, Lemon and Lall defined weak sufficient statistics for team decision problems, and showed that these statistics are sufficient for optimality and necessary for simultaneous optimality with respect to all cost functions. This prior work studied the extent to which the complexity of team decision problems can be reduced while maintaining exact optimality. However, when faced with a computationally difficult problem, we are often willing to sacrifice exact optimality for significant reductions in complexity. In this paper we define approximate sufficient statistics, which are a generalization of weak team sufficient statistics. Then we prove that these statistics are quantifiably close to being optimal.