Witsenhausen's Counterexample: When Actions Speak
A tiny decentralized-control problem broke the linear logic of classical LQG. Connecting it to communication and information theory turned that warning into a program of constructions, converses, approximation guarantees, and new ways to see information hidden in physical action.
In this story
The small problem that broke a large intuition
Witsenhausen introduced the counterexample in 1968 to show that information patterns matter. The much later work in this story did not discover that lesson, or the usefulness of nonlinear quantization; it built new ways to expose, bound, and generalize the phenomenon.
The setup is almost perversely small. A first controller sees the initial state accurately but pays heavily to move it. A second controller can correct what remains, but sees the state only through noise. It's a team problem: the controllers share the same quadratic objective. The plant is linear, the noise is Gaussian, and the cost is quadratic — precisely the ingredients that normally make linear control feel inevitable.
What breaks that intuition is the order of knowledge. The first action changes the physical state and the observation from which the second controller must infer that state. Control and information can no longer be separated: moving the state a little may be valuable physically, while moving it toward a recognizable value may be valuable informationally. A nonlinear action can exploit both effects at once.
That was Witsenhausen's enduring warning. A controller is not simply handed information and then asked to act. In a decentralized system, one controller's action can determine what another controller will know.
The first controller sees clearly but acts weakly; the second acts strongly but sees through noise. The first action therefore changes both the state and what the second controller can infer.
Figure 1 of Demystifying the Witsenhausen Counterexample (2010), a later explanatory rendering of Witsenhausen's original setup.
From counterexample to separation
A single fixed problem can look like an isolated pathology. In 1999, working with Sanjoy Mitter, we changed the scale of the question: instead of asking only what happens at one set of parameters, we studied an asymptotic family of Witsenhausen problems. Across that family, the gap between the best linear and nonlinear strategies grows without bound. Linearity was not missing a small numerical improvement; it was missing the operative mechanism.
This scaling move came naturally from information theory, where one often learns what matters by embedding a problem in a family and asking which effects dominate. It also changed the natural nonlinear strategy. Binary quantization had appeared before. The new view used a growing collection of reproduction points — a lattice in the scalar line — so that the first controller could steer the state toward one of many recognizable values.
The asymptotics and the lattice belonged together. Scaling proved that the linear failure could be arbitrarily severe; multipoint quantization gave that failure a reusable structure.
A multipoint strategy moves the state toward one of many separated representatives. The movement costs control effort; the separation makes the result easier for the noisy second controller to recognize.
Figure 5(a) of Demystifying the Witsenhausen Counterexample (2010), illustrating the multipoint/lattice perspective introduced in Information and Control: Witsenhausen Revisited (1999).
The 1999 contribution was the asymptotic family, the resulting unbounded separation between linear and nonlinear strategies, and the multipoint/lattice perspective.
The counterexample and I met by assignment, not by choice. For my Area Exam at MIT, I was handed Witsenhausen's paper to read, present, and extend — and the extension, showing that the linear/nonlinear gap could be made arbitrarily large, became the 1999 paper with Sanjoy Mitter. I mention this for any student who wonders whether an assigned problem can matter: this one set a thread running through decades of my research.
Reading information in the action
The communication connection first pays off as explanation. Replace real amplitudes by a deterministic stack of bit levels. Observation noise wipes out low-order distinctions while sufficiently separated high-order distinctions survive. The first controller can use its action to remove or reorganize exactly the portion of the state that the second controller would otherwise be unable to distinguish.
This is implicit communication: there is no separate message wire, but the first action changes what the second controller can infer. The deterministic model is more than a cartoon. Borrowed from communication theory, it strips away inessential amplitude bookkeeping and retains the signal levels that carry operationally useful information. That makes a nonlinear strategy readable before one confronts the full Gaussian optimization problem.
There is a teaching connection here too. In Fall 2008, I co-taught Network Information Flow, a special-topics course on information theory, with David Tse; we discussed such deterministic models extensively.
The multiple-access and Witsenhausen models share a bit-level logic. The first action changes which distinctions sit above or below the noise level, and therefore which parts of the state remain inferable.
Figure 3 of Demystifying the Witsenhausen Counterexample (2010).
The first action is useful not only for where it moves the state, but for which distinctions it makes survive observation noise.
Vectorization exposes the geometry
We came back to the problem for reasons that had little to do with research strategy. The counterexample was turning forty, and a special session was being organized in its honor at the 2008 Conference on Decision and Control. We wanted to shed more light on the problem — to honor the man as well as the mathematics. (The conference was in Cancún, and Pulkit Grover was a great student who deserved a treat.) The high-dimensional version suggested itself because our hands were already warm: we had been studying the decoding of channel codes, and had been drawn to dirty-paper coding in other contexts, and both felt as if they might finally have something to say here.
The vector extension turns a scalar staircase into source-channel geometry. The first controller chooses a nearby codepoint. Covering determines how far the state must move to reach a codepoint; packing determines whether noise will make that point confusable with another. The two control costs become the two sides of a familiar coding problem.
That connection brought techniques, not merely vocabulary. Rate-distortion theory supplies converses on how cheaply a source can be made recoverable. Dirty-paper coding supplies achievability ideas for communicating while acting against a known host or interference. Joint source-channel coding and information embedding suggest useful constructions. Recasting the vector problem as assisted interference suppression made these tools available, producing bounds that also sharpened understanding of the scalar case.
High dimension did not replace Witsenhausen's original puzzle. It more fully revealed the geometry that the scalar lattice was hinting at.
Two geometries, two costs. Left: the covering radius controls how far the first controller may need to move the state to a lattice point. Right: the packing radius controls how much observation noise can be tolerated before the second controller confuses neighboring points.
Figure 2 of Approximately Optimal Solutions to the Finite-Dimensional Witsenhausen Counterexample (2013); the two original panels are paired here without alteration.
The communication interpretation imported a working toolkit: lattice constructions and dirty-paper ideas for upper bounds; rate-distortion and sphere-packing ideas for lower bounds. The connection changed what strategies could be designed and what limits could be proved.
It came in two steps, and the second was not a theorem. The new lower bound we presented at that CDC made us suspect we were onto something. Certainty came while preparing the talk itself: we needed a picture of dirty-paper coding that a control audience could read at a glance, and the strategy we drew — the state pulled to the nearest point of a lattice — looked strikingly like the plots from the neural-network searches of Baglietto, Parisini, and Zoppoli a decade earlier. Search had found the same shape that coding theory was now deriving by construction, and when two very different methods agree on a picture, you are usually looking at something real. The journal version records the correspondence explicitly: the DPC scheme "turns out to be a vector extension" of those neural schemes. Below, an original neural-search plot sits beside the later scalar and vector pictures.
The resemblance that made the connection convincing. Upper left: the solid neural-control curve from Baglietto, Parisini, and Zoppoli's Figure 4 (). Upper right: the later scalar schematic's green staircase. The axes and parameters differ, so this is a comparison of shapes rather than values. Below: the same idea extended to vector dirty-paper coding.
Upper left: Figure 4 of Numerical Solutions to the Witsenhausen Counterexample by Approximating Networks (2001). Right and lower panels: Figure 11 of Witsenhausen's Counterexample as Assisted Interference Suppression (2010). Panels are cropped and arranged for comparison.
Understanding without solving exactly
Witsenhausen's scalar problem still has no closed-form optimal controller. But exact optimization is not the only form of understanding. The next step was to pair explicit nonlinear strategies with lower bounds and ask whether their costs remain within a controlled multiplicative factor for every parameter regime.
The vector and asymptotic work first showed that lattice strategies have the right order. A large-deviation sphere-packing philosophy then carried the converse through finite dimensions and back to the scalar problem. The result was a sequence of uniform approximation guarantees: not a claim that a particular staircase is exactly optimal, but a proof that no hidden strategy is orders of magnitude better.
This matters scientifically. A constant-factor approximation identifies the mechanism that any dramatically better controller would have to beat. It separates robust structure from a fortunate numerical curve, and it turns a famous open optimization problem into something theory can still constrain.
The original scalar problem is not solved exactly. The 2013 finite-dimensional paper proves that regular lattice strategies are within a factor of 100 of its lower bound in the scalar case; computation suggests the gap may be no larger than about 8. The factor 8 is numerical evidence, not the theorem.
What signaling was hiding
Calling the first action a signal is useful, but incomplete. Generalized variants of the counterexample make that limitation visible: change the ordering or information structure and implicit communication can become useless, harmful, or impossible, with linear strategies returning as optimal. Signaling is not a magic property of decentralization; it depends on the architecture.
The sharper distinction is between an implicit channel and source simplification. An action may communicate information about a state to a later controller. But it may also change the state into something easier to estimate. In ordinary communication, the encoder describes a fixed source. In Witsenhausen's problem, the first controller can move the source toward a small, robust set of representatives before the second controller ever sees it.
The source-simplification paper concluded that this second role is the more significant one in the counterexample. That refinement keeps the communication connection honest: information theory supplied powerful constructions and converses, while the control problem exposed where the conventional fixed-source model was too narrow.
The first controller does not merely send information about the old state. It changes the state into one that needs less information to understand.
Compare three stated scalar policies for a Gaussian initial state with standard deviation 5: no first action, a numerically optimized linear policy, and nearest-lattice movement followed by nearest-lattice decoding. The cost bars separately show weighted movement and residual error, averaged by numerical Gaussian integration. The selected state is a worked example; it does not determine those averages. The original-state comparison exposes information erased within each lattice cell.
An original interactive illustration of the lattice and source-simplification ideas discussed in Demystifying the Witsenhausen Counterexample and The Source-Simplification Aspect of Signaling. This policy comparison is not a claim of nonlinear optimality or a numerical reproduction of a paper figure.
Computation later reinforced the value of structure. Neural-network experiments found many local minima with generic architectures, while networks biased toward the slopey quantizers suggested by theory more reliably found strong strategies. Even in two dimensions, learned strategies could improve on simply applying the best scalar policy coordinate by coordinate. The lesson was not that a neural network had solved Witsenhausen, but that computation became more informative when its architecture inherited what analysis had already uncovered. Neural networks thus bracket this story from both ends: in the 1990s, search found the shape before there was a theory to explain it; two decades later, the theory told search where to look.
Words and actions should not repeat each other
Witsenhausen remains the spine of this story, but the communication connection created traffic in both directions. Information theory and coding supplied new ways to construct controllers and prove limits; control problems in turn suggested new communication models and theorems.
Add a low-rate explicit channel to a Witsenhausen-like system, and the best design does not use words to repeat what the physical action already reveals. The implicit path carries coarse distinctions that survive noise. The explicit link supplies the finer bin index most likely to be lost. Binning, familiar from source coding with side information, becomes a constructive control strategy: each path carries the information that the other preserves poorly.
The physical action and the explicit channel carry complementary information. Coarse location is available through the implicit path; the repeated color, or bin index, sent explicitly resolves distinctions that observation noise would erase.
Figure 5.6 of Pulkit Grover's dissertation, Actions Can Speak More Clearly Than Words (2010). The binning strategy is developed in Synergistic Implicit and Explicit Communication in Decentralized Control (2010).
A finite binning example: thirteen equally likely lattice states, Gaussian observation noise, and one noiseless explicit bit. Compare the exact posterior distributions after a sign bit and an alternating lattice-index bit. The uncertainty is conditional on the displayed observation, not an average control cost. Both the local-ambiguity and coarse-ambiguity presets matter: a useful message depends on what the physical observation already reveals.
An original toy illustration inspired by the binning construction in Synergistic Implicit and Explicit Communication in Decentralized Control and Actions Can Speak More Clearly Than Words. The finite uniform prior is chosen for this lab; it is not the full optimization problem or a reproduction of the paper's performance guarantees.
One action can play three roles. The information-embedding work distinguished physical regulation, making the state easier to estimate, and embedding an independent message. Different systems and objectives value these roles differently; naming them makes the theory portable without pretending that every useful nonlinear action is the same kind of signaling.
Network coding becomes a control theorem
The connection to network coding went further. The algebraic mincut-maxflow theorem generalized the classical result to linear time-invariant networks whose edges carry transfer functions rather than scalar capacities. A new network-linearization argument converted arbitrary relay topology into an equivalent acyclic form and showed that the algebraic mincut is achievable by an LTI scheme.
That theorem could then be brought back to decentralized control. By externalizing the information flow implicit in LTI controllers, the capacity-stabilizability work related whether a plant can be stabilized to the capacity of the induced network. This was not simply a communication metaphor for a known control condition: connecting linear systems and network coding produced a theorem and a new way to derive control limits.
Witsenhausen suggested looking for communication hidden inside control. Network coding then supplied an algebraic language for that hidden flow, while linear-systems structure led in return to a mincut-maxflow theorem for networks of transfer functions.
Backlog is an implicit channel
The queueing work begins with a creative change of viewpoint. A backlog is normally treated as delay or unfinished work. But it is also an observed physical state whose evolution depends on upstream information. A downstream decision-maker can infer system parameters from queue lengths even when no explicit protocol message was sent: the backlog itself is an implicit channel.
Once seen that way, information theory supplies the lower-bound technique. A communication-simulation reduction turns a queueing policy with a certain performance into a communication scheme with corresponding performance. Communication limits then imply queue-length and cost limits. The resulting tradeoff is important, but it follows from the central insight: refusing explicit protocol information may not remove communication cost; it may store that cost in the physical queue.
The communication system induced by a queueing policy. Relay behavior acts as a transmitter; the observable queue lengths form the channel output; downstream costs let the receiver decode information about the upstream parameters.
Figure 2 of Queue Length as an Implicit Communication Channel (2013).
The same habit extends through time. In infinite-horizon decentralized LQG, the plant becomes an ongoing medium through which controllers repeatedly reveal information, and deterministic communication models expose that continuing exchange. The broader lesson is not that every action should be treated as a codeword. It is that the informational consequences of action are part of the system, whether a designer exploits them deliberately or pays for them accidentally.
What the counterexample became
Witsenhausen's counterexample remains open if open means a formula for the exact optimal scalar controller. But it is no longer only a warning that linear control can fail. It became a meeting point where control drew on information-theoretic scaling, coding constructions, deterministic models, geometric converses, and network-flow ideas — while control problems suggested new communication questions in return.
That movement across fields is what advanced the subject. Asymptotics made the nonlinear separation impossible to dismiss. Lattices made the strategy geometric. Rate-distortion, dirty-paper coding, and sphere packing made approximation provable. Source simplification revealed the limits of the channel metaphor. Algebraic flow and communication simulation carried the same mode of thought into networks and queues.
The counterexample endured because it made one uncomfortable fact impossible to ignore: in decentralized control, acting and communicating are sometimes the same event. Recognizing that connection changes not only how the system is described, but which mathematics becomes available to understand it.
The papers
Eight of the twenty papers collected under this story are shown below; the "Explore this story's papers" link opens the full set. They follow the main Witsenhausen spine first: asymptotic separation, vectorization, finite-dimensional approximation, information-theoretic bounds, retrospective explanation, and later computation. The associated story collection also includes the interpretive and branching papers on generalized information patterns, source simplification, explicit/implicit synergy, information embedding, algebraic network flow, ongoing signaling, and queues as channels.