Non-signaling Approximations of Stochastic Team Problems
For researchers in decentralized control and team decision theory, it provides a novel approximation framework for team-optimal policies using non-signaling correlations.
The paper introduces a hierarchy of decision rules for stochastic teams and proves that extendible non-signaling policies can approximate team-optimal policies with small error when the extension is large, leading to a linear programming approximation for sequential teams.
In this paper, we consider non-signaling approximation of finite stochastic teams. We first introduce a hierarchy of team decision rules that can be classified in an increasing order as randomized policies, quantum-correlated policies, and non-signaling policies. Then, we establish an approximation of team-optimal policies for sequential teams via extendible non-signaling policies. We prove that the distance between extendible non-signaling policies and decentralized policies is small if the extension is sufficiently large. Using this result, we establish a linear programming (LP) approximation of sequential teams. Finally, we state an open problem regarding computation of optimal value of quantum-correlated policies.