PreprintarXiv licencearXiv
The Exact Boundary of Linear Optimality in Witsenhausen's Counterexample
Abstract
Witsenhausen's counterexample has resisted a closed form solution for decades. However, it has remained unknown whether a mathematically tractable representation exists or not. In this paper, we solve this open problem, showing that the optimal policies are either linear or not tame and characterizing the exact regions where the two properties hold. Moreover, in the linear optimal region, we give an essentially unique closed form solution for the optimal policy, and show that no optimal first-stage policy is definable in any o-minimal expansion of the ordered real field in the nonlinear optimal region.
Related
- From Optimal Transport to Optimal Quantization: A Variational Study of the Witsenhausen Counterexample
- Optimality and Exact Moment-SDP Formulations for Robust Two-Stage Convex Polynomial Multiobjective Optimization
- A Riemannian Extension of a Quadrature Surface Free Boundary Problem: Stability and Optimality
- Optimality of Affine Policies in Distributionally Robust Linear-Quadratic Control with Temporally Correlated Noise
- Exact Bayes Regret and Asymptotic Optimality in High-Dimensional Gaussian Bandits
BibTeX
@misc{lu2026exact,
title = {{The Exact Boundary of Linear Optimality in Witsenhausen's Counterexample}},
author = {Yikai Lu and Tongxin Li},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.25853},
eprint = {2610.25853},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.25853},
}
RIS
TY - UNPB
TI - The Exact Boundary of Linear Optimality in Witsenhausen's Counterexample
AU - Yikai Lu
AU - Tongxin Li
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.25853
UR - https://arxiv.org/abs/2610.25853
AB - Witsenhausen's counterexample has resisted a closed form solution for decades. However, it has remained unknown whether a mathematically tractable representation exists or not. In this paper, we solve this open problem, showing that the optimal policies are either linear or not tame and characterizing the exact regions where the two properties hold. Moreover, in the linear optimal region, we give an essentially unique closed form solution for the optimal policy, and show that no optimal first-stage policy is definable in any o-minimal expansion of the ordered real field in the nonlinear optimal region.
ER -