Witsenhausen's counterexample, shown in the figure below, is a deceptively simple toy problem in decentralized stochastic control.
[1] It is a counterexample to a natural conjecture that one can generalize a key result of centralized linear–quadratic–Gaussian control systems—that in a system with linear dynamics, Gaussian disturbance, and quadratic cost, affine (linear) control laws are optimal—to decentralized systems.
Witsenhausen constructed a two-stage linear quadratic Gaussian system where two decisions are made by decision makers with decentralized information and showed that for this system, there exist nonlinear control laws that outperform all linear laws.
The problem of finding the optimal control law remains unsolved.
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.
of the second controller is free, but it is based on noisy observations
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
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.
[4] Variations considered by Tamer Basar[5] show that the hardness is also because of the structure of the performance index and the coupling of different decision variables.
It has also been shown that problems of the spirit of Witsenhausen's counterexample become simpler if the transmission delay along an external channel that connects the controllers is smaller than the propagation delay in the problem.
However, this result requires the channels to be perfect and instantaneous,[6] and hence is of limited applicability.
A justification of the failure of attempts that discretize the problem came from the computer science literature: Christos Papadimitriou and John Tsitsiklis showed that the discrete version of the counterexample is NP-complete.
[7] A number of numerical attempts have been made to solve the counterexample.
, researchers have obtained strategies by discretization and using neural networks.
[8] Further research (notably, the work of Yu-Chi Ho,[9] and the work of Li, Marden and Shamma[10]) has obtained slightly improved costs for the same parameter choice.
The best known numerical results for a variety of parameters, including the one mentioned previously, are obtained by a local search algorithm proposed by S.-H. Tseng and A. Tang in 2017.
[11] The first provably approximately optimal strategies appeared in 2010 (Grover, Park, Sahai) [12] where information theory is used to understand the communication in the counterexample.
The optimal solution of the counterexample is still an open problem.