Abstract
There has been substantial progress recently in understanding toy problems of purely implicit signaling. These are problems where the source and the channel are implicit -- the message is generated endogenously by the system, and the plant itself is used as a channel. In this paper, we explore how implicit and explicit communication can be used synergistically to reduce control costs. The setting is an extension of Witsenhausen's counterexample where a rate-limited external channel connects the two controllers. Using a semi-deterministic version of the problem, we arrive at a binning-based strategy that can outperform the best known strategies by an arbitrarily large factor. We also show that our binning-based strategy attains within a constant factor of the optimal cost for an asymptotically infinite-length version of the problem uniformly over all problem parameters and all rates on the external channel. For the scalar case, although our results yield approximate optimality for each fixed rate, we are unable to prove approximately-optimality uniformly over all rates.
Introduction: The Challenge of Decentralized Coordination
In decentralized control systems, such as autonomous vehicle fleets or smart grids, multiple agents must coordinate to minimize global costs. Coordination typically relies on two modes of communication: explicit (via dedicated links like radio) and implicit (where control actions modify the physical state, allowing other agents to infer information). While Witsenhausen’s counterexample famously highlighted the power of implicit signaling, modern systems often have access to both.
This paper investigates the synergy between these modes. Specifically, it extends Witsenhausen’s model by adding a rate-limited external channel between controllers. The central question is: if an external channel is available, how should it be used synergistically with implicit communication to minimize total control costs?
Methodology: Semi-Deterministic Abstraction and Binning
To crack this problem, the authors first simplify the system using a semi-deterministic abstraction. In this model, real-valued signals are represented by their binary expansions. Noise is modeled as a "floor" that completely corrupts bits below a certain threshold while leaving higher-order bits untouched. This simplification allows for a clear visualization of how control inputs $u_1$ can be used to "push" state information above the noise floor.
Building on this intuition, the authors develop a binning-based quantization strategy inspired by Wyner-Ziv coding (source coding with side information). Instead of redundantly sending the same information over both channels, the first controller quantizes the state into "bins." It sends the bin index over the explicit external channel. Meanwhile, it uses its control input to push the physical system state toward the exact quantization point, transmitting the "fine" location over the noisy implicit channel. When combined at the decoder, these two pieces of information act like puzzle pieces that perfectly reconstruct the state.
Key Insights: Orthogonalizing Information
The core discovery is that implicit and explicit channels should transmit complementary, rather than redundant, data. If you send the exact same message on both, you waste power. By "orthogonalizing" the information—sending coarse bin indices explicitly and using the physical plant for fine-grained signaling—the system achieves far higher precision than either could alone.
This approach demonstrates that implicit communication is not made obsolete by external channels. In fact, using them together yields performance gains that can be arbitrarily large compared to using explicit communication naively.
Key Results
- Unbounded Improvement: The proposed synergistic binning strategy outperforms the best-known linear explicit strategies by a factor that diverges to infinity as the signal-to-noise ratio (SNR) of the initial state grows.
- Asymptotic Approximate Optimality: For infinite-length vector versions of the problem, the authors prove their strategy achieves costs within a strict constant factor (less than 8) of the theoretical lower bound. This holds uniformly over all problem parameters and external channel rates.
- Scalar Case Bounds: For the finite-length scalar case, the strategy is proven to be within a constant factor of optimal for any fixed external channel rate.
Limitations and Future Work
A primary limitation concerns the scalar (finite-length) version of the problem. While the strategy is approximately optimal for any fixed rate, the ratio between the proposed upper bound and the theoretical lower bound diverges as the external channel rate ($R_{ex}$) approaches infinity. Future work suggests using large-deviation techniques to solve the scalar problem with a Gaussian external channel and exploring how these findings apply to designing better strategies for finite-memory control systems.
Summary updated