  We consider the problem of estimating a stochastic linear time-invariant
(LTI) dynamical system from a single trajectory via streaming algorithms. The
problem is equivalent to estimating the parameters of vector auto-regressive
(VAR) models encountered in time series analysis (Hamilton (2020)). A recent
sequence of papers (Faradonbeh et al., 2018; Simchowitz et al., 2018; Sarkar
and Rakhlin, 2019) show that ordinary least squares (OLS) regression can be
used to provide optimal finite time estimator for the problem. However, such
techniques apply for offline setting where the optimal solution of OLS is
available apriori. But, in many problems of interest as encountered in
reinforcement learning (RL), it is important to estimate the parameters on the
go using gradient oracle. This task is challenging since standard methods like
SGD might not perform well when using stochastic gradients from correlated data
points (Gy\"orfi and Walk, 1996; Nagaraj et al., 2020).
  In this work, we propose a novel algorithm, SGD with Reverse Experience
Replay (SGD-RER), that is inspired by the experience replay (ER) technique
popular in the RL literature (Lin, 1992). SGD-RER 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 for standard problem settings. Thus, we provide the first
- to the best of our knowledge - optimal SGD-style algorithm for the classical
problem of linear system identification aka VAR model estimation. Our work
demonstrates that knowledge of dependency structure can aid us in designing
algorithms which can deconstruct the dependencies between samples optimally in
an online fashion.
