Timezone: »
Poster
Complexity of Decentralized Control: Special Cases
Martin Allen · Shlomo Zilberstein
The worst-case complexity of general decentralized POMDPs, which are equivalent to partially observable stochastic games (POSGs) is very high, both for the cooperative and competitive cases. Some reductions in complexity have been achieved by exploiting independence relations in some models. We show that these results are somewhat limited: when these independence assumptions are relaxed in very small ways, complexity returns to that of the general case.
Author Information
Martin Allen (Connecticut College)
Shlomo Zilberstein (Univ of Mass)
More from the Same Authors
-
2014 Poster: Stochastic Network Design in Bidirected Trees »
Xiaojian Wu · Daniel Sheldon · Shlomo Zilberstein -
2010 Poster: MAP Estimation for Graphical Models by Likelihood Maximization »
Akshat Kumar · Shlomo Zilberstein -
2009 Poster: Robust Value Function Approximation Using Bilinear Programming »
Marek Petrik · Shlomo Zilberstein -
2009 Spotlight: Robust Value Function Approximation Using Bilinear Programming »
Marek Petrik · Shlomo Zilberstein