Finite Sample Analyses for Continuous-time Linear Systems: System Identification and Online Control

We extend our gratitude to the reviewer for the constructive suggestions and questions. We have added relevant experiments and clarified the main novelty and contributions of the paper. We address the reviewer's concerns belows:

Q1: Given the discrete time results in the literature, one may hope that the assumption of a known stabilizing controller would not be needed for the online control algorithm. This assumption has been removed in the discrete-time setting.

A1: Thank you for the insightful comment. While existing methods like Thompson sampling[1] have removed this assumption, they face another issue: the state is not well-constrained during the early exploration phase before a stabilizing controller is identified. Instead of relying on a single trajectory without a stabilizing controller, we prefer to first find a stabilizing controller using multiple trajectories, as shown in Algorithm 2, and then proceed with single-trajectory online control.

Q2: Section 5.2 provides a detailed comparison to the line of work of Faradonbeh et al. There is clearly a difference, however the delta does not seem to be large. The previous work uses a slightly stronger assumption and the algorithm is different. Removing the annoying log factor is a clear contribution, but the technical and algorithmic contribution is not as clear.

A2: Thank you for pointing out this question. We have updated Section 5 to emphasize the differences and contributions more clearly. The modifications have been highlighted and marked in blue for clarity in the updated version.

Q3: The results in the case where a stabilizing controller is not known are weaker than the other two main contributions. They do not seem to provide a practical algorithm or novel technical tool.

A3: We acknowledge that this contribution is relatively weaker compared to the other two. This result is primarily a straightforward application of the system identification method. Our main goal in proposing this algorithm is to provide an efficient approach for obtaining a stabilizer.

Q4: Empirical evaluation of the proposed algorithms is not provided. Such results would strengthen the impact of the theory.

A4: We appreciate the reviewer's suggestions. In response, we have added an experimental section in Section 5.3 of the paper, comparing our algorithm with the baseline algorithm. Please refer to the latest PDF version for details.

Q5: What are the major technical challenges in continuous time (or in your reduction) when transitioning results on control of discrete time systems without an initial stabilizing controller to continuous time?

A5: Thank you for the question. The primary technical challenge lies in providing a sharp bound on the early exploration phase rather than in transitioning the results. While methods like Thompson sampling [1] can work with sufficient exploration, the state may experience rapid divergence during early exploration, making these methods impractical. To address this, we adopt a simpler and more efficient approach: using multiple trajectories to first find a stabilizer and then applying control.

Q6: Beyond the novel discretization, what technical challenges (and novel technical ideas) where needed when adapting the discrete time tools to continuous time?

A6: Thank you for pointing out this question. The technical novelty lies in finding the exact reverse $Ah$ of the matrix exponential $e^{Ah}$. Two key novel ideas address this challenge. First, we identify a domain \|X\|\leq \frac{1}{4}\ where $f(X)=e^{X}$ is one-to-one, and the distance between $f(X_1)$ and $f(X_2)$ is lower bounded by $\frac{1}{2}\|X_1-X_2\|$, as shown in Lemma 7 in our paper. This property enables the analysis of estimation errors. Second, we apply Taylor expansion to compute the estimator. Detailed descriptions are highlighted in blue in Section 4.

Finally, we thank the reviewer once again for the effort in providing us with valuable suggestions. We will continue to provide clarifications if the reviewer has any further questions.

References

[1] Shirani Faradonbeh, M. K., Shirani Faradonbeh, M. S., & Bayati, M. (2022). Thompson sampling efficiently learns to control diffusion processes. Advances in Neural Information Processing Systems, 35, 3871-3884.

We express our gratitude to the reviewer for the insightful comments. We address the reviewer's questions in more detail as follows:

Q1: There are no empirical results presented in paper.

A1: We appreciate the reviewer's suggestions. In response, we have added an experimental section in Section 5.3 of the paper, comparing our algorithm with the baseline algorithm. Please refer to the latest PDF version for details.

Q2: There are typos in Algorithm 3, line 435, on page 6 (in steps 4 and 5), and in the Abstract.

A2: We sincerely thank the reviewer for pointing out the typos. These have been corrected in the updated version, with changes highlighted in blue.

Q3: Also I confess that I have not checked each mathematical conduction presented in the paper in details since this paper is mathematical heavily.

A3: Thank you for regarding the mathematical details. To address this, we have made some modifications in the appendix to improve clarity and ensure the mathematical derivations are easier to follow.

Q4: This algorithm can not be applied in nonstochastic settings or adversarial settings since in exploration stage the action is perturbed by gaussian noises.

A4: We thank the reviewer for the insightful comment. Our primary focus is on system identification and regret analysis for continuous-time linear systems with stochastic noise. Addressing nonstochastic noise is indeed a more challenging problem. Current research of nonstochastic noise has only achieved sublinear regret for discrete-time systems[1][2], and not for continuous-time systems. We consider this a promising direction for future work.

We thank the reviewer once again for the valuable and helpful suggestions. We would be happy to provide further clarifications if the reviewer has any additional questions.

References

[1] Agarwal, Naman, et al. "Online control with adversarial disturbances." International Conference on Machine Learning. PMLR, 2019.

[2] Hazan, Elad, Sham Kakade, and Karan Singh. "The nonstochastic control problem." Algorithmic Learning Theory. PMLR, 2020.

We thank the reviewer for the comments and constructive suggestions. We have added relevant experiments and clarified the main novelty and contributions of the paper. We address the reviewer's questions in more detail as follows:

Q1: It is hard to trust the regret bounds presented in the paper without any numerical simulations, and it is also hard to accept the paper in good faith without a limitations section.

A1: We appreciate the reviewer's suggestions. In response, we have added an experimental section in Section 5.3 of the paper, comparing our algorithm with the baseline algorithm. Please refer to the latest PDF version for details.

Q2: The assumption of having $H>1$ could be justified further in line 349. For instance, it is a significant weakening to run the system of multiple trajectories, instead of a single, purely online, trajectory.

A2: Our primary focus is on the system identification problem when a stabilizer $K$ is known beforehand. Running multiple trajectories is not our main concern; it serves merely as a tool to estimate the stabilizer $K$ in cases where no prior information about it is available.

Q3: The paper only studies the model of the LQR cost function, but how does this extend to more general costs?

A3: We thank the reviewer's comment. Our primary focus is on system identification. The LQR cost function serves as an example to demonstrate that our system identification method is applicable to online control and performs well under the finite observation assumption. For general costs, a explore-then-exploit strategy can still be applied, and we consider this a promising direction for future work.

Q4: The exact technical novelty of the paper seems to be unclear.

A4: We appreciate the reviewer's feedback and provide a clearer explanation of the contributions. The technical novelty lies in finding the exact reverse $Ah$ of the matrix exponential $e^{Ah}$. Two key novel ideas address this challenge. First, we identify a domain \|X\|\leq \frac{1}{4}\ where $f(X)=e^{X}$ is one-to-one, and the distance between $f(X_1)$ and $f(X_2)$ is lower bounded by $\frac{1}{2}\|X_1-X_2\|$, as shown in Lemma 7 in our paper. This property enables the analysis of estimation errors. Second, we apply Taylor expansion to compute the estimator. Detailed descriptions are highlighted in blue in Section 4.

Q5: Why aren’t the time intervals chosen in a dynamic fashion? Surely, this would lead to better bounds?

A5: We appreciate the reviewer’s question. We also considered using dynamic time intervals during our analysis. We find that changing the time interval gap does not significantly improve performance. As stated in Theorem 2 regarding the lower bound, the estimation error is determined by the total running time $T$, rather than the interval gap.

Q6: Line 162, would be good to clarify somewhere that $\mathcal{S}_+$ represents the set of symmetric PSD matrices,

A6: Thank you for pointing this out. We have updated the text to clarify that $\mathcal{S}_+$ represents the set of symmetric positive semi-definite matrices.

Q7: How do we know that the optimal mapping is unique in line 169? If it is not unique, then the convergence described in Line 176 is not guaranteed?

A7: Thank you for the question. The uniqueness of the optimal mapping in line 169 is guaranteed by the assumptions on $A,B,Q,R$, as detailed in [1]. The convergence described in line 176, however, relies on the properties of the Riccati function rather than the uniqueness of the optimal mapping.

Q8: Why is the determinant in line 1456 never becomes 0?

A8: Thank you for raising this question. We ensure that $\lambda\leq\frac{1}{4\|\Sigma\|}$, which guarantees that for any nonzero $x$, $\|(I-2\lambda\Sigma)x\|\geq \|x\|-\|2\lambda\Sigma x\|\geq \|x\|-\frac{1}{2}\|x\|>0.$

Thus, the determinant of $I -\lambda \Sigma$ never becomes zero.

Q9: How small should $h$ in line 283 be for the estimation to hold?

A9: Thank you for the question. The value of $h$ can follow $\frac{1}{15\kappa_{A}}$ as specified in Assumption 1.

Q10: There are many notions of regret in line 190. It would be good for the authors to clarify that this is the expected regret of the system.

A10: Thank you for pointing this out. We have clarified the statement in the updated version to specify that this refers to the expected regret of the system.

Q11: Grammatical issues and missing reference.

A11: We thank the reviewer for pointing out the mistakes. These have been corrected in the updated version, with changes highlighted in blue.

We thank the reviewer once again for the valuable and helpful suggestions. We would be happy to provide further clarifications if the reviewer has any additional questions.

References

[1] Yong, Jiongmin, and Xun Yu Zhou. Stochastic controls: Hamiltonian systems and HJB equations. Vol. 43. Springer Science & Business Media, 2012.

I thank the authors for their detailed reply.

Regarding the experiments, I have a couple of questions:

1. Why does the estimation error increase so rapidly in Figure 2?
2. Since this is a 3x3 matrix, each element between [-1,1], the Frobenius norm of this matrix is always bounded (from above) by sqrt(9*1^2) = 3, but this is the same (worst case) error the model gets even after seeing 500 trajectories (Figure 2). It seems that the model requires around 2000 trajectories to get an estimation error below 1.0. Can the authors comment on why this is the case? In general, some discussion about these results would be great.
3. 2000 trajectories is a lot. As the authors mention in their rebuttals, they are not concerned with the amount of trajectories required... however, I fear that this large number makes the algorithm intractable for actual applications.

Also, as I asked in my initial review: $\kappa$ is assumed to be known in advance (this is potentially a very significant assumption since the entire point of the system identification is to estimate A and B). I would certainly appreciate it if the authors could comment on this.

I wonder if "the technical innovation" the authors describe is novel. Upon looking at the proof of Lemma 7, the proof seems straightforward. Based on point 3 in the author's reply, this seems to be a result focused more on stability, rather than optimization. This makes me wonder if the results are as novel as the authors claim, since many works in the control literature work in continuous-time settings. I also feel that this result should be compared with the nonstochastic optimization and policy optimization results.

Based on the above, I tentatively lower my score to a 3.

We sincerely appreciate the reviewer's insightful comments and suggestions. Below, we provide responses to the raised questions.

Q1: Concern of the novelty and significance. The system ID of linear systems is very well studied for discrete-time systems. The extension to continuous time systems is interesting, but I don't see significant technical difficulty. Besides, most classical control literature [1] considers continuous time linear systems already in the past. The authors should provide a better summary of the technical novelty for their convergence rate analysis.

A1: We appreciate the reviewer's feedback and provide a clearer explanation of the contributions. The technical novelty lies in finding the exact reverse $Ah$ of the matrix exponential $e^{Ah}$. Two key ideas address this challenge. First, we identify a domain \|X\|\leq \frac{1}{4}\ where $f(X)=e^{X}$ is one-to-one, and the distance between $f(X_1)$ and $f(X_2)$ is lower bounded by $\frac{1}{2}\|X_1-X_2\|$, as shown in Lemma 7 in our paper. This property enables the analysis of estimation errors. Second, we apply Taylor expansion to compute the estimator. Detailed descriptions are highlighted in blue in Section 4.

Q2: The lower bound and the regret analysis also seem to be straightforward extensions of the existing results for the discrete time systems in [2]. The authors should provide a better summary of the technical novelty for their lower bound analysis.

A2: We thank for the reviewer's suggestion. The key novelty lies in analyzing the discretized transformation law, as shown in Equation 7 in our paper, and conditioning on any finite set of observed times. While we acknowledge that our approach shares similarities with prior works like [2] in addressing this well-described problem, our method introduces a new perspective tailored to continuous-time systems.

Q3: This paper mentions that the one major motivation is practicability: most linear systems in practice are continuous time. But does this paper consider other practical issues, such as uneven time sampling?

A3: We appreciate the reviewer's feedback. We also considered using dynamic time intervals during our analysis. We find that changing the time interval gap does not significantly improve performance. As stated in Theorem 2 regarding the lower bound, the estimation error is determined by the total running time $T$, rather than the interval gap. This is one of the key differences between discrete and continuous systems.

Q4: Another practical issue is the imperfect state observation. This is easier than output feedback but this is also a common issue in real-world applications. How can the proposed algorithm be generalized to handle imperfect state observations?

A4: We agree that imperfect state observation is an important scenario to address. If the observed state serves as an unbiased estimator of the true state, it can be directly incorporated into our method. Even when the observation error is stochastic, our system identification approach remains effective. By setting $U_{t}=KX_{t}+u_{k}$ for $t\in[kh,(k+1)h]$, the observed state transitions as: $X_{(k+1)h}=AX_{kh}+BU_{kh}+e_{k}.$

where $e_{k}$ depends on the observation error and the stochastic noise $W_t$. Since $e_k$ has zero mean, we can apply similar analytical techniques as in our method to handle this case.

Finally, we thank the reviewer once again for the effort in providing us with valuable and helpful suggestions. We will continue to provide clarifications if the reviewer has any further questions.

References

[1] Kopp, R.E. and Orford, R.J., 1963. Linear regression applied to system identification for adaptive control systems. Aiaa Journal, 1(10), pp.2300-2306.

[2] Simchowitz, M., Mania, H., Tu, S., Jordan, M.I. and Recht, B., 2018, July. Learning without mixing: Towards a sharp analysis of linear system identification. In Conference On Learning Theory (pp. 439-473). PMLR.

Thanks again for your valuable feedback! Could you please let us know whether your concerns have been addressed? We are happy to make further updates if you have any other questions or suggestions.