Logarithmic Regret Bound in Partially Observable Linear Dynamical Systems

Abstract

We study the problem of system identification and adaptive control in partially observable linear dynamical systems. Adaptive and closed-loop system identification is a challenging problem due to correlations introduced in data collection. In this paper, we present the first model estimation method with finite-time guarantees in both open and closed-loop system identification. Deploying this estimation method, we propose adaptive control online learning (AdaptOn), an efficient reinforcement learning algorithm that adaptively learns the system dynamics and continuously updates its controller through online learning steps. AdaptOn estimates the model dynamics by occasionally solving a linear regression problem through interactions with the environment. Using policy re-parameterization and the estimated model, AdaptOn constructs counterfactual loss functions to be used for updating the controller through online gradient descent. Over time, AdaptOn improves its model estimates and obtains more accurate gradient updates to improve the controller. We show that AdaptOn achieves a regret upper bound of $\text{polylog}\left(T\right)$, after $T$ time steps of agent-environment interaction. To the best of our knowledge, AdaptOn is the first algorithm that achieves $\text{polylog}\left(T\right)$ regret in adaptive control of unknown partially observable linear dynamical systems which includes linear quadratic Gaussian (LQG) control.

References in corpus (15)

• Improper Learning for Non-Stochastic Control
• Logarithmic Regret for Online Control
• Model-Free Linear Quadratic Control via Reduction to Expert Prediction
• Online Least Squares Estimation with Self-Normalized Processes: An Application to Bandit Problems
• Logarithmic Regret for Adversarial Online Control
• Naive Exploration is Optimal for Online LQR
• Thompson Sampling for Linear-Quadratic Control Problems
• Learning Linear Dynamical Systems with Semi-Parametric Least Squares
• Learning Linear-Quadratic Regulators Efficiently with only $\sqrt{T}$ Regret
• Online Linear Quadratic Control
• The Nonstochastic Control Problem
• Regret Minimization in Partially Observable Linear Quadratic Control
• Sample Complexity of Kalman Filtering for Unknown Systems
• No-Regret Prediction in Marginally Stable Systems
• Robust guarantees for learning an autoregressive filter

Cited by in corpus (23)

• Online Optimization with Memory and Competitive Control
• Near-Optimal Design of Safe Output Feedback Controllers from Noisy Data
• System-level, Input-output and New Parameterizations of Stabilizing Controllers, and Their Numerical Computation
• Meta-Adaptive Nonlinear Control: Theory and Algorithms
• Black-Box Control for Linear Dynamical Systems
• Adaptive Regret for Control of Time-Varying Dynamics
• Imitation and Transfer Learning for LQG Control
• Making Non-Stochastic Control (Almost) as Easy as Stochastic
• Online Learning for Unknown Partially Observable MDPs
• Neural optimal feedback control with local learning rules
• PAC-Bayes Generalisation Bounds for Dynamical Systems Including Stable RNNs
• Non-Stochastic Control with Bandit Feedback
• Distributed Online Linear Quadratic Control for Linear Time-invariant Systems
• Regret Analysis of Distributed Online LQR Control for Unknown LTI Systems
• On Uninformative Optimal Policies in Adaptive LQR with Unknown B-Matrix
• Lower Bounds on Information Requirements for Causal Network Inference
• On the Sample Complexity of Decentralized Linear Quadratic Regulator with Partially Nested Information Structure
• Stability and Identification of Random Asynchronous Linear Time-Invariant Systems
• Learning the Linear Quadratic Regulator from Nonlinear Observations
• PAC-Bayesian bounds for learning LTI-ss systems with input from empirical loss
• Geometric Exploration for Online Control
• Exact Asymptotics for Linear Quadratic Adaptive Control
• Identification and Adaptive Control of Markov Jump Systems: Sample Complexity and Regret Bounds