Exact Asymptotics for Linear Quadratic Adaptive Control

Abstract

Recent progress in reinforcement learning has led to remarkable performance in a range of applications, but its deployment in high-stakes settings remains quite rare. One reason is a limited understanding of the behavior of reinforcement algorithms, both in terms of their regret and their ability to learn the underlying system dynamics---existing work is focused almost exclusively on characterizing rates, with little attention paid to the constants multiplying those rates that can be critically important in practice. To start to address this challenge, we study perhaps the simplest non-bandit reinforcement learning problem: linear quadratic adaptive control (LQAC). By carefully combining recent finite-sample performance bounds for the LQAC problem with a particular (less-recent) martingale central limit theorem, we are able to derive asymptotically-exact expressions for the regret, estimation error, and prediction error of a rate-optimal stepwise-updating LQAC algorithm. In simulations on both stable and unstable systems, we find that our asymptotic theory also describes the algorithm's finite-sample behavior remarkably well.

References in corpus (11)

• StarCraft II: A New Challenge for Reinforcement Learning
• Safe Model-based Reinforcement Learning with Stability Guarantees
• Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator
• Logarithmic Regret Bound in Partially Observable Linear Dynamical Systems
• Online Least Squares Estimation with Self-Normalized Processes: An Application to Bandit Problems
• Learning-based Control of Unknown Linear Systems with Thompson Sampling
• Naive Exploration is Optimal for Online LQR
• Logarithmic Regret for Adversarial Online Control
• Thompson Sampling for Linear-Quadratic Control Problems
• Learning nonlinear dynamical systems from a single trajectory
• Non-asymptotic and Accurate Learning of Nonlinear Dynamical Systems