turkmath.org

Decentralized stochastic control theory studies decisions of agents that are acting collectively based on their local information to optimize a common cost function under stochastic uncertainty. Currently available techniques (such as classical dynamic programming, policy iteration, value iteration, linear programming, etc.) in centralized stochastic control does not apply under decentralized and asymmetric information structures. Even for a very simple decentralized stochastic control problem (i.e., Witsenhausen’s counterexample), application of classical methods for obtaining good strategies leads to poor performance. Moreover, we note that computing optimal strategies for decentralized stochastic control problems is in general known to be NP hard. Hence, we need new viewpoints and new approaches that overcome decentralized nature of the problem. In this talk, I will consider non-signaling approximation of finite decentralized stochastic control problems. I will first introduce a hierarchy of control policies that can be classified in an increasing order as randomized policies and non-signaling policies. Then, I will establish an approximation of optimal policies for decentralized stochastic control systems via extendible nonsignaling policies. I will show that the distance between extendible non-signaling policies and decentralized policies is small if the extension is sufficiently large. Using this result, I will establish a linear programming (LP) approximation of decentralized stochastic control problems.