Regret Lower Bounds for Learning Linear Quadratic Gaussian Systems
This work provides foundational theoretical insights for learning in control systems, addressing a core problem in adaptive control and reinforcement learning.
The paper tackles the problem of establishing regret lower bounds for adaptively controlling unknown linear Gaussian systems with quadratic costs, showing that systems that are hard to control are also hard to learn to control, with regret scaling as √T and capturing control-theoretic parameters.
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 $\sqrt{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.