  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.
