Learning-based Control of Unknown Linear Systems with Thompson Sampling

Abstract

We propose a Thompson sampling-based learning algorithm for the Linear Quadratic (LQ) control problem with unknown system parameters. The algorithm is called Thompson sampling with dynamic episodes (TSDE) where two stopping criteria determine the lengths of the dynamic episodes in Thompson sampling. The first stopping criterion controls the growth rate of episode length. The second stopping criterion is triggered when the determinant of the sample covariance matrix is less than half of the previous value. We show under some conditions on the prior distribution that the expected (Bayesian) regret of TSDE accumulated up to time T is bounded by O(\sqrt{T}). Here O(.) hides constants and logarithmic factors. This is the first O(\sqrt{T} ) bound on expected regret of learning in LQ control. By introducing a reinitialization schedule, we also show that the algorithm is robust to time-varying drift in model parameters. Numerical simulations are provided to illustrate the performance of TSDE.

Cited by in corpus (20)

• On the Sample Complexity of the Linear Quadratic Regulator
• A Tour of Reinforcement Learning: The View from Continuous Control
• Learning Linear-Quadratic Regulators Efficiently with only $\sqrt{T}$ Regret
• Posterior Sampling for Large Scale Reinforcement Learning
• Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes
• Robust-Adaptive Control of Linear Systems: beyond Quadratic Costs
• Combining Model-Based and Model-Free Methods for Nonlinear Control: A Provably Convergent Policy Gradient Approach
• Regret Minimization in Partially Observable Linear Quadratic Control
• Online Learning for Unknown Partially Observable MDPs
• Online Learning for Stochastic Shortest Path Model via Posterior Sampling
• Robust exploration in linear quadratic reinforcement learning
• Robust Reinforcement Learning: A Case Study in Linear Quadratic Regulation
• SLIP: Learning to Predict in Unknown Dynamical Systems with Long-Term Memory
• Revised Progressive-Hedging-Algorithm Based Two-layer Solution Scheme for Bayesian Reinforcement Learning
• Optimistic robust linear quadratic dual control
• Stable Online Control of Linear Time-Varying Systems
• System Identification via Meta-Learning in Linear Time-Varying Environments
• Exact Asymptotics for Linear Quadratic Adaptive Control
• Statistical Consistency of Set-Membership Estimator for Linear Systems
• Closed-loop Parameter Identification of Linear Dynamical Systems through the Lens of Feedback Channel Coding Theory