Identification of Analytic Nonlinear Dynamical Systems with Non-asymptotic Guarantees
Authors: Negin Musavi
Ziyao Guo
Geir Dullerud
Yingying Li
Venue: NeurIPS 2024 poster (2024)
Keywords: set-membership
least-squares
nonlinear systems
non-asymptotic guarantees
Primary area: learning_theory
TL;DR: This paper generalizes the system estimation conditions for nonlinear control systems under i.i.d. inputs and provides non-asymptotic analysis.

Abstract: This paper focuses on the system identification of an important class of nonlinear systems: nonlinear systems that are linearly parameterized, which enjoy wide applications in robotics and other mechanical systems. We consider two system identification methods: least-squares estimation (LSE), which is a point estimation method; and set-membership estimation (SME), which estimates an uncertainty set that contains the true parameters. We provide non-asymptotic convergence rates for LSE and SME under  i.i.d. control inputs and control policies with i.i.d. random perturbations, both of which are considered as non-active-exploration inputs. Compared with the counter-example based on piecewise-affine systems in the literature, the success of non-active exploration in our setting relies on a key assumption about the system dynamics: we require the system functions to be real-analytic. Our results, together with the piecewise-affine counter-example, reveal the importance of differentiability in nonlinear system identification through non-active exploration. Lastly, we numerically compare our theoretical bounds with the empirical performance of LSE and SME on a pendulum example and a quadrotor example.

Identification of Analytic Nonlinear Dynamical Systems with Non-asymptotic Guarantees
Negin Musavi nmusavi20illinois edu
Ziyao Guo
ziyaog20illinois. edu
Geir Dullerud dullerud@illinois. edu
Yingying Li y1101@illinois. edu
Coordinated Science Laboratory University of Illinois Urbana- Chbama-Champaign
Abstract
This paper focuses on the system identification of an important class of nonlinear systems: nonlinear systems that are linearly parameterized, which enjoy wide applications in robotics and other mechanical systems. We consider two system identification methods: least-squares estimation (LSE), which is point estimation method; and set- set-membership estimation (SME), which estimates uncertainty set that contains the true parameters. We provide non-asymptotic convergence rates for LSE and SME under i.i.d. control inputs and control policies with i.i.d. random perturbations, both of which are considered non-active-expe eexplveeepplooation inputs. Compared with the counter-example based piecewise-affiin systems in the literature, the success non-active exploration our setting relies on a key assumption about the system dynamics: we require the system functions real-analytic. Our results, together with the piecewise- reveal the importance of differentiability in nonlinear system identification through non-active exploration. Lastly, we numerically compare our theoretical bounds with the empirical performance of LSE and SME on pendulum example and quadrotor example.
counter-exx pounter-example,
Introduction
Learning control-dynamical systems with statistical methodology has received significant attention in the past decade (Sarker et al., 2023 Li et al., 2023b Chen and Hazan [222 Simchowitz and Foster 2020; Wagenmaker and Jamieson 2020 Simchowitz et al., 2018]] Dean al. [2188] Abbasi- Yadaori and Szepesvári 2011; Li et al. (2221b). In particular, the estimation of linear dynamical systems, e.g. Tt-1 = A" 13" + W relatively well-studied: it has been shown that non-active exploration by i.i.d. noises control inputs Me and system disturbances w; are already enough for accurate system identification, and least square estimation (LSS) can achieve the optimal estimation convergence rate Simchowitz and Foster 2020; Simchowitz et al. 2018).
However, nonlinear control systems ubiquitous in real-world applications, e.g. robotics (Siciliano et al.
Alaimo et al. 2013), power systems (Simpson- Porco el al.) (0066), transportation (Kong al. 2015 etc. Motivated by this, there has been a lot of attention on learning nonlinear systems recently. One natural and popular direction to study nonlinear system identification is on learning linearly parameterized nonlinear systems defined below, which is straightforward extension from
2010
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

the standard linear systems (Mania et al.
2022 K Khosravi 2023
Foster et al. 2020
F++1 0_ ( Ut) + wy
where 0_ is vector of unknown parameters and 6(12,, U4) is known vector of nonlinear features.
On the one hand, some classes of these systems are shown enjoy similar benefits of linear systems. For example, bilinear systems can also be estimated by LSE under non-active exploration with i.i.d. noises (Sattar et al., 2022), as well linear systems with randomly perturbed nonlinear policies (Li et al. 2023bb.
On the other hand, it is also known that non-active exploration is insufficient for general linearly parameterized nonlinear systems. In particular, (Mania et al., 2022) provides a counter example showing that non-active exploration is insufficient to learn accurate models under piece-wise affine feature functions. This motivates a sequence of follow-up work on the design of active exploration for nonlinear system estimation, which is largely motivated by the non-smooth feature functions such as ReLu in neural networks (Mania et al. 2022 Kowshik et al. 2021 Khosravi 2023).
exploration
However, there is big gap between bilinear systems, which is infinitely differentiable, and the counter example by non-smooth systems. A natural question is: to what extent can non-active exploration still work for linearly parameterized nonlinear systems?
Contributions. One major contribution of this paper is showing that LSE with non-active i.i.d. noises can efficiently learn any linearly parameterized nonlinear systems with real-analytic feature functions and provide a non-asymptotic convergence rate. Notice that real-analytic feature functions common in physical systems. For example, polynomial systems satisfy this requirement and have wide applications in power systems (Simpson- Porco et al. 2016), fluid dynamics (Noack et al., 2003), )
etc. Further, trigonometric functions also satisty the real-analyti property so large range of robotics and mechanical systems also satisfy this requirement (Siciliano et al. 2010 Alaimo et al. 2013
A side product of our LSE convergence rate analysis is the convergence rate for another commonly used uncertainty quantification method in control: set membership estimation (SME).
Numerically, we test our theoretical results in pendulum and quadrotor systems. Simulations show that LSE and SME can indeed efficiently explore the system and converge the true parameter under non-active exploration noises.
Technically, the key step in our proof is establishing the block moeck-mrttigalle-iie sisecsmmallaaall condition (BMSB) for general analytic feature functions, which greatly generalizes the bilinear feature function in Sattar al. (2022). Our result is built on an intuition inspired by the counter example in MMania et al. 2022): the counter example in (Mania et al.) 2022) requires that some feature function is zero in certain region, so nothing can be learned about its parameter if the states stay in this region. However, analytic functions cannot be a constant zero in positive-measure region unless it is a constant zero everywhere. Therefore, the counter example does not work, and non-active exploration around any states can provide some useful information. Our proof formalizes this intuition by utilizing the Paley-Zygmund Petrov inequality (Petrov) 2007).
Related work. Inspired by neural network parameterization, nonlinear systems of the form T++11 = ((A,r;) + W; is also studied in the literature, where <(-) is a known nonlinear link function and A. is unknown. The least square cost is no longer quadratic or even convex in this case and various optimization methods have been proposed learn this type of systems (Kowshik al. 202T Sattar
ct al.
2022 Foster et al. 2020).
Another related line of research focuses on nonlinear regression with dependent data (Ziemann and Tu 2022 Ziemann et al., 2023 2024) which can be applied to nonlinear system identification. The nonlinear regression in (Ziemann and Tu 2022 Ziemann et al. 2023 2024 is based non- parametric LSE and its variants, and their convergence rates under different scenarios have been analyzed. It is interesting to note that this line of work usually assumes certain persistent excitation assumptions 2 whereas our paper demonstrates that persistent excitation holds by establishing the BMSB condition for linearly parameterized and real-analytic nonlinear control systems.
yy fwx) + we considered, where ze and y correlate with the historical data. FFrr example, Zieeannn and Tu 2022) assumes hyper contracttttttiiitty. and (Ziemann et al. 2024 assumes the empirical covariance of the {ze process is invertible with high probability (Corollary 3.2).

---

Uncertainty set estimation is crucial for robust control under model uncertainties Lu and Cannon
(2023); Lorenzen al. (2019): Li et al. (2021a). SME is a widely adopted uncertainty set estimation
method in robust adaptive control (Lorenzen et al. 2019 Lu and Cannon 2023 Bertsekas) 1971| Bai
et 1995). Recently, there is an emerging interest in analyzing SME's convergence and convergence rate for dynamical systems ([.i et al. 2024, Lu et al.
2019;] Xu and Li (024). because previous
analysis focus more on the linear regression problem (c.g. (Akçay) 2004 Bai et al.
1998)). There are
also recent applications of SME to online control Yu et al. (2023), power systems
Ych et al. (2024),
and computer vision Gao et al. al.a (2024); Tang et al. (2024).
The set of non-negative real numbers is denoted by Rzo. The notation [-] stands for the ceiling function. For a real vector 2 E IR", represents its Eg norm, ||=||oc represents its &oo norm, and 2" represents its i-th component with i = 11...2. n. The set of real symmetric matrices is denoted by S". For a real matrix Z. 2T represents its transpose, / its maximum singular value, | its Frobenius norm, a minn (Z) its minimum singular value, vec( 2) its vectorization obtained by stacking its columns, and for a real square matrix Z, tr(Z) represents its trace. For a real symmetric matrix Z, 2 0 and Z > 0 indicate that Z is positive definite and positive semi-definite, respectively. For a measurable set C R", (E)) represents its Lebesgue measure in R" and E represents its complement in R" The notation 9 stands for the empty set. For a set T of matrices 0 E R=xm (Ta denotes its diameter and it is defined as diam(T) = suupa,0ee7 ||0 F' For 2; E R with i = 1, 1.... f, the notation diag(21, ... ,E)) denotes a matrix in R with diagonal entries of z₁. This paper uses truncated Gads-Gussiannn Tw, [- [-W (maxx] refer to the truncated Gaussian distribution generated by Gaussian distribution with zero mean and o variance with truncated range
Notation.
[- Umax; [max]] The same applies to multi-variate truncated Gaussian distributions.
2 Problem Formulation and Preliminaries
This paper studies the system identifiaation/estiattin of linearly parameterized nonlinear systems:
Fe+1 = 6.0(11, Uz) + Wts
where 2, E RT= U4 R"=, and W/ E RT denote the state, control input, and system disturbance
respectively; 0, E IR Xno denotes the unknown parameters to be estimated, and Φ(-) denotes a
vector of known nonlinear feature/basis functions, i.e., Φ(-) (.)..).. 6 (-)) where d'())=
Rho + TR. Without loss of generality, we consider zero initial condition, i.e. To = 0. and linearly
independent feature functions, that is, E 0; (It, U4) implies that c; = for all i
The linearly parameterized nonlinear system [I is natural generalization of linear control systems It-1 A_ + B.u, + W. and has wide applications in, for example, robotics (Siciliano al. Alaimo et al. 2013). power systems (Simpson-Poon Pornnon-oooooooo et al.) 2016), transportation (Kong et al. 2015), etc. Therefore, there has been lot of research learning this type of system ( utilizing the methodology and insights from linear system estimation. For example, it is common to estimate a linearly parameterized nonlinear system by least squares estimation (LSE), which enjoys desirable performance in linear systems.
2010:
In particular, LSE for 1 is reviewed below
Ōr = arg min
Σ | - Osbiae, u.) 1
For linear systems, LSE enjoys the following good property: LSE can achieve the optimal rate of convergence with i.i.d. noises W; and i.i.d. control inputs ue under proper conditions (Simchowitz) ct al. 2018)). This good property has been generalized to some linearly parameterized nonlinear systems, such as bilinear systems, and linear systems with nonlinear control policies. Unfortunately, general linearly parameterized nonlinear systems do not enjoy this good property of linear systems, meaning i.i.d. random inputs may not provide enough exploration for non non-smooth feature functions ((.). Therefore, a series of follow-up work focuses on the design of active exploration methods.
However, due to the simplicity of implementation, i.i.d. random inputs remain a popular method in empirical research of system identification and sometimes enjoy satisfactory performance, despite
If the features are not independent, they can be converted to independent ones since the features known.
3

---

the lack of theoretical guarantees. Therefore, this paper aims to establish more general conditions that allow provable convergence of nonlinear system estimation under i.i.d random inputs.
In the rest of this paper, we will show that with certain smoothness and continuous conditions, i.i.d. random inputs sufficient for estimation of (T. which recovers the good property of linear systems.
2.1 Assumptions
In the following, we formally describe the smoothness and continuity conditions that enables efficient exploration of (I) by i.i.d. random inputs.
Assumption 1 (Analytie feature functions). All components of the feature vector Φl)) are real analytic functions in IR i.e., for every S S nag o' (z, u) is an infinitely differentiable function such that the Taylor expansion in every (i, u) converges point-wise to ø' (x, u) in a neighborhood of (z. a).
Analytic functions include polynomial functions and trigonometric functions, which are important components of many physical systems in real-world applications, e-g. power systems, robotics, transportation systems, etc. In particular, we provide two illustrative examples below.
Example 1 (Pendulum). Many multilink robotic manipulators can be understood as interconnected pendulum dynamics. The motion equations of single pendulum, consisting of mass m suspended from a weightless rod of length fixed at a pivol without friction, can be expressed as:
= sin(a)
2
+ w0
ml2
where a represents the angle of the rod relative to the vertical axis, is the gravity constant, u is the torque imput, and w is the disturbance applied this system. After discretization the system dynamics can be rewritten in the structure of ( with the feature vector consisting of expressions involving sin(a) and u. all of which are analytic functions. The matrix of unknown parameters contains terms of the pendulun's 's mass and the rod's 's length.
Example 2 (Quadrotor (Alaimo et al. 2013)). Let E R and E R represent the center of mass position and velocity of the quadrotor in the inertial frame, respectively; let R denote its angular velocity in the body-fixed frame and E R denote the quaternion vector. The quadrotor's equations of motion can then be expressed as:
gez + LQS
dt
52
+
(Tu w x Iw)
where g is the gravity constant, m is its total mass, = diag( Iza, Tny Tzz) its inertia matrix with
respect to the body-fixed frame. fu E IR. the total thrust, Tu E RR3 the total moment in the body-fixed
9ō + qì ob - oz
2 4043)
2(go42 - -1143)
frame, e (0,0,1)T,Q=
2(q1 9u9s)
6 qi 9 93
2(9293 99991
and
2 4092)
2 4293)
g - पी 92 + 93
0
W2
Ww3
W1
W3
W22
W3
0
W3
W2
W1
Similar to the pendulum example, after discretization the system dynamics can be rewritten in the structure of (7) with the feature vector consisting of cubic polynomials in states and inputs. which are real-analytic. The unknown parameters contain terms of the mass and inertial moments of the quadrotor.
Next, we introduce the assumption the random inputs, which relies on the following definition.
Definition 1 (Semi--ontinuous distribution). We define probability distribution P as semi-continuous there does not exist set F. with Lebesgue measure zero such that TP(F))
"This assumption be relaxed to locally analytic functions in large enough bounded set.

---

The semi coniicontiuuous distribution is weaker requirement than continuous distributions, In particular, any continuous distributions, or a mixture distribution with one component as a continuous distribu- tion, can satisfy the requirement of semi-continuity. The semi-continuity can also be interpreted by the Lebesgue Decomposition Theorem (Chapter 6 of (Halmos) 2013)) as discussed below.
Remark (Connection with Lebesgue Decomposition Theorem). Definition 7 can be interpreted by the Lebesgue Decomposition Theorem, which suggests that any probability distribution can be decomposed into a purely atomic component and non-atomic component (see more details in Halmos 2013)). A coniicontimuuus distribution as defined in Defimition 1 requires the distribution' ss non-atomic component to be nonzero.
In the following, we provide the assumptions on w, and using the semi-continuity definition.
Assumption 2 (Bounded iid. and semi-continuous disturbance). wy is i.dd. following a semi- continuous distribution with zero mean and a positive definite covariance matrix En 2 outn. 0 and a bounded support, i.e. ||w/]| S Umax almost surely for all t.
The i.i.d. assumption is common in the literature of system identification for linear and nonlinear systems. As for the bounded assumption on W/, although it is stronger than the Lub-Gaussian assumption on Wi in the literature of linear system estimation, it is a common assumption in the literature of nonlinear system estimation (Mania et al.) 2022 Shi et al. 2021 Kim and Lavaei] 2024). Further, in many physical applications, noises are usually bounded, e.g. the wind disturbances in quadrotor systems are bounded, the renewable energy injections in power systems are also bounded, etc.
The semi-continuity assumption may seem restrictive since it rules out the discrete distributions. However, the disturbances in many realistic systems can satisfy the semi-continuity because realistic noises are usually generated from a mixture distribution where at least one component is continuous, e.g. the wind disturbances and renewable generations are continuous.
For the control inputs Ue, we first impose the same assumption as Assumption 2 for simplicity. Later in Section 3 we will also discuss the relaxation of this assumption to include control policies. Assumption 3 (Bounded i.i.d. and semi-continuone inputs). Ue is ii.d. following a semi-continuous distribution with zero mean and positive definite covariance En, F IhIng 0 and bounded support, i.e. || S Umax almost surely for all t.
Lastly, we introduce our stability assumption based on the input-to- state stability definition below.
Definition 2 (Locally input-to- st-stt stability (LISS)). Consider the general nonlinear system Tt+11 f de) with x4 E R²" , de E R"', f being a continuous function such that f(0.0) = 0. This system is called locally input-to-state stable (LISS) if there exist constants Px 0, p > 0 and functions E K, 3 E K.L. such that for all 2o E {wo E R : ||:00||2 S Pa} and any imput de {d E IR'" : sup, ||de lloo I pb. it holds that ||xell2 S 3(1zool22.t) + (sup; [delloo) for all t A
Assumption 4 (LISS system). System ① is LISS with parameters Ps and p such that P= 2 2||zoll and p 2 max max(Wmax. Umax), respectively.
Assumption 4 is imposed, together with the bounded disturbances and inputs in Assumptions 2 and 3 to guarantee bounded states during the control dynamics (for instance, see the proof of Theorem n Appendix AA). In particular, many studies on learning-basse nonlinear control require
certain boundedness on the states for theoretical analysis Sattar and Oymak (2022) ; Foster et al.
(2020): Li et al. (2023a).
In addition, is interesting to note that this paper only requires local stability of the dynamics, whereas several Saaning-basse nonlinear control papers assume certain global properties, such as global exponential stability in (Foster et al. 2020). global exponential incremental stability in (Sattar and
Oymak 2022 Li et al. 2023a] Lin et al. 2024 or global Lipschitz smoothness in (Lee al. 2024 This difference in the dynamics assumption reflects a trade-off with the disturbance assumptions:
'A function 7 R20 2x is a I. function if it is continuous, strictly increasing and 7(0) 0. A function R220 x Rg0 -> IR=0 a KL function if, for each fixed > 0. the function ((: t) is K. function, and for each fixed s 2 0, the function ((s, -) is decreasing and ((x,t) - as + co. GGlobll Lipschitz smoothness may exclude system dynamics with higher-order polynomials.
5

---

we assume stronger assumption on the boundedness of disturbances and a weaker assumption on local stability, whereas much of the literature considers (sub)Gaussian distributions (which can be unbounded) but requires stronger global properties for dynamics. Since this paper is largely motivated by physical systems, which typically encounter bounded disturbances/inputs and generally only satisfy local stability (Slotine and Li, 1991). we address this trade-off through our current set of assumptions, leaving it as an exciting future direction to consider relaxing these assumptions.
Main Results
In this section, we provide the estimation error bounds of LSE for linearly parameterized nonlinear systems under i.idd random inputs. The estimation error bounds rely on the establishment of probabilistic persistent excitation, which will be introduced in the first subsection. Later, also generalize the results to include control policies and discuss the convergence rate of another popular uncertainty quantification method in the control literature, set membership estimation, whose formal definition is deferred to the corresponding subsection.
3.1 Probabilistic Persistent Excitation
It is well-known that persistent excitation (PE) is crucial condition for successful system identifi- cation (Narendra and Annaswamy 1987). ). In the following, we introduce the persistent excitation condition for our linearly parameterized nonlinear systems.
Definition 3 (Persistent excitation (Skantze et al.) 22000] (aastry and Bodson 2011)). System 1 is
persistently excited if there exist & > 0 and m 2 such that for any to 2 O, we have
t-+m-1 Σ t=
s(I1, ui (IU, ui) s² Ing.
In the stochastic setting, PE is closely related with block-martingale small-ball (BMSB) condition proposed in (Simchowitz et al. (2018), which can be viewed as a probabilistic version of PE.
Definition 4 (BMSB (Simchowitz al. 2018)). Les (Fe)ez1 denote a filtration and let {ye h221 be an (FF)h21-ddaptee random process taking values in "R"", We say {ycte21 satisfies the (k, 1 ab, p)- block martingale small-ball (BMSB) condition for positive integer l'ab O, and a p E [0, 1]. if for any fixed v E IR' such that [|l||2 = 1, the process (yehe1 satisfies Ei_ PP 2 / VoTlabb Fi) 2 P almost surely for any 2 1.
One major contribution of this paper is formally establishing the BMSB condition for linearly parameterized nonlinear systems with real- real-analytic feature functions.
In the following, first investigate the open-loop system with i..d. inputs and later extend the results to the closed-loop systems with inputs T(x)) + M/t where represents the noise and R Th. denotes control policy. The following theorem considers the open-loop systems.
Th and consider the filtration F, hold, then there ex- ist 84 > 0 and Pe E 10,1) such that the Filezz-adapted process ( u.) 1t) satisfies the T Po) BMMSB condition.
Theorem 1 (BMSB for open-loop systems). Lei
F(wo, ... W1t-1, Tig Te; Tlo. .))). Suppose Assumptions 7
Proof Sketch. Intuitively, BMSB requires that any linear combination of feature functions remains positive with a non-vanishen non-vanis probability. Notice that a linear combination of real-analytic functions itself real-analytie, and the zeros of an analytic function have measure zero. These facts allow to show that the probability of linear combination linearly independent feature functions equaling zero is less than one, as long the noises follow semi-continus distributions, by the connection of the Lebesgue measure and the probability measure in Definition
In more detail, the proof leverages variant of the Paley-Zygmund argument (Petrov 2007). which provides a lower bound for the tail properties of positive random variables. Specifically, it states that the probability of positive random variable being small depends on the ratio of its moments.

---

We apply this result to the random variable |0" 6(1(+1 u(+1) Fel with || = and aim to show that the lower bound is non-trivial for any direction u with || = and any filtration F, / 2 0. We then use results from measure theory demonstrate the existence of such non-trivial lower bound. This is done by showing that the Lebesgue measure of the set where je' 0( Mc+1)) | = 0 is zero, and thus the even moments of |u (f ux+1) Fel are non-zero, provided that the noise and disturbance distributions are semi-continuous. For further details, please refer Appendix A
It is worth pointing out that Theorem [ only establishes the existence of the constants ($.. Po). and deriving explicit formulas of these constants are left for future work. In particular, it can be challenging to derive a generic formula for all linearly parameterized nonlinear systems, but an exciting direction to study reasonable sub-classes of systems and construct their corresponding formulas of the constants (sp. Po).
3.2 Non-asymptotic Bounds for LSE
We prepared present the non-asymptotic convergence rate for the LSE in learning the unknown parameters the system ①
Theorem 2 (LSE's convergence rate for open-loop systems). Consider the dynamical system de-
scribed in 7 with Lid. inputs u4 = 1tt and assume that Assumptions 3 4 are satisfied. Let se
and p& be as defined in Theorem |
and define by sup:20 El ((
For fixed 8 E (0, 1) and
2 1, Tf satisfies the condition
10
(3)
10 -
b
T2
log
2n log
ns log
8852
PΦ
Ps
then LSE's estimation Ör satisfies the following error bound with probability at least 1 - 33.
n2 + log :/
+ n log
ng log
b0
900
00r - 0-112 S
Ps
T S
The proof relies on Theorem and Theorem 2.4 in (Simchowitz et al. provided in Appendix B.I
2018 The complete proof is
Theorem demonstrates that LSE converges to the true parameters under random control inputs and random disturbances (non-active exploration) at rate of _ for linearly parameterized nonlinear
VT systems. This is consistent with the convergence rates of LSE for linear systems terms of T',
Regarding the dependence of the convergence rate on dimension, the explicit dependence is F2g where n2 and no refer to the dimensions of the state and the characteristic vector, respectively. In addition, it is worth mentioning that other parameters, such 8a. Pa- bs, may also implicitly depend on the dimensions. For some special systems, such as bilinear systems, it has been shown that these constants independent of dimensions (Sattar et al. (022). It is left future work to explore other nonlinear systems' implicit dimension dependence.
Next, we can generalize the i.i.d. inputs u, to include control policies, i.e., Me = T(xe) + 1), where T satisfies Assumption 3 and π (ax)) ) analytic.
Corollary 1 (LSE's convergence rate for closed-loop systems). Consider imputs u4 ((x)) Tr where π(-) is real-analytic, ÿ)t satisfies Assumption 3 and the closed-loop system de+1 =
0, 02 xt (xx) M)) uy satisfies Assumption 4 for both wa and πe- Then, the same convergence
rate as in Theorem[2hon holds.
The proof is provided in Appendix B.2
3.3 Non-asymptotic Diameter Bounds for SME
Set membership estimation (SME) is another popular method for uncertainty quantification control system estimation (Bertsekas) 1971 Fogel and Huang. 1982 Lu and Cannon] 2023 Li et al. 2024). Unlike LSE, SME set-estimator and directly estimates uncertainty set. Since the analysis of SME also relies the probabilistic persistent excitation analysis, can also establish the
7

---

convergence rate of SME for linearly parameterized nonlinear systems under i.idd. noises in the following, In particular, SME estimates the uncertainty set as
T-1 n E
i zi+1 - O0(x,, un) EW].
Dr
(3)
where W is a bounded set such that wA W for all t O.
The convergence of SME relies on an additional assumption as shown the following: the tightness of the bound W on the support of wy,", This tightness assumption is commonly considered in SME's literature (Li et al. 2024 Lu et al. 2019; Akçay 2004). In addition, (Li et al. 2024) discusses the relaxation of this assumption by learning a tight bound at the same time as learning the uncertainty set of 8, for linear systems. Similar tricks can be applied to nonlinear systems, but this paper only considers the vanilla case of SME for simplicity.
Assumption 5 (Tight bound on disturbances), Assume for any c > O, there exists qar(c) > 0, such that for any 1 S j S and t 0, we have P(w! + Wmax S 2 qw((e) 0, IPWWmax / S 9h > 0.
Assumption requires that we can visit the boundary of the set W arbitrarily closely with positive probability. For example, for a oie-dimensional assumption requires that there is positive probability that w, is close Wmax and Wmax that is, for any c > O, we have P(umax - S W/ I Wmax) > O and P(-Wmax I W, -maa + <c > 0.
bounded by -Wmax I S Wmax, the
Next, we state non-asymptotic bound on the diameter of the uncertainty estimated by SME.
Theorem 3 (SME's diameter bound for open-loop systems), Consider the system ( with i..d. inputs We = M/- Suppose Assumptions 2 3 are satisfied. Consider 86 and pe defined in Theorem 7 and let bæ- sup120 [1 For any
and 8 (0, when T > m, we have
T Ô (n
an To exp(-a3m) O(n25ng n 5) no (1 Qu
a1d
P diam(Or) 5)
4
m
where 01
SoPe
02
64b
03
Pie
16b, /nz, 04
The constants hidden in Ô are provided in S8p
the Appendix C.7
The proof of Theorem 3 is based on Theorem T in this paper and Theorem 1 from (Li et al. 2024).
The detailed proof is provided in Appendix C.1
Theorem 3 establishes an upper bound on the "failure" probability of SME, that is, the probability that the diameter of the uncertainty set exceeds 6. To ensure that the failure probability is less than 1. one can select m = O (log(T) and choose a sufficiently large such that T 2 m (log(T)). wi is more likely to visit the boundaries of the set W (meaning larger (f)), the SME is less likely to estimate an uncertainty set with a diameter greater than
To provide more intuitions on the diameter bound in Theorem 3 consider q (f) = C.. for some Gy > O. Note that several common distributions, including the uniform distribution and the truncated Gaussian distribution, satisfy this property Ow (f) (see Appendix C.2 for explicit formulas of cw).
With qu (f) = C, we can provide a convergence rate of the SME in terms of T in the following.
Corollary (SME's convergence rate when qu (E) Cavl ). For any e > 0, let
m 2 o log (2) + no log
8bg
Lope
p2g
If we's 's distribution satisfies q (f) = & for all l > 0, then when T >> m, we have:
m m n
log (2) + mn 1.5 1.5 log
diam de <
CuSePoT
with probability at least 1 2c. Here the constants hidden in O(:) are provided in Appendix C.
8

---

The proof of Corollary is provided in Appendix C.2
Finally, similar to LSE,
extend SME's convergence rates from open-loop systems closed- loop systems with real-analytic control policies, i.e., U = (xx) + yt, where t/ satisfies Assumption
3 and (122) is real-analytic.
Corollary 3 (SME's convergence rate for closed-loop systems). Consider inputs ue = =((x)) + Ye, where x(-) is real-analytic, Tt satisfies Assumption 3 and the closed-loop system 1++11 0. 0, TI (It) + 1/)) + We satisfies Assumption 4 in terms of both we and ft- Then, the same convergence rates as in Theorem 3 and Corollary
still hold.
The proof of Corollary is provided in Appendix
4 Numerical Experiments
In this section, we evaluate the performance of LSE in estimating the unknown parameter 0, and SME in estimating the uncertainty set for the unknown parameters using the pendulum and quadrotor examples outlined in Section 2 We compare the empirical convergence rates of LSE and SME with the theoretical rates in Theorem [2 and Corollary 2 In each case, the input u, is composed of control policy and i.i.d. noise, such that ú, = ग (2t) + Mパ- For our experiments, we employ noise and disturbances drawn from uniform and Gaasssin distributions. To compute theoretical rates, we numerically estimate parameters such as sy and pa (see Appendix E Further details can be found in our source code f
The details for these scenarios are outlined below:
Pendulum I In the pendulum example described in Section the control input is 1 mI?
-kå Th- This scenario includes two unknown parameters: 0 and 0g
For the quadrotor example in Section the control input defined as Ut (xx) T7, where (xx) follows the controller proposed by Alaimo al. (2013). The quadrotor system involves 13 states and 4 inputs, with the unknown parameter matrix 8, containing 7 parameters, including the mass m and specific elements of the inertia matrix I.
Quadrotor 2:
Further details on controller gains and unknown parameters are provided in Appendix D
LSE Results: Figures La and lb present comparison between the LSE theoretical bound from Theorem 2 with its empirical estimation error of the unknown parameters 0, versus trajectory length for the pendulum example, with uniform and -aauasiin noises and disturbances. Similarly, Figures Ic and Id show this comparison for the quadrotor example. In each figure, both the theoretical bound and empincal error are normalized by the l2 norm of the nominal parameter é.. The log-log plots for both scenarios demonstrate that the empirical error rate achieves O which in consistent with the theoretical rate in Theorem 2
SME Results: Figures 2a and 2b show the empirical convergence rate of SME for the pendulum example, for uniform and truncated- Gaussian noises and disturbances, in comparison to the theoretical rate from Corollary - Both the theoretical bound and empirical error in the figures are normalized by the la norm of the nominal parameter 0., The log-log plots indicate that the empirical rate achieves 00 ). which is consistent with the results from Corollary 2 and with the related results for linear systems in (Li et al. 2024). A similar result can be observed Tor the quadrotor example, in Figures 2c and 2d] Additionally, F shows the uncertainty sets estimated by SME for the two unknown parameters, labeled 0, and 02. in the pendulum example, along with the diameters of these sets as trajectory length grows. We observe that these sets contract as trajectory length increases, with the true values of the unknown parameters lying within the estimated uncertainty sets. The illustration of uncertainty sets for the quadrotor example is provided in Appendix D.2)
truncated-Gaussian

---

pendulum
pendulum
quadrotor
quadrotor
10
10"3
theo
10-2
theo
8.1./ |0.|
10-3
0..p 10.
10-
10
empr
10
empr
10-4
10"4
theo
theo
-5
10
empr
10
empr
10-1
10-1
10a
10
10a
10
10
10"
(a) Uniform
(b) Truncaled-Gaussin
(c) Uniform
(d) Muuncted-Gauusian
Figure I: Convergence rate of the LSE for pendulum and quadrotor scenarios: (a) Pendulum example with
uniform, (b) Pendulum example with Sancaate-GGuusian, (c) Quadrotor example with uniform, and (d) Quadrotor example with truncated- truncate--Gausian Gaussian noises and disturbances. Here, uniform noises and disturbances are i.i.d. generated from uniform( (1-1, 1I), and truncated- Gaassssan noises and disturbances are i.i.d. generated from truncat ed ad--aussiann( 0.1, [-1,1]] "theo" denotes the thcoretical convergence rate, and "empr" represents the empirical rate. The mean error across 20 trials is shown by dots on the empirical plots, with shaded areas illustrating empirical standard deviation.
normalized liedd diamater
pendulum
normallee lizee diemeter
pendulum
normelized diamater
10-2
quadrotor
normalized diamater
quadrotor
10-1
10-2
10->
empr
thoo empr
theo
theo empr
10-3
10-4
10-3
empr
10-4
10a
104
10a
104
10
10a
10"
(a) Uniform
(h)
(c) Uniform
(d) Saaneated-Gaussinn
Figure 2: Convergence rate of the SME for pendulum and quadrotor scenarios: (a) Pendulum example with
uniform, (b) Pendulum example with munsated-Gaussian.e (c) Quadrotor example with uniform, and (d) Quadrotor example with truncated- Gaussian noises and disturbances. Here, uniform noises and disturbances are i.i.d. generated from uniform(( (|11, 1J). and truncated- Gaassssin noises and disturbances are i..d. generated from truncated- Sawcccate--Guusssae Gaussian (0, 0.5, [-1, IJ). "theo" denotes the theoretical convergence rate, and "empr" represents
the empirical rate. The mean error across 10 trials is shown by dots on the empirical plots, with shaded areas illustrating empirical standard deviation.
5 Concluding Remarks
Conclusion. This study examines the probabilistic persistent excitation in class of nonlinear systems influenced by ii.d. noise and stochastic disturbances, with the stipulation that their distributions do not concentrate sets of Lebesgue measure zero. Based on this then present explicit bound on the convergence rate of SME estimations and LSE estimations for this class of dynamical systems. Additionally, numerical experiments in the context of robotics provided to illustrate both methods.
L Limitations. One limitation of this work is that our analysis relies on a specific class of i.i.d. noises and stochastic disturbances, where the probability distribution is not concentrated on sets of I Lebeggue measure zero. While this a sufficient condition, is possible that the BMSB conditions are satisfied under other circumstances. Another limitation is that, though provide sufficient conditions for the existence parameters satisfying the BMSB condition, the explicit dependence is not detailed here. Lastly, imperfect observations are not considered here.
Future Work. Our future work includes several promising directions, e.g., to explore cases that do not satisfy our semi- semi-continuity assumption, such as discrete noises, and to investigate the explicit dependence the BMSB parameter on system attributes, such as state, input, and feature dimensions, etc. Furthermore, extending this work to imperfect state observations is important next step. Finally, a potential direction is to provide a non-asymptotic analysis of the volumes of uncertainty sets estimated by SME uncertainty sets, opposed to the current focus their diameters.
10

---

T-50
T-200
T-250
T-400
T-500
True
10
40.04
10a
40.02
10a
40.00
100
39,98
10-3
39.94
10"
250
500
750
1000
1.96
1.98
2.00
2.02
2.04
(a) Pendulum
(b) Uncertainty set diameter
(c) Uncertainty set
Figure 3: Performance of SME for pendulum in (a) with control input Ue = -ók + where k = 0.1, i.i.d. generated from -aatteddddaaiiia((. 2, [-2, 2)) and disturbed with i.idd. generated from sewccated-Gusssiann 1, [-1, 1]). (b) Diameter of the uncertainty set estimated by SME, (c) Uncertainty set depicted T 50, 200, 250, 400, 500.
Broader Impact
This paper is a foundation research and develops theoretical insight to estimation nonlinear control systems. We do not see direct path negative applications in general. But want mention that successful applications of our theoretical results rely on verifying the assumptions in this paper.
References
Yasin Abbasi-Yadkorf and Csaba Szepesvári. Regret bounds for the adaptive control linear quadratic systems. In Proceedings of the 24th Annual Conference Learning Theory, pages 1-26. JMLR Workshop and Conference Proceedings, 2011.
Hüseyin Akçay. The size of the membership-set in probabilistic framework. Automatica, 40(2): 253-260, 2004.
Andrea Alaimo, Valeria Artale, C Milazzo, Angela Ricciardello, and LUCA Trefiletti. Mathematical modeling and control of a hexacopter. In 2013 International conference unmanned aircraft systems (ICUAS), pages 1043-1050. IEEE, 2013.
Er-Wei Bai. Roberto Tempo, and Hyonyong Cho. Membership set estimators: size, optimal inputs, complexity and relations with least squares. IEEE Transactions Circuits and Systems I: Fundamental Theory and Applications, 42(5):266-277, 1995.
Er-Wei Bai, Hyonyong Cho, and Roberto Tempo Convergence properties of the membership set. Automatica, 14450):1245-1249, 1998.
Dimitri Bertsekas. Control of uncertain systems with deeceeeepprssiippeeipiiiiiiiii of the uncertainty. PhD thesis, Massachusetts Institute of Technology. 1971.
Vladimir Igorevich Bogachev and Maria Aparecida Soares Ruas. Measure theory, volume 1. Springer, 2007.
Xinyi Chen and Elad Hazan. Black-box control for linear dynamical systems. In Conference on Learning Theory, pages 1144.114.. PMLR, 2021.
Alexandru Crăciun and Debarghya Ghoshdastidar. On the stability of gradient descent for large learning rate. arXiv preprint Xiv::2402.131000 2024.
Sarah Dean, Horia Mania, Nikolai Matni. Benjamin Recht, and Stephen Tu. Regret bounds for robust adaptive control of the linear quadratic regulator. Advances in Neural Information Processing Systems, 11:4188-4197 2018.
Eli Fogel and Yih-Fang Huang. On the value of information system identification noise case. Automatica, 18(2):229-23) 1982.

---

Dylan Foster, Tuhin Sarkar, and Alexander Rakhlin. Learning nonlinear dynamical systems from single trajectory. Learning for Dynamics and Control, pages 851-861. PMLR. 2020.
Yihuai Gao, Yukai Tang, Han Qi, and Heng Yang. Closure: Fast quantification of pose uncertainty sets. arXiv preprint 2et::240300990 2024.
Paul R Halmos. Measure theory, volume 18. Springer, 2013.
Mohammad Khosravi. Representer theorem for learning koopman operators. JEEE Transactions on Automatic Control, 2023.
Jihun Kim and Javad Lavaci. Online bandit control with dynamic batch length and adaptive learning rate. 2024.
Jason Kong, Mark Pfeiffer, Georg Schildbach, and Francesco Borrelli. Kinematic and dynamic vehicle models for autonomous driving control design. In 2015 IEEE intelligent vehicles symposium (IV), pages 1094-1099, IEEE, 2015.
Suhas Kowshik, Dheeraj Nagaraj. Prateek Jain, and Praneeth Netrapalli. Near-optimal offline and streaming algorithms for learning non-linear dynamical systems. Advances Neural Information Processing Systems,
2021.
Steven Krantz and Harold R Parks. A primer real analytic functions. Springer Science & Business Media, 2002.
Bruce D Lee, Ingvar Ziemann, George J Pappas, and Nikolai Matni. Active learning for control- oriented identification of nonlinear systems. arXiv preprint (rXiv:2404.090300 2024.
Yingying Li, Subhro Das, and Na Li. Online optimal control with affine constraints. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 8527-8537, 2021a.
Yingying Li. Yujie Tang, Runyu Zhang, and Na Li. Distributed reinforcement learning for decentral- ized linear quadratic control: A serivative-free policy optimization approach. IEEE Transactions on Automatic Control, 67(12):6449-66 6444, 2021b.
Yingying Li, James A Preiss, Na Li, Yiheng Lin, Adam Wierman, and Jeff Shamma. Online switching control with stability and regret guarantees. In Learning for Dynamics and Control Conference, pages 1138-1151. PMLR, 2023a.
Yingying Li, Tianpeng Zhang, Subhro Das, Jeff Shamma, and Na Li. Non-asymptotic system identification for linear systems with nonlinear policies. PanC-PPpprsOOLiie,, 5661)))12 2023b.
Yingying Li, Jing Yu, Lauren Conger, Taylan Kargin, and Adam Wierman. Learning the uncertainty sets of linear control systems via set membership: A non-asymptotic analysis. In Proceedings of the 41st International Conference on Machine Learning, pages 29234-29265. PMLR, 2024. URL htttps:/prroceedingg
amriiinnnsmm........mmmmm... mlr wwl..prres//ve srrress/v355/1 vats////3/////2 htmm
Yiheng Lin, James Preiss, Emile Anand, Yingying Li, Yisong Yue, and Adam Wierman. On- line adaptive policy selection in time-varying systems: No-regret via contractive perturbations. Advances in Neural Information Processing Systems, 36, 2024.
Matthias Lorenzen, Mark Cannon, and Frank Allgöwer. Robust mpc with recursive model update. Automatica, 103:461 -711, 2019.
Xiaonan Lu and Mark Cannon. Robust adaptive model predictive control with persistent excitation conditions. Automatica, 152:1 10959, 2023.
Xiaonan Lu, Mark Cannon, and Denis Koksal-Rivet. Robust adaptive model predictive control: Performance and parameter estimation. International Journal of Robust and Nonlinear Control, 2019.
Horia Mania, Michael Jordan, and Benjamin Recht. Active learning for nonlinear system identifica- tion with guarantees. Journal of Machine Learning Research, 23(32):1-30, 2022.
12

---

Kumpati S Narendra and Anuradha M Annaswamy. Persistent excitation in adaptive systems. International Journal of Control, 45(1):127-160, 1987.
Bernd Noack, Konstantin Afanasiev, Marek Morzyński, Gilead Tadmor, and Frank Thiele. hierarehy of low-dimensional models for the transient and post-transient cylinder wake. Journal of Fluid Mechanics, 497:335-366 363, 2003.
Valentin V Petrov. lower bounds for tail probabilities. Journal of statistical planning and inference, 137(3))2703-2777 2007.
Arnab Sarker, Peter Fisher, Joseph E Gaudio, and Anuradha M Annaswamy. Accurate parameter estimation for safety-critical systems with unmodeled dynamics. Artificial Intelligence, page
Shankar Sastry and Marc Bodson. Adaptive control: stability, convergence and robustness. Courier Corporation, 2011.
Yahya Sattar and Samet Oymak. Non-asymptotic and accurate learning of nonlinear dynamical systems. Journal of Machine Learning Research, 23(140): 2022.
Yahya Sattar, Samet Oymak, and Necmiye Ozay. Finite sample identification of bilinear dynamical systems. In 2022 IEEE 61st Conference on Decision and Control (CDC), pages 6705-6711. IEEE, 2022.
Guanya Shi, Kamyar Azizzadenesheli, Michael O' O'Connell Soon-Jo Chung, and Yisong Yue. Meta- adaptive nonlinear control: Theory and algorithms. Advances in Neural Information Processing Systems, 34:10013-10025, 2021.
B. Siciliano, L. Sciavicco, L. Villani, and G. Oriolo. Robotics: Modelling, Planning and Con- trol. Advanced Textbooks Control and Signal Processing. Springer London, 2010. ISBN 9781 9781846286414. httL::ttts://book.ggge google com/bbokss2idjpPAAnn..
Max Simchowitz and Dylan Foster. Naive exploration is optimal for online lqr. In International Conference on Machine Learning, pages 8937-8948. PMLR, 2020.
Max Simchowitz, Horia Mania, Stephen Tu, Michael Jordan, and Benjamin Recht. Learning without mixing: Towards a sharp analysis of linear system identification. In Conference On Learning Theory, pages 439-473. PMLR, 2018.
John W Simpson-Porco. Florian Dörfler, and Francesco Bullo. Voltage stabilization in microgrids via quadratic droop control. IEFF Transactions Automatic Control, 62(3): 2016.
Fredrik P Skantze, A Kojié, A-P Loh, and Anuradha M Annaswamy. Adaptive estimation of discrete-time systems with nonlinear parameterization. Automatica, 36(12):1879-18887 2000.
Jean-Jacques Slotine and Weiping Li. Applied nonlinear control, volume 199. Prentice hall
Englewood Cliffs, NJ, 1991.
Yukai Tang, Jean-Bernard Lasserre, and Heng Yang. Uncertainty quantification of set-membership estimation in control and perception: Revisiting the minimum enclosing ellipsoid. In 6th Annual Learning for Dynamics & Control Conference, pages 286-298. PMLR, 2024.
Andrew Wagenmaker and Kevin Jamieson. Active learning for identification of linear dynamical systems. In Conference on Learning Theory, pages 3487-3582, PMLR, 2020.
Haonan Xu and Yingying Li. On the convergence rates of set membership estimation of linear systems with disturbances bounded by general convex sets. arXiv preprint arXiv:2406.00577 2024.
Christopher Yeh, Jing Yu, Yuanyuan Shi, and Adam Wierman. Online learning for robust voltage control under uncertain grid topology. IEEE Transactions Smart Grid, 2024.
Jing Yu, Dimitar Ho, and Adam Wierman. Online adversarial stabilization of unknown networked systems. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 7(1):1-43, 2023.
13

---

Ingvar Ziemann and Stephen Tu. Learning with little mixing. Advances in Neural Information Processing Systems, 35:4626-4637. 2022.
Ingvar Ziemann, Anastasios Tsiamis, Bruce Lee, Yassir Jedra, Nikolai Matni, and George Pappas. A tutorial on the non-asymptotic theory of system identification. In 2023 62nd IEEE Conference on Decision and Control (CDC), pages 8921 8921-8939. IEEE, 2023.
Ingvar Ziemann, Stephen Tu, George Pappas, and Nikolai Matni. Sharp rates in dependent learning theory: Avoiding sample size deflation for the square loss. arXiv preprint
2024.
14

---

Appendix
Roadmap
Appendix provides a proof of Theorem
Appendix provides proofs of Theorem 2 and Corollary
1
Appendix C presents proof of Theorem and Corollaries 2 and 3
Appendix provides more details of the simulation settings.
Appendix discusses the numerical estimation of the BMSB parameters (sp.Po) in Theo- rem
The NeurlPS Paper Checklist is provided after the appendices.
A Proof Theorem 1
Proof. Given that u = Tt and satisfies the conditions in Assumption 3 u4 is bounded, meaning
uu U, where L/ is compact set. Moreover, since the system is LISS, there exist functions 7 E I.
and B E KL, such that for all 2 O, the following holds:
E X " Rd ||1||2 ((2z 0) +7
with parameters Ps 2 || l2 and p 2 max(Wmaxx Umax). Let 2 X x xu, then žt for 2 The set Z is compact subset of Ra
To show that the (Feltz--ddppted process fō(2))121 satisfies the BMSB condition, it sufficient to demonstrate that there exist sæ > O and Ps E (0,1) such that for all t 2 0 and for any v E R with ||r|||2 1, the following holds:
P P P (1 2 s s0|l1|12 Ft
Pa-
(4)
To establish this, we apply the Zygmudd inequality, which gives lower bound on the tail probability of non-negative random variable:
Lemma 1. (Paley-Zygmund (Petrov 2007 Let be non-negative random variable. Then for any
r E (0, 1), the following holds:
2
x rerryBB ///11
(1 n2)2
B(x-1]
Based on this result, for any r E (0, 1), we have:
2
co 2
|
P (ITTOZZH1)) > >r)))sr r ((TT( F
F 2 (1
22
(5)
IE
(oTO(Z++1))
Fr
Let V= fo E " ||e||2 = 13. To show that the BMSB condition holds, it sufficient to establish
the following two points:
inf inf B[( Fi] > o.
Fe. 120
wEv
and sup sup E (( Fi) xc.
Jr. f20
120
vEv
15

---

These conditions ensure that the with some constants $6 and Ps E (0, 1). We will divide the proof into two parts:
process {Ø(z)) satisfies the BMSB condition
Step 1. Showing that inf inf E ([(((T((((z))) Fi) 0: Fc, 120 NEV
We begin by noting the following:
inf inf E (oTo(2411)) |r Fe. 120
inf
inf E VEV
(o T (eTo(EL)), u(1)) Fr
NEV
Fr. 120
inf
inf
E (vT (0. ur, m(+1)² Fi
Fr. 120
VE
Since 2e Fe while wt, Uz+1 & Fr, we can treat ot as constant and we, Us+1 Tx+1 as random variables. From the continuity of features o(-), we can conclude that:
( inf inf E (u (UT Fe = inf inf E (u (vT (.0(2) + tw, w1)))) 120 VEV
Z22 DEV
where w. 17 are independent random variables, as assumed in Assumptions and Now, let No = {(w.T) E W Wxx: u (To(h(2, = 03. and we have:
(M). E (uTo(((2, w)) (()
0]
((( m) # #0}
+ E
E (UTo(b(2, w), (w.n) & No
P (w, & N:
1 - p (w. E N: ) E (TT(h(2, m))² (w.n) & No
Therefore, we have:
inf inf IE #2Z vEV
(oTo(((,,w)))))
= inf inf L (o (h(,, w), ZE2 ver
(w,,) n) $ NN5
(6)
x (1-sup sup sup P (w.n) E NN:))
zez vev
It is evident that if No 0. then
inf inf E (vT (h(2, wh)) * 0, and sup sup P (w, m) E No) =
#EZ V
seZ vev
leading to inf inf E (uTo(1(z, zE2 NEV For this, we can use the following lemma concerning the zero set of real-analytic functions in terms of Lebesgue measure.
0. Now we proceed with the case where A8t * 0.
Lemma 2 (The zero set of real-analytic functions (Cräciun and Ghoshdastidar 2024)). The set of zeros of a non non-trivial real-analytic function f R - R. has Lebesgue measure zero in R
This is known result and can be proved using the identity theorem along with Fubini's theorem. For further information on this topic, see sources such as (Krantz and Parks 2002 Bogachey and Ruas 2007).
Recall that we defined h(2, w) = f20(2) + w. Notice that h(.,.) .) is real-tnalytic. Now consider
vt (T)( = Σ
16

---

where Øf (h(z, w), n) are linearly independent. Hence, the sum Ei=1 e²00 (h(2, w) 7) # 0 for any E V. This implies that v (T w), n7) is real-analytic and non-zero. Consequently, by Lemma 2 x (N3)= 0 for any E V.
Under Assumptions 3 and 2 there cannot exist a set C Z of Lebesgue measure zero in R".t". for which the P( ((w, 17) E' 1. Taking this into account, along with the fact that Aa= (N,) = 0 and that the sets and are closed sets (implying they include all their limit points), we can conclude that
sup sup P (w, E EN: =E2 VEV
+ 1.
Moreover, since Au (N?) 0 and Aur (W U) + 0, it follows that (W3) + 0. This implies
inf inf TE (oTO(M(z,w),))) (w, n) & NJ #0. sE2 NEV
Substituting these results into we obtain:
inf inf [((TT(()+1)) Fil 0. Fo 120 DE
Step 2. Showing that sup sup E (u (oTp(E42))) Fil < co:
F., 120 eEV
Since 2, E for 2 O, and considering that the noise and disturbances are bounded while the features are real-analytic, it follows that FF is a bounded random variable. Consequently, e (2(+1)) also bounded. Given that both 2 and V are compact sets sets- meaning they contain all their limit points and that any random variable with bounded support has finite moments, we conclude that
sup sup E (TT Jr. 120 eE
Fi] < co.
We finalize the proof by combining the results from Step 1 and Step 2.
B Proofs for Theorem 2 and Corollary 1
B.1 Proof of Theorem 2
Proof. The proof hinges on the following key meta-theorem about the LSE convergence rate:
Theorem 4 (LSE meta-theorem (Simchowitz et al. 2018 Fix ō (0, 1, and abb < r. Consider a random process (11e (R" x I ) and a filtration {Fihe2 Suppose the following conditions hold:
z₁ =0 + We where w/ is a zero mean o², sub- Gaus-iann
(uchez is an
random process satisfying the (k: I' Lba p)- -MMBB condition,
P you A TT S 5.
If the trajectory length satisfies
10k T>
log det (Pr
10 )
log
(
3b
2ng log
2
then with probability at least 1
35, LSE estimation error is bounded by:
+ log det (rrz) + ny log 10
+ log 11
90m p
00 0-112- <
T I'o min (Tab) sb)
17

---

Since Wy satisfies the Assumption 2) and w, & Fe, then ow Fi is sub-Gaussian with parameter ow. Additionally, system D is linear in unknown parameters e_, From Theorem I the 1
process (12 satisfies the (1 I ng. Ps (a).P& -BMSB condition for some 86 and Pp E (0, 1].
To complete the proof, it is left to show that for any å E (0, 1), there exists I sg such that
P
(=)) 1 (T < d. (z))0T
To see this, note that for by sup,20
[=)1(())))1))) we have:
T
boT 1m
(bTT Ino (oo
(2))0T
(2+) 1
P
Amax
Σ t=
(()))oT(E))
Amax
T
BoT
P
(2())T((22)))
6
dE
T 0 )oT (2)))l
boT
In addition, we have:
E
Σ (z)))
E B[1l((z))11) < T Tuppppppp Tup =[op(((()))15)
120
which implies that:
T
Σ
(
# ST)) 26
where r by n since 2, 2 for all f 0, with 2 being compact set (due the system's 's LISS 8
property and features d(.) being real-analytic), such bounded by exists, completing the proof. L
B.2 Proof of Corollary
!
Proof. We start the proof by stating the following lemma which is extension of Theorem to the case with in = (xx)) N7.
Lemma 3. Let us = ( x(-) is real-analytic, ne satisfies Assumption Consider the filtration Fi F(wo, ... T0. 3t, x (ar), , (x+), ro. .T)). Suppose Assumptions 1 2 hold
and that the closed-loop system Ft+1 = 0_ π (xx))
) + Th) + w. satisfies Assumption 4 for both
wi and nh- Then there exist so > O, and ps E (0, 1) such that the (Fih121-adaph process
{ u.) be21 satisfies the (1, s.., PB)-BBSBB -BMSB condition.
Proof of Lemma 3 The proof closely follows the steps of Theorem First, observe that u, = (xx)) + nh- Since nh satisfies the conditions outlined in Assumption and the closed-loop system It-1 = 0z x (x²) + Th) + we adheres to Assumption 4 with respect to both w, and 7), there exist functions 7 E K. and K.L such that for all 0 the following holds:
E X x
E R" ||0/|2 B(pz, 0) +(0)
with parameters Px 2 ||xo [2 and p max (Wmaxx Umaxx. Let Z X' x U, where 2/ is compact set containing dn for all 2 O. Thus, 2, E Z for all t 2 0. The set a compact subset of IR R. tru The remaining part of the proof, specifically to show that sup sup (vTT((+))) Fi < oo Fi, 120 VeV
follows similarly to the proof in Theorem
18

---

It remains to show that
inf
inf E (((
Fil > O. This can be shown follows:
Fr, 120
inf
inf E (UT((2(1))) )) |
= inf
inf vEV
E
(1 m)+1)) [
Fe 120 vEV
Fex 120
uT ( 1 (12411) + m )² Fe
inf
inf
Fr, 120
inf
inf
UT 0_ (2)((2)) + wes
Fr. 120
NE
T(0-((z)) + ws) + m )) |
Since E Fi and Wt, Th+1 & Fc then 2, is treated as constant while Wt, 7 considered random variables. Then, by the continuity of & we conclude that
inf E (uT)(Z+11)) Ft Fex 120 veV
inf
inf inf E sEZ
B TT NEV
+ w. x 0.0(2) + w) + ( 0.0(2))
27
k(ww)
2
inf inf E sE2 VEV
oT l12z, w), n (h(z, ()) +
where w and are independent random variables constrained as described in Assumptions 2 and 3
By letting N;- {(w.n) W w uT oT((( w), n (h(z, w)) + +7) = 0}. similar to 6 we have:
( 1TT (12,,,),,T((G w)) +11
inf inf E sEZ VEV
uTT h(2, w), x (1(2, w)) + +7)) ())+)))))))))
inf inf E ZEZ vEV
(w,u) & No
x (1
(1-sup sup sup PP (u. E No zEZ vEV
We aim to show that tm. (N3) by applying Lemma 2 Note that Φ)-), k(.), and x(-) are real-
analytic. To use the results of Lemma we need to establish that TT h(2, w), n (h(z, w)) + 77 is non-zero for any V. First, observe that:
no
T (h(z w)) v) Σ vi (M)2,))), n))
Now consider two scenarios:
All components of π (h(2, w)) are linearly independent with any component of h(z, w).
At least one component of π (h(2, w)) is linearly dependent with one or more components w).
In both cases, due to the additive nature of 1). all the functions @ (h(z, w), क (h(2,, + n)) with
i = 1, .... Big are linearly independent, ensuring that (1((, w), [h[(2, w)) + +n) 전 0 for any
E V. The remainder of the proof follows similarly the argument Theoreml 1
Using this Lemma, Theorem 4 and reasoning similar to that in the proof of Theorem the proof can be completed.
19

---

C Proofs for Theorem? 3 Corollary
2 and Corollary 3
C.1 Proof of Theorem
Proof. The proof follows from applying the following meta-theores on the convergence rate of SME.
Theorem (SME meta-theorem (Li al. 2024)). Consider a general time series model with linear
responses as follows:
21 0.3/ + Wt: t t2 0.
Also, define the fillration Fr F(wo, ... w 1, yo. Wt) Assume the following conditions are met:
We are ii.d. with variance ou and box-constrained, i.e., we W {w 12 | I Wmax] J for some Wmax > 0.
Ryche1 is an tion.
random process satisfying the (k, sy y Pv) P -BMSB condi-
There exists by > O such that || < by almost surely for all 1 2 0.
For any & > O, there exists (C) > O, such that for any 1 S j S and { 2 0, we have
P(w] + Wmax e) 2 9w (e) O, Pwmmx 1 f) qu ( > 0.
Then for any m 2 and any 8 E (0, 1), when T > m, the diameter of the uncertainty set
T-1
θ =
n t=
0
Uye E w
satisfies:
IP diam(@)) (0))>6) >6)
< 544
2.5 log(azng exp(- -amm) ny m
2.5 log la n. (1 tu
a1d
[T/m]
+ 544n 2.5
ny
4 A
where aj
SuPu 02
61b²
03
04 = 8
max
1buy/zz
Observe that system is linear in the unknown parameters 0., and we can prove Theorem by showing that the (Fr, 1 process (Ø(2z and w, meet the conditions of the meta- and since wt & Fr, the noise wi fulfills all the requirements the meta-thcorem. Moreover, according Theorem I the {Fi radaeteddd process 6(2) satisfies the (1, Ing PBMBB condition for some 8 LISS, have E 2 for all 2 where 2 is the compact set defined in the proof of Theorem T Therefore, there exists a constant by > 0 such that sup,20 [()(2) ||2 S bg. completing the proof of the theorem.
theorem. By Assumptions[lanee
and Ps (0, 1]. Lastly, since the system is
Explicitly, this means that for any m 1, for any d E (0, 1), when T m, we have:
P diam(Or)) 5)
< 544
T
n
2.5
log(azns)a" exp(-asm)
(8)
log log(asmang)) nnno (1 qu a1d
[T/m]
+ 544n
2.5 2.5 n
4
where 01
02
6
03
P2 8
a4
16bay/m
SoPo
20

---

C.2 Proof of Corollary 2
Let us provide two example distributions, truncated Gaussian and uniform, along with their corre- sponding (-) (from (Li et al. 2024)):
If we follows uniform distribution on Wmax: Wmax "0 then qu (f) Cw with Cu-
20mmax
If follows truncated-Gaussian distribution on [-W Wmax ] generated by Gaus- sian distribution with zero mean and covariance matrix on then qu (c) Cw with
Cw min( 2
exp(
2
max
Now, fix (0, We want to show that if q( a1d Cwo
4
aid and choose such that 4
log
T
+ no log((z)) + 2.5 log(ns) log log(a)ns) + log((44)).
(9)
a3
then for all 2 m, we have
my nr log (2) + mmm..nn log (
8 S 0
saPa
(10)
Sup
with probability at least 1--22 2c.
Let the two terms in the right-han hand side of (8) be denoted by "term 1" and "term 2". We proceed with the proof in two steps follows:
Step I: showing that with the choice of in (2, term 1 S e
With this choice m, it is straightforward to see that
544T'm 2.5 log(aznz)a)" ne exp(- (3p) S
and thus term S E.
Step 2: letting term 2 = and showing that ó satisfies the inequality in (10):
Assuming without loss of generality that T. is integer, note that term 2 implies:
aid
+
5 2.5 log ( nin
< log
544m2.5n 2.5 log(ammenooag nen
log
T
(544m25n2 2.5 log log(ann nono
m
()) + log(as)) + 2.5 log(n.ns) + log log(aan.ns) + 1og(544))
log
T
If qwi
015
= Ow A.ni for some constant Cw 0, then:
a1d
1/D,
4 T
log (-) + log(as)lunig + 2.5 log(n,nss) + log log log(a + log(544)
5 5
aI
16 /6
log (2) + ne log
16bs The
GusoPoT
myn log (?) m...--nn log
TTpTTT
Combining these two steps, we conclude that, with probability at least 2c.
diam diam(Or) s 0 m m log (2) + mn 1.5 ns log (hams sap0
Supo
21

---

set to be C.3 Proof of Corollary 3
This corollary's proof builds on Lemma in Appendix B.2 and closely aligns with the proofs of Theorem and Corollary
D Numerical Experiments
This section provides details on the simulation experiments.
D.1
Pendulum
The ground truth for the unknown parameters for pendulum example in Example |
m 0.1 (kg),
= 0.5 (m),
and discretization time step in our numerical experiments dt 0.01 (s). The control input is simple feedback controller u, kkà, Th- In Figures [a [a] and [b we choose k = 2 and in Figures Za and we choose = 0.1. Note there are two unknown parameters this pendulum example as follows:
01
82
1'
ml?
D.2 Quadrotor
The ground truth for the unknown parameters for quadrotor example in Example 2 is set to
m 0.468 (kg),
Ja 4.856 x 10-3 (kg/m²), Ing 4.856 x 10-3 (kg/m²), I.a 8.801 x 10-3 (kg/m²).
The discretization time step in numerical experiments is di 0.01 (s). The control input is control policy plus i..dd noise. The control policy on altitude and the three Euler angles is borrowed from (Alaimo al. 2013). The controller gains in our numerical experiments chosen as:
kp 0.75, kd, 1.25, kp = 0.03, kd = 0.00875,
kpp 0.03, kdg 0.00875,
kp 0.03, kdg 0.00875.
Note that there seven unknown parameters in this quadrotor example, follows:
1
8
m
Lu
1
Lew
Los 1sz
00
03
04
05
06
07
1
T
y9
Figure 4 displays the uncertainty estimated by SME for the seven unknown parameters in the quadrotor example for various trajectory lengths, with 7) and w/ being i.i.d. samples from truncated- Gaussian distributions. The uncertainty sets observed shrink the trajectory length increases, consistent with our theoretical results. Note that the ground truth value contained within all the uncertainty sets.
E
Numerical Estimation of BMSB Parameters (Sor P.p)
We compare the empirical rates of LSE and SME with their theoretical counterparts in Section 4 The theoretical results presented Theorem 2 and Corollary rely on the parameters by bg. and the BMSB parameters (s0. Ps). However, the explicit relationship of these parameters with system, noise, and disturbance characteristics such as n,, nue no. Fu, and aw not known and we will address this in future work. Consequently, we estimate these parameters numerically and utilize these
22

---

T 200
500
T= 1000
T= 2000
Tue
0.8
2084
-0.9
1.0
0.05
208.2
-1.0
83
0.00
0.5
-0.05
205.8
-0.10
2.13
2.14
2.15
205.8 206.0 206.2 206.4
205
206
112
113
114
81
8
6n
Figure 4: 2D projections of the uncertainty estimated SME for the unknown parameters of the quadrotor example. The noises and disturbances are i.i.d generated from SaanccttedGaussaan((( 0.5, [-1,
estimates to calculate the theoretical rates discussed in Section While by and by are straightforward to estimate, special attention required to estimate the BMSB parameters. This section dedicated to describing this estimation process.
For this, consider system of the form (I. For this system, our goal estimate ss and ps, where
Pe
inf
inf P [ ((2(+11) 2 86 F+
5,.200 pull==
numerically. First, observe that 6(2++1) ) = 6(0 6(2)) We, u++1), where 2, Fr. This implies that (((+11) Fr is random variable influenced by wi and ut+1- We proceed by fixing s (for To accomplish this, we first select time horizon T and generate several trajectories of length T for the system. Let D represent the set of these trajectories, while D' denotes subset containing all trajectories up to < T. Additionally, we create multiple vectors Rat such that ||o|| = 1; we refer to this collection as V. These vectors are randomly sampled from Gaussian distribution and subsequently normalized.
some $ > 0) and empirically estimate
We then estimate p as:
p = min min min P |0" (00 ((2) + We, 4111)
(E[T] DD NED
As increases, along with the number of trajectories and vectors v, the minimum estimates will more accurately reflect the infimums. In this context, represents the minimum of P (1e2 600 d(2) +
Wt., (+41) 2 across all combinations in (T) x DJ x V. For each combination in this set, we
estimate the probability PP [oF ((=)==()>>>)))))<)))) - wr. ue+1)l 2 using Monte Carlo simulations. This
process entails generating multiple random samples based on the distributions of wy and u4+1- verifying whether each sample satisfies the condition :o x(2)] > 3. and tallying how many samples meet this criterion. We repeat this procedure for various values of until we identify a pair (3, p) such that P (0, 1). The estimated probability is calculated as the ratio of the count of successful samples to the total number of samples. According to the law large numbers, this ratio converges to the true probability as the number of samples increases. For estimations, we select T 50,
|V] 1000, and D 20.
23


Reviews:
[{"review_id": "Kt0WVc4D4X", "reviewer": "Reviewer_Dfmt", "summary": "The authors extend the work of Simchowitz et al. (2018) [linear] and Sattar et al. (2022) [bi-linear] to linear in the parameters but analytic nonlinear features showing that PE of inputs still results in PE of the states which for general nonlinear systems is not true. From this result LSE results like those originally in Simchowitz et al. (2018) are recovered for this new class of systems and SME results like those in Li et al. (2023a) are recovered for this broader class of systems.", "questions": "- I would much prefer the simulations in the appendix and the inclusion of the entirety of the proof of the main theorem in the main text with clear exposition of how the properties of analytic functions can be exploited to prove PE of u results in PE of x for these systems. This paper is not as bad as others where the main text is only an advertisement of the main result, but it would be a much tighter and more useful paper if this was done. This reviewer may be an outlier though as it seems the trend in these conferences is to do just the opposite of what I have suggested.", "limitations": "limitations are discussed", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- originality: original part is recognizing that analytics functions are only bad in finite number of spots and are otherwise \"nice\" functions \n- quality: yes rigorous math\n- clarity: well written\n- significance: greatly extends the original results to a much larger class of systems", "weaknesses": "- the biggest weakness of the paper is that very little time is spent on the analysis in the main text. yes their is a proof sketch for the main theorem, but it would be nice to get more intuition from the main text.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your constructive comments! We will address the comments below.\n\n----\n\n`Weakness:` \n>The biggest weakness of the paper is that very little time is spent on the analysis in the main text. yes their is a proof sketch for the main theorem, but it would be nice to get more intuition from the main text.\n\n`Answer:` Thanks for your comment! We agree that the main text should provide more details and intuitions for the proofs of the main theorem. We will move the proof of Theorem 1 to the main text by taking advantage of the one additional page in the camera-ready version.\n\n-----\n\n`Question:` \n>I would much prefer the simulations in the appendix and the inclusion of the entirety of the proof of the main theorem in the main text with clear exposition of how the properties of analytic functions can be exploited to prove PE of u results in PE of x for these systems.\n\n`Answer:` Thanks for your suggestions! We will add more intuitions to the paper and move the simulations to the main text. Below is a brief discussion on intuitions. Firstly, notice that we only need to prove BMSB, which can be viewed as a stochastic version of PE. BMSB requires that any linear combination of feature functions should be positive with a non-vanishing probability. Since the linear combination of analytic functions is still an analytic function, and the zeros of an analytic function have measure zero, the probability that a linear combination of feature functions equal to 0 is also 0, as long as the noises follow semi-continuous distributions, which converts Lebesgue measure 0 to probability measure 0. We will incorporate this intuition together with more proof details in the revision.\n\n----\n\nThanks again for your helpful suggestions!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EgunbJEp8I", "reviewer": "Reviewer_on2R", "summary": "The authors study the problem of system identification from a trajectory generated by an unknown linearly parametrized nonlinear system whose nonlinearity is an analytic function. Specifically, they theoretically analyze to estimators: the least squares estimator, and the set membership estimator. Both estimators, while being widely used in practice, do not have theoretical guarantees in many of the settings in which they are applied. The authors give such guarantees, and also conduct numerical experiments on certain nonlinear systems.", "questions": "If instead of assuming that the nonlinearity is analytic, one assumed directly that there does not exist an open set on which it vanishes identically, would the proof carry through?", "limitations": "The authors adequately adress the limitations of their work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The authors provide non asymptotic theoretical guarantees for common system identification estimators in settings more broad than those covered by existing theoretical results. As far as I can tell the results are new and the argumentation is sound. They also conduct experiments which verify that such estimators converge to the true system parameters in practice.", "weaknesses": "While the theoretical arguments presented seem sound, I am not sure that the extension of system identification results to the case of linearly parametrized smooth nonlinear systems is sufficiently significant from a theoreitcal perspective.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your constructive comments! We will address your concerns below:\n\n---\n\n\n`Weakness:` \n>While the theoretical arguments presented seem sound, I am not sure that the extension of system identification results to the case of linearly parametrized smooth nonlinear systems is sufficiently significant from a theoretical perspective.\n\n`Answer:` Thanks for raising your concern! Though seemingly straightforward, the extension from linear systems to linearly parameterized nonlinear systems is actually **highly nontrivial as reflected by the development of learning-based control literature in the past few years**. In around 2020, the learning-based control community also thought this extension could be straightforward after extensive research on learning-based *linear* control. Unfortunately, the analysis of linearly parameterized nonlinear systems turned out to be much more challenging. For example, the efforts on straightforward extension from linear systems got stuck at bilinear systems (Sattar et al. 2022), which leaves the study of more general linearly parameterized nonlinear systems as an open question. Later, (Mania et al. 2022) provide a quite surprising counter-example, which shows that direct extension of linear control learning approaches may fail in some linearly parameterized nonlinear systems. This counter-example motivates new designs for nonlinear systems (Kowshik et al. 2021, Khosravi et al. 2023) instead of following the footsteps of learning-based linear control. \n\nHowever, our results indicate that a **much larger class** of linearly parameterized nonlinear systems exists than bilinear systems that still enjoy similar performance as linear systems. Our results greatly **reduce the gaps** in our understanding of linearly parameterized nonlinear systems compared with linear systems. In addition, our results actually support the reviewer's and the community's initial intuition: linear systems and linearly parameterized nonlinear systems indeed share a lot of similarities, as long as nonlinear systems are analytic. This is an interesting and novel message to the learning-based control community.\n\nTheoretically, the major challenge of this work is to identify the largest possible yet reasonable class of systems that enjoys similar performance to linear systems. At first, we established this result for quadratic systems via pretty involved algebraic manipulations, but later, we realized that by leveraging the Paley-Zygmund concentration inequality (Petrov 2007) and the properties of analytic functions, we can generalize the results to all analytic nonlinear feature functions. \n\nThe significance of this work is also recognized by Reviewer Dfmt, who finds our work \"greatly extends the original results to a much larger class of systems\", and by Reviewer wxwx, who thinks this work \"has great potential for practical application.\" \n\nWe are happy to provide more discussions if you have remaining questions or concerns! We will add the explanations above to the revised paper.\n\n&nbsp;\n\n----\n\n`Question`: \n>If instead of assuming that the nonlinearity is analytic, one assumed directly that there does not exist an open set on which it vanishes identically, would the proof carry through?\n\n`Answer:` Thanks for raising this question! If the system is 1-dimensional, then it is enough to assume directly that there does not exist a non-empty open set on which the feature function vanishes identically. However, for multi-dimensional systems, there are multiple feature functions, so we need to assume any linear combination of these feature functions does not vanish on a non-empty open set. We didn't present this assumption in our paper because we find it difficult to verify in practice. Nevertheless, we agree that this condition may contain a larger class than analytic functions, so we will include this and the corresponding discussions in the revised manuscript.\n\n&nbsp;\n\n----\n\n\n\nWe are happy to discuss more if the reviewer has remaining concerns or additional questions! Hope our response has addressed your concerns successfully! Look forward to hearing from you soon!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Zt0vKUTeF7", "reviewer": "Reviewer_wxwx", "summary": "The manuscript provides theoretical guarantees for nonlinear system identification using non-active i.i.d. noises, extending from linear systems to linearly parametrized nonlinear systems with analytic feature functions.  The findings demonstrate that non-active i.i.d. noises are capable of efficiently learning these systems with a non-asymptotic convergence rate.", "questions": "Can the authors please clarify the implications of the assumptions regarding bounded noises in more practical scenarios? It would be highly beneficial to delve deeper into the impact of these theoretical assumptions on real-world applications.", "limitations": "It is recommended to further explore the potential limitations of this  theoretical guarantees in practical applications. For instance, whether non-asymptotic convergence implies reduced data collection efficiency for some high-dimensional systems, and whether it is still preferable to actively design experiments in certain scenarios.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Training data selection is a crucial factor in ensuring the generalizability and robustness of identification algorithms. This is particularly important to linearly parametrized nonlinear systems, as there is still a theoretical gap regarding the effectiveness of non-active i.i.d. noise exploration. The study is well-motivated and has great potential for practical application. The authors establish conditions on noise that guarantee probabilistic persistent excitation for nonlinear dynamical systems, as defined by the BMSB condition. The findings in this study provide theoretical support for designing training data and identifying nonlinear systems.", "weaknesses": "Although the authors present an interesting idea, the manuscript could be improved by addressing the following concerns: 1. It is suggested to discuss the potential limitations of the non-asymptotic convergence rate in practical applications. 2. The analysis of the numerical experiments lacks depth. Could the authors further explore the convergence characteristics and the advantages and disadvantages of using i.i.d. noise for excitation? 3. The proof sketches could benefit from additional clarifications to enhance readability. For example, in line 234, the meaning of $\\delta$ and $\\bar{b}_\\phi$ could be re-mentioned.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your helpful suggestions! We discuss your concerns and suggestions below. (For figures, please refer to rebuttal.pdf)\n\n-----\n\n`Weakness 1 & Limitation`: \n\n**On actively designing experiments in certain scenarios**\n\n`A:` In certain scenarios, active exploration can be preferable despite the theoretical guarantees of non-active exploration. For instance, consider the following scenarios: \n1. Some feature functions are sharper in certain regions away from the origin. For example, in a system described by $\\dot x = \\theta_{*} u^{3}+w_t$, $u^3$ is flat around $u=0$ but sharp around $u=3$. Active exploration can collect more useful data in these sharp regions, improving convergence performance over non-active exploration. Figure 4 in rebuttal.pdf shows such performance; \n\n2. For a stable system, inactive exploration only explores around an equilibrium point. But in some cases, the exploration can be boosted by deliberately driving the system to other larger states because larger states can increase the signal-to-noise ratio and improve the information in the data collected; \n\n3. For systems that are very sensitive to noises, the system may become unstable or even suffer cascading failures after adding exploration noises. In those systems, it is better to use a carefully designed controller that can actively explore while being safe.\n\n&nbsp;\n\n**On data efficiency in high-order systems**\n\n`A:` Data efficiency decreases as the system dimension increases. This is evident in simulations of a cascade system with quadratic sub-systems as shown in Figure 3 in rebuttal.pdf. \n\n&nbsp;\n\n**Other potential limitations of theoretical guarantees in practical applications**\n\n`A:`  Real-world disturbances are more complex than the i.i.d. noises considered in this paper. Disturbances can be influenced by factors like fluid and aerodynamic dynamics, which may not be captured accurately and can include non-analytic components. Modeling may also miss high-frequency errors. In these scenarios, our convergence rate may become invalid. It is an exciting direction to test LSE in realistic scenarios and see when the convergence rate holds and conduct new convergence analysis when existing bounds fail. \n\n&nbsp;\n\n----\n\n\n\n`Weakness 2`\n\n**On convergence characteristics**\n\n`A:` We provide additional simulation results to explore the following convergence characteristics in rebuttal.pdf.\n\n1. State Dimensions-- Increasing the dimension leads to worse convergence performance, consistent with theoretical bounds (see Figure 3); \n\n2. Exploration Noise-- In a pendulum example, higher exploration noises ($\\sigma_{u}$) improve convergence performance (Figure 1.a), which is consistent with our theoretical bound as shown by a decrease in $1/s_{\\phi}p_{\\phi}$ with increased $\\sigma_{u}$ (Figure 1.b); \n\n3. Disturbance Noise-- The effect of disturbance noise ($\\sigma_{w}$) on convergence varies by system. In a pendulum example, higher $\\sigma_{w}$ worsens convergence (Figure 1.c), which is consistent with terms capturing its effect in our theoretical bound ($\\sigma_{w}/s_{\\phi}p_{\\phi}$ in Figure 1.d). \n\n&nbsp;\n\n**Pros and Cons of i.i.d. exploration noises**\n\n`A:` The major advantage is the simplicity and generality of this approach. One does not need an additional special design for different systems but can simply add i.i.d. noises to the existing controller.  Besides, it saves computation time to compute active exploration design. Another advantage is that i.i.d. exploration makes it easy to balance exploration and exploitation: this can be done by controlling the size of the exploration noises vs. the near-optimal nominal controller.  \n\nMost disadvantages of i.i.d. exploration noises are discussed in our response to `Weakness 1 & Limitation` under **on actively designing experiments in certain scenarios**. In addition, i.i.d. exploration noises may create fluctuations that are undesirable for some applications. It is usually recommended to use sinusoidal noises instead for more steady inputs. \n\n\n&nbsp;\n\n----\n\n\n\n\n`Weakness 3:` **Readability of the Proof Sketch**\n\n`A:` In the revised manuscript, we will re-mention the meanings of these important variables and concepts. We will also add more details to the proof sketch to improve the readability.\n\n&nbsp;\n\n----\n\n\n\n`Question:` **Practical impacts of bounded Noise Assumption**\n\n`A:` Firstly, most noises in practical scenarios are arguably bounded. For example, the forces/thrusts by wind gusts or fluid dynamics are bounded for robots/mechanics in the air or in the water, the power generations are also bounded for a time step, which is usually a small time period, etc. However, the bounds of the noises are usually unknown. In many cases, only a conservative upper bound can be acquired. Though LSE does not require the knowledge of the noise bounds during implementation, our convergence rate bound can become over-conservative if the noise bounds are also conservative. Another potential issue is when the upper bounds are not conservative but fail to consider a few outliers. In this case, the convergence rate may still hold because the constants in the convergence rate are usually quite conservative. However, the major challenge comes from stability: the few outliers may drive the system to be unstable, thus causing unsafe system behaviors or even causing numeric issues during system identification.\n\n----\n\nWe will add the discussions above to the revised manuscript. We are happy to discuss more if the reviewer has more questions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Zigd1VxFqJ", "reviewer": "Reviewer_QHWP", "summary": "This paper studies the problem of identifying an observable stochastic nonlinear dynamical system, in case the transition function is linearly parametrized and the noise is additive. The authors assume that the feature functions are analytic, and both the inputs and the noises are i.i.d., bounded, semi-continuous and have nonvanishing variances in each coordinate direction. It is also assumed that the system is locally input-to-state stable. Two kinds of estimation methods are studied: the classical least-squares estimate (LSE), which provides point estimates, and a set membership method, which provides region estimates. Finite sample bounds for the performance of LSE are proved, based on a block-martingale-small-ball condition, for both the open-loop and the close-loop cases. The sample complexity of the set membership method is studied under an additional assumption (tight bound on disturbance) and only for open-loop (i.i.d.) inputs. Finally, the authors present some numerical evaluations of LSE and set membership methods on pendulum and quadrotor examples to empirically illustrate their convergence rates.", "questions": "- What is the intuitive meaning of Assumption 5 (tight bound on disturbance)? This should be explained in the paper.", "limitations": "There is a section dedicated to the limitations of the work, which is a good thing. On the other hand, this section did not mention some key limitations, such as bounded noises, bounded and i.i.d. inputs, as well was fully observable states.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The presentation is clear, the paper is well-structured, the need assumptions are precisely stated.\n- The LSE are widely used, and the set membership approach is also reasonable and practically relevant.\n- Sample complexity analysis of system identification methods for nonlinear systems is an important problem. On the other hand, it is more relevant for control theory than to machine learning.\n- Finite sample error bounds are provided for both methods under the assumption that the features are analytic. This approach seems original and could be interesting for the community.\n- The examples illustrate well the theoretical viability of the analytic features assumption.", "weaknesses": "- Many of the assumptions are restrictive, such as bounded noises and inputs. Moreover, the inputs should also be i.i.d. (or should have an additive i.i.d. exploration noise, for the closed-loop case) which is unrealistic.\n- The error bounds contain terms which are unknown in practice, such as s_\\phi.\n- Corollary 1: the controller for the closed-loop case also contains an additive noise term that satisfies the assumptions for the open-loop inputs, and the system with the controller satisfies the stability assumption, in which case the statement becomes a simple consequence of Theorem 1. A case without additional noises on the inputs would have been much more interesting.\n- The figures do not show the actual bounds deducted by the paper, they only illustrate the empirical performance of LSE and set membership identification, which is a bit pointless, as they are classical, well-studied methods. I understand that the bounds of the paper are theoretical in nature, so they are conservative and mostly just give the convergence rate, still showing them (for example, on a logarithmic scale) would have been informative.\n- The title could be misleading, as the word \"analytic\" should refer to the feature vectors, but in the current title the term \"analytic system identification\" could also be understood in a way that the obtained solution is analytic.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable comments!\n\n---\n\n`Q1`: **Bounded noises/inputs**\n\n`A`: First, we politely point out that, though **linear** control usually considers unbounded noises/inputs, bounded noises/inputs are commonly studied in many **nonlinear** control literature (Mania et al. 2022, Shi et al. 2021, Kim et al. 2024). \n\nSecond, even for nonlinear control papers with unbounded noises/inputs, they usually impose **stronger assumptions on system dynamics**, e.g. globally exponentially stable systems (Sattar & Oymak 2022), or global Lipschitz smooth dynamics (Lee et al. 2024). However, in practice, most nonlinear systems can only be locally stable (Slotine & Li 1991). Further, global Lipschitz smoothness doesn't include polynomial systems with order >=3, which have many applications (see Example 2 in our paper, Slotine & Li 1991). \n\nThus, there is a **tradeoff** between noise assumptions vs. dynamics assumptions. For physical system applications, we think bounded noises/inputs are more practical than globally stable or globally smooth dynamics. After all, most noises in physical systems are bounded, e.g. wind gusts for quadrotors, renewable energy generation for power systems, etc.; and most inputs are also bounded, e.g. bounded thrusts from propellers and bounded energy generation by conventional power plants. \n\nYet, it is interesting to study convergence rates under unbounded noises but stronger dynamics assumptions. After a quick check, our results still hold under the assumptions in (Sattar & Oymak 2022), but assumptions in other papers need more work.\n\n&nbsp;\n\n---\n\n`Q1 cont'd & Q3`:  **I.i.d. exploration noises & Cor. 1**\n\n`A`: First, we politely mention that i.i.d. exploration noises are commonly added to existing controllers to provide necessary exploration when learning linear (Simchowitz & Foster 2020, Dean et al. 2019) and nonlinear systems (Sattar et al. 2023, Li et al. 2023). Compared with other exploration methods, e.g. optimism-in-the-face-of-uncertainty (OFU), Thompson sampling (TS), and PE-based recursive constrained optimization (RCO) (Lu & Cannon 2023), exploration noises are popular for the following reasons:\n- Generating i.i.d. noises is usually much **simpler and less computationally demanding** than other methods, e.g. OFU can be intractable for nonlinear control (see Kakade et al. 2020), TS's posterior sampling and RCO are also time-consuming.\n- Exploration noises are a **generic plug-in** to most existing controllers and don't need new control designs as in OFU, etc.\n- **Optimal performance guarantees** can be achieved by additive i.i.d. exploration noises on linear systems (Simchowitz & Foster 2020), which motivates its applications on nonlinear systems. \n\nRegarding the practical challenges and how to address them:\n- Locally stable systems may become **unstable** with large exploration noises. To address this, one can 1) start from a small exploration noise then gradually increase it, 2) adopt a stability certificate and switch to a noiseless stabilizing controller when the system fails the certificate (Fisac et al. 2018).\n- In some applications, the **fluctuations** caused by i.i.d. noises are not desirable. To address this, it is common to replace the i.i.d. noises with sinusoidal noises, which enjoy similar empirical performances (Nesic et al. 2012).\n\nAs for Cor. 1 without i.i.d. noises, we note that if the noiseless inputs satisfy BMSB, then our convergence rates still hold. The major difficulty is designing such noiseless inputs and formally proving BMSB.\n\nWe will add the discussions to the revised paper. We are happy to discuss more if you have remaining concerns!\n\n&nbsp;\n\n---\n\n`Q2`: **Unknown $s_\\phi$**\n\n`A`: The empirical values of $(s_\\phi,p_\\phi)$ can be estimated by Monte Carlo simulation (see Fig. 5 in rebuttal.pdf). By definition, $(s_\\phi,p_\\phi)$ can take multiple values for the same system so we plot them as a curve. When computing the theoretical upper bounds in Thm. 2 (Fig. 2 in rebuttal.pdf), we choose the largest $s_\\phi p_\\phi$ for better bounds.\n\nThe explicit formulas of $(s_\\phi, p_\\phi)$ call for stronger assumptions on dynamics, and we don't think a generic formula exists for all analytic nonlinear systems. During our research, we obtained formulas of $(s_\\phi,p_\\phi)$ for quadratic systems by algebraic manipulation, but we didn't use this proof because it cannot be generalized to other systems. It is left as future work to provide explicit forms of $(s_\\phi,p_\\phi)$ for other systems.\n\n&nbsp;\n\n---\n\n`Q4`: **Plot theoretical bounds**\n\n`A`: We plot theoretical bounds and empirical performance in Fig. 2 of rebuttal.pdf, both of which have slope -1/2 in a log-log scale, being consistent with our convergence rate.\n \n`Q5 & Q7`: **Title & limitations**\n\n`A`: Thanks for the suggestions! We will revise the title and discuss these limitations.\n\n`Q6`: **Intuition of Ass. 5**\n\n`A`: We will add the following intuitions. Consider the upper bound of a 1-dim $w_t$ bounded by $-w_{\\max}\\leq w_t\\leq w_{\\max}$. Ass. 5 assumes a tight bound, meaning that there is a non-vanishing probability for $w_t$ to visit around $w_{\\max}$, i.e. $P(w_{\\max}-\\epsilon\\leq w_t\\leq w_{\\max})>0$ for any $\\epsilon>0$. \n\n&nbsp;\n\n---\n\nReferences\n\nKakade et al. 2020: Information-theoretic regret bounds for online nonlinear control, Neurips.\n\nShi et al. 2021: Meta-adaptive nonlinear control: Theory and algorithms, Neurips.\n\nLee et al. 2024: Active Learning for Control-Oriented Identification of Nonlinear Systems.\n\nKim & Lavaei 2024: Online Bandit Control with Dynamic Batch Length and Adaptive Learning Rate.\n\nSlotine & Li 1991: Applied nonlinear control\n\nLu & Cannon 2023: Robust adaptive model predictive control with persistent excitation conditions, Automatica.\n\nFisac et al. 2018: A general safety framework for learning-based control in uncertain robotic systems, IEEE-TAC.\n\nNesic et al. 2012, A framework for extremum seeking control of systems with parameter uncertainties. IEEE-TAC.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Thanks for your time and valuable comments! The attached is a pdf that contains new plots for addressing the questions from Reviewer wxwx and Reviewer QHWP.

Please feel free to ask us if you have any other questions. Looking forward to hearing your feedback!

Meta-review: This paper extends important results from linear and bi-linear system identification to a broader class of nonlinear systems by providing non-asymptotic guarantees for both least-squares estimators (LSE) and set-membership estimators (SME) within a framework that incorporates analytic functions. The work is rigorous, original, and well-presented, with reviewers particularly appreciating the clarity and significance of the theoretical contributions. While some concerns were raised regarding the restrictive nature of certain assumptions and the conservative nature of the theoretical bounds, the overall impact and novelty of the work still hold. Therefore, I recommend acceptance.
Decision: Accept (poster)