Witsenhausen's counterexample
Witsenhausen's counterexample, shown in the figure below, is a deceptively simple
Statement of the counterexample
The statement of the counterexample is simple: two controllers attempt to control the system by attempting to bring the state close to zero in exactly two time steps. The first controller observes the initial state There is a cost on the input of the first controller, and a cost on the state after the input of the second controller. The input of the second controller is free, but it is based on noisy observations of the state after the first controller's input. The second controller cannot communicate with the first controller and thus cannot observe either the original state or the input of the first controller. Thus the system dynamics are
with the second controller's observation equation
The objective is to minimize an expected cost function,
where the expectation is taken over the randomness in the initial state and the observation noise , which are distributed independently. The observation noise is assumed to be distributed in a Gaussian manner, while the distribution of the initial state value differs depending on the particular version of the problem.
The problem is to find control functions
that give at least as good a value of the objective function as do any other pair of control functions. Witsenhausen showed that the optimal functions and cannot be linear.
Specific results of Witsenhausen
Witsenhausen obtained the following results:
- An optimum exists (Theorem 1).
- The optimal control law of the first controller is such that (Lemma 9).
- The exact solution is given for the case in which both controllers are constrained to be linear (Lemma 11).
- If has a Gaussian distribution and if at least one of the controllers is constrained to be linear, then it is optimal for both controllers to be linear (Lemma 13).
- The exact nonlinear control laws are given for the case in which has a symmetric distribution(Lemma 15).
- If has a Gaussian distribution, for some values of the preference parameter a non-optimal nonlinear solution for the control laws is given which gives a lower value for the expected cost function than does the best linear pair of control laws (Theorem 2).
The significance of the problem
The counterexample lies at the intersection of control theory and information theory. Due to its hardness, the problem of finding the optimal control law has also received attention from the theoretical computer science community. The importance of the problem was reflected upon in the 47th IEEE Conference on Decision and Control (CDC) 2008, Cancun, Mexico,[2] where an entire session was dedicated to understanding the counterexample 40 years after it was first formulated.
The problem is of conceptual significance in decentralized control because it shows that it is important for the controllers to communicate[3] with each other implicitly in order to minimize the cost. This suggests that control actions in decentralized control may have a dual role: those of control and communication.
The hardness of the problem
The hardness of the problem is attributed to the fact that information of the second controller depends on the decisions of the first controller.
A justification of the failure of attempts that discretize the problem came from the computer science literature:
Attempts at obtaining a solution
A number of numerical attempts have been made to solve the counterexample. Focusing on a particular choice of problem parameters , researchers have obtained strategies by
References
- ^ Witsenhausen, Hans. "A counterexample in stochastic optimum control." SIAM J. Control, Volume 6, Issue 1, pp. 131–147 (February 1968)
- ^ a b Ho, Yu-Chi, "Review of the Witsenhausen problem". Proceedings of the 47th IEEE Conference on Decision and Control (CDC), pp. 1611–1613, 2008.
- ^ Mitterrand and Sahai. "Information and Control: Witsenhausen revisited". Learning, control and hybrid systems, 1999, Springer.
- ^ Ho, Yu-Chi. "Team decision theory and information structures". Proceedings of the IEEE, Vol. 68, No.6, June 1980.
- ^ Basar, Tamer. "Variations on the theme of the Witsenhausen counterexample". 47th IEEE Conference on Decision and Control Cancun, Mexico, Dec. 9–11, 2008.
- ^ Rotkowitz, M.; Cogill, R.; Lall, S.; "A Simple Condition for the Convexity of Optimal Control over Networks with Delays," Decision and Control, 2005 and 2005 European Control Conference. CDC-ECC '05. 44th IEEE Conference on, pp. 6686–6691, 12–15 December 2005.
- ^ Christos Papadimitriou and John Tsitsiklis. "Intractable problems in control theory." 24th IEEE Conference on Decision and Control, 1985
- ^ Baglietto, Parisini, and Zoppoli. "Numerical solutions to the Witsenhausen counterexample by approximating networks." IEEE Transactions on Automatic Control. 2001.
- ^ Lee, Lau, and Ho. "The Witsenhausen counterexample: A hierarchical search approach for nonconvex optimization problems." IEEE Transactions on Automatic Control, 2001
- ^ Li, Marden, and Shamma. "Learning approaches to the Witsenhausen counterexample from a view of potential games." IEEE Conference on Decision and Control, 2009.
- ^ Tseng and Tang. "A Local Search Algorithm for the Witsenhausen's Counterexample." IEEE Conference on Decision and Control, 2017.
- ^ Grover, Sahai, and Park. "The finite-dimensional Witsenhausen counterexample." IEEE WiOpt 2010, ConCom workshop, Seoul, Korea.