Information structures, causality, and nonsequential stochastic control.
Mark S. Andersland · Deep Blue (University of Michigan) · 1989
Consider a generic stochastic control problem involving N control actions. Constrain each control action's control law to be a measurable function of a noisy observation of some subset of the N control actions. Let the objective be to identify a set of N control laws (one for each control action), called a design, that maximizes exactly, or to within some tolerance, an expected reward. When the time ordering of the control actions can not be fixed in advance in a design-independent manner, the generic problem is said to be non-sequential. In non-sequential problems, two or more of the control actions my be interdependent under some designs (e.g., $u\\sp1$ may depend on $u\\sp2$ under some circumstances although $u\\sp2$ depends on $u\\sp1$ under other circumstances). Due to this interdependence, these designs need not possess expected rewards or causal implementations (e.g., $u\\sp1$ and $u\\sp2$ may be simultaneously interdependent). In practice--i.e., in distributed data, communication, manufacturing, and detection networks--the latter phenomenon manifests itself as a deadlock. In this dissertation, the structural and qualitative properties of the generic problem are investigated within the framework of Witsenhausen's intrinsic model (SIAM J. Control, May 1971), the principal objective being to relate properties of the problem's information structure (i.e., the specification of the control agents' available information) to conditions ensuring that the problem's designs possess expected rewards and causal implementations. Specifically, necessary and sufficient conditions are developed for: (1) all of the generic problem's designs to possess expected rewards and causal implementations, and (2) particular designs to possess expected rewards and causal implementations. It is also shown, by example, that there exist stochastic control problems for which all sequential designs are suboptimal. These results subsume Witsenhausen's sufficient conditions (op. cit.), suggest a framework for the optimization of non-sequential problems, and provide a complete and surprisingly intuitive characterization of the cause/effect notion of causality. The results also have implications in game theory--they suggest, for instance, necessary and sufficient conditions for a finite game to possess an extensive form.