Sufficient Statistics for Team Decision Problems
pdf
In a team decision problem, a team of agents interacts with a system; each agent receives
a measurement that is probabilistically related to the state of the system; each agent uses its
measurement to choose an action; and the team incurs a cost that is a function of the state of
the system and the actions of the agents; the objective is to design the rules that the agents
use to choose their actions in order to minimize the expected cost. Despite their simplicity,
team decision problems are a fundamental building block of decentralized control, and the
solution of many more general problems can be reduced to the solution of a team decision
problem. In many practical scenarios, the measurements received by the agents contain
extraneous information that is not necessary to make optimal decisions. A sucient statistic
is a compressed measurement that can be used to make optimal decisions. By eliminating
irrelevant information, we can decrease the memory needed to store the measurements,
simplify the search for optimal decision rules, and obtain insight into the structure of the
problem. Compressed measurements are especially important for simplifying the search for
optimal decision rules because team decision problems are known to be NP-hard in general,
so even modestly sized problems are intractable without such compression. Wu and Lall gave
the rst de nition of sucient statistics for team decision problems, and showed that their
de nition possesses many, but not all, of the desirable properties of the sucient statistics in
the well-developed theory of classical decision problems. More recently, we have studied the
properties of an alternative de nition that has some desirable properties that the original
de nition lacks. However, it is currently unknown whether the alternative de nition has all
of the desirable properties of the rst de nition. Additionally, we have proposed a de nition
of approximate suciency for team problems. This is an important step in increasing the
applicability of the theory because the computational complexity of decentralized decision
making means that we often must settle for approximately optimal decision rules. We are
currently studying the properties of our de nitions of sucient and approximately sucient
statistics, and developing algorithms for computing these statistics.
Submitted by Sanjay Lall
on
In a team decision problem, a team of agents interacts with a system; each agent receives
a measurement that is probabilistically related to the state of the system; each agent uses its
measurement to choose an action; and the team incurs a cost that is a function of the state of
the system and the actions of the agents; the objective is to design the rules that the agents
use to choose their actions in order to minimize the expected cost. Despite their simplicity,
team decision problems are a fundamental building block of decentralized control, and the
solution of many more general problems can be reduced to the solution of a team decision
problem. In many practical scenarios, the measurements received by the agents contain
extraneous information that is not necessary to make optimal decisions. A sucient statistic
is a compressed measurement that can be used to make optimal decisions. By eliminating
irrelevant information, we can decrease the memory needed to store the measurements,
simplify the search for optimal decision rules, and obtain insight into the structure of the
problem. Compressed measurements are especially important for simplifying the search for
optimal decision rules because team decision problems are known to be NP-hard in general,
so even modestly sized problems are intractable without such compression. Wu and Lall gave
the rst de nition of sucient statistics for team decision problems, and showed that their
de nition possesses many, but not all, of the desirable properties of the sucient statistics in
the well-developed theory of classical decision problems. More recently, we have studied the
properties of an alternative de nition that has some desirable properties that the original
de nition lacks. However, it is currently unknown whether the alternative de nition has all
of the desirable properties of the rst de nition. Additionally, we have proposed a de nition
of approximate suciency for team problems. This is an important step in increasing the
applicability of the theory because the computational complexity of decentralized decision
making means that we often must settle for approximately optimal decision rules. We are
currently studying the properties of our de nitions of sucient and approximately sucient
statistics, and developing algorithms for computing these statistics.