A constant-factor approximately optimal solution to the Witsenhausen counterexample
Se Yong Park, Pulkit Grover, Anant Sahai · 2009
Despite its simplicity (two controllers and otherwise LQG), Witsenhausen's counterexample is one of the long-standing open problems in stochastic distributed control. Recently, it was proved that an asymptotic vector ¿relaxation¿ can be solved to within a constant factor of the optimal cost. A parallel result is shown here for the original scalar problem. Between linear strategies and explicit-signalling-based nonlinear strategies, the optimal performance can be obtained to within a constant factor that is uniformly bounded regardless of the problem parameters. The key contribution is a new lower bound that is much tighter than Witsenhausen's bound for some parameter values.