Online Control with Adversarial Disturbance for Continuous-time Linear Systems

We extend our gratitude to the reviewer for the comments and suggestions. Below, we address the primary concern that has been raised. The minor issues and typographical errors have been corrected in our manuscript.

Q1: Could the authors provide more detailed explanations on the technical challenges of dealing with continuous-time systems compared with the analysis in a discretized one?

A1: We appreciate the reviewer for raising this question and we will provide the main technical challenge here. Both of these challenges arise when extending from discrete systems to continuous systems and we can not directly apply the method in [1] which is only suitable for discrete system.

For the first technical challenge of unbounded states in continuous system, as in discrete system it is straightforward to demonstrate that the state sequence by applying the dynamics inequality $\|x_{t+1}\| \le a\|x_t\| + b$ and the induction method presented in [1]. In continuous system, one naive approach is to use the Taylor expansion of each state to derive the recurrence formula of the state. However, this argument requires the prerequisite knowledge that the states within this neighborhood are bounded by the dynamics, leading to circular reasoning. We use Gronwall's inequality to overcome this challenge.

For the second challenge, initially we set out to follow the approach from [1], where the OCO parameters are updated at each step. Our regret is primarily composed of three components: the error caused by discretization $R_1$, the regret of OCO with memory $R_2$ and the difference between the actual cost and the approximate cost $R_3$. The discretization error $R_1$ is $O(hT)$, therefore if we achieve $O(\sqrt{T})$ regret, we must choose $h$ no more than $O(\frac{1}{\sqrt{T}})$.

If we update the OCO with memory parameter at each timestep follow the method in [1], we will incur the regret of OCO with memory $R_2 = O(H^{2.5}\sqrt{T})$. The difference between the actual cost and the approximate cost $R_3 = O(T(1-h\gamma)^{H})$. To achieve sublinear regret for the third term, we must choose $H = O(\frac{\log T}{h\gamma})$, but since $h$ is no more than $O(\frac{1}{\sqrt{T}})$, $H$ will be larger than $\Theta(\sqrt{T})$, therefore the second term $R_2$ will definitely exceed $O(\sqrt{T})$.

Therefore, we adjusted the frequency of updating the OCO parameters by introducing a two level algorithm approach, update the parameters once in every $m$ steps. This will incur the third term $R_3 = O(T(1-h\gamma)^{Hm})$ but keep the OCO with memory regret $R_2 = O(H^{2.5}\sqrt{T})$, so we can choose $H = O(\frac{\log T}{\gamma})$ and $m=O(\frac{1}{h})$. Then the term of $R_2$ is $O(\sqrt{T}\log T)$ and we achieve the same regret compare with the discrete system.

Q2: Definition 1 is a little different from the standard strong stability condition in discretized systems.

A2: We understand the reviewers' concern regarding the difference in definitions for discrete systems. We will provide further explanation here. For discrete systems, we have the following transition equation: $x_{t+1} = Ax_t+Bu_t + w_t.$ For continuous systems, the transition equation is: $\dot{x}_{t} = \tilde{A}x_t+\tilde{B}u_t + \tilde{w}_t.$

If we consider a relatively small time interval $h$, we can approximate it as follows: $x_{t+h} - x_t = \int_{0}^h \dot{x}_{t+s} ds \approx h( \tilde{A}x_t+\tilde{B}u_t + \tilde{w}_t).$

Therefore, we have $x_{t+h} \approx (I+h \tilde{A})x_t+h\tilde{B}u_t + h\tilde{w}_t.$ Thus, we can express the dynamics of the two systems as follows: $A \approx I+h \tilde{A}, B \approx h\tilde{B}.$ As the definition of strongly stable in discrete system is $A-BK = PLP^{-1}$, so we extend the definition to continuous system as $I+h\tilde{A}-h\tilde{B}K = PL_hP^{-1}$, that is $I+h(\tilde{A}-\tilde{B}K) = PL_hP^{-1}$.

Q3: Assumption 1, compared with the standard non-stochastic disturbances in discretized systems, uses an extra condition of the noise.

A3: We understand the reviewers' concern regarding the difference in assumptions for discrete systems. We will provide further explanation here. Similar to the analysis in A2, using the The Taylor formula with Lagrange remainder, we get

$$x_{t+h} = x_t + h \dot{x}_t + \frac{h^2}{2} \ddot{x}_m$$

where $m$ is a number between $[t,t+h]$.

Using the notation and analysis in A2, we get the following relation of discrete and continuous system:

$$w_{t} = h \tilde{w}_t + \frac{h^2}{2} \dot{\tilde{w}}_m$$

Therefore, if we have the assumption of $\|w_t\|$ is bounded in discrete system, we naturally extend the assumption to $\|\tilde{w}_t\|$ and $\|\dot{\tilde{w}}_t\|$ is bounded in continuous system. We will add some discussion of this assumption in our next version.

Q4: The arrangement of Section 3.2, missing citations in Section 4, missing definition of $g_t$.

A4: We sincerely appreciate the reviewers pointing out these errors, and we will correct them in the next version of the paper.

We thank the reviewer once again for the valuable and helpful suggestions. We would love 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.

We thank the reviewer for the comments and constructive suggestions. In the following, we focus on explaining why updating policy at each step fail. We also appreciate the comments on notations and will incoporate them in the updated version.

Q1: Why updating the DAC policy at each time step does not work.

A1: We appreciate the reviewer for raising this valuable question. Intuitively, as the disturbance $\omega_t$ is nonstochastic, updating the policy at each discrete step would make the policy unnecessarily sensitive to $\omega_t$ and can incur huge future regret for some worst case disturbance. An alternative would be to use a very small step size $\eta = \Theta(h)$ but large memory size $H = \Theta(1/h)$. However, such an algorithm would not be practical due to the huge memory requirement.

We provide more formal explanations below. Initially, we set out to follow the approach from [1], where the OCO parameters are updated at each step. Our regret is primarily composed of three components: the error caused by discretization $R_1$, the regret of OCO with memory $R_2$ and the difference between the actual cost and the approximate cost $R_3$. The discretization error $R_1$ is $O(hT)$, therefore if we achieve $O(\sqrt{T})$ regret, we must choose $h$ no more than $O(\frac{1}{\sqrt{T}})$.

If we update the OCO with memory parameter at each timestep follow the method in [1], we will incur the regret of OCO with memory $R_2 = O(H^{2.5}\sqrt{T})$. The difference between the actual cost and the approximate cost $R_3 = O(T(1-h\gamma)^{H})$. To achieve sublinear regret for the third term, we must choose $H = O(\frac{\log T}{h\gamma})$, but since $h$ is no more than $O(\frac{1}{\sqrt{T}})$, $H$ will be larger than $\Theta(\sqrt{T})$, therefore the second term $R_2$ will definitely exceed $O(\sqrt{T})$.

Therefore, we adjusted the frequency of updating the OCO parameters by introducing a new parameter $m$, update the parameters once in every $m$ steps. This will incur the third term $R_3 = O(T(1-h\gamma)^{Hm})$ but keep the OCO with memory regret $R_2 = O(H^{2.5}\sqrt{T})$, so we can choose $H = O(\frac{\log T}{\gamma})$ and $m=O(\frac{1}{h})$. Then the term of $R_2$ is $O(\sqrt{T}\log T)$ and we achieve the same regret compare with the discrete system.

Q2: The way the authors use to denote time steps is very confusing and $t+1$ and $t+h$ often seem to be used interchangeably.

A2: In lines 155-157 of the paper, we explained that we simplified the subscripts containing "h" to those without "h." However, when recording time, we used the time with "h." In the next version, we will further unify the notation by also writing the time without "h."

Q3: The matrices of the DAC policy are sometimes used with square brackets and sometimes without. $m$ and $n$ are most frequently used to denote the state and input dimension of the dynamial system, I suggest using different constants in Algorithm 1.

A3: In line 161, we explain that the subscripts of the DAC matrix represent the parameter in step $t$, while the superscripts denote each component. Since our paper does not focus on the state and input dimension of the dynamical system and the algorithm is dimension-free, we forgot this issue. We will use more appropriate notation in future versions. We appreciate the reviewer's reminder.

Q4: There are many typos in the proofs in the appendix. Some of the notations in the paper need to be corrected.

A4: We greatly appreciate the reviewer for carefully reading our appendix and providing many valuable suggestions for correcting the notation in the paper, and we will carefully check and correct these issues in the next version of the paper.

Q5: The assumption of $x_0=0$ should be stated somewhere in the main body of the text explicitly. The assumption requires the system to be initialized at the steady state of the system that the benchmark policy aims to stabilize.

A5: We use the condition $x_0=0$ in the proof, and we will add it to the assumptions. Our algorithm does not assume that the system must be initialized at a benchmark-stabilizable steady state; it only requires that the benchmark policy is strongly stable. We appreciate the reviewer's question.

References

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

We greatly appreciate the reviewer's valuable suggestions. We address the reviewer's questions as follows:

Q1: The paper lacks comparison with other state-of-the-art methods.

A1: We appreciate the reviewer's suggestion, and we will include a discussion of some recent works in the next version of the paper. We only compared our work with [3] in the paper. The papers [4][5] also focus on online control setups with continuous-time stochastic linear systems and unknown dynamics. They achieve $O(\sqrt{T}\log(T))$ regret by different approaches. [4] uses the Thompson sampling algorithm to learn optimal actions. [5] takes a randomized-estimates policy to balance exploration and exploitation.

The main difference between [3][4][5] and our paper is that they consider stochastic noise of Brownian motion, while the noise in our setup is adversarial. This makes our analysis completely different from theirs.

Q2: Experiments are conducted in simulated environments.

A2: We admit that we cannot run real-world experiments in a limited time. We believe that applying the algorithm to physical systems is a meaningful future direction.

Q3: The assumption of the access to $\dot{x}_t$ at each time step is strong.

A3: We did not assume access to the derivative of $x_t$ in the paper. As can be seen from Algorithm 1, we only require access to $x_t$. The design of the policy $u_t$ relies on $x_t$ and the estimated values of noise $\hat{w}_t$. The estimation $\hat{w}_t$, as shown in Equation 1, only depends solely on the past values of $x_t$ and $u_t$, not the state derivative.

Q4: Explain the definition of regret in section 3.4.

A4: Our definition of regret is based on [1] and [2], which study online control in discrete systems. In [1], the noise is stochastic, whereas in [2], the noise is adversarial. Lemma 4.3 in Paper 1 proves that under stochastic conditions, the optimal strategy is a strongly stable linear policy. Therefore, regret is measured against the optimal strongly stable policy. Paper 2 continues to use this definition of regret. Consequently, we have adopted their definition.

Q5: Assumption 1 and 2 are quite strict.

A5: Our use of Assumptions 1 and 2 follows those in paper [2] without modification. [2] primarily analyzes discrete systems, and our contribution is extending their results to continuous systems without additional assumptions. Furthermore, a function being bounded by a quadratic function does not necessarily imply that it is quadratic. For example, consider the function $C(x,u) = |x|^{1.5}+|u|^{1.5}$, it also satisfies this assumption.

Q6: The motivation of Definition 1.

A6: We appreciate the reviewers' question regarding the motivation behind the definition of "strongly stable." This definition originates from [1] and [2]. Strong-stability is a quantitative version of stability, any stable policy is stronglystable for some $\kappa$ and $\gamma$ (See Lemma B.1 in [1]). Conversely, strong-stability implies stability. A strongly stable policy is a policy that exhibits fast mixing and converges quickly to a steady-state distribution. Thus, this definition is equivalent to the stable policy, with the constants $\kappa$ and $\gamma$ introduced primarily for non-asymptotic theoretical analysis to obtain a more precise convergence bound.

Q7: The challenge of trading off approximation error & OCO regret in section 4 is subtle.

A7: We appreciate the reviewer for raising this valuable question. Initially, we set out to follow the approach from [2], where the OCO parameters are updated at each step. Our regret is primarily composed of three components: the error caused by discretization $R_1$, the regret of OCO with memory $R_2$ and the difference between the actual cost and the approximate cost $R_3$. The discretization error $R_1$ is $O(hT)$, therefore if we achieve $O(\sqrt{T})$ regret, we must choose $h$ no more than $O(\frac{1}{\sqrt{T}})$.

If we update the OCO with memory parameter at each timestep follow the method in [2], we will incur the regret of OCO with memory $R_2 = O(H^{2.5}\sqrt{T})$. The difference between the actual cost and the approximate cost $R_3 = O(T(1-h\gamma)^{H})$. To achieve sublinear regret for the third term, we must choose $H = O(\frac{\log T}{h\gamma})$, but since $h$ is no more than $O(\frac{1}{\sqrt{T}})$, $H$ will be larger than $\Theta(\sqrt{T})$, therefore the second term $R_2$ will definitely exceed $O(\sqrt{T})$.

Therefore, we adjusted the frequency of updating the OCO parameters by using a two-level approach and update the OCO parameters once in every $m$ steps. This will incur the third term $R_3 = O(T(1-h\gamma)^{Hm})$ but keep the OCO with memory regret $R_2 = O(H^{2.5}\sqrt{T})$, so we can choose $H = O(\frac{\log T}{\gamma})$ and $m=O(\frac{1}{h})$. Then the term of $R_2$ is $O(\sqrt{T}\log T)$ and we achieve the same regret compare with the discrete system.

Once again, we thank the reviewer for the constructive comments.

References

[1] Cohen, Alon, et al. "Online linear quadratic control." International Conference on Machine Learning. PMLR, 2018.

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

[3] Basei, Matteo, et al. "Logarithmic regret for episodic continuous-time linear-quadratic reinforcement learning over a finite-time horizon." Journal of Machine Learning Research 23.178 (2022): 1-34.

[4] Shirani Faradonbeh, Mohamad Kazem, Mohamad Sadegh Shirani Faradonbeh, and Mohsen Bayati. "Thompson sampling efficiently learns to control diffusion processes." Advances in Neural Information Processing Systems 35 (2022): 3871-3884.

[5] Faradonbeh, Mohamad Kazem Shirani, and Mohamad Sadegh Shirani Faradonbeh. "Online Reinforcement Learning in Stochastic Continuous-Time Systems." The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.

We express our gratitude to the reviewer for the insightful comments. We address the reviewer's concerns belows:

Q1: There is a gap between the theoretical results and the experimental results. More discussion is needed.

A1: We appreciate the reviewers for raising this issue. On a high level, we first identify the connection between the popular technique known as domain randomization and a theoretical framework knwon as nonstochastic control. Next, we noticed that existing nonstochastic control algorithms cannot be readily applied to common domain randomization experiments. Therefore, we propose a continuous time analysis and highlight two adaptations (skip and stack). We then verify that the technique as well as the analyses indeed can improve upon vanilla policy optimization for domain randomization problems.

We will provide more detailed explanation below. First, we highlight some definitions of stochastic and robust control problem.

In the context of stochastic control, as discussed in [1], the disturbance $w_t$ follows a distribution $\nu$, with the aim being to minimize the expected cost value:

$

\min_{\mathcal{A}} \mathbb{E}_{w_t \sim \nu} [J_T(\mathcal{A})]. \tag{Stochastic control}

$

In the realm of robust control, as outlined in [2], the disturbance may adversarially depend on each action taken, leading to the goal of minimizing worst-case cost:

$

\min_{u_1} \max_{w_{1: T}} \min_{u_2} \ldots \min_{u_t} \max_{w_T} J_T(\mathcal{A}). \tag{Robust control}

$

We then proceed to establish the framework for domain randomization. When training the agent, we select an environment from the distribution $\nu$ in each episode. Each distinct environment has an associated set of disturbances ${w_t}$. However, these disturbances remain fixed once the environment is chosen, unaffected by the agent's interactions within that environment. Given our limited knowledge about the real-world distribution $\nu$, we focus on optimizing the agent's performance within its training scope set $\mathcal{V}$. To this end, we aim to minimize the following cost:

$

\min_{\mathcal{A}} \max_{\nu \in \mathcal{V}} \mathbb{E}_{w \sim \nu} [J_T(\mathcal{A})] . \tag{Domain randomization}

$

From the aforementioned discussion, it becomes clear that the Domain Randomization (DR) setup diverges significantly from traditional stochastic or robust control. Firstly, unlike in stochastic frameworks, the randomness of disturbance in DR only occurs during the initial environment sampling, rather than at each step of the transition. Secondly, since the system dynamics do not actively counter the controller, this setup does not align with robust control principles.

So how should we analyze DR from a linear control prospective? Notice that [3] also introduces the concept of non-stochastic control. In this context, the disturbance, while not disclosed to the learner beforehand, remains fixed throughout the episode and does not adaptively respond to the control policy. Our goal is to minimize the cost without prior knowledge of the disturbance:

$

\min_{\mathcal{A}} \max_{w_{1: T}} J_T(\mathcal{A}) . \tag{Non-stochastic control}

$

In this framework, there's a clear parallel to domain randomization: fixed yet unknown disturbances in non-stochastic control mirror the unknown training environments in DR. As the agent continually interacts with these environments, it progressively adapts, mirroring the adaptive process seen in domain randomization. Therefore, we propose to study DR from a non-stochastic control perspective. As [3] only consider the discrete system, we extent it to continuous system and integrate the two-stage algorithm design idea into the domain randomization experimental environment to see whether it lead to some improvements.

Q2: There are several minor writing or notation errors that need to be checked carefully.

A2: We sincerely appreciate the reviewers pointing out these minor errors, and we will correct them in the next version of the paper.

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] Cohen, Alon, et al. "Online linear quadratic control." International Conference on Machine Learning. PMLR, 2018.

[2] Khalil, I. S., Doyle, J. C., & Glover, K. (1996). Robust and optimal control (Vol. 2). Prentice hall.

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