1

Deterministic Annealing Optimization for
Witsenhausen’s and Related Decentralized
Stochastic Control Problems

arXiv:1607.02893v1 [] 11 Jul 2016

Mustafa Said Mehmetoglu, Student Member, IEEE, Emrah Akyol, Member, IEEE,
and Kenneth Rose, Fellow, IEEE

Abstract—This note studies the global optimization of controller mappings in discrete-time stochastic control problems
including Witsenhausen’s celebrated 1968 counter-example. We
propose a generally applicable non-convex numerical optimization method based on the concept of deterministic annealing
– which is derived from information theoretic principles and
was successfully employed in several problems including vector
quantization, classification and regression. We present comparative numerical results for two test problems that show strict
superiority of the proposed method over prior approaches in
literature.
Index Terms—Decentralized control, Optimization methods,
Numerical simulation, Physical models.

I. I NTRODUCTION
Decentralized control systems have multiple controllers
designed to collaboratively achieve a global objective while
taking actions based on local observations. One of the most
studied structures, termed “linear quadratic Gaussian” (LQG),
involves linear dynamics, quadratic cost functions and Gaussian variables. Since in the case of centralized LQG problems,
the optimal mappings are linear, it was naturally conjectured
that linear control mappings remain optimal in decentralized
settings. However, Witsenhausen proposed an example of a
decentralized LQG control problem, commonly referred to
as Witsenhausen’s counter-example (WCE), for which he
provided a simple non-linear control strategy that outperforms
all linear strategies [1]. The problem has been viewed as a
benchmark in stochastic networked control, see, e.g., [2] for
a detailed treatment.
Decentralized control systems such as WCE arise in many
practical applications, and numerous variations on WCE have
been studied in the literature (see, e.g., [3]–[8]). In general,
linear control strategies are not optimal for LQG systems,
except when the system admits some specific information
structure (see, e.g., [9], [10]). It is well-understood that if
the information structure in a decentralized control problem
Mustafa S. Mehmetoglu and Kenneth Rose are with the Department of
Electrical and Computer Engineering, University of California, Santa Barbara,
CA, 93106, USA (e-mail: mehmetoglu@ece.ucsb.edu, rose@ece.ucsb.edu)
Emrah Akyol is with the Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL, 61801, USA (email:
akyol@illinois.edu)
This work is supported by the NSF under grants CCF-1118075 and CCF1016861. The material in this paper was presented in part at the IEEE
International Symposium on Information Theory (ISIT), Honolulu, HI, USA,
June 2014

is nonclassical, as in the case of WCE, non-linear strategies
may widely outperform optimal linear strategies. Finding the
optimal mappings for such problems is usually a difficult task
unless they admit an explicit (and often as simple as linear)
solution [3].
Recent research efforts have focused on developing efficient
numerical methods for decentralized control problems [11]–
[14], specifically for WCE [15]–[18]. Some of the existing
methods rely on simplifying properties of WCE, such as
monotonicity, and are therefore not easily generalizable [11],
[12], [19]. Moreover, methods that require analytical derivation
for each particular setting are not fully automated [14], [19].
In this work, building on our prior work [20], we propose
an optimization method, based on the concept of deterministic
annealing (DA), for a class of decentralized stochastic control
problems. DA has been successfully used in various problems
in control theory including dynamic coverage control problems
[21]–[23] and cluster analysis in control systems [24], in
addition to other problems involving non-convex optimization
such as vector quantization [25], regression [26], zero-delay
source-channel coding [27], and more (see review in [28]).
There are many important advantages of the proposed method
compared to prior work, including ability to avoid poor local
minima and independence from initialization.
We demonstrate the DA-based method on two specific
problems. We first analyze the numerically ”over-mined” WCE
problem. We then study a more involved variation, introduced
in [7], which includes an additional noisy channel over which
the two controllers communicate. The second controller, therefore, has access to some side information which is controlled
by the first controller. We refer to this setting as the “side
channel problem” motivated by the class of ”decoder side
information” problems in communications and information
theory [29]. It has been demonstrated in [7] that non-linear
strategies may outperform the best linear strategies, however,
the question of how to approach the optimal solution remains
open.
Having a powerful optimization method at hand, we analyze the structure of experimentally obtained mappings. For
instance, Wu and Verdú have shown [30] that the optimal
solution of WCE must have real analytic left inverse, thus,
a piecewise linear function cannot be optimal. Our numerical
results demonstrate that the “steps” in obtained mappings show
small deviations from linear, experimentally confirming this
theoretical finding.

2

II. P ROBLEM D EFINITION

A. Derivation

A. Notation
Let R, E(·) and P(·) denote the set of real numbers, the
expectation and probability operators, respectively. We represent random variables and their realizations with uppercase
and lowercase letters (e.g., X and x), respectively. Let Xij
denote the set Xi , . . . , Xj . The probability density function of
the random variable X is fX (x). The Gaussian density with
mean µ and standard deviation σ is denoted as N (µ, σ 2 ). We
use natural logarithms which, in general, may be complex, and
the integrals are, in general, Lebesgue integrals.
B. General Problem Definition
Formally, we consider a discrete-time stochastic control
problem with nonclassical information pattern involving n
controllers, and assume that the order of control actions is
fixed in advance, i.e., the system is sequential [31]. Following
the problem definition in [31], let (Ω, B, P) be a probability
space, where Ω denotes the random quantities involved in the
system such as initial input, and (Ui , Σi ), for i = 1, . . . , n,
are measurable spaces with Ui denoting the set of control
actions. Controller mappings (functions) are denoted by gi :
Ω×U1 ×U2 . . . Ui−1 → Ui , for i = 1, . . . , n. For convenience,
we denote the input set of gi by Xi = Ω × U1 × U2 . . . Ui−1 .
The system is then defined by the following set of equations
ui = gi (xi ), i = 1, . . . , n.

(1)

Let f be a real-valued and bounded measurable function of
ω, un1 on (Ω, B), i.e., f is a random variable. The problem
objective is to find the set of functions g1n that minimize the
value of the cost function J:
J = E{f (ω, un1 )}.

(2)

III. P ROPOSED M ETHOD
A quick overview of the proposed method at the high
level is as follows: We introduce controlled randomization
into the optimization process by randomizing the controller
mappings, and impose a constraint on the level of randomness
(measured by the Shannon entropy) while minimizing the
expected cost of the system. The resultant Lagrangian functional can be viewed as the “free energy” of a corresponding
physical system, wherein the Lagrangian parameter is the
“temperature”. The optimization is equivalent to an annealing
process that starts by minimizing the cost (free energy) at a
high temperature, which effectively maximizes the entropy.
The minimum cost is then tracked at successively lower
temperatures as the system typically undergoes a sequence of
phase transitions through which the complexity of the solution
(controller mappings) grows. As the temperature approaches
zero, hard (nonrandom) mappings are obtained. DA avoids
poor local minima through randomization of mappings, slowly
tracks the minimum cost, and can achieve the global minimum
under certain conditions on the type (and continuity) of
phase transitions. However, there is no general guarantee of
convergence to the globally optimal solution.

Let us denote the space of controller input xi by Rxi , for i =
1, . . . , n. Assume there exists a partition of Rxi into Mi > 0
disjoint regions denoted by Ri,mi (mi = 1, . . . , Mi ):
M
[i

Ri,mi = Rxi .

(3)

mi =1

Note that each value of xi belongs to exactly one of the
partition regions, referred to as a deterministic (non-random)
partition.
We begin our formulation by imposing a piecewise structure
on the controller mappings. Consider the structured mapping
gi , for i = 1, . . . , n, written as
gi (xi ) = gi,mi (xi ) for xi ∈ Ri,mi .

(4)

Each gi,mi (xi ) is a parametric function referred to as “local
model”. Effectively, each of the mappings gi is defined with
a structure determined by two components: a space partition
where regions are denoted by Ri,mi and a parametric local
model per partition cell, i.e., gi,mi (xi ) for Ri,mi . The number
of local models (partition regions) for mapping gi is Mi .
The local models can take any prescribed form such as
linear, quadratic or Gaussian and we let Λ(gi,mi ) denote the
parameter set for local model gi,mi .
The crucial idea in DA is to introduce controlled randomization into the problem formulation. We replace the deterministic
partition of space by a random partition, i.e., we associate
every input point (xi ) with partition regions in probability. To
this end, we introduce random variables Mi , for i = 1, . . . , n,
whose realization is the partition index mi . We define the
association probabilities as conditional distribution on the
partition index given the input:
pi (mi |xi ) = P{xi ∈ Ri,mi } = P{gi (xi ) = gi,mi (xi )}, (5)
for i = 1, . . . , n. Consequently, the mappings are now random,
in the sense that the output of controller gi for an input xi is
given in probability as
gi (xi ) = gi,mi (xi ) with probability pi (mi |xi ).

(6)

By construction, we have that given Xi , Mi is independent of
the random variables M1i−1 .
The expectation in (2) is now taken over Xin and Min . Let
us rewrite it for a fixed value of i as follows:
Z X
Mi
J=
E{f (ω, un1 )|mi , xi }pi (mi |xi )fxi (xi )dxi (7)
xi m =1
i

where E{f (ω, un1 )|mi , xi } can be viewed as the cost of associating xi with local model gi,mi . Assuming fixed local model
parameters, optimizing (7) with respect to pi (mi |xi ) would
clearly produce deterministic mappings, since the minimum is
achieved by setting pi (mi |xi ) = 1 for the pair {mi , xi } for
which E{f (ω, un1 )|mi , xi } is minimum. Therefore, the ultimate objective of obtaining optimum deterministic controllers
is preserved as the random encoders share the same global
minimum as deterministic ones. However, direct optimization
of the cost with respect to pi (mi |xi ) results in poor local

3

minima. Instead, we minimize (2) at prescribed levels of
randomness, which we measure by the Shannon entropy. The
joint entropy of the system can be written
H(X1n , M1n ) = H(X1 ) +

n
X
i=2

+H(M1 |X1 ) +

H(Xi |M1i−1 , X1i−1 )

n
X

H(Mi |Xi , M1i−1 , X1i−1 ).

n
X

H(Mi |Xi ).

i=2

(8)

It is easy to see from conditional independence arguments
that the conditional entropies in the second term in the
righthand side of (8) can be simplified to H(Xi |X1i−1 ), and
those in the last term to H(Mi |Xi ). Thus the first two terms
of (8) are fixed and determined by the problem statement (the
joint distribution of X1n ). We therefore discard the first two
fixed terms of (8), rearrange the remaining terms, to obtain a
conveniently compact measure of randomness defined as
H,

i=1

(9)

The conditional entropy H(Mi |Xi ) is given by
Z X
Mi
p(mi |xi ) log p(mi |xi )fXi (xi )dxi .
H(Mi |Xi ) = −
xi m =1
i

Accordingly, we construct the Lagrangian
F = J − TH

(10)
(11)

as the objective function to be minimized, where J is given
in (2), H is given in (9) and T is the Lagrange multiplier
associated with the entropy constraint. The notational choices
are to emphasize the analogy to statistical physics, where
F can be viewed as the Helmholtz free energy, J as the
thermodynamic energy, H as the entropy, and T as the
temperature, of a corresponding physical system (see [28] for
a detailed treatment of the statistical physics analogy).
B. Optimization Method
The practical method consists of gradually reducing the
temperature T while tracking the minimum of the free energy F . The central iteration at each temperature consists
of optimizing the local model parameters and association
probabilities. Initially, for T → ∞, the minimum F is obtained
by maximizing H, which is achieved by uniform association
probabilities as can be seen from (9). Consequently, for each
controller, the local models are all optimized for the same
distribution over the input space, and are therefore all identical,
i.e., there is effectively a single “distinct” local model. As
the temperature is decreased, the system will undergo “phase
transitions” where the current solution no longer represents a
minimum (the old minimum typically becomes a saddle point)
and there exists a better solution with increased number of
distinct local models. Since it is computationally more efficient
to keep only distinct models, we initialize with a single model
(Mi = 1) and trigger phase transitions by duplicating existing
models and slightly perturb them at each temperature. The

minimization of F will either produce the existing solution
(the duplicated and perturbed local models seek to merge
at their initial values), or a better solution with increased
number of distinct models, depending on whether a “critical
temperature” has been reached. Accordingly, in we combine
identical models. At the limit T → 0, we perform zero
temperature iteration (equivalent to gradient descent) by fully
assigning source points to the model that makes the smallest
contribution to J, thus obtaining the desired deterministic
mappings. (This is referred to as ”quenching” in the physical
analogy.)
Remark 1: Our method is derived without recourse to discretization. Although practical simulations involve sampling
of the continuous space during numerical computations of
integrals, this is in contrast to methods that are entirely
formulated in discrete settings.
Remark 2: Critical temperatures can be derived analytically
if, for the problem considered, phase transitions are of “continuous” nature, in the sense that tracked minimum becomes
a saddle point at the exact critical temperature. The condition
for saddle point can be obtained using variational calculus,
see [28] for phase transition analysis in DA. Our experiments
indicate that, at least for the test cases considered in this paper,
phase transitions are not continuous. While pre-calculating the
critical temperature may enable a numerical speed up of the
annealing process, it is not necessary to implementing the
practical algorithm. Hence, the derivation and characteristics
of phase transitions are kept outside the scope of this paper.
The optimal pi (mi |xi ) that minimize (11) can be derived
in closed form. Plugging (7) and (10) in (11), straightforward
derivation gives the optimal pi (mi |xi ) as
n

e−E{f (ω,u1 )|mi ,xi }/T
pi (mi |xi ) = P −E{f (ω,un )|m ,x }/T
i i
1
e

(12)

mi

Optimization of parameters in Λ(gmi ) can be done using
any standard method. Typically, a variant of gradient descent
is used when closed form expressions cannot be obtained.
IV. A PPLICATIONS OF THE P ROPOSED DA M ETHOD
A. Witsenhausen’s Counterexample
1) Problem Description: Let X0 and W be Gaussian ran2
dom variables with distributions N (0, σX
) and N (0, 1), re0
spectively. WCE is a 2-stage control problem with controllers
g1 : R → R and g2 : R → R, defined by the following
equations:
U1 = g1 (X0 ),

U2 = g2 (X1 + W ),

X1 = X0 + U1 , X2 = X1 − U2 .

(13)

The schematic representation is given in Figure 1a. The
objective is to minimize the cost
J = E{k 2 U12 + X22 }.

(14)

For convenience, we define f1 (X0 ) = g1 (X0 ) + X0 .
Some properties of f1 (·) are known, including the property
of symmetry about the origin (thus, positive half is enough to
describe a given solution) [1]. Witsenhausen has provided the

4

TABLE I
R ESULTS FOR WCE
Solution
Optimal linear Solution
1-step, Witsenhausen [1]
2-step, [11]
Sloped 2.5 - step, [15]
Sloped 3.5 - step, [19]
Sloped 3.5 - step, [17]
Sloped 4 - step, [16]
Sloped 5 - step, our result

(a)

(b)
Fig. 1. Settings used for testing the proposed method (a) Witsenhausen’s
counter-example (b) Side channel problem.

following solution that outperforms the optimal linear solution
for a given set of problem parameters (k = 0.2, σX0 = 5):
f1 (x0 ) = σX0 sgn(x0 )

(15)

where sgn(·) is the signum function. Since there is a single
“step” in the positive half of real line, this solution is referred
to as a “1-step” solution. Improved solutions that appeared in
literature utilize 2.5, 3, 3.5 and 4-step functions (an x.5 step
function has a step that straddles the origin). Moreover, the
latter solutions made improvements by using slightly sloped
steps rather than constant ones.
Although in standard application of DA-based method we
randomize all controllers, for computational efficiency, we
restrict the randomization to only g1 as
g1 (x0 ) = g1,m1 (x0 ) with probability p1 (m1 |x0 )

(16)

and numerically compute (update) g2 by using the fact that
optimal g2 given g1 is
g2 (Y2 ) = E{X1 |Y2 }

(17)

where Y2 = X1 + W .
For this particular problem, we use linear local models given
by
g1,m1 (x0 ) = a1,m1 x0 + b1,m1 .
(18)
while noting that optimal g1 must have analytic left inverse and
hence cannot be piecewise linear [30]. Nevertheless, the minimal cost can be approached arbitrarily closely by piecewise
linear functions [30]. Thus, for numerical algorithms, linear
models are sufficient.
2) Results for WCE: Preliminary results on the application
to WCE appeared in [20]. We first provide results for the standard benchmark case where k = 0.2, σX0 = 5 that was used in
many papers in literature. The annealing process is illustrated
in Figure 2, where evolution of the mapping can be seen (only
the positive half is shown thanks to the symmetry property).
The obtained mapping is referred to as a “sloped 5-step”
solution. At high temperature, there is only one local model,
thus, the function is 1-step. As the temperature is lowered, the
solution undergoes phase transitions, revealing more steps for
the mapping function. In this work we calculated the solution
with 5 steps. Although more steps possibly exist, improvement
to cost is numerically insignificant with additional steps. Some

Cost
0.96
0.404253
0.190
0.1701
0.1673132
0.1670790
0.16692462
0.16692291

earlier results from the literature are given in Table I, where
it can be seen that our method produced the minimum cost
achieved to date.
Another benchmark case, k = 0.63, was suggested in [5] as
potentially being more relevant for confirming the high gains
of optimal non-linear mappings. Our resulting mapping for
k = 0.63, σX0 = 5 is given in Figure 3a, which is a 6-step
solution. Our numerical results suggest that the gain over linear
solution is smaller compared to the standard benchmark case
above: J = 0.844 for the solution in Figure 3a whereas cost
associated with the optimal linear mapping is J = 0.961.
These numerical results illustrate an important theoretical
result as well. In [30] authors proved that the optimal f1 must
have analytic left inverse and therefore cannot be piecewise
linear, which was believed to be the case due to numerical
results (see, e.g., [19]). Our numerical results indicate that
steps are in fact non-linear, as shown in Figure 3b. The steps
become non-linear during the final stages of the algorithm as
multiple local models appear to form a single step. To the best
of our knowledge, this is the first numerical result illustrating
non-linearity of the steps.
B. Side Channel Problem
1) Problem Description: Let X0 be a Gaussian random
2
variable with distribution N (0, σX
), and W1 , W2 be inde0
pendent Gaussian random variables, both with a distribution
N (0, 1). The system is defined by the following equations:
U1 = g1 (X0 ), U2 = g2 (X0 ), U3 = g3 (X1 + W1 , U2 + W2 ),
X1 = X0 + U1 ,

X2 = X1 − U3 .

(19)

The problem is to optimize the cost function
J = E{k 2 U12 + X22 }

(20)

for given σX0 and positive parameter k, subject to a power
constraint on U2 :
bSN R = E{U22 }
(21)

where bSN R is the specified power level. We again define
f1 (X0 ) = g1 (X0 ) + X0 .
This problem setting is illustrated in Figure 1b and was introduced in [7]. It can be seen as a generalization of WCE with
an additional communication channel between the controllers,
i.e., a non-linear function of input X0 is communicated by
g2 to the controller denoted by g3 : R2 → R. The non-linear
mappings analyzed in [7], which widely outperform the best
linear solution in a large range of bSN R , are such that both f1
and g2 are staircase functions of x0 .

5

T = 5.000, D = 0.3510, H = 0.693

T = 0.275, D = 0.1898, H = 0.121

T = 0.153, D = 0.1729, H = 0.068

T = 0.021, D = 0.1671, H = 0.009

T = 0.005, D = 0.1670, H = 0.002

30

30

30

30

30

15

15

15

15

15

f 1 (x 0 )
0

0
0

10

20

30

0
0

10

20

30

0
0

10

20

30

0
0

10

20

30

0

10

20

30

Fig. 2. Evolving graph of f1 (x0 ) in WCE during various phases of the annealing process. We note that mapping is actually random during algorithm run.
Here, for demonstration, we fully associate every x0 with g1,m1 for which p1 (m1 |x0 ) is largest.

f1 (x0 )

30

0.04

20

0.02

10

0

0
0

10

f1 (x0 )-line

20

-0.02
30
0

2

(a)

4

6

(b)

Fig. 3. Numerical result for WCE in the case of k = 0.63, σX0 = 5. (a)
6-step solution. (b) The deviation of the first step in f1 (x0 ) from a straight
line between the end points of the step.
TABLE II
C OST C OMPARISON TABLE FOR S IDE C HANNEL P ROBLEM
bSN R
0
2.6
4.7
5.9
9.0

Linear Cost
0.960
0.696
0.432
0.344
0.203

J M ( [7])
0.185
0.149
0.101
0.081
0.052

J∗
0.167
0.079
0.040
0.026
0.012

V. A DVANTAGES OF P ROPOSED M ETHOD

(J M −J ∗)/J M
0.10
0.47
0.60
0.68
0.77

2) Results for Side Channel Problem: The original problem
is to minimize (20) subject to the constraint in (21). We follow
the standard approach in optimization theory and convert this
constrained problem to unconstrained Lagrangian formulation:
J = E{k 2 U12 + X22 + λU22 }

stage. Intuitively, as the second controller has access to better
side information (i.e. at higher SNR), the estimation error is
decreased and as observed in Figure 4, f1 (x0 ) approaches x0 .
The relative improvement in cost, given in Table II, increases
with SNR, which is consistent with the above observation.
The mappings for the side channel, g2 , are irregular and
the overall shape varies with SNR. This observation, together
with the above for f1 , suggests that the mappings f1 and g2 are
not scale invariant. The discontinuities in f1 and g2 coincide
as expected, as the discontinuities in side information signal
those in f1 to g3 .
Note: For numerical results in this paper, MATLAB codes
can be found in [32].

(22)

where λ is chosen to satisfy the power constraint (21) with
equality. In the experiments, we used the standard benchmark
parameters that were used for the original WCE, that is,
k = 0.2 and σX0 = 5. We have varied λ to obtain results
at different bSN R .
In Table II we compare the cost of our solutions (denoted
by J ∗ ) to the ones given in [7] (denoted by J M ), and the best
linear mappings. Significant cost reductions can be observed.
The relative improvement over the solution of [7] is listed in
the last column.
Remark 3: When bSN R = 0, the problem degenerates to
WCE, thus the cost is 0.1669, the best known to date.
We present several mappings obtained by our method in
Figure 4. Some interesting features of these mappings are
observed. The mappings f1 are staircase functions with constant steps similar to the ones obtained for the original WCE
problem, however, the steps get smaller and increase in number
as the side channel SNR increases; that is, f1 (x0 ) approaches
x0 . Note that the control cost term in (20), E{k 2 U12 }, achieves
its minimum when g1 = 0, i.e., f1 (x0 ) = x0 . This is,
however, not optimal due to the estimation error at the second

There are several improvements of the method proposed
here over existing methods in literature.
1) It is derived in the original, continuous domain, without
discretization. The continuous space is sampled during
numerical computation of integrals only. This is in
contrast with many prior methods such as those in [12],
[16], [17] that are entirely formulated in a discrete
setting.
2) Our method is based on DA, a powerful non-convex
optimization framework. DA has been successfully used
as a remedy to the problem of poor local minima in
non-convex optimization problems [28], and is shown to
outperform competing methods such as “noisy channel
relaxation” (NCR) [27]. Although NCR performs well
for the simple setting of WCE [16], it is susceptible to
get trapped in local minima in more involved settings.
3) From its DA foundation, our method directly inherits
notably useful properties including reduced sensitivity
to initialization. The authors in [15] had to experiment
with a large number of initial weight vectors to obtain
the result included in Table I.
4) We do not make any assumptions about the controller
mappings. Methods presented in [11], [12], [19] benefit
from the monotonicity of optimal mapping in WCE. The
results in Figure 4 demonstrate that monotonicity may
not hold for optimal mappings in the general setting.
5) The method is fully automated and does not require
analytical derivations or manual interventions during
algorithm run. This is in contrast to the method presented in [19] which requires analytical work during the
procedure.
6) Method is applicable to a broad class of stochastic
control problems. Many prior methods require nontrivial work in order to generalize, for instance, [17]

6

bsnr = 2.6

20

cost = 0.079

f1
0

-20
-15

cost = 0.040

0

-5

0

5

10

15

-20
-15

cost = 0.012

f1

g2

-10

bsnr = 9.0

20

f1

g2

-10

bsnr = 4.8

20

0

-5

x0

0

5

x0

10

15

-20
-15

g2

-10

-5

0

5

10

15

x0

Fig. 4. Some of the mappings we obtained for the side channel variation problem. The first controller is plotted at various SNR levels.

proposes a method that is generalizable, but it requires
conversion to a potential game problem.
VI. C ONCLUSIONS
In this paper, we proposed an optimization method for
distributed control problems, whose solutions are known to be
non-linear, and demonstrated its effectiveness on two problems
from the literature. The first problem is the celebrated benchmark problem known as Witsenhausen’s counter-example, for
which our approach obtained the best known cost value. As
a second test case we focused on the side channel setting
introduced in [7], where it is motivated as a two stage
noise cancellation problem. The mappings obtained are highly
nontrivial, offer considerably improved performance, and raise
interesting questions about the functional properties of optimal
mappings in decentralized control, which are the focus of
ongoing research.
R EFERENCES
[1] H. Witsenhausen, “A counterexample in stochastic optimum control,”
SIAM Journal on Control, vol. 6, no. 1, pp. 131–147, 1968.
[2] S. Yüksel and T. Başar, Stochastic Networked Control Systems: Stabilization and Optimization under Information Constraints. Springer,
2013.
[3] T. Başar, “Variations on the theme of the Witsenhausen counterexample,”
in 47th IEEE Conference on Decision and Control Proceedings (CDC).
IEEE, 2008, pp. 1614–1619.
[4] G. Gnecco, M. Sanguineti, and M. Gaggero, “Suboptimal solutions to
team optimization problems with stochastic information structure,” SIAM
Journal on Optimization, vol. 22, no. 1, pp. 212–243, 2012.
[5] P. Grover, S. Y. Park, and A. Sahai, “Approximately optimal solutions to
the finite-dimensional Witsenhausen counterexample,” Automatic Control, IEEE Transactions on, vol. 58, no. 9, pp. 2189–2204, 2013.
[6] Y. Ho and K. Chu, “Information structure in dynamic multi-person
control problems,” Automatica, vol. 10, no. 4, pp. 341 – 351, 1974.
[7] N. Martins, “Witsenhausen’s counter example holds in the presence of
side information,” in Decision and Control, 2006 45th IEEE Conference
on, 2006, pp. 1111–1116.
[8] N. Saldi, S. Yüksel, and T. Linder, “Finite Model Approximations and
Asymptotic Optimality of Quantized Policies in Decentralized Stochastic
Control,” ArXiv e-prints, 2015.
[9] Y. Ho and K. Chu, “Team decision theory and information structures in
optimal control problems–Part I,” Automatic Control, IEEE Transactions
on, vol. 17, no. 1, pp. 15–22, 1972.
[10] R. Radner, “Team decision problems,” The Annals of Mathematical
Statistics, vol. 33, no. 3, pp. 857–881, 09 1962.
[11] M. Deng and Y. Ho, “An ordinal optimization approach to optimal
control problems,” Automatica, vol. 35, no. 2, pp. 331 – 338, 1999.
[12] Y.-C. Ho and J. Lee, “Granular optimization: An approach to function
optimization,” in Decision and Control, 2000. Proceedings of the 39th
IEEE Conference on, vol. 1, 2000, pp. 103–111 vol.1.
[13] L. Jiang, D. Shah, J. Shin, and J. Walrand, “Distributed random access
algorithm: Scheduling and congestion control,” Information Theory,
IEEE Transactions on, vol. 56, no. 12, pp. 6182–6207, 2010.

[14] A. Kulkarni and T. Coleman, “An optimizer’s approach to stochastic
control problems with nonclassical information structures,” Automatic
Control, IEEE Transactions on, vol. PP, no. 99, pp. 1–1, 2014.
[15] M. Baglietto, T. Parisini, and R. Zoppoli, “Numerical solutions to the
Witsenhausen counterexample by approximating networks,” Automatic
Control, IEEE Transactions on, vol. 46, no. 9, pp. 1471–1477, 2001.
[16] J. Karlsson, A. Gattami, T. Oechtering, and M. Skoglund, “Iterative
source-channel coding approach to Witsenhausen’s counterexample,” in
American Control Conference (ACC), 2011. IEEE, 2011, pp. 5348–
5353.
[17] N. Li, J. Marden, and J. Shamma, “Learning approaches to the Witsenhausen counterexample from a view of potential games,” in Decision
and Control, 2009 held jointly with the 2009 28th Chinese Control
Conference. CDC/CCC 2009. Proceedings of the 48th IEEE Conference
on. IEEE, 2009, pp. 157–162.
[18] W. McEneaney and S. Han, “Optimization formulation and monotonic
solution method for the Witsenhausen problem,” Automatica, vol. 55,
pp. 55 – 65, 2015.
[19] J. Lee, E. Lau, and Y.-C. Ho, “The Witsenhausen counterexample:
a hierarchical search approach for nonconvex optimization problems,”
Automatic Control, IEEE Transactions on, vol. 46, no. 3, pp. 382–397,
2001.
[20] M. Mehmetoglu, E. Akyol, and K. Rose, “A deterministic annealing
approach to Witsenhausen’s counterexample,” in Information Theory
(ISIT), 2014 IEEE International Symposium on, June 2014, pp. 3032–
3036.
[21] P. Sharma, S. Salapaka, and C. Beck, “Entropy-based framework for
dynamic coverage and clustering problems,” Automatic Control, IEEE
Transactions on, vol. 57, no. 1, pp. 135–150, 2012.
[22] Y. Xu, S. Salapaka, and C. Beck, “Clustering and coverage control for
systems with acceleration-driven dynamics,” Automatic Control, IEEE
Transactions on, vol. 59, no. 5, pp. 1342–1347, 2014.
[23] A. Kwok and S. Martinez, “A distributed deterministic annealing algorithm for limited-range sensor coverage,” Control Systems Technology,
IEEE Transactions on, vol. 19, no. 4, pp. 792–804, 2011.
[24] M. Morozkov, O. Granichin, Z. Volkovich, and X. Zhang, “Fast algorithm for finding true number of clusters. Applications to control
systems,” in Control and Decision Conference (CCDC), 2012 24th
Chinese, 2012, pp. 2001–2006.
[25] K. Rose, E. Gurewitz, and G. Fox, “Vector quantization by deterministic
annealing,” Information Theory, IEEE Transactions on, vol. 38, no. 4,
pp. 1249–1257, 1992.
[26] A. Rao, D. Miller, K. Rose, and A. Gersho, “A deterministic annealing
approach for parsimonious design of piecewise regression models,”
Pattern Analysis and Machine Intelligence, IEEE Transactions on,
vol. 21, no. 2, pp. 159–173, 1999.
[27] M. Mehmetoglu, E. Akyol, and K. Rose, “Deterministic annealingbased optimization for zero-delay source-channel coding in networks,”
Communications, IEEE Transactions on, vol. 63, no. 12, pp. 5089–5100,
2015.
[28] K. Rose, “Deterministic annealing for clustering, compression, classification, regression, and related optimization problems,” Proceedings of
the IEEE, vol. 86, no. 11, pp. 2210–2239, 1998.
[29] A. El Gamal and Y. Kim, Network Information Theory. Cambridge
University Press, 2011.
[30] Y. Wu and S. Verdu, “Witsenhausen’s counterexample: A view from
optimal transport theory,” in Decision and Control and European Control
Conference (CDC-ECC), 2011 50th IEEE Conference on, 2011, pp.
5732–5737.
[31] H. Witsenhausen, “A standard form for sequential stochastic control,”
Mathematical systems theory, vol. 7, no. 1, pp. 5–11, 1973.
[32] http://lab.scl.ece.ucsb.edu/html/witsen.html.

