Identification of Analytic Nonlinear Dynamical Systems with Non-asymptotic Guarantees

Thanks for your valuable comments!

---

Q1: Bounded noises/inputs

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).

Second, 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).

Thus, 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.

Yet, 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.

 

---

Q1 cont'd & Q3: I.i.d. exploration noises & Cor. 1

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:

• 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.
• Exploration noises are a generic plug-in to most existing controllers and don't need new control designs as in OFU, etc.
• 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.

Regarding the practical challenges and how to address them:

• 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).
• 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).

As 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.

We will add the discussions to the revised paper. We are happy to discuss more if you have remaining concerns!

 

---

Q2: Unknown $s_\phi$

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.

The 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.

 

---

Q4: Plot theoretical bounds

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.

Q5 & Q7: Title & limitations

A: Thanks for the suggestions! We will revise the title and discuss these limitations.

Q6: Intuition of Ass. 5

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$.

 

---

References

Kakade et al. 2020: Information-theoretic regret bounds for online nonlinear control, Neurips.

Shi et al. 2021: Meta-adaptive nonlinear control: Theory and algorithms, Neurips.

Lee et al. 2024: Active Learning for Control-Oriented Identification of Nonlinear Systems.

Kim & Lavaei 2024: Online Bandit Control with Dynamic Batch Length and Adaptive Learning Rate.

Slotine & Li 1991: Applied nonlinear control

Lu & Cannon 2023: Robust adaptive model predictive control with persistent excitation conditions, Automatica.

Fisac et al. 2018: A general safety framework for learning-based control in uncertain robotic systems, IEEE-TAC.

Nesic et al. 2012, A framework for extremum seeking control of systems with parameter uncertainties. IEEE-TAC.

Thank you very much for your helpful suggestions! We discuss your concerns and suggestions below. (For figures, please refer to rebuttal.pdf)

---

Weakness 1 & Limitation:

On actively designing experiments in certain scenarios

A: In certain scenarios, active exploration can be preferable despite the theoretical guarantees of non-active exploration. For instance, consider the following scenarios:

1. 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;

2. 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;

3. 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.

 

On data efficiency in high-order systems

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.

 

Other potential limitations of theoretical guarantees in practical applications

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.

 

---

Weakness 2

On convergence characteristics

A: We provide additional simulation results to explore the following convergence characteristics in rebuttal.pdf.

1. State Dimensions-- Increasing the dimension leads to worse convergence performance, consistent with theoretical bounds (see Figure 3);

2. 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);

3. 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).

 

Pros and Cons of i.i.d. exploration noises

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.

Most 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.

 

---

Weakness 3: Readability of the Proof Sketch

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.

 

---

Question: Practical impacts of bounded Noise Assumption

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.

---

We will add the discussions above to the revised manuscript. We are happy to discuss more if the reviewer has more questions.

Thank you very much for your constructive comments! We will address your concerns below:

---

Weakness:

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.

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.

However, 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.

Theoretically, 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.

The 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."

We are happy to provide more discussions if you have remaining questions or concerns! We will add the explanations above to the revised paper.

 

---

Question:

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?

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.

 

---

We 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!

Thank you very much for your constructive comments! We will address the comments below.

---

Weakness:

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.

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.

---

Question:

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.

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.

---

Thanks again for your helpful suggestions!