Regret Lower Bounds for Learning Linear Quadratic Gaussian Systems

2022/01/05 by Ziemann, Ingvar, Sandberg, Henrik · 1 citation
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2201.01680

Abstract

TWe establish regret lower bounds for adaptively controlling an unknown linear Gaussian system with quadratic costs. We combine ideas from experiment design, estimation theory and a perturbation bound of certain information matrices to derive regret lower bounds exhibiting scaling on the order of magnitude √(T) in the time horizon T. Our bounds accurately capture the role of control-theoretic parameters and we are able to show that systems that are hard to control are also hard to learn to control; when instantiated to state feedback systems we recover the dimensional dependency of earlier work but with improved scaling with system-theoretic constants such as system costs and Gramians. Furthermore, we extend our results to a class of partially observed systems and demonstrate that systems with poor observability structure also are hard to learn to control.

Cited by

• Adversarially Robust Multitask Adaptive Control

Related

• Adaptive Control and Regret Minimization in Linear Quadratic Gaussian\n (LQG) Setting
• Regret Analysis of Learning-Based Linear Quadratic Gaussian Control with Additive Exploration
• Rate-matching the regret lower-bound in the linear quadratic regulator with unknown dynamics
• Minimal Expected Regret in Linear Quadratic Control
• Learning Linear-Quadratic Regulators Efficiently with only \√(T)\n Regret