Speaker: Sanjay Lall

Joined work with Randy Cogill

Title: Sum of Squares and Decentralized Stochastic Decision Problems

Abstract:

In this talk we consider decentralized stochastic decision problems. The problem of determining optimal decentralized policies for a class of multi-agent Markov decision processes is considered, and we focus on a specific model in which state transitions for each agent are independent, but joint rewards are earned at each step. It is shown that even for the two agent case, this problem is NP-hard. It is then shown that this problem has an equivalent formulation as a problem of maximizing a polynomial subject to linear and quadratic constraints.
We make use of this polynomial formulation of the problem, and use linear programming to construct positivstellensatz refutations to give upper bounds on the maximum achievable reward. We also consider the associated dual conditions, which correspond to a lifting of the original optimization problem. We show how to use this lifting in combination with a projection to construct suboptimal decentralized policies. The upper bounds developed are always tighter than those associated with the optimal centralized policy, and we give several examples when it is tight. The talk is illustrated by several examples of both static classification problems as well as Markov decision processes, and we also give an application to medium-access control in wireless networks.