Robust guarantees for learning an autoregressive filter

Abstract

The optimal predictor for a linear dynamical system (with hidden state and Gaussian noise) takes the form of an autoregressive linear filter, namely the Kalman filter. However, a fundamental problem in reinforcement learning and control theory is to make optimal predictions in an unknown dynamical system. To this end, we take the approach of directly learning an autoregressive filter for time-series prediction under unknown dynamics. Our analysis differs from previous statistical analyses in that we regress not only on the inputs to the dynamical system, but also the outputs, which is essential to dealing with process noise. The main challenge is to estimate the filter under worst case input (in ${\mathcal{H}}_{\infty }$ norm), for which we use an $L^{\infty }$-based objective rather than ordinary least-squares. For learning an autoregressive model, our algorithm has optimal sample complexity in terms of the rollout length, which does not seem to be attained by naive least-squares.

27 pages

References in corpus (7)

• Gradient Descent Learns Linear Dynamical Systems
• On the Sample Complexity of the Linear Quadratic Regulator
• Online Learning for Time Series Prediction
• Non-Asymptotic Analysis of Robust Control from Coarse-Grained Identification
• Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification
• Learning Linear Dynamical Systems with Semi-Parametric Least Squares
• Spectral Filtering for General Linear Dynamical Systems

Cited by in corpus (2)

• Logarithmic Regret Bound in Partially Observable Linear Dynamical Systems
• No-Regret Prediction in Marginally Stable Systems