Gautam Goel (Simons Institute)

April 12, 2023

Title and Abstract

Competitive Control

Classical approaches to optimal control first posit a model of the environment and then design a controller which is optimal for that specific environment. We instead consider control from the perspective of competitive analysis. In the competitive control framework, we seek to design an online (causal) controller which approximates the performance of a hypothetical clairvoyant (noncausal) controller, which selects the optimal control inputs given perfect information of the disturbance sequence. A natural performance metric in this setting is competitive ratio, which is the ratio between the cost incurred by the online controller and the cost which could have been counterfactually obtained by the clairvoyant controller. A controller with low competitive ratio is guaranteed to achieve near-optimal performance regardless of what environment it encounters. Using operator-theoretic techniques from robust control, we derive a computationally efficient state-space description of the controller with optimal competitive ratio. We also describe surprising connections to gradient-based algorithms from online learning.

Bio

Gautam is a postdoc at the Simons Institute for the Theory of Computing at UC Berkeley, where he is part of the Foundations of Data Science Institute. His research interests include online learning, statistical learning theory, and connections to signal processing and control. Before joining Berkeley he was a PhD student in the Computing and Mathematical Sciences (CMS) department at Caltech, where he was advised by Babak Hassibi. His thesis was awarded the Bhansali Family Doctoral Prize in Computer Science, which is awarded by the CMS department to a single outstanding dissertation in computer science each year.