Rate-Optimal Regret for the Safe Learning-based Control of the Constrained Linear Quadratic Regulator

We study the problem of adaptive control of the stochastic linear quadratic regulator (LQR) with constraints that must be satisfied at every time step. Prior work on the multidimensional problem has shown tildeO(T2/3) regret and satisfaction of robust constraints, leaving open the question of whether tildeO(√T) regret can be attained in the constrained LQR setting. We contribute to this problem by showing tildeO(√T) regret and satisfaction of chance constraints. This type of constraints allow us to handle unbounded noise and also enable analytical techniques not directly applicable to robust constraints. Our proposed algorithm for this problem uses an SDP to select an optimistic policy, and then "scales back" this policy until it is verifiably-safe. Our theoretical analysis establishes regret and constraint guarantees via a key lemma that bounds the system covariance in terms of the chosen policy. This covariance-based analysis is in contrast with the cost-to-go based analysis that is typically used in adaptive LQR.