Logarithmic Regret for Learning Linear Quadratic Regulators Efficiently

Abstract

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.

arXiv commentAccepted for presentation at International Conference on Machine Learning (ICML) 2020

References in corpus (7)

• Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator
• Derivative-Free Methods for Policy Optimization: Guarantees for Linear Quadratic Systems
• Near optimal finite time identification of arbitrary linear dynamical systems
• Online Control with Adversarial Disturbances
• Logarithmic Regret for Online Control
• Model-Free Linear Quadratic Control via Reduction to Expert Prediction
• Naive Exploration is Optimal for Online LQR

Cited by in corpus (1)

• Sample Efficient Reinforcement Learning with Partial Dynamics Knowledge