Exact optimal control in the scalar Witsenhausen benchmark
Let $X_0 \sim N(0, 25)$ and $Z \sim N(0, 1)$ be independent. A first controller observes $X_0$ and applies $U_1 = f(X_0)$; a second controller observes only $Y = X_0 + U_1 + Z$ and applies $U_2 = g(Y)$. For Borel functions $f, g : \mathbb{R} \to \mathbb{R}$ of finite cost let $$J_* = \inf_{f, g} \mathbb{E}\left[ 0.04\, f(X_0)^2 + \bigl( X_0 + f(X_0) - g(X_0 + f(X_0) + Z) \bigr)^2 \right].$$ This is Witsenhausen's counterexample with $k = 0.2$ and $\sigma = 5$, that is, cost $k^2 \mathbb{E}[U_1^2] + \mathbb{E}[(X_0 + U_1 - U_2)^2]$ with $X_0 \sim N(0, \sigma^2)$. For a fixed $f$ the best $g$ is the conditional mean $g(y) = \mathbb{E}[X_0 + f(X_0) \mid Y = y]$. Witsenhausen proved that an optimal pair exists, and that for $k = 1/\sigma$ with $\sigma$ large enough some nonlinear pair has smaller cost than every affine pair. Wu and Verdú proved that for every optimal pair the map $x \mapsto x + f(x)$ is strictly increasing, unbounded and piecewise real analytic, with a real analytic left inverse (2011).
Problem. Determine the exact value of $J_*$ and an optimal pair $(f, g)$, with a proof of global optimality over all Borel pairs of finite cost. A stationarity condition, or numerical optimization over a chosen family of functions, does not suffice.
Source: Witsenhausen (1968). Stated by AIM — Open Applied Problems at k = 0.2, σ = 5, the parameters of the standard numerical benchmark (used, e.g., by Lee, Lau and Ho, 2001).
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- OC — Optimization and Control
- Secondary
- IT, PR
- Keywords
- AIM Open Applied Problems, team decision problems, Witsenhausen's counterexample
References
@article{witsenhausen1968,
author = {Witsenhausen, H. S.},
title = {A counterexample in stochastic optimum control},
journal = {SIAM J. Control},
volume = {6},
number = {1},
year = {1968},
pages = {131--147},
doi = {10.1137/0306011},
}
@inproceedings{wu2011,
author = {Wu, Yihong and Verd{\'u}, Sergio},
title = {Witsenhausen's counterexample: a view from optimal transport theory},
booktitle = {Proceedings of the 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC)},
address = {Orlando, FL},
year = {2011},
pages = {5732--5737},
doi = {10.1109/CDC.2011.6160829},
}
@article{lee2001,
author = {Lee, Jonathan T. and Lau, Edward and Ho, Yu-Chi},
title = {The {W}itsenhausen counterexample: a hierarchical search approach for nonconvex optimization problems},
journal = {IEEE Trans. Automat. Control},
volume = {46},
number = {3},
year = {2001},
pages = {382--397},
doi = {10.1109/9.911416},
}
@misc{aim-witsenhausen-exact-optimum,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Exact optimal control in the scalar Witsenhausen benchmark}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/134-witsenhausen-exact-optimum.md},
note = {Entry 134 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00570, "Exact optimal control in the scalar Witsenhausen benchmark", clopen.solutions.