# Streaming Linear System Identification with Reverse Experience Replay

arXiv: https://arxiv.org/abs/2103.05896 · HTML: https://mlsanity.com/paper/2103.05896/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 59 references that are in the map.
- First posted on arXiv 10 Mar 2021.

## Builds on (most cited first, 29 of 29)

- [Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification](https://mlsanity.com/paper/1802.08334/) (2018)
- [Online Control with Adversarial Disturbances](https://mlsanity.com/paper/1902.08721/) (2019)
- [Near optimal finite time identification of arbitrary linear dynamical systems](https://mlsanity.com/paper/1812.01251/) (2018)
- [Gradient Descent Learns Linear Dynamical Systems](https://mlsanity.com/paper/1609.05191/) (2016)
- [Non-asymptotic Identification of LTI Systems from a Single Trajectory](https://mlsanity.com/paper/1806.05722/) (2018)
- [Finite Sample Analysis of Stochastic System Identification](https://mlsanity.com/paper/1903.09122/) (2019)
- [Finite Time Identification in Unstable Linear Systems](https://mlsanity.com/paper/1710.01852/) (2017)
- [Online Linear Quadratic Control](https://mlsanity.com/paper/1806.07104/) (2018)
- [Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms](https://mlsanity.com/paper/2006.08916/) (2020)
- [The Nonstochastic Control Problem](https://mlsanity.com/paper/1911.12178/) (2019)
- [Learning Linear Dynamical Systems via Spectral Filtering](https://mlsanity.com/paper/1711.00946/) (2017)
- [Logarithmic Regret Bound in Partially Observable Linear Dynamical Systems](https://mlsanity.com/paper/2003.11227/) (2020)
- [Learning nonlinear dynamical systems from a single trajectory](https://mlsanity.com/paper/2004.14681/) (2020)
- [Black-Box Control for Linear Dynamical Systems](https://mlsanity.com/paper/2007.06650/) (2020)
- [Regularized estimation in sparse high-dimensional time series models](https://mlsanity.com/paper/1311.4175/) (2013)
- [Non-asymptotic and Accurate Learning of Nonlinear Dynamical Systems](https://mlsanity.com/paper/2002.08538/) (2020)
- [Finite-time Identification of Stable Linear Systems: Optimality of the Least-Squares Estimator](https://mlsanity.com/paper/2003.07937/) (2020)
- [A Neural Autoregressive Approach to Collaborative Filtering](https://mlsanity.com/paper/1605.09477/) (2016)
- [Online Learning of the Kalman Filter with Logarithmic Regret](https://mlsanity.com/paper/2002.05141/) (2020)
- [Sample Complexity Lower Bounds for Linear System Identification](https://mlsanity.com/paper/1903.10343/) (2019)
- [No-Regret Prediction in Marginally Stable Systems](https://mlsanity.com/paper/2002.02064/) (2020)
- [On-Line Learning of Linear Dynamical Systems: Exponential Forgetting in Kalman Filters](https://mlsanity.com/paper/1809.05870/) (2018)
- [Low Rank and Structured Modeling of High-dimensional Vector Autoregressions](https://mlsanity.com/paper/1812.03568/) (2018)
- [Sample Complexity of Kalman Filtering for Unknown Systems](https://mlsanity.com/paper/1912.12309/) (2019)
- [SLIP: Learning to Predict in Unknown Dynamical Systems with Long-Term Memory](https://mlsanity.com/paper/2010.05899/) (2020)
- [Non-asymptotic Closed-Loop System Identification using Autoregressive Processes and Hankel Model Reduction](https://mlsanity.com/paper/1909.02192/) (2019)
- [Reverse Experience Replay](https://mlsanity.com/paper/1910.08780/) (2019)
- [Theory and Algorithms for Forecasting Time Series](https://mlsanity.com/paper/1803.05814/) (2018)
- [A Robotic Model of Hippocampal Reverse Replay for Reinforcement Learning](https://mlsanity.com/paper/2102.11914/) (2021)

## Built on by (most cited first, 17 of 17)

- [Stochastic Gradient Descent under Markovian Sampling Schemes](https://mlsanity.com/paper/2302.14428/) (2023)
- [Adapting to Mixing Time in Stochastic Optimization with Markovian Data](https://mlsanity.com/paper/2202.04428/) (2022)
- [Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs](https://mlsanity.com/paper/2110.08440/) (2021)
- [Near-optimal Offline and Streaming Algorithms for Learning Non-Linear Dynamical Systems](https://mlsanity.com/paper/2105.11558/) (2021)
- [Understanding Deep Neural Function Approximation in Reinforcement Learning via ε-Greedy Exploration](https://mlsanity.com/paper/2209.07376/) (2022)
- [Introspective Experience Replay: Look Back When Surprised](https://mlsanity.com/paper/2206.03171/) (2022)
- [Distributed Online System Identification for LTI Systems Using Reverse Experience Replay](https://mlsanity.com/paper/2207.01062/) (2022)
- [Long-Context Linear System Identification](https://mlsanity.com/paper/2410.05690/) (2024)
- [Lifelong Learning of Video Diffusion Models From a Single Video Stream](https://mlsanity.com/paper/2406.04814/) (2024)
- [Multiscale replay: A robust algorithm for stochastic variational inequalities with a Markovian buffer](https://mlsanity.com/paper/2601.01502/) (2026)
- [High-Probability Bounds for SGD under the Polyak-Lojasiewicz Condition with Markovian Noise](https://mlsanity.com/paper/2603.14514/) (2026)
- [Finite-Time Analysis of Temporal Difference Learning with Experience Replay](https://mlsanity.com/paper/2306.09746/) (2023)
- [Regret Analysis of Distributed Online Control for LTI Systems with Adversarial Disturbances](https://mlsanity.com/paper/2310.03206/) (2023)
- [The Complexity of Sequential Prediction in Dynamical Systems](https://mlsanity.com/paper/2402.06614/) (2024)
- [Efficient Continual Finite-Sum Minimization](https://mlsanity.com/paper/2406.04731/) (2024)
- [A Tighter Convergence Proof of Reverse Experience Replay](https://mlsanity.com/paper/2408.16999/) (2024)
- [High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependence](https://mlsanity.com/paper/2606.26316/) (2026)

## Abstract (arXiv)

We consider the problem of estimating a linear time-invariant (LTI) dynamical system from a single trajectory via streaming algorithms, which is encountered in several applications including reinforcement learning (RL) and time-series analysis. While the LTI system estimation problem is well-studied in the em offline setting, the practically important streaming/online setting has received little attention. Standard streaming methods like stochastic gradient descent (SGD) are unlikely to work since streaming points can be highly correlated. In this work, we propose a novel streaming algorithm, SGD with Reverse Experience Replay (mathsfSGD-mathsfRER), that is inspired by the experience replay (ER) technique popular in the RL literature. mathsfSGD-mathsfRER divides data into small buffers and runs SGD backwards on the data stored in the individual buffers. We show that this algorithm exactly deconstructs the dependency structure and obtains information theoretically optimal guarantees for both parameter error and prediction error. Thus, we provide the first -- to the best of our knowledge -- optimal SGD-style algorithm for the classical problem of linear system identification with a first order oracle. Furthermore, mathsfSGD-mathsfRER can be applied to more general settings like sparse LTI identification with known sparsity pattern, and non-linear dynamical systems. Our work demonstrates that the knowledge of data dependency structure can aid us in designing statistically and computationally efficient algorithms which can "decorrelate" streaming samples.