Northwestern Institute on Complex Systems
Towards understanding goal-oriented communication: The many wonders of Witsenhausen’s counterexample
Wednesdays@NICO Seminar, Noon, November 7, Chambers Hall, Lower Level
Prof. Cedric Langbort, University of Illinois Urbana-Champaign
Understanding why and how groups communicate is a central question in many fields, from biology and linguistics to economics and, recently, computer science, control engineering, and robotics.
A thesis that is particularly relevant to these latter fields is that at least some form of communication is goal-oriented, i.e., that group communication occurs as a means to enable the group to perform a joint task, and to do so more efficiently than non-communicating individuals. A natural question, then, is "how does communication emerge endogenously from a group task specification?" and "what kind of 'language' is created in the process?"
In 1968, Hans Witsenhausen, a prominent control and information theorist, formulated a simple-looking two-stage optimization problem to model decentralized decision-making in a team of agents (in this case, two of them). In spite of the team cost being quadratic and the dynamics between stages being linear, he showed that the optimal control strategy must be nonlinear, and involve some kind of communication between agents (known as "signaling"), due to the unusual information structure specifying what is known to them at decision time. It was deemed a ``counterexample" since simpler linear quadratic problems had yielded linear optimal decision strategies.
For over forty years, the exact form of the nonlinear optimal control strategy in the Witsenhausen counterexample has remained elusive, but provably good approximations and structural results (is the optimal solution continuous? of bounded variations?...) are now available.
In this talk, I will review these results and present several variants of Witsenhausen's counterexample that all yield their own set of surprises and lead to the emergence of their own type of signaling... or not. Implications and insights in terms of goal-oriented communication and applications will be discussed.
Cedric Langbort is currently on sabbatical at UC Berkeley from the University of Illinois at Urbana-Champaign (UIUC), where he is an associate professor of Aerospace Engineering and affiliated with the Decision & Control Group at CSL. Prior to joining UIUC in 2006, he studied at the Ecole Nationale Superieure de l'Aeronautique et de l'Espace - Supaero in Toulouse (France), the Institut Non-Lineaire in Nice, and Cornell University, from which he received his Ph.D. in January 2005. He also spent a year and a half as a postdoctoral scholar in the Center for the Mathematics of Information at Caltech. He works on applications of control, game, and optimization theory to a variety of fields; most recently to "smart infastructures" problems within the Center for People & Infrastructures which he co-founded and co-directs at CSL. He is a recipient of the NSF CAREER Award, the advisor of a IEEE CDC best student paper award recipient, and a subject editor for OCAM, the journal of Optimal Control Applications and Methods.