Witsenhausen Counterexample: Optimal Strategy and Cost

Witsenhausen Counterexample: Optimal Strategy and Cost

Definitions and mathematical statement

Fix the usual parameters $k>0$ and $\sigma>0$. Let $X_0\sim N(0,\sigma^2)$ and $V\sim N(0,1)$ be independent. The first decision maker chooses $U_1=\gamma_1(X_0)$, after which \[ X_1=X_0+U_1,\qquad Z_2=X_1+V. \] The second chooses $U_2=\gamma_2(Z_2)$ and $X_2=X_1+U_2$. Over measurable strategies with finite expected cost, determine the exact infimum and optimal strategies for \[ J^*(k,\sigma)=\inf_{\gamma_1,\gamma_2} {\mathbb{E}}\left[k\gamma_1(X_0)^2+ (X_0+\gamma_1(X_0)+\gamma_2(Z_2))^2\right]. \] The first control changes what the second decision maker observes; this information structure is the essential constraint. Arbitrary nonlinear strategies are allowed. The catalogue uses $kU_1^2$, not the common alternative notation $k^2U_1^2$; changing that convention requires reparametrizing $k$.

Formulation and concept references: [S1].

Short English statement

What are the exact optimal nonlinear policies and minimum expected cost in Witsenhausen's two-stage control problem with its specified information structure?

Research attempt

Scope and source check.

This attempt by GPT-6 Astra Ultra was prepared on 27 September 2026. Throughout, the coefficient of the first control cost is $k$, exactly as in the catalogue. A source using $k_0^2U_1^2$ corresponds to $k=k_0^2$. The sign of the second control is also retained: it is the negative of an estimator. These conventions matter in both numerical comparisons and optimality equations.

The historical slide [S1] illustrates nonlinear signalling. Park, Grover, and Sahai [E1] give a uniform constant-factor approximation, which is different from the exact optimum requested here. The recent manuscript [E2] uses a transport formulation and studies stationarity and numerical quantization. The reduction below is proved directly; none of its additional regularity or asymptotic claims is needed. In particular, this attempt does not identify a minimizing law for every pair of parameters. The concrete progress consists of an exact one-controller reduction, a rigorous separation from every affine policy at one parameter pair, and a universal scalar lower bound.

Lemma 488.1: eliminate the second controller exactly.

Write $X=X_0$, $g(x)=x+\gamma_1(x)$, $S=g(X)$, and $Y=S+V$. Finite first-stage cost implies $S\in L^2$. Let $m(Y)=\mathbb E[S\mid Y]$. For every admissible second controller $h$, orthogonal projection gives \begin{equation}\label{wsref-0-61-34-38-38-3a-70-72-6f-6a-65-63-74-69-6f-6e} \mathbb E(S+h(Y))^2 =\mathbb E(S-m(Y))^2+\mathbb E(m(Y)+h(Y))^2. \end{equation} Indeed, the cross term has conditional expectation zero given $Y$. If the left side is finite, $h(Y)\in L^2$ by the triangle inequality; therefore the calculation covers all finite-cost competitors. The unique best second action, up to observation-null sets, is $h=-m$.

For $\phi(t)=(2\pi)^{-1/2}e^{-t^2/2}$ and $\phi_\sigma(x)=\sigma^{-1}\phi(x/\sigma)$, a version is \begin{equation}\label{wsref-0-61-34-38-38-3a-70-6f-73-74-65-72-69-6f-72} m_g(y)= \frac{\int_{\mathbb R}g(x)\phi(y-g(x))\phi_\sigma(x)\,dx} {\int_{\mathbb R}\phi(y-g(x))\phi_\sigma(x)\,dx}. \end{equation} The denominator is strictly positive. The numerator is finite since $\phi$ is bounded and $\mathbb E|S|<\infty$. Thus the exact target is \begin{equation}\label{wsref-0-61-34-38-38-3a-72-65-64-75-63-65-64} J^*(k,\sigma)=\inf_{g:\,\mathbb E(g(X)-X)^2<\infty} \left\{k\mathbb E(g(X)-X)^2+ \mathbb E(S-m_g(S+V))^2\right\}. \end{equation} This is a variational reformulation, not an evaluation of the infimum. It removes one information constraint while leaving a nonlinear functional of $g$ through the full observation distribution.

A useful normalization that does not assume oddness.

Replacing $S$ by $S+c$ leaves its estimation error unchanged: translate the observation and then translate the posterior mean. Meanwhile \[ \mathbb E(S+c-X)^2 =\mathbb E(S-X)^2+2c\mathbb E(S-X)+c^2. \] Choosing $c=-\mathbb E(S-X)$ cannot increase the objective. Hence the infimum may be restricted to $\mathbb ES=0$. This argument does not show that $g$ is odd, or that an optimizer is a uniform quantizer. Symmetry of the Gaussian input makes reflection a symmetry of the problem, but averaging two reflected policies changes their signalling distributions. Convexity needed to justify that averaging is not available here.

Lemma 488.2: an exact optimization over output laws.

Let $\mu=N(0,\sigma^2)$ and let $\nu$ range over probability laws on $\mathbb R$ with finite second moment. Define \[ W_2^2(\mu,\nu)=\inf\mathbb E(A-B)^2, \qquad A\sim\mu,\ B\sim\nu, \] where the infimum ranges over couplings. Let $D(\nu)=\mathbb E(S-\mathbb E[S\mid S+V])^2$ for $S\sim\nu$ independent of $V$. Then \begin{equation}\label{wsref-0-61-34-38-38-3a-74-72-61-6e-73-70-6f-72-74} J^*(k,\sigma)=\inf_{\nu}\{kW_2^2(\mu,\nu)+D(\nu)\}. \end{equation} For a fixed law $\nu$, the estimation term depends only on that law. The least transport cost is attained by the increasing quantile map \[ T_\nu(x)=F_\nu^{-1}(F_\mu(x)),\qquad F_\nu^{-1}(u)=\inf\{t:F_\nu(t)\ge u\}. \] Here $F_\mu(X)$ is uniform on $(0,1)$, so this is a deterministic admissible controller even when $\nu$ has atoms.

For completeness, the optimal-coupling fact follows by maximizing $\mathbb E(AB)$ with fixed marginals. For bounded nonnegative variables, the layer-cake identity expresses that expectation as \[ \int_0^\infty\!\int_0^\infty \mathbb P(A>s,B>t)\,ds\,dt. \] Each integrand is at most the smaller marginal tail probability. The common-uniform quantile coupling attains all these bounds simultaneously because its upper-tail events are nested intervals in $(0,1)$. Translating bounded variables makes them nonnegative without changing which coupling maximizes the product. Truncation and $L^2$ convergence extend the result to arbitrary finite second moments. Expanding $(A-B)^2$ proves the claim.

Consequently one may restrict to nondecreasing $g$ without increasing the infimum. This is more informative than merely centering $g$, but it does not determine $\nu$: smooth, atomic, and mixed laws are still competitors. We make no assertion here that a minimizing law must have any one of these forms. Equation (a488:transport) agrees with the type of reformulation in [E2], with the parameter conversion already specified.

Lemma 488.3: the affine benchmark is a one-variable problem.

Take $g(x)=\alpha x+b$. Gaussian conditioning gives \[ m_g(y)=b+\frac{\alpha^2\sigma^2}{1+\alpha^2\sigma^2}(y-b), \qquad D=\frac{\alpha^2\sigma^2}{1+\alpha^2\sigma^2}. \] Hence the best cost with affine first control, even allowing an arbitrary second controller, is \begin{equation}\label{wsref-0-61-34-38-38-3a-61-66-66-69-6e-65} J_{\rm aff}(k,\sigma) =\min_{0\le\alpha\le1} \left\{k\sigma^2(\alpha-1)^2+ \frac{\alpha^2\sigma^2}{1+\alpha^2\sigma^2}\right\}. \end{equation} The optimum has $b=0$. Replacing $\alpha<0$ by $|\alpha|$ lowers the first term and preserves the second; replacing $\alpha>1$ by $1$ lowers both. Endpoints have derivative of opposite nonzero signs, so an optimum lies in $(0,1)$ and satisfies \begin{equation}\label{wsref-0-61-34-38-38-3a-71-75-69-6e-74-69-63} k(\alpha-1)(1+\sigma^2\alpha^2)^2+\alpha=0. \end{equation} There may be several stationary roots. Solving one root or initializing near $\alpha=1$ is insufficient; every admissible root must be compared. The trivial policies also give the universal upper bound \[ J^*(k,\sigma)\le\min\{k\sigma^2,\sigma^2/(1+\sigma^2)\}. \]

Proposition 488.4: a certified nonlinear improvement.

For $a>0$, choose $g(x)=a\operatorname{sgn}(x)$ and $h(y)=-a\operatorname{sgn}(y)$; values at zero do not matter. Let $Q(a)=\int_a^\infty\phi(t)\,dt$. Direct calculation gives \begin{equation}\label{wsref-0-61-34-38-38-3a-73-69-67-6e-63-6f-73-74} J_{\rm sign}(a)=k\left(\sigma^2+a^2-2a\sigma\sqrt{2/\pi}\right) +4a^2Q(a). \end{equation} The first identity uses $\mathbb E|X|=\sigma\sqrt{2/\pi}$. Conditional on $S=a$, the decoder is wrong exactly when $V<-a$; the other sign is symmetric. An error has squared residual $4a^2$. This also proves finiteness of the policy cost.

Set $k=1/25$, $\sigma=5$, and $a=4$. Every affine first policy has cost at least $9/16$. In fact, for $\alpha\le1/4$ its first term $(\alpha-1)^2$ is at least $9/16$, while for $\alpha\ge1/4$ its second term is at least $25/41>9/16$. An intercept only adds cost. On the other hand, \[ J_{\rm sign}(4)=\frac{41}{25}-\frac85\sqrt{2/\pi}+64Q(4) <\frac38. \] Here is a rationally checkable bound, independent of numerical quadrature. Since $\pi<22/7$, one has $\sqrt{2/\pi}>797/1000$. For $a>0$, \[ Q(a)\le\frac1a\int_a^\infty t\phi(t)\,dt =\frac{e^{-a^2/2}}{a\sqrt{2\pi}}. \] The finite sum $\sum_{j=0}^{14}8^j/j!>2900$ and $\sqrt{2\pi}>2$ give $64Q(4)<8/2900$. Finally \[ \frac{41}{25}-\frac85\frac{797}{1000}+\frac8{2900}<\frac38. \] Thus $J^*(1/25,5)<3/8<9/16\le J_{\rm aff}(1/25,5)$. This rederives the basic nonlinear advantage with deliberately loose, transparent constants. It does not claim that the two-level policy is globally optimal or that these are the best known bounds.

The best decoder for this same two-level encoder improves the bound: Bayes' rule gives $m(y)=a\tanh(ay)$ and posterior variance $a^2\operatorname{sech}^2(ay)$. The hard sign decoder is useful because its performance is especially easy to certify; optimizing the decoder does not certify the encoder.

Lemma 488.5: a lower bound that holds for every measurable policy.

Let $P=\mathbb E(S-X)^2$ and let $D=D(\mathcal L(S))$. Then \begin{equation}\label{wsref-0-61-34-38-38-3a-6c-6f-77-65-72} J^*(k,\sigma)\ge\inf_{P\ge0} \left\{kP+ \left(\frac{\sigma}{\sqrt{1+(\sigma+\sqrt P)^2}}-\sqrt P\right)_+^2 \right\},\qquad r_+=\max\{r,0\}. \end{equation} To prove this, $\mathbb ES^2\le(\sigma+\sqrt P)^2$ by the $L^2$ triangle inequality. For the additive Gaussian channel, with information measured in natural logarithms, \[ I(X;Y)=I(S;Y)\le\tfrac12\log(1+\operatorname{Var}S) \le\tfrac12\log(1+(\sigma+\sqrt P)^2). \] The equality follows since $S$ is a function of $X$ and the conditional law of $Y$ given $X$ depends only on $S$. The upper bound follows by maximizing entropy at fixed variance: $h(Y)\le\frac12\log(2\pi e \operatorname{Var}Y)$ and $h(Y\mid X)=\frac12\log(2\pi e)$.

For any square-integrable estimator $\widehat X(Y)$ of the Gaussian variable $X$, conditional entropy and the same variance bound imply \[ I(X;Y)\ge\tfrac12\log \frac{\sigma^2}{\mathbb E(X-\widehat X(Y))^2}. \] Indeed $h(X\mid Y)=h(X-\widehat X(Y)\mid Y)$ is at most the entropy of the error, and that entropy is bounded by its second moment. The entropy inequalities can equivalently be expressed using nonnegative relative entropy; degenerate cases follow by regularization. Applying the result to $\widehat X=m(Y)$ and then using \[ \|X-m(Y)\|_2\le\|X-S\|_2+\|S-m(Y)\|_2=\sqrt P+\sqrt D \] proves (a488:lower). The expression on the right is strictly positive for fixed $k,\sigma>0$: it is continuous, tends to infinity as $P\to\infty$, and can vanish only if $P=0$, where its second term is $\sigma^2/(1+\sigma^2)>0$.

This bound is not asserted to improve the literature. Its purpose is to show precisely where a universal estimate loses information. It replaces the actual output law by a variance bound and treats the two errors in a triangle inequality. Their equality conditions need not coexist with an optimal signalling policy. A positive lower bound and a good quantizer upper bound leave an interval; they do not determine its exact value.

Attempt to close the gap by alternating best responses.

For a fixed decoder $h$, the first-controller objective is pointwise in $x$: \[ H_x(t)=k(t-x)^2+\int_{\mathbb R}(t+h(t+v))^2\phi(v)\,dv. \] If $h$ is bounded and continuous, this is continuous and coercive in $t$, and a measurable choice of minimizer gives a best first response. The measurability follows, for example, by taking the smallest minimizer: compact sublevel sets and continuity allow its level sets to be tested with infima over rational intervals. The selected response has finite expected cost, since $H_x(t_{\min})\leq H_x(x)\leq (|x|+\|h\|_\infty)^2$, which is integrable under the Gaussian prior. Under differentiability and domination sufficient to differentiate under the integral, an interior stationary response satisfies \begin{equation}\label{wsref-0-61-34-38-38-3a-66-69-72-73-74-72-65-73-70-6f-6e-73-65} k(t-x)+\mathbb E[(t+h(t+V))(1+h'(t+V))]=0. \end{equation} The bounded-continuous argument covers the posterior decoder of the two-level policy. It is not an existence proof for best responses to every arbitrary measurable decoder.

Alternating (a488:posterior) with minimization of $H_x$ makes a useful search method. A fixed point, even one using global minimization in each coordinate separately, need not minimize jointly. The elementary function \[ F(s,t)=(st-1)^2+\varepsilon(s^2+t^2),\qquad0<\varepsilon<1/2, \] has $(0,0)$ as a pair of global coordinate best responses, with value $1$, while $F(1,1)=2\varepsilon<1$. This is a diagnostic of the logical implication, not a counterexample policy for this control problem. No convexity theorem has been proved here that excludes such a failure for the reduced Witsenhausen functional.

Verification and exact remaining obligation.

The displayed nonlinear separation was checked with rational arithmetic for the finite exponential sum and the two final comparisons; floating point values are unnecessary to its proof. The posterior, affine, and transport reductions are symbolic arguments, not results of a finite search. The information lower bound is uniform over admissible policies. None of these checks explores all output laws or establishes global optimality of a numerical stationary point.

UNRESOLVED. To finish the catalogue problem one must identify, for arbitrary $k,\sigma>0$, a law or policy attaining a value that a matching lower bound proves minimal. The exact reductions and the proved nonlinear-versus-affine separation do not supply that matching certificate. No general solution or novelty claim is made.

Sources

• S1 Formal statement, Lecture 4 slide, 'Witsenhausen Problem $1968$'. https://people.seas.harvard.edu/~ho/DEDS/OO/Lecture4/Slide01.html. Formulation source.
• E1 Se Yong Park, Pulkit Grover, and Anant Sahai, A constant-factor approximately optimal solution to the Witsenhausen Counterexample, author-hosted manuscript, Theorem 1. https://people.eecs.berkeley.edu/~sahai/Papers/CDC09Submission.pdf. Uses the coefficient $k^2$; cited for approximation context, not an exact optimum.
• E2 Quanyan Zhu, From Optimal Transport to Optimal Quantization: A Variational Study of the Witsenhausen Counterexample, arXiv:2609.18992v1, accessed 27 September 2026. https://arxiv.org/abs/2609.18992v1. The transport formulation is rederived here; additional manuscript claims are not used as established premises.