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.