Consider the problem of distributed controllers sequentially maneuvering a system to a desired state. In 1968, Witsenhausen constructed an example to show that even seemingly simple abstractions of this problem can be hard. The problem, now famous as the Witsenhausen counterexample, has been unsolved for more than 40 years, requiring researchers to search in the entire function space in order to find good control strategies. In this talk, we will see how tools from information theory can be used to provide the first provably approximately optimal solution to Witsenhausen's counterexample and some other related problems. 

In order to simplify the counterexample, we first formulate an asymptotically infinite-length vector extension of the problem. Lower bounds on the control cost are obtained for this vector extension using ideas from lossy transmission of a source across a channel. Upper bounds are obtained using  dirty-paper coding based strategies. Using these bounds, we characterize the asymptotic optimal cost to within a factor of 1.3 for all problem parameters. 

To address the original scalar problem (and the finite-length extensions), we use a sphere-packing analysis to obtain a tighter lower bound for any finite vector length. Lattice-based quantization techniques are then shown to attain within a constant factor of the optimal cost uniformly over all vector lengths. For the original counterexample, this constant factor is shown to be smaller than 8.

Similar constant factor results are obtained for extensions of the counterexample with costs on all states and inputs, and noise in all observations and state evolutions.