PAC Learnability of Stable Selective State-Space Models from a Single Time Series

Selective State-Space Models (SSMs) are dynamical systems where the state-transition, input and readout maps may depend on the current input. This mechanism is central to the celebrated Mamba architecture for long-range tasks, but it is also present in more classical model classes used in control engineering and time-series predictions, such as Linear Parameter-Varying (LPV) systems. In this paper we study learnability from a single time-series for a certain class of selective SSMs of which the state-transition, input and readout maps are affine functions of suitable features of the current inputs. We propose a concrete learning algorithm and a finite-sample probabilistic $\tilde{O}(1/N^{\zeta })$, $\zeta \le 1/2$ PAC bound on the parameter-estimation (and hence prediction error) for this learning algorithm. The algorithm itself is an extension of the Ho–Kalman realization-based learning algorithm for linear systems, and it relies on computing the so-called Markov parameters of the SSMs. Our results show that the proposed class of selective SSMs satisfies the single-trajectory analogue of PAC learnability, i.e., it is possible to learn a model with high-enough probability and high-enough accuracy, given a sufficient number of data points.