Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Sum of squares and decentralized stochastic decision processes

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.
Type of Seminar:
Public Seminar
Prof. Sanjay Lall
Aeronautics and Astronautics, Stanford University
Jun 22, 2004   14:00

ETH Zentrum, ETZ E 81
Contact Person:

Prof. P. Parrilo
File Download:

Request a copy of this publication.
Biographical Sketch:
Sanjay Lall is Assistant Professor of Aeronautics and Astronautics at Stanford University. Until 2000 he was a Research Fellow at the California Institute of Technology in the Department of Control and Dynamical Systems, and prior to that he was NATO Research Fellow at Massachusetts Institute of Technology, in the Laboratory for Information and Decision Systems. He received the Ph.D. in Engineering from the University of Cambridge, England.