Rate-Matching the Regret Lower-Bound in the Linear Quadratic Regulator with Unknown Dynamics

The theory of adaptive learning-based control currently suffers from a mismatch between its empirical performance and the theoretical characterization of its performance, with consequences for, e.g., the understanding of sample efficiency, safety, and robustness. The linear quadratic regulator with unknown dynamics is a fundamental adaptive control setting with significant structure in its dynamics and cost function, yet even in this setting the ratio between the best-known regret or estimation error upper bounds and their corresponding best-known lower bounds is unbounded due to polylogarithmic factors in
$T$
. This gap has not been closed in any of the many papers theoretically studying the linear quadratic regulator with unknown dynamics, and indeed similar gaps have plagued other areas of theoretical online learning such as reinforcement learning. The contribution of this paper is to close that gap by establishing a novel regret upper-bound of
$O_{p}(\sqrt{T})$
, and simultaneously establishes an estimation error bound on the dynamics of
$O_{p}(T^{-1/4})$
. The two keys to our improved proof technique are (1) a more precise upper- and lower-bound on the system Gram matrix by establishing exact rates of eigenvalues from different sub-spaces and (2) a self-bounding argument for the expected estimation error of the optimal controller. Our technique may shed light on removing polylogarithmic factors in other adaptive learning problems.