Online Control with Multiple Sensors

We consider a variant of the partially observed online control problem where there are _multiple sensors_ which provide noisy linear measurements of the system. In our setting, the system state evolves according to a discrete-time linear dynamical system. The objective is to design an algorithm which minimizes regret relative to the best _single-sensor_ policy (within a restricted class) in hindsight. When the system and process noise is stochastic and the costs are quadratic in the control and _unobserved state_, we design an algorithm that achieves $\mathcal{O}(\mathrm{poly}\log(S)\sqrt{n})$ regret over time horizon $n$ relative to our benchmark policy class if there are $S$ sensors. Notably, this regret guarantee is with respect to the _state costs_, which are never fully observed. When the system and process noise is chosen by an oblivious adversary, and the cost functions are convex-Lipschitz (or subquadratic) functions of the control and _observations_, then a similar $\mathcal{O}(\mathrm{poly}\log(S)\sqrt{n})$ regret is achievable. While our work is the first, to our knowledge, to study this generalization of the online control problem, we remark that a na\"ive application of known results in the partially observed online control literature have regret scaling $\mathcal{O}(\mathrm{poly}(S)\sqrt{n})$, exponentially worse than our regret scaling in terms of dependence on the number of sensors. Our algorithm is based on the Follow-The-Regularized-Leader framework, and our analysis carefully exploits the $\ell_1$ geometry of the policy class.