Learning Linear-Quadratic Regulators Efficiently with only $\sqrt{T}$ Regret

Abstract

We present the first computationally-efficient algorithm with $\tilde{O}(\sqrt{T})$ regret for learning in Linear Quadratic Control systems with unknown dynamics. By that, we resolve an open question of Abbasi-Yadkori and Szepesvári (2011) and Dean, Mania, Matni, Recht, and Tu (2018).

References in corpus (4)

• Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator
• On the Sample Complexity of the Linear Quadratic Regulator
• Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification
• Learning-based Control of Unknown Linear Systems with Thompson Sampling

Cited by in corpus (14)

• Logarithmic Regret Bound in Partially Observable Linear Dynamical Systems
• Variance-reduced $Q$-learning is minimax optimal
• Finite-time Analysis of Approximate Policy Iteration for the Linear Quadratic Regulator
• From self-tuning regulators to reinforcement learning and back again
• Logarithmic regret for episodic continuous-time linear-quadratic reinforcement learning over a finite-time horizon
• Combining Model-Based and Model-Free Methods for Nonlinear Control: A Provably Convergent Policy Gradient Approach
• The Nonstochastic Control Problem
• Regret-optimal control in dynamic environments
• Non-Stochastic Control with Bandit Feedback
• Task-Optimal Exploration in Linear Dynamical Systems
• On Uninformative Optimal Policies in Adaptive LQR with Unknown B-Matrix
• Regret Bounds for LQ Adaptive Control Under Database Attacks (Extended Version)
• Continuous Control with Contexts, Provably
• Geometric Exploration for Online Control