Abstract

System identification bridges control theory and machine learning by providing methods to model dynamical systems from data, enabling better prediction and control [1]. Within this field, optimal experiment design and targeted exploration [2] develop methods to optimally excite dynamical systems to reduce model uncertainty, thereby (i) attaining a model with desired accuracy [3, 4], or (ii) ensuring the feasibility of a subsequent robust control design [5, 6, 7, 8, 9]. Theoretical results on optimal experiment design rely primarily on asymptotic bounds for identification error, which are valid in the limit as the amount of data approaches infinity [1]. However, in practice we only have finite data from experiments and the reliability of the model-based controller depends significantly on the quality of the data used for system identification. Recently, numerous results have been developed for non-asymptotic (finite-sample) analysis of system identification [10, 11, 12] and subsequent control [13, 14, 15]. An overview of these methods is provided in [16]. In general, these non-asymptotic results depend on excitation from applying random inputs to ensure learning, and do not optimize the inputs for excitation. Recent works [17, 18] consider targeted exploration with periodic/sinusoidal inputs, adopting a frequency-domain analysis for parameter estimation. However, neither approach explicitly accounts for transient effects [1] during input design or analysis. Hence their guarantees are contingent on the dissipation of transient error and the attainment of steady-state response. This leads to prolonged experiment durations, which may be impractical for many real-world applications.

In this paper, we design a targeted exploration strategy that ensures a desired error bound on the estimated parameters with high probability by utilizing a non-asymptotic data-dependent uncertainty bound [13, 11]. In particular, we derive a priori guarantees on the error bound that can be ensured before exploration. To shape and reduce uncertainty in a targeted manner, we consider multi-sine exploration inputs in selected frequencies and optimized amplitudes. As our main contribution, we derive sufficient conditions directly in terms of the exploration inputs that ensure a desired parameter error bound with high probability through finite-time exploration. In particular, we explicitly account for transient error due to the input and the effect of the disturbances in the design of targeted exploration. We use these sufficient conditions to formulate linear matrix inequalities (LMIs) for exploration, ensuring the desired parameter error bound. This leads to a targeted exploration design with minimal input energy based on a semidefinite program (SDP).

Outline: We first provide the setting and define the exploration objective in Section 2. We then summarize data-dependent non-asymptotic identification bounds from [13, 11] in Section 3. In Section 4, we derive sufficient conditions on the exploration data. In Section 5 we derive sufficient conditions on the exploration inputs by leveraging the theory of spectral lines [18] and explicitly accounting for transient error due to the input in the exploration design. Finally, in Section 6, we provide a numerical example to highlight the effect of the finite time of the experiment on the required input energy.

Notation: The transpose (conjugate transpose) of a matrix \( A \in \mathbb{R}^{n \times m} (\mathbb{C}^{n \times m})\) is denoted by \( A^\top\) (\( A^\mathsf{H}\) ). The positive semi-definiteness (definiteness) of a matrix \( A \in \mathbb{C}^{n \times n}\) is denoted by \( A = A^\mathsf{H} \succeq (\succ) 0\) . The Kronecker product operator is denoted by \( \otimes\) . The operator \( \mathrm{vec}(A)\) stacks the columns of \( A\) to form a vector. The operator \( \textnormal{diag}(A_1,\dots,A_n)\) creates a block diagonal matrix by aligning the matrices \( A_1,\dots,A_n\) along the diagonal. The Euclidean norm for a vector \( x\in\mathbb{R}^n\) is denoted by \( \|x\|=\sqrt{x^\top x}\) . Given a matrix \( P \in \mathbb{R}^{n \times n},\, P \succ 0\) , the weighted Euclidean norm is given by \( \|x\|_P=\sqrt{x^\top P x}\) . The largest singular value of a matrix \( A\in\mathbb{C}^{m\times n}\) is denoted by \( \|A\|\) . \( \mathbb{E}[X]\) denotes the expected value of a random variable \( X\) . \( \mathbb{P}[E]\) denotes the probability of an event \( E\) occurring.

Consider a discrete-time linear time-invariant dynamical system of the form

where time \( k \in \mathbb{N}\) , \( x_k \in \mathbb{R}^{n_\mathrm{x}}\) is the state, \( u_k \in \mathbb{R}^{n_\mathrm{u}}\) is the control input, and \( w_k \in \mathbb{R}^{n_\mathrm{x}}\) is the disturbance. It is assumed the state \( x_k\) is directly measurable. In order to simplify the exposition, we assume that the initial state \( x_0\) is zero. The true system parameters \( A_\mathrm{tr}\) , \( B_\mathrm{tr}\) are initially uncertain, and it is necessary to collect informative data through the process of exploration to enhance the accuracy of the parameters. Henceforth, we denote \( \phi_k=[x_k^\top\,, u_k^\top]^\top \in \mathbb{R}^{n_\phi}\) where \( n_\phi=n_\mathrm{x}+n_\mathrm{u}\) . The system (1) can be re-written in terms of the unknown parameter \( \theta_\mathrm{tr}=\textnormal{vec}([A_\mathrm{tr},B_\mathrm{tr}]) \in \mathbb{R}^{n_\theta}\) as

where \( n_\theta = n_\mathrm{x}n_\phi\) . We consider a filtration of \( \sigma\) -algebras \( \{\mathcal{F}_k \}_{k \geq 0}\) such that \( \phi_k\) is \( \mathcal{F}_{k-1}\) -measurable and \( w_k\) is \( \mathcal{F}_k\) -measurable.

The sub-Gaussian distributions encompass Gaussian, uniform, and other distributions with light tails. We assume that some prior knowledge on the dynamics is available.

Exploration goal: Since the true system parameters \( \theta_\mathrm{tr} = \text{vec}([A_\mathrm{tr}\) , \( B_\mathrm{tr}])\) are not precisely known, there is a necessity to gather informative data through the process of exploration. Our primary goal is to design exploration inputs that excite the system, for a fixed user chosen time \( T \in \mathbb{N}\) , in a manner as to obtain an estimate \( \hat{\theta}_T=\text{vec}([\hat{A}_T,\hat{B}_T])\) that satisfies

Here, \( D_\mathrm{des} \succ 0\) is a user-defined matrix characterizing how closely \( \hat{\theta}_T\) approximates the true parameters \( \theta_\mathrm{tr}\) . The exploration inputs are computed such that it excites the system sufficiently with minimal input energy, based on the initial parameter estimates (cf. Assumption 3). Denote \( U=[u_0^\top,…,u_{T-1}^\top]^\top \in \mathbb{R}^{T n_\mathrm{u}}\) . Bounding the input energy by a constant \( T \gamma_\mathrm{e}^2\geq 0\) can be equivalently written as

In this section, we focus on quantifying the uncertainty associated with the unknown parameters \( \theta_\mathrm{tr}=\textnormal{vec}([A_{\mathrm{tr}},B_{\mathrm{tr}}])\) . For this purpose, we first outline regularized least squares estimation, and then summarize existing results by [13, 11] that provide a data-dependent uncertainty bound on the uncertain parameters.

Given observed data \( \mathcal{D}_{T+1}=\{x_k,u_k\}_{k=0}^{T}\) of length \( T+1\) , we denote

Given (6), the regularized least squares estimate is given by

with the regularization constant \( \lambda > 0\) and the excitation

Using (7), the estimate \( \hat{\theta}_{T}\) can be expressed as

Thus, the regularized least squares error satisfies

Self-normalized Martingales: The sequence \( \{S_T \}_{ T \geq 0}\) with \( S_T=(\Phi\otimes I_{n_\mathrm{x}}) W\) is a martingale with respect to \( \{\mathcal{F}_T \}_{T=0}^\infty\) ((1), [20]). This sequence is crucial for the construction of confidence ellipsoids for \( \theta_\mathrm{tr}\) . In [13, Theorem 1], a `self-normalized bound' for the martingale \( \{S_T \}_{T \geq 0}\) is derived by assuming scalar disturbances \( w_k\) , i.e., \( n_\mathrm{x}=1\) . The following lemma generalizes the bound in [13, Theorem 1] to vector-valued disturbances, i.e., \( n_\mathrm{x} > 1\) , by utilizing covering techniques as in [11, Proposition 8.2] or [16].

The proof of Lemma 1 may be found in [11, Proposition 8.2] or [16]. In order to derive the confidence ellipsoid, we first derive a bound on \( \theta_\mathrm{tr}\) of the form \( \|\theta_\mathrm{tr}\| \leq \bar{\theta}\) . By applying the Schur complement twice to the condition in (3), we get \( (\hat{\theta}_0-\theta_\mathrm{tr})(\hat{\theta}_0-\theta_\mathrm{tr})^\top \preceq (D_0 \otimes I_{n_\mathrm{x}})^{-1}\) , from which we have

Using the triangle inequality, we have

The following theorem utilizes the result in Lemma 1 to derive a data-dependent uncertainty bound in the form of a confidence ellipsoid centered at the estimate \( \hat{\theta}_{T}\) for the uncertain parameters \( \theta_\mathrm{tr}\) .

We utilize this data-dependent uncertainty bound to design a targeted exploration strategy that achieves the exploration goal provided in (4).

Given the uncertainty bound in Theorem 1, the following theorem presents conditions on the exploration data that imply the exploration goal (4).

In contrast to standard asymptotic bounds, e.g., [6, 9], Theorem 2 depends additionally on the term \( (R(\bar{D}_T)^\frac{1}{2} + \lambda^\frac{1}{2} \bar{\theta})^2\) which is nonconvex in \( \bar{D}_T\) . Hence, in the following lemma we derive a sufficient condition that is convex in \( \bar{D}_T\) .

Note that Inequality (24) depends quadratically on \( \Phi\) , specifically on the finite excitation term \( \Phi \Phi^\top\) [18]. This further depends on the amplitudes of the inputs \( U_\mathrm{e}\) and the disturbances. Additionally, the linear mapping from the input sequence to the state sequence is uncertain due to the uncertainty in the true dynamics. These issues are addressed in the next section.

In this section, we determine sufficient conditions for exploration in terms of the spectral content of \( \Phi\) in order to pose the exploration problem directly in terms of the inputs. To this end, we first define the amplitude of a spectral line.

In what follows, we first establish the exploration strategy in Section 5.1 and then provide a bound on the excitation \( \Phi \Phi^\top\) in terms of spectral information in Section 5.2. We then explicitly account for transient error due to the input and the effect of disturbances in Section 5.3. In order to derive conditions linear in the decision variables, we provide a convex relaxation procedure in Section 5.4 and an upper bound on excitation in Section 5.5. Finally, we account for parametric uncertainty and obtain an SDP for exploration which provides us with exploration inputs that ensure the exploration goal in Section 5.6.

5.1 Exploration strategy

5.2 Bound on excitation based on spectral lines

5.3 Bounds on transient error and the effect of disturbance

5.4 Convex relaxation

5.5 Upper bound on excitation and \( \bar{D}_T\)

5.6 Bounds on transfer matrices and Exploration SDP

In this section, we demonstrate the applicability of the exploration strategy through a numerical example. Numerical simulations The source code for the simulations is available at https:\( //\) github.com\( /\) jananivenkatasubramanian\( /\) NonAsymptoticTE were performed on MATLAB using CVX [23] in conjunction with the default SDP solver SDPT3. We consider a linear system (1) with

which belongs to a class of systems identified as ‘hard to learn’ [24]. In our simulations, we set the desired error bound as \( D_\mathrm{des}^{-1}=10^4 I_{n_\phi}\) (cf. (4)). Furthermore, we select \( L=5\) frequencies \( \omega_i\in\{0,0.1,0.2,0.3,0.4\}\) and the initial estimate as \( \hat{\theta}_0=\theta_\mathrm{tr}+(4 \times 10^{-4})\mathbf{1}_{n_\mathrm{x}n_\phi}\) with initial uncertainty level \( D_0 = 10^3 I_{n_\phi}\) . We set \( \epsilon=0.5\) , \( \lambda =1\) , \( \delta = 0.05\) and \( \sigma_\mathrm{w}=0.01\) . In what follows, we study the effect of the finite duration \( T\) of the experiment on the average input energy required.

Non-asymptotic behaviour: In the asymptotic case where \( T \to \infty\) [9], the required input energy \( T\gamma_\mathrm{e}^2\) scales linearly with the desired accuracy \( \|D_\mathrm{des}\|\) . In this example, we study the effect of the exploration time \( T\) and the transient error decay, on the required input energy \( \gamma_\mathrm{e}^2\) . For this purpose, we run six trials for the following exploration times \( T \in \{ 10^{10},10^{11},10^{12},10^{13},10^{14},10^{15}\}\) . For each trial, we scale \( D_\mathrm{des}\) proportionately, yielding \( D_\mathrm{des} \in \{10^0,10^1,10^2,10^3,10^4,10^5 \}\) , respectively. Each trial comprises executing Algorithm 1 to obtain the exploration inputs (27) and average input energy \( \gamma_\mathrm{e}^2\) . In Figure 1, we see that for \( T >> 10^{12}\) , we approximately recover this linear relationship, while for \( T < 10^{11}\) , we see that the transient effects are significant and slightly more input energy is required. This particularly highlights the role of transient effects in finite-time experiment design, indicating the need for careful input design in order to mitigate transient effects even for large times \( T\) .