Logarithmic Regret for Learning Linear Quadratic Regulators Efficiently
  We consider the problem of learning in Linear Quadratic Control systems whose
transition parameters are initially unknown. Recent results in this setting
have demonstrated efficient learning algorithms with regret growing with the
square root of the number of decision steps. We present new efficient
algorithms that achieve, perhaps surprisingly, regret that scales only
(poly)logarithmically with the number of steps in two scenarios: when only the
state transition matrix $A$ is unknown, and when only the state-action
transition matrix $B$ is unknown and the optimal policy satisfies a certain
non-degeneracy condition. On the other hand, we give a lower bound that shows
that when the latter condition is violated, square root regret is unavoidable.
