# Optimal Gaussian Strategies for Vector-valued Witsenhausen Counterexample with Non-causal State Estimator

Mengyuan Zhao, Tobias Oechtering, Maël Le Treust

► To cite this version:

Mengyuan Zhao, Tobias Oechtering, Maël Le Treust. Optimal Gaussian Strategies for Vector-valued Witsenhausen Counterexample with Non-causal State Estimator. CDC 2024 - 63rd IEEE Conference on Decision and Control, Dec 2024, Milano, Italy. pp.1-6. hal-04863317

HAL Id: hal-04863317

https://hal.science/hal-04863317v1

Submitted on 3 Jan 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Optimal Gaussian Strategies for Vector-valued Witsenhausen Counterexample with Non-causal State Estimator

Mengyuan Zhao<fnref n="1" />, Tobias J. Oechtering<fnref n="1" /> and Maël Le Treust<fnref n="2" />

**Abstract**— In this study, we investigate a vector-valued Witsenhausen model where the second decision maker (DM) acquires a vector of observations before selecting a vector of estimations. Here, the first DM acts causally whereas the second DM estimates non-causally. When the vector length grows, we characterize, via a single-letter expression, the optimal trade-off between the power cost at the first DM and the estimation cost at the second DM. In this paper, we show that the best linear scheme is achieved by using the time-sharing method between two affine strategies, which coincides with the convex envelope of the solution of Witsenhausen in 1968. Here also, Witsenhausen's two-point strategy and the scheme of Grover and Sahai in 2010 where both devices operate non-causally, outperform our best linear scheme. Therefore, gains obtained with block-coding schemes are only attainable if all DMs operate non-causally.

## I. INTRODUCTION

In 1968, Witsenhausen proposed his celebrated counterexample [1] showing that the optimal control law of the Linear-Quadratic-Gaussian (LQG) problem is not linear when the information pattern is nonclassical. Nowadays, it still serves as an important toy example in distributed decision-making field [2]–[5] and information-theoretic control [6]–[13].

Despite the simplicity of Witsenhausen counterexample, finding its globally optimal strategy and optimal cost remains an open problem. To understand the difficulty, we consider a decentralized stochastic decision problem where the first DM knows the state of the system perfectly but has a power cost. The second DM estimates the interim state from a noisy observation which causes an estimation cost. Thus, the first DM aims to serve two purposes of control, steer the state at low cost as well as enable effective state estimation (dual role of control). Numerous studies over the last decades have aimed to enhance understanding and propose solutions using approaches such as numerical optimization [14, 15], neural networks [16], hierarchical search [17], learning [18], and optimal transport [19].

Motivated by the vector-valued extension of the counterexample formulated in [20], advanced coding schemes using methods from information theory provide new insights. For example, [20] established a lowerbound where both the DMs have non-causal access to the entire sequences of observation employing block-coding. Additionally, [21]

obtained a lattice-based optimal solution for finite-length vector case. The vector-valued approaches simplify the characterization of fundamental bounds in the limit of large vector lengths, additionally facilitating performance gains from block-coding through non-causal operations.

However, it remained open whether causal control schemes also could offer any advantage or even surpass the performance of Witsenhausen's two-point strategy. In [22], the optimal Gaussian cost for the Witsenhausen problem is under study where the first DM is non-causal and the second DM is causal. This optimal Gaussian cost was achieved through a so-called *time-sharing* strategy, which convexifies the linear cost region by utilizing two operational points. In this paper, we flip the causality property to explore the optimal Gaussian cost for the scenario where the first DM acts causally while the second DM acts non-causally. To this end, we employ the theoretical result of the characterization of the achievable Witsenhausen cost region and the information constraints derived in [23]. Despite differences with the cost region of [22], both frameworks end up to have the same optimal Gaussian cost. Moreover, we uncover the remarkable finding that across five vector-valued Witsenhausen problem setups that feature at least one causal controller, there exists an identical optimal Gaussian cost outcome, regardless of the presence of any feedback or feed-forward information [24]. Surprisingly, this optimal vector-valued Gaussian cost featuring causal DMs is again outperformed by Witsenhausen's two-point strategy [1] and the non-causal strategy by Grover and Sahai [20].

This paper is structured as follows: Section II introduces the model of causal encoding and noncausal decoding. The main result of the optimal Gaussian cost, a lemma determining the relation of Gaussian covariance coefficients given Markov chains and a corollary implied by the main result are presented in Section III. Section IV discusses the numerical results and the theorem's implications which serve as our main contribution. The proofs of the main theorem, supportive lemmas and corollary are shown in Appendix.

## II. SYSTEM MODEL

In this section, we introduce the setup and recapitulate some foundational results to our problem. Throughout this paper, capital letters, e.g. $X_0$ denote random variables while lowercase letters, e.g. $x_0$ denote realisations. The notation $X_0^n$ denotes a random vector of length $n \in \mathbb{N}$, $X_{0,t}$ denotes the $t$-th entry of $X_0^n$, and $X_0^t = (X_{0,1}, \dots, X_{0,t})$ represents the segment of $X_0^n$ up to stage $t$, where $t \in \{1, \dots, n\}$.

<footnote>This work was supported by Swedish Research Council (VR) under grant 2020-03884.</footnote>

<footnote n="1">¹M. Zhao and T. J. Oechtering are with the Division of Information Science and Engineering, KTH Royal Institute of Technology, 100 44 Stockholm, Sweden {mzhao, oech}@kth.se</footnote>

<footnote n="2">²M. Le Treust is with CNRS, Inria, IRISA UMR 6074, University of Rennes, F-35000 Rennes, France mael.le-treust@cnrs.fr</footnote>
<figure><img src="image_2.png" /><figcaption>Fig. 1. The i.i.d. state and the channel noise are drawn according to Gaussian distributions $X_0^n \sim \mathcal{N}(0, Q\mathbb{I})$ and $Z_1^n \sim \mathcal{N}(0, N\mathbb{I})$.</figcaption></figure>

Let's consider the vector-valued Witsenhausen counterexample setup with causal source states and channel noises that are drawn independently according to the i.i.d. Gaussian distributions $X_0^n \sim \mathcal{N}(0, Q\mathbb{I})$ and $Z_1^n \sim \mathcal{N}(0, N\mathbb{I})$, for some $Q, N \in \mathbb{R}^+$, where $\mathbb{I}$ is the identity matrix, see Figure II. We denote by $X_1$ the memoryless interim state and $Y_1$ the output of the memoryless additive channel, generated by

$$X_1 = X_0 + U_1 \quad \text{with } X_0 \sim \mathcal{N}(0, Q), \quad (1)$$

$$Y_1 = X_1 + Z_1 = X_0 + U_1 + Z_1 \quad \text{with } Z_1 \sim \mathcal{N}(0, N). \quad (2)$$

We denote by $\mathcal{P}_{X_0} = \mathcal{N}(0, Q)$ the generative Gaussian probability distribution of the state, and by $\mathcal{P}_{X_1, Y_1|X_0, U_1}$ the channel probability distribution according to (1) and (2).

**Definition II.1.** For $n \in \mathbb{N}$, a "control design" with causal encoder and noncausal decoder is a tuple of conditional distributions $c = (\{f_{U_{1,t}|X_0}^{(t)}\}_{t=1}^n, g_{U_2^n|Y_1^n})$, where at time instant $t \in \{1, ..., n\}$, $f_{U_{1,t}|X_0}^{(t)}$ selects a channel input $U_{1,t}$ based on the past source sequence $X_0^t$ up to $t$, while $g_{U_2^n|Y_1^n}$ selects the whole estimation sequence $U_2^n$ based on the whole channel output sequence $Y_1^n$. This induces a distribution over sequences of symbols:

$$\prod_{t=1}^{n} \mathcal{P}_{X_{0,t}} \times \prod_{t=1}^{n} f_{U_{1,t}|X_0}^{(t)} \times \prod_{t=1}^{n} \mathcal{P}_{X_{1,t}, Y_{1,t}|X_{0,t}, U_{1,t}} \times g_{U_2^n|Y_1^n},$$

We denote by $C_e(n)$ the set of control designs with causal encoder and non-causal decoder.

We evaluate the power cost and the estimation cost by considering their respective average over the sequences of symbols.

**Definition II.2.** We define the two n-stage cost functions $c_P(u_1^n) = \frac{1}{n} \sum_{t=1}^n (u_{1,t})^2$ and $c_S(x_1^n, u_2^n) = \frac{1}{n} \sum_{t=1}^n (x_{1,t} - u_{2,t})^2$. The pair of costs $(P, S) \in \mathbb{R}^2$ is achievable if for all $\varepsilon > 0$, there exists $\bar{n} \in \mathbb{N}$ such that for all $n \ge \bar{n}$, there exists a control design $c \in C_e(n)$ such that

$$\mathbb{E}[|P - c_P(U_1^n)| + |S - c_S(X_1^n, U_2^n)|] \le \varepsilon.$$

The optimal achievable pairs of costs $(P, S) \in \mathbb{R}^2$, which we refer to as the Witsenhausen cost, are characterized in the following theorem.

**Theorem II.3** ([23, Theorem I]). The pair of Witsenhausen costs $(P, S)$ is achievable if and only if there exists a joint distribution over the random variables

$(X_0, W_1, W_2, U_1, X_1, Y_1, U_2)$ that decomposes according to
$$\mathcal{P}_{X_0} \mathcal{P}_{W_1} \mathcal{P}_{W_2|X_0, W_1} \mathcal{P}_{U_1|X_0, W_1} \mathcal{P}_{X_1, Y_1|X_0, U_1} \mathcal{P}_{U_2|W_1, W_2, Y_1}, \quad (3)$$

such that

$$I(W_1, W_2; Y_1) - I(W_2; X_0|W_1) \ge 0, \quad (4)$$

$$P = \mathbb{E}[U_1^2], \quad S = \mathbb{E}[(X_1 - U_2)^2], \quad (5)$$

where $\mathcal{P}_{X_0}$ and $\mathcal{P}_{X_1, Y_1|X_0, U_1}$ are the given Gaussian distributions, $W_1, W_2$ are two auxiliary random variables, and where the mutual information $I(W_1, W_2; Y_1)$ is the Kullback-Leibler divergence between the joint distribution $\mathcal{P}_{W_1, W_2, Y_1}$ and the product of the marginal distributions $\mathcal{P}_{W_1, W_2} \mathcal{P}_{Y_1}$.

Condition (4) characterizes the feasibility set of the Witsenhausen costs. The auxiliary random variables $W_1, W_2$ are introduced specifically for forming the single-letter solutions (3) and (4). They have operational meanings: $W_1$ is used for codewords adapted to the channel assisting a reliable communication, and $W_2$ is used for a description of the compressed source states. Therefore, the dual role of control is explicitly captured by the two auxiliary random variables. Since the region characterized above is optimal, $W_1, W_2$ also provide all freedom for the optimization process.

**Remark II.4.** The following Markov chains follow from the joint probability distribution (3):

$$\left\{
\begin{array}{l}
X_0 \text{ is independent of } W_1, \\
U_1 \leftarrow (X_0, W_1) \leftarrow W_2, \\
(X_1, Y_1) \leftarrow (X_0, U_1) \leftarrow (W_1, W_2), \\
U_2 \leftarrow (W_1, W_2, Y_1) \leftarrow (X_0, U_1, X_1).
\end{array}
\right.
\quad (6)$$

The first two Markov chains are consequences of causal encoding. The third Markov chain is related to the processing order of the Gaussian channel. The last Markov chain comes from the non-causal decoding and the symbol-wise reconstruction. These Markov chains play a crucial role in the proof of the main theorem.

### III. OPTIMAL GAUSSIAN COST

In the following, we fix a power cost $P \ge 0$ and investigate the optimal estimation cost at the decoder obtained from using Gaussian random variables.

**Definition III.1.** Given a power cost parameter $P \ge 0$, we define the estimation cost obtained by jointly Gaussian random variables to be

$$S_G(P) = \inf_{\mathcal{P} \in \mathcal{P}(P)} \mathbb{E}[(X_1 - U_2)^2], \quad (7)$$

$$\mathbb{P}(P) = \begin{cases} (\mathcal{P}_{W_1}, \mathcal{P}_{W_2|X_0, W_1}, \mathcal{P}_{U_1|X_0, W_1}, \mathcal{P}_{U_2|W_1, W_2, Y_1}), \\ \text{s.t. } P = \mathbb{E}[U_1^2], \ I(W_1, W_2; Y_1) - I(W_2; X_0|W_1) \ge 0, \\ X_0, W_1, W_2, U_1, X_1, Y_1, U_2 \text{ are jointly Gaussian} \end{cases}. \quad (8)$$

The set $\mathbb{P}(P)$ denotes the optimization domain.

Note that the minimum mean-squared error (MMSE) estimation for the decoder is given by the conditional expectation. We have the following proposition.
**Proposition III.2.** Given a power cost parameter $P \ge 0$, the estimation cost $S_G(P)$ satisfies

$$S_G(P) = \inf_{P \in \mathbb{P}_G(P)} \mathbb{E} \left[ \left( X_1 - \mathbb{E}[X_1|W_1, W_2, Y_1] \right)^2 \right], \quad (9)$$

$$ \mathbb{P}_G(P) = \begin{cases} (P_{W_1}, P_{W_2|X_0,W_1}, P_{U_1|X_0,W_1}) \quad \text{s.t. } P = \mathbb{E}[U_1^2], \\ I(W_1, W_2; Y_1) - I(W_2; X_0|W_1) \ge 0, \quad \text{and} \\ X_0, W_1, W_2, U_1, X_1, Y_1, U_2 \text{ are jointly Gaussian} \end{cases} \quad (10) $$

The best linear strategy below in our setting is again the same as the one in Witsenhausen's paper [1] following the same arguments.

**Lemma III.3** ([1, Lemma 11], [22, Lemma 5]). The best linear policy is $U_1 = -\sqrt{\frac{P}{Q}}X_0$, if $P \le Q$, otherwise $U_1 = -X_0 + \sqrt{P-Q}$, which induces the estimation cost

$$S_{\ell}(P) = \begin{cases} \frac{(\sqrt{Q}-\sqrt{P})^{2 \cdot N}}{(\sqrt{Q}-\sqrt{P})^{2+N}} & \text{if } P \in [0, Q], \\ 0 & \text{otherwise.} \end{cases} \quad (11)$$

The best linear cost provides an upper bound for the optimal Gaussian cost. However, the function $P \mapsto S_{\ell}(P)$ is not always convex. The best Gaussian estimation cost derived in Theorem III.4 below obtains the convex envelope of $S_{\ell}$, which coincides with the solution proposed by Witsenhausen in [1, Lemma 12] and the solution for the problem of flipped causality [22, Theorem 2].

The proofs of Theorem III.4, Lemma III.5 and Corollary III.6 stated in the following are shown in the appendix.

**Theorem III.4** (Main Result). The optimal Gaussian estimation cost for Witsenhausen problem with causal encoder and non-causal decoder is given by

$$S_G(P) = \begin{cases} \frac{N \cdot (Q-N-P)}{Q} & \text{if } Q > 4N \text{ and } P \in [P_1, P_2], \\ S_{\ell}(P) & \text{otherwise.} \end{cases} \quad (12)$$

where the parameters

$$P_1 = \frac{1}{2}(Q - 2N - \sqrt{Q^2 - 4QN}), \quad (13)$$

$$P_2 = \frac{1}{2}(Q - 2N + \sqrt{Q^2 - 4QN}). \quad (14)$$

In this theorem, $P_1$ and $P_2$ given in (13) and (14) are the two operating points for conducting the time-sharing strategy, which enables us to achieve a cost gain from the affine policy.

The following lemma states the general relation of Gaussian covariance coefficients given a Markov chain. It is a direct consequence combining several well-known results.

**Lemma III.5.** If the jointly Gaussian random vector $(X, Y, Z)$ satisfy the Markov chain $X \leftarrow Y \leftarrow Z$ and have a covariance matrix

$$\Sigma_{X,Y,Z} = \begin{pmatrix} P & \rho_1 \sqrt{PQ} & \rho_2 \sqrt{PV} \\ \rho_1 \sqrt{PQ} & Q & \rho_3 \sqrt{QV} \\ \rho_2 \sqrt{PV} & \rho_3 \sqrt{QV} & V \end{pmatrix}, \quad (15)$$

with the covariance coefficients $(\rho_1, \rho_2, \rho_3) \in [-1, 1]^3$ ensuring that $\det(\Sigma_{X,Y,Z}) \ge 0$, then, we have

$$\rho_2 = \rho_1 \rho_3. \quad (16)$$

In other words, with the context of the Markov chain of jointly Gaussian $X \leftarrow Y \leftarrow Z$, if $X$ and $Y$ (or if $Z$ and $Y$) are uncorrelated (i.e., if $\rho_1 = 0$ or $\rho_3 = 0$), it follows that $X$ and $Z$ are also uncorrelated (i.e., $\rho_2 = 0$).

**Corollary III.6.** The problem for causal encoder and non-causal decoder with channel feedback (i.e., channel output $Y_1$ is available to the first DM) has the same cost result (12).

The cost region characterization of this setup is investigated in [24, Sec. C]. From Corollary III.6, we get that having channel feedback information to assist communication does not contribute to any performance gain in the Gaussian case.

Next, we recall Witsenhausen's two-point strategy. It outperforms the best Gaussian cost (12) for some values of $Q$ and $N$.

**Theorem III.7** ([1, Sec. 6], [22, Prop. 11]). For parameter $a \ge 0$, Witsenhausen's two-point strategy is given by

$$U_1 = a \cdot \mathrm{sign}(X_0) - X_0.$$

The power and estimation costs are given by

$$ \begin{aligned} P_2(a) &= Q + a \left( a - 2\sqrt{\frac{2Q}{\pi}} \right), \\ S_2(a) &= a^2 \sqrt{\frac{2\pi}{N}} \phi \left( \frac{a}{\sqrt{N}} \right) \int \frac{\phi \left( \frac{y_1}{\sqrt{N}} \right)}{\cosh \left( \frac{ay_1}{N} \right)} dy_1, \end{aligned} \quad (17) $$

where $\phi(x) = \frac{1}{\sqrt{2\pi}}e^{-\frac{x^2}{2}}$ and the optimal receiver's strategy is given by $\mathbb{E}[X_1|Y_1 = y_1] = a \tanh(\frac{ay_1}{N})$.

## IV. DISCUSSIONS

The numerical results of the best affine cost $S_{\ell}(P)$ in (11), the optimal Gaussian cost $S_G(P)$ in (12), Witsenhausen's two-point strategy cost $S_2(P)$ in (17), and the Dirty Paper Coding (DPC) based cost for cases where both DMs are non-causal $S_{\mathrm{dpc}}(P)$ in [20, App. D.1-D.7] and [22, Eq.(47)] are illustrated in Fig 2, for the parameters $(Q, N) = (0.8, 0.1)$.

**Remark IV.1.** Now, we discuss the optimal Gaussian cost for the case where both DMs are causal.

* The optimal Gaussian strategy discussed in [22, App. B-B] is a single-letter (causal) approach, which provides a valid control strategy for a more restrictive setup assuming that the second DM is also causal. Therefore, (12) is an upper bound of this cost.

* From the genie-aided argument, a lower bound for the optimal cost is given by the optimal cost of a more superior system, such as the setup discussed in Corollary III.6. Therefore, (12) is a lower bound of the optimal cost of causal encoding and causal decoding Witsenhausen setup.

Consequently, the optimal Gaussian cost for the causal encoding and decoding setup is the same as (12).
<figure><img src="image_3.png" /><figcaption>Fig. 2. Comparison of the four cost functions $S_{\ell}(P)$, $S_{G}(P)$, $S_{2}(P)$ and $S_{dpc}(P)$. In this particular case, $S_{2}(P)$ outperforms $S_{G}(P)$ and $S_{\ell}(P)$, and the cost induced by the non-causal strategy $S_{dpc}(P)$ outperforms all other cost functions.</figcaption></figure>

**Remark IV.2.** Our discussions above lead us to a remarkable conclusion: Even though the optimal achievable cost regions are different, the optimal Gaussian costs for the following five distinct configurations are the same:

1) Causal encoding and causal decoding.

2) Causal encoding and non-causal decoding.

3) Causal encoding and non-causal decoding with channel feedback.

4) Non-causal encoding and causal decoding.

5) Non-causal encoding and causal decoding with source feedforward.

This equality is surprising since these settings all have different single-letter optimal regions, but these regions coincide if we restrict to Gaussian schemes. Therefore, block-coding gains can be obtained only if both DMs are non-causal.

APPENDIX

**Proof of the Main Result.** Without loss of generality, we consider the joint Gaussian random variables $(X_0, W_1, W_2, U_1) \sim \mathcal{N}(0, K)$ optimal for problem (9), are centered with the covariance matrix

$$K = \begin{pmatrix} Q & \rho_1 \sqrt{QV_1} & \rho_2 \sqrt{QV_2} & \rho_3 \sqrt{QP} \\ \rho_1 \sqrt{QV_1} & V_1 & \rho_4 \sqrt{V_1 V_2} & \rho_5 \sqrt{V_1 P} \\ \rho_2 \sqrt{QV_2} & \rho_4 \sqrt{V_1 V_2} & V_2 & \rho_6 \sqrt{V_2 P} \\ \rho_3 \sqrt{QP} & \rho_5 \sqrt{V_1 P} & \rho_6 \sqrt{V_2 P} & P \end{pmatrix}. \quad (18)$$

Since $X_0 \perp W_1$, $\rho_1 = 0$. Also, given the Markov chain $U_1 \leftarrow (X_0, W_1) \leftarrow W_2$, from Lemma III.5, we can obtain $\rho_6 = \rho_2\rho_3 + \rho_4\rho_5$. Moreover, other active correlation coefficients $(\rho_2, \rho_3, \rho_4, \rho_5) \in [-1, 1]^4$ are chosen such that

$$\det(K) = QV_1V_2P(-1 + \rho_2^2 + \rho_4^2)(-1 + \rho_3^2 + \rho_5^2) \ge 0.$$

Given (18) and (2), the covariance matrix $K_2$ of $(X_0, W_1, W_2, Y_1)$ could be easily computed, with a determinant given by

$$\det(K_2) = QV_1V_2(-1 + \rho_2^2 + \rho_4^2)(P(-1 + \rho_3^2 + \rho_5^2) - N).$$

The positive semi-definite property of $K_2$ must also be satisfied with properly chosen $(\rho_2, \rho_3, \rho_4, \rho_5)$.

We have the following lemma determining the explicit formulas of the information constraint (4) and the optimization object (9).

**Lemma IV.3.** Assume $(X_0, W_1, W_2, U_1) \sim \mathcal{N}(0, K)$, then

$$\begin{aligned} & I(W_1, W_2; Y_1) - I(W_2; X_0|W_1) \\ &= I(W_1; Y_1) - I(W_2; X_0|W_1, Y_1) \end{aligned} \quad (19)$$

$$= \frac{1}{2} \log \left( \frac{T_1}{T_1 - T_2} \right), \quad (20)$$

where the terms

$$T_1 = (P + Q + N + 2\rho_3\sqrt{QP})(-1 + \rho_2^2 + \rho_4^2),$$

$$T_2 = N\rho_2^2 + P\rho_2^2(1 - \rho_3^2) - P\rho_5^2(1 - \rho_4^2).$$

And the object to minimize is

$$\begin{aligned} & \mathbb{E} \left[ \left( X_1 - \mathbb{E}[X_1 | W_1, W_2, Y_1] \right)^2 \right] \\ &= \frac{N \cdot f_1(\rho_2, \rho_3, \rho_4, \rho_5)}{(1 - \rho_4^2) \cdot N + f_1(\rho_2, \rho_3, \rho_4, \rho_5)}, \end{aligned} \quad (21)$$

where $f_1(\rho_2, \rho_3, \rho_4, \rho_5) = -P\rho_2^2\rho_3^2 - (Q + 2\rho_3\sqrt{PQ})(-1 + \rho_2^2 + \rho_4^2) + P(1 - \rho_4^2)(1 - \rho_5^2)$.

**Proof of Lemma IV.3.**

$$\begin{aligned} & I(W_1, W_2; Y_1) - I(W_2; X_0|W_1) \\ &= I(W_1; Y_1) + I(W_2; Y_1|W_1) - I(W_2; X_0|W_1) \end{aligned}$$

$$\begin{aligned} & \stackrel{(a)}{=} I(W_1; Y_1) + I(W_2; Y_1|W_1) - I(W_2; X_0, Y_1|W_1) \\ &= I(W_1; Y_1) - I(W_2; X_0|W_1, Y_1) \end{aligned}$$

$$= \frac{1}{2} \log \left( \frac{\sigma_{W_1}^2 \cdot \sigma_{Y_1}^2 \cdot \det(K_2)}{\det(\Sigma_{W_1, W_2, Y_1}) \cdot \det(\Sigma_{X_0, W_1, Y_1})} \right)$$

$$= \frac{1}{2} \log \left( \frac{T_1}{T_1 - T_2} \right),$$

where (a) comes from the Markov chain $Y_1 \leftarrow (X_0, W_1) \leftarrow W_2$, and thus $I(W_2; Y_1|X_0, W_1) = 0$. Additionally,

$$\begin{aligned} & \mathbb{E} \left[ \left( X_1 - \mathbb{E}[X_1 | W_1, W_2, Y_1] \right)^2 \right] \\ &= \mathrm{Var}(X_1|W_1, W_2, Y_1) \end{aligned}$$

$$\begin{aligned} & \stackrel{(b)}{=} \sigma_{X_1}^2 - \Sigma_{X_1 W}^\top \Sigma_{W W}^{-1} \Sigma_{X_1 W} \\ &= \frac{N \cdot f_1(\rho_2, \rho_3, \rho_4, \rho_5)}{(1 - \rho_4^2) \cdot N + f_1(\rho_2, \rho_3, \rho_4, \rho_5)}, \end{aligned}$$

where step (b) is obtained using the Schur complement. Here, $W = (W_1, W_2, Y_1)^\top$, $\Sigma_{X_1 W} = (\sigma_{X_1, W_1}, \sigma_{X_1, W_2}, \sigma_{X_1, Y_1})^\top$, and $\Sigma_{W W}$ is the covariance matrix of $(W_1, W_2, Y_1)$. $\square$

Thus, given the expression of (20), we can obtain a new expression of the original information constraint

$$\frac{1}{2} \log \left( \frac{T_1}{T_1 - T_2} \right) \ge 0 \Leftrightarrow T_1 \ge T_2 \ge 0 \text{ or } T_1 \le T_2 \le 0.$$

If $1 - \rho_4^2 = 0$, from (21), we can get that

$$\mathbb{E} \left[ \left( X_1 - \mathbb{E}[X_1 | W_1, W_2, Y_1] \right)^2 \right] = N.$$
Next, we focus on the case if $1 - \rho_4^2 \neq 0$. In this case, (21) is of the form

$$ \frac{N \cdot f(\rho_2, \rho_3, \rho_4, \rho_5)}{N + f(\rho_2, \rho_3, \rho_4, \rho_5)}, \qquad (22) $$

where $f(\rho_2, \rho_3, \rho_4, \rho_5) = f_1(\rho_2, \rho_3, \rho_4, \rho_5)/(1 - \rho_4^2) = \frac{-P\rho_2^2\rho_3^2 - (Q+2\rho_3\sqrt{PQ})(-1+\rho_2^2+\rho_4^2)+P(1-\rho_4^2)(1-\rho_5^2)}{(1-\rho_4^2)}$.

Note that, the function $x \mapsto \frac{N \cdot x}{N+x}$ is nonnegative and strictly increasing over the region $(-\infty, -N] \cup [0, \infty)$. Therefore, our goal of minimizing (22) is now transformed to either minimizing the nonnegative object

$$ f(\rho_2, \rho_3, \rho_4, \rho_5) \geq 0 $$

or minimizing the negative object

$$ f(\rho_2, \rho_3, \rho_4, \rho_5) \leq -N $$

subject to the following constraints:

$$ 1. \det(K) \geq 0 \Rightarrow $$

$$ QV_1V_2P(-1 + \rho_2^2 + \rho_4^2)(-1 + \rho_3^2 + \rho_5^2) \stackrel{(A)}{\geq} 0, $$

$$ 2. \det(K_2) \geq 0 \Rightarrow $$

$$ QV_1V_2(-1 + \rho_2^2 + \rho_4^2)(P(-1 + \rho_3^2 + \rho_5^2) - N) \stackrel{(B)}{\geq} 0, $$

$$ 3. T_1 \geq T_2 \geq 0 \Rightarrow $$

$$ \begin{aligned} & (Q + P + N + 2\rho_3\sqrt{QP})(-1 + \rho_2^2 + \rho_4^2) \\ & \stackrel{(C1)}{\geq} N\rho_2^2 + P\rho_2^2(1 - \rho_3^2) - P\rho_5^2(1 - \rho_4^2) \stackrel{(D1)}{\geq} 0, \\ & \text{or, } T_1 \leq T_2 \leq 0 \Rightarrow \\ & (Q + P + N + 2\rho_3\sqrt{QP})(-1 + \rho_2^2 + \rho_4^2) \\ & \stackrel{(C2)}{\leq} N\rho_2^2 + P\rho_2^2(1 - \rho_3^2) - P\rho_5^2(1 - \rho_4^2) \stackrel{(D2)}{\leq} 0. \end{aligned} $$

To simplify the above constraints, we consider the following two distinct cases:

Case 1, if $-1 + \rho_2^2 + \rho_4^2 \geq 0$, constraints (A) and (B) together yield $-1 + \rho_3^2 + \rho_5^2 \geq \frac{N}{P}$. Moreover, constraint (C1) gives us $f(\rho_2, \rho_3, \rho_4, \rho_5) \leq -N$. In this case, our optimization problem boils down to minimizing

$$ f(\rho_2, \rho_3, \rho_4, \rho_5) \leq -N, \qquad (23) $$

subject to

$$ 1. -1 + \rho_2^2 + \rho_4^2 \geq 0, \qquad (24) $$

$$ 2. -1 + \rho_3^2 + \rho_5^2 \geq \frac{N}{P}, \qquad (25) $$

$$ 3. N\rho_2^2 + P\rho_2^2(1 - \rho_3^2) - P\rho_5^2(1 - \rho_4^2) \geq 0. \qquad (26) $$

Notice that $f(\rho_2, \rho_3, \rho_4, \rho_5)$ is decreasing function of $\rho_5^2$. From (26), we get that $\rho_5^2 \leq \frac{N\rho_2^2 + P\rho_2^2(1-\rho_3^2)}{P(1-\rho_4^2)}$. Therefore, the optimizer is given by $(\rho_5^*)^2 = \frac{N\rho_2^2 + P\rho_2^2(1-\rho_3^2)}{P(1-\rho_4^2)}$. By plugging $(\rho_5^*)^2$ into (23), we obtain that

$$ f(\rho_2, \rho_3, \rho_4, \rho_5^*) = \frac{(-1 + \rho_2^2 + \rho_4^2)(Q + P + 2\rho_3\sqrt{PQ}) - N\rho_2^2}{1 - \rho_4^2} $$

Since

$$ \frac{\partial f(\rho_2, \rho_3, \rho_4, \rho_5^*)}{\partial \rho_4^2} \leq 0, $$

we know that $f$ decreases to $-\infty$ as $\rho_4^2$ approaches 1. Moreover, since $\mathbb{E}[(X_1 - \mathbb{E}[X_1|W_1, W_2, Y_1])^2]$ is continuous and converges to $N$ when $\rho_4^2 \to 1$, in this case, the minimal value of $N$ is obtained at the boundary $\rho_4^2 = 1$.

Case 2, If $-1 + \rho_2^2 + \rho_4^2 \leq 0$, conditions (A) and (B) together give us $-1 + \rho_3^2 + \rho_5^2 \leq 0$, and (C2) gives us $f(\rho_2, \rho_3, \rho_4, \rho_5) \geq -N$ (but only $f \geq 0$ contributes to a nonnegative estimation cost). Therefore, in this case, our optimization problem boils down to minimizing

$$ f(\rho_2, \rho_3, \rho_4, \rho_5) \geq 0, \qquad (27) $$

subject to

$$ 1. -1 + \rho_2^2 + \rho_4^2 \leq 0, \qquad (28) $$

$$ 2. -1 + \rho_3^2 + \rho_5^2 \leq 0, \qquad (29) $$

$$ 3. N\rho_2^2 + P\rho_2^2(1 - \rho_3^2) - P\rho_5^2(1 - \rho_4^2) \leq 0. \qquad (30) $$

Since $f(\rho_2, \rho_3, \rho_4, \rho_5)$ is reduced especially when $\rho_5^2$ is increased, therefore, from (29), we get that $(\rho_5^*)^2 = 1 - \rho_3^2$. By replacing $(\rho_5^*)^2$ into (27), we get that

$$ f(\rho_2, \rho_3, \rho_4, \rho_5^*) = \frac{(1 - \rho_2^2 - \rho_4^2)(\sqrt{P}\rho_3 + \sqrt{Q})^2}{(1 - \rho_4^2)}. \qquad (31) $$

Therefore, when $P \geq Q$, taking $\rho_3^* = -\sqrt{\frac{Q}{P}}$ and any $\rho_2, \rho_4$ satisfy the constraints results in the optimal value of $f(\rho_2, \rho_3^*, \rho_4, \rho_5^*) = 0$. In this case, $\mathbb{E}[(X_1 - \mathbb{E}[X_1|W_1, W_2, Y_1])^2] = 0$.

When $P < Q$, $f(\rho_2, \rho_3, \rho_4, \rho_5^*)$ is a decreasing function of $\rho_2^2$. The constraint (30) gives us the optimal value of $\rho_2^2$:

$$ (\rho_2^*)^2 = \frac{P(1 - \rho_3^2)(1 - \rho_4^2)}{N + P(1 - \rho_3^2)}. \qquad (32) $$

Plugging the $(\rho_2^*)^2$ in (32) into (31), we have

$$ f(\rho_2^*, \rho_3, \rho_4, \rho_5^*) = \frac{N(\sqrt{P}\rho_3 + \sqrt{Q})^2}{N + P(1 - \rho_3^2)}. $$

Then, taking $\frac{\partial f}{\partial \rho_3} = 0$ gives us the optimum

$$ \rho_3^* = -\frac{P + N}{\sqrt{QP}}, $$

which is valid only if the following condition holds

$$ (\rho_3^*)^2 = \frac{(P + N)^2}{QP} \leq 1 \Rightarrow \begin{cases} Q > 4N, \\ P \in [P_1, P_2], \end{cases} \qquad (33) $$

where $P_1 = \frac{1}{2}(Q - 2N - \sqrt{Q^2 - 4QN})$, $P_2 = \frac{1}{2}(Q - 2N + \sqrt{Q^2 - 4QN})$. In this case, $(\rho_5^*)^2 = \frac{QP - (P+N)^2}{QP}$, and $f(\rho_2^*, \rho_3^*, \rho_4^*, \rho_5^*) = \frac{N(Q-N-P)}{N+P}$, which results in the estimation cost of

$$ \mathbb{E}[(X_1 - \mathbb{E}[X_1|W_1, W_2, Y_1])^2] = \frac{N(Q - N - P)}{Q}. $$
In the case when the condition (33) is unmet, we always have $-\frac{P+N}{\sqrt{QP}} < -1$. Since $\frac{\partial f}{\partial \rho_3} > 0$, function $f$ increases when $\rho_3 \in [-1, 1]$ increases. Therefore, the minimal value of $f$ achieves at the left boundary $\rho_3^* = -1$, which gives us $\rho_2^* = \rho_5^* = 0$ and $f(\rho_2^*, \rho_3^*, \rho_4^*, \rho_5^*) = (\sqrt{Q} - \sqrt{P})^2$. Hence,

$$ \mathbb{E}[(X_1 - \mathbb{E}[X_1|W_1, W_2, Y_1])^2] = \frac{N \cdot (\sqrt{Q} - \sqrt{P})^2}{N + (\sqrt{Q} - \sqrt{P})^2}. $$

Obviously, the minimal estimation cost value $N$ from case 1 is always larger than the cost derived in case 2. Therefore, summarizing our above analysis, the optimal Gaussian cost $S_G(P)$ is given by (12). □

**Proof of Lemma III.5.** From the Markov chain, we have that

$$ \begin{aligned} 0 &= I(X; Z|Y) \\ &= H(X, Y) + H(Y, Z) - H(Y) - H(X, Y, Z) \\ &= \frac{1}{2} \log \left( \frac{\det(\Sigma_{X,Y}) \cdot \det(\Sigma_{Y,Z})}{\sigma_Y^2 \cdot \det(\Sigma_{X,Y,Z})} \right), \end{aligned} $$

where all the information of the last step can be obtained from the covariance matrix (15). Therefore,

$$ \begin{aligned} 0 &= \det(\Sigma_{X,Y}) \cdot \det(\Sigma_{Y,Z}) - \sigma_Y^2 \cdot \det(\Sigma_{X,Y,Z}) \\ &= PQ^2V(\rho_1\rho_3 - \rho_2)^2, \end{aligned} $$

which implies the result (16). □

**Proof of Corollary III.6.** According to [24], the information constraint for Witsenhausen counterexample with causal encoder and non-causal decoder with channel feedback $Y_1$ is

$$ I(W_1; Y_1) - I(U_2; X_0|W_1, Y_1) \ge 0. \quad (34) $$

Moreover, in the Gaussian settings, the MMSE estimator of $X_1$ can be represented as $U_2 = \mathbb{E}[X_1|W_1, W_2, Y_1] = a \cdot W_1 + b \cdot W_2 + c \cdot Y_1$, with some constants $a, b, c \in \mathbb{R}$. Hence, the information constraint (34) can be rewritten as

$$ \begin{aligned} I(W_1; Y_1) - I(U_2; X_0|W_1, Y_1) &= I(W_1; Y_1) - I(a \cdot W_1 + b \cdot W_2 + c \cdot Y_1; X_0|W_1, Y_1) \\ &= I(W_1; Y_1) - I(W_2; X_0|W_1, Y_1), \end{aligned} $$

which recovers the information constraint for the framework without channel feedback (19). Thus, the optimization domain for this optimization problem is exactly the same as the one without channel feedback, i.e., (8). □

## REFERENCES

[1] H. S. Witsenhausen, “A counterexample in stochastic optimum control,” *SIAM Journal on Control*, vol. 6, no. 1, pp. 131–147, 1968.

[2] R. Bansal and T. Başar, “Stochastic teams with nonclassical information revisited: When is an affine law optimal?,” in *1986 American Control Conference*, pp. 45–50, IEEE, 1986.

[3] E. I. Silva, G. C. Goodwin, and D. E. Quevedo, “Control system design subject to SNR constraints,” *Automatica*, vol. 46, no. 2, pp. 428–436, 2010.

[4] S. Yüksel and T. Başar, *Stochastic networked control systems: Stabilization and optimization under information constraints*. Springer Science & Business Media, 2013.

[5] A. Gupta, S. Yüksel, T. Başar, and C. Langbort, “On the existence of optimal policies for a class of static and sequential dynamic teams,” *SIAM Journal on Control and Optimization*, vol. 53, no. 3, pp. 1681–1712, 2015.

[6] N. C. Martins and M. A. Dahleh, “Fundamental limitations of performance in the presence of finite capacity feedback,” in *Proceedings of the 2005, American Control Conference, 2005.*, pp. 79–86, IEEE, 2005.

[7] J. S. Freudenberg and R. H. Middleton, “Feedback control performance over a noisy communication channel,” in *2008 IEEE Information Theory Workshop*, pp. 232–236, IEEE, 2008.

[8] M. S. Derpich and J. Ostergaard, “Improved upper bounds to the causal quadratic rate-distortion function for gaussian stationary sources,” *IEEE Transactions on Information Theory*, vol. 58, no. 5, pp. 3131–3152, 2012.

[9] A. Agrawal, F. Danard, B. Larrousse, and S. Lasaulce, “Implicit coordination in two-agent team problems with continuous action sets. application to the Witsenhausen cost function,” in *European Control Conference, ECC 2015, Linz, Austria, July 15-17, 2015*, pp. 1854–1859, IEEE, 2015.

[10] E. Akyol, C. Langbort, and T. Başar, “Information-theoretic approach to strategic communication as a hierarchical game,” *Proceedings of the IEEE*, vol. 105, no. 2, pp. 205–218, 2017.

[11] C. D. Charalambous, C. Kourtellaris, and I. Tzortzis, “Hierarchical optimality of linear controllers-encoders-decoders operating at control-coding capacity of LQG control systems,” in *2017 IEEE 56th Annual Conference on Decision and Control (CDC)*, pp. 3682–3687, IEEE, 2017.

[12] M. Wiese, T. J. Oechtering, K. H. Johansson, P. Papadimitratos, H. Sandberg, and M. Skoglund, “Secure estimation and zero-error secrecy capacity,” *IEEE Transactions on Automatic Control*, vol. 64, no. 3, pp. 1047–1062, 2018.

[13] P. A. Stavrou, M. Skoglund, and T. Tanaka, “Sequential source coding for stochastic systems subject to finite rate constraints,” *IEEE Transactions on Automatic Control*, vol. 67, no. 8, pp. 3822–3835, 2022.

[14] S.-H. Tseng and A. Tang, “A local search algorithm for the Witsenhausen’s counterexample,” in *2017 IEEE 56th Annual Conference on Decision and Control (CDC)*, pp. 5014–5019, 2017.

[15] J. Karlsson, A. Gattami, T. J. Oechtering, and M. Skoglund, “Iterative source-channel coding approach to Witsenhausen’s counterexample,” in *Proceedings of the 2011 American Control Conference*, pp. 5348–5353, 2011.

[16] M. Baglietto, T. Parisini, and R. Zopponi, “Numerical solutions to the Witsenhausen counterexample by approximating networks,” *IEEE Transactions on Automatic Control*, vol. 46, no. 9, pp. 1471–1477, 2001.

[17] J. Lee, E. Lau, and Y.-C. Ho, “The Witsenhausen counterexample: a hierarchical search approach for nonconvex optimization problems,” *IEEE Transactions on Automatic Control*, vol. 46, no. 3, pp. 382–397, 2001.

[18] N. Li, J. R. Marden, and J. S. Shamma, “Learning approaches to the Witsenhausen counterexample from a view of potential games,” in *Proceedings of the 48th IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference*, pp. 157–162, 2009.

[19] Y. Wu and S. Verdú, “Witsenhausen’s counterexample: A view from optimal transport theory,” in *2011 50th IEEE Conference on Decision and Control and European Control Conference*, pp. 5732–5737, 2011.

[20] P. Grover and A. Sahai, “Witsenhausen’s counterexample as assisted interference suppression,” *International Journal of Systems, Control and Communications*, vol. 2, pp. 197–237, 2010.

[21] P. Grover, S. Y. Park, and A. Sahai, “Approximately optimal solutions to the finite-dimensional Witsenhausen counterexample,” *IEEE Transactions on Automatic Control*, vol. 58, no. 9, pp. 2189–2204, 2013.

[22] M. Le Treust and T. J. Oechtering, “Power-estimation trade-off of vector-valued Witsenhausen counterexample with causal decoder,” *IEEE Transactions on Information Theory*, vol. 70, no. 3, pp. 1588–1609, 2024.

[23] M. Zhao, M. Le Treust, and T. J. Oechtering, “Coordination coding with causal encoder for vector-valued witsenhausen counterexample,” in *2024 IEEE International Symposium on Information Theory (ISIT)*, pp. 3255–3260, IEEE, 2024.

[24] M. Zhao, M. Le Treust, and T. J. Oechtering, “Causal vector-valued witsenhausen counterexamples with feedback,” *arXiv preprint arXiv:2408.03037*, 2024.