Distributed Online System Identification for LTI Systems Using Reverse Experience Replay

Ting-Jui Chang, Shahin Shahrampour

Introduction

System identification—the process of estimating the internal mathematical parameters of a dynamical system from observed input-output data—is a foundational task in control theory, signal processing, and reinforcement learning. While offline methods, which process a complete dataset at once, are well-established, "online" or streaming identification presents significant challenges. In online settings, data arrives sequentially, and the estimator must update its model in real-time.

The primary difficulty in identifying Linear Time-Invariant (LTI) systems, typically defined by the state-space equation $x_{t+1} = Ax_t + w_t$, is the inherent temporal correlation of the data. In a time series, the current state is a direct function of the previous state and noise. Standard Stochastic Gradient Descent (SGD) applied to this stream results in biased estimators because the noise at any given step is correlated with future states. This problem is compounded in distributed environments, such as robotic swarms or sensor networks, where data is spread across multiple agents. This paper introduces DSGD-RER, a decentralized algorithm designed to overcome these biases and achieve high-accuracy identification through collaboration.

The DSGD-RER Algorithm

The proposed Distributed Stochastic Gradient Descent with Reverse Experience Replay (DSGD-RER) algorithm integrates two primary mechanisms to ensure unbiased and efficient learning across a network.

1. Reverse Experience Replay (RER)

To address the bias caused by temporal dependency, the authors employ a "Reverse Experience Replay" strategy. Each agent stores incoming streaming data in local buffers of size $B$. Rather than processing this data chronologically, the agent performs SGD updates in reverse order—from the end of the buffer back to the beginning. Mathematically, this reversal ensures that the noise realizations are independent of the "future" states (which are now processed as if they were in the past), effectively transforming a biased streaming problem into an unbiased one similar to offline learning.

2. Decentralized Consensus

Agents are arranged as nodes in a communication network. After performing a local update using the RER mechanism, agents interact with their immediate neighbors. They update their local parameter estimates by calculating a weighted average of their neighbors' estimates, governed by a doubly stochastic matrix $P$. This consensus step allows the network to aggregate information without the need for a central coordinator.

3. Buffer Gaps

To further minimize correlation between successive data batches, the algorithm implements "buffer gaps." A small segment of data is discarded between consecutive buffers, ensuring that the starting state of a new buffer is sufficiently decorrelated from the end of the previous one.

Theoretical Analysis and Experimental Setup

The authors provide a rigorous finite-time analysis of DSGD-RER. A key theoretical contribution is the derivation of an error bound (Theorem 1) that demonstrates how the estimation error decreases as the number of agents ($m$) increases. Specifically, the error scales at a rate of $1/\sqrt{m}$, suggesting that a network of 50 agents will significantly outperform a single agent even when the total data processed per agent remains constant.

Experimental Framework

The algorithm was validated using synthetic LTI systems with transition matrices ($A$) featuring eigenvalues near 0.9 to test the limits of stability. The researchers compared performance across three network topologies:

  • Net A: A fully disconnected network (no collaboration).
  • Net B: A 2-cyclic graph (each agent communicates with two neighbors).
  • Net C: A fully connected network.

Key Results

Simulations confirmed the theoretical predictions, highlighting several critical insights:

  • The Necessity of Reversal: "Vanilla" Distributed SGD (without RER) failed to converge to the true parameters in experiments. The temporal bias inherent in the LTI system prevented the standard algorithm from reaching the correct solution, whereas DSGD-RER converged reliably.
  • Collaboration and Scaling: Increasing the network size from 5 to 50 agents resulted in a marked decrease in the logarithm of the estimation error. This confirms that the algorithm successfully "pools" the statistical power of the network.
  • Connectivity Impact: The "spectral gap" of the network—a measure of how well-connected the nodes are—directly influenced the speed of convergence. The fully connected Net C reached lower error rates faster than the sparse Net B, though both outperformed the disconnected Net A.

Limitations and Future Directions

While DSGD-RER represents a significant step forward for online distributed learning, several avenues for future research remain:

  1. Heterogeneity: The current model assumes all agents observe the same system dynamics ($A$). Future work could explore scenarios where agents observe slightly different but related systems.
  2. Stability: The analysis currently focuses on stable systems ($\|A\| < 1$). Extending these proofs to unstable systems is a known challenge in the field.
  3. Non-linearity: The algorithm is designed for linear systems. Adapting the reverse replay logic for non-linear dynamical systems could broaden the application of these techniques to more complex real-world phenomena.
  4. Adaptive Control: Integrating these online estimates into an active control loop, such as a distributed Linear Quadratic Regulator (LQR), would allow for systems that learn and optimize their behavior simultaneously.

Summary updated

Abstract

Identification of linear time-invariant (LTI) systems plays an important role in control and reinforcement learning. Both asymptotic and finite-time offline system identification are well-studied in the literature. For online system identification, the idea of stochastic-gradient descent with reverse experience replay (SGD-RER) was recently proposed, where the data sequence is stored in several buffers and the stochastic-gradient descent (SGD) update performs backward in each buffer to break the time dependency between data points. Inspired by this work, we study distributed online system identification of LTI systems over a multi-agent network. We consider agents as identical LTI systems, and the network goal is to jointly estimate the system parameters by leveraging the communication between agents. We propose DSGD-RER, a distributed variant of the SGD-RER algorithm, and theoretically characterize the improvement of the estimation error with respect to the network size. Our numerical experiments certify the reduction of estimation error as the network size grows.
BibTeX
@inproceedings{chang2022distributed,
  author = {Ting-Jui Chang and Shahin Shahrampour},
  title = {{Distributed Online System Identification for LTI Systems Using Reverse Experience Replay}},
  booktitle = {CDC},
  year = {2022},
  url = {https://openreview.net/forum?id=Gwej3UkgdB},
}
Figure