Online Control with Adversarial Disturbance for Continuous-time Linear Systems

Summary

This paper considers the problem of online non-stochastic control within continuous-time linear dynamical systems. To this end, the authors proposed a two-level online algorithm, where the higher level deals with a discretized reduced problem to minimize the performance measure of regret, while the lower level handles the discretization error. This work achieves an $O(\sqrt{T} \log T)$ regret, which is the same as that in the discretized system. Finally, empirical evaluations validate the effectiveness of the proposed method.

Strengths

This work investigates the meaningful problem of controlling a continuous-time linear dynamical system. This work provides an $O(\sqrt{T} \log T)$ regret, which is in the same order compared with the result in discretized systems. Furthermore, the authors have conducted sufficient experiments to study the effects of frame stack and frame skip, and show the effectiveness of the proposed method.

Weaknesses

Although this work has done a nice job in handling continuous-time systems in the online non-stochastic control setup, my major concern is that the technical novelty seems insufficient. Specifically, as the authors have said, two technical challenges exist to achieve the main Theorem 1. The first one is to control the magnitude of the states, and the second one is to handle the curse of dimensionality caused by discretization. As for the first technical challenge, the idea of "employ Gronwall’s inequality to bound the first and second-order derivatives in the neighborhood of the current state" (Line 207-209) seems to be pretty natural because of the continuous nature of the system. And the second technical challenge seems to be leveraging the *lazy-update* paradigm to facilitate some kind of parameter tuning for the desired regret bound. Both technical challenges seem to be a little minor and thus insufficient from my point of view. 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?

Questions

In this part, I list some other questions or suggestions: 1. In Line 90, the authors said "However, it is unclear why domain randomization works in theory". However, this work does not illuminate the role of domain randomization in theory either because the DR only appears in the experiments part. I suggest that the authors could revise the sentence to avoid unnecessary misunderstanding of this work's contributions. 2. Section 3.2, in my opinion, could be put in the appendix because the relationship with robust control should be explained as a part of the related work, but not necessarily to be mentioned when introducing the problem setup of *this* work. 3. Assumption 1, compared with the standard non-stochastic disturbances in discretized systems, uses an extra condition of $\|\dot{w}_t\| \le W$. I guess that this additional condition is used to solve the first technical challenge (employ Gronwall’s inequality to bound the first and second-order derivatives in the neighborhood of the current state)? Am I right? Besides, the comparison of Assumption 1 with the previous one should be explicitly explained in the next version. 4. Definition 1 is a little different from the standard strong stability condition in discretized systems. In discretized systems, a linear controller is strongly stable if $A - BK = P L P^{-1}$. However, in this work, the strong stability holds for $I + h(A-BK)$. By setting $h=1$ as a special case, this assumption is still different with an extra identity matrix $I$. Why are they different? And the comparison with the standard discretized strong stability assumption should be explained in the next version. 5. In Section 4, some citations of the pioneering work [Agarwal et al., ICML 2019] are missing. For example, Definition 2,3,4 should cite [Agarwal et al., ICML 2019]. I understand that there exist minor differences in the definitions in this work compared with those in [Agarwal et al., ICML 2019] for discretized systems. However, correct citations should still be provided to avoid unnecessary misunderstandings of this work's contributions. 6. In the equation after Line 172, the notation of '$g_t$' is not defined. I noticed that $g_t$ is first defined in Algorithm 1 on the next page. 7. In Figure 2, the font sizes of 'Replay' and 'Buffer' seem to be different?

Rating

4

Confidence

4

Soundness

2

Presentation

3

Contribution

2

Limitations

The authors have adequately addressed the limitations and, if applicable, potential negative societal impact of their work.

Summary

This paper presents an algorithm for the non-stochastic control problem for continuous-time systems. In particular, the proposed algorithm discretizes the continuous-time system and balances the sampling time for discretization and update frequence of the online learning algorithm, in order to obtain a sublinear regret guarantee. The theoretical results are validated in numerical experiments.

Strengths

The paper is well written and studies an interesting research question. In order to obtain their results, the authors make use of novel proof techniques and design ideas for the proposed algorithm.

Weaknesses

In my opinion, the main weakness of this work is that the presentation of the results is often unclear and/or confusing. In particular, - the way the authors use to denote time steps is very confusing and often $t+1$ and $t+h$ seem to be used interchangeably (compare, e.g., line 8 'Use the action...' in Algorithm 1). Similarly $t$ and $i$ seem to be used interchangeably in Lemma 12. As this paper works with both, continuous and discrete-time, I believe it is highly important to use a notation that is less ambiguous. - the matrices $M$ of the DAC policy are sometimes used with square brackets (for either the sub- or superscript) and sometimes without apparently without meaning different matrices - $n$ and $m$ are most frequently used to denote the state and input dimension of the dynamial system, I suggest using different constants in Algorithm 1 - There are many typos in the proofs in the appendix, for example there should not be an 'a' in (2), the constant $a$ is generally not defined (at some point you introduce the condition $|M^i_t | \leq a(1-h\gamma)^{i-1}$, but this does not match the DAC policy class in Algorithm 1?), I believe the definition of $\gamma_1$ after line 555 is wrong, above line 582, you require $n=\lfloor\frac{T}{h}\rfloor$ contrary to your definition in Algorithm 1 (which, however, you require earlier on in the proof; similar arguments hold for $p$ after line 592), and after line 622, the first sum should start at $i=1$ by definition of $u_t$, whereas it should be $Q_h^i$ instead of $Q_h^{i-1}$ when replacing $x_t(M)-x_t^*$. More generally, I believe that the results are qualitatively correct, but the constants (which are omitted in the $\mathcal O$-notation) are frequently wrong so that I was not able to verify all the presented results

Questions

I am not sure whether I fully understand why updating the DAC policy at each time step (compared to every $m$-th time step as you propose) does not work. Intuitively, I would assume that updating the DAC policy more frequently yields better performance, and therefore also a lower regret bound. After Lemma 10 (page 24) the authors argue 'It is worth noting that the cost of OCO with memory depends on the the update frequency $H$.' However, $H$ is not immediately connected to the update frequency, but rather denotes the size of the memory in the OCO with memory framework described above Lemma 10. Could you please clarify why updating the DAC policy less often leads to improved performance (i.e., lower regret)?

Rating

6

Confidence

4

Soundness

2

Presentation

2

Contribution

3

Limitations

From the proof (e.g., after line 549), you seem to assume $x_0=0$. While this assumption is very commonly adopted in the related literature, it should be stated somewhere in the main body of the text explicitly. Furthermore, I am not sure whether this assumption is restrictive: It requires the system to be initialized at i) a steady state of the system and ii) the steady state of the system, that the benchmark policy $K^*$ aims to stabilize.

Summary

This paper studies the sample complexity of online control for continuous-time linear systems. A novel two-level online algorithm was proposed. Specifically, a sublinear regret is guaranteed. Finally, the authors applied their method to the SAC algorithm and achieves improved simulation results.

Strengths

This paper studies the sample complexity of online control with adversarial disturbances for continuous-time linear systems, providing a complementary perspective to discrete-time linear systems and achieving the same sublinear rate.

Weaknesses

1. There is a gap between the theoretical results and the experimental results. It is not clear how the setting studied in this paper is implemented in the experiments. More discussion is needed. 2. There are several minor writing or notation errors that need to be checked carefully. For example: line 21 they "has" line 36 it "reliers" line 104, missing definition of $\mathcal{K}$

Questions

How the setting studied in this paper is related to the experiments.

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

As mentioned in the paper, the theroical results relies on the access of system model and the loss function is convex. Extentions to model-free methods should be discussed.

Summary

The work tackles the challenge of applying simulated controllers to real-world scenarios to manage continuous-time linear systems that face unpredictable disturbances. It introduces a double-layer control approach that balances slow policy updates with quick feedback adjustments. This way it effectively minimizing errors over time. The work is tested on various real world tests in simulation environments and it shows that it significantly boosts the performance of agents, even under uncertain situations.

Strengths

- Introduction of a new two-level online control strategy that manages both policy learning & feedback control - Good theoretical analysis that achieves sublinear regret - Validation of theory with practical experiments using domain randomization in various robotic simulation environments

Weaknesses

- The paper lacks a comprehensive comparative analysis with other state-of-the-art methods. - Experiments are conducted in simulated environments with domain randomization. There is limited discussion on how well these results generalize to physical systems outside of controlled simulations

Questions

- In Section 3.1: the authors assumes access to \cdot{x}/t at each time step. This is a strong assumption, as measuring the state derivative directly is often not possible in practice. Work should discuss implications of this assumption & show it can be extended to more realistic case of only having access to state measurements. - Regret defn in section 3.4 compares to the best linear policy in hindsight. Why this is an appropriate comparator class? Why not best non-linear policy? more discussion needed on this choice of benchmark & limitation - Assumption 1 is quite strict. What if disturbances may occasionally have large spikes leading to violating these bounds (which happens in practical setting)? include discussion on this case - Assumption 2 on the cost function seems to imply the costs are quadratic (due to the D^2 term). But the paper also says the costs are convex, which is a more general class. Clarify precise assumption on the cost function here - Definition 1 of a strongly stable linear policy is central to the paper, but the motivation behind this definition is not entirely clear. - The challenge of trading off approximation error & OCO regret in section 4 is subtle. More details needed on why this trade-off arises & how this two-level algorithm resolves it. - $w_t$ notion is inconsistent. line \sims 100 w_t is treated as a random variable with an unknown distribution. In line 98, it is a specific realization of the disturbance at time t, rather than a random variable.

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

- Strict assumptions restrict the applicability of finding systems that meet these criteria - Method is tailored for non-stochastic disturbances, leaving out scenarios where disturbances might have stochastic elements.

Thanks for the feedback

Thanks for the detailed feedback and explanations. I have read the response carefully, where A2 and A3 have solved my concerns raised in the original review. I believe these assumptions are not stronger than those in the discretized system. I also agree with the technical challenges mentioned in A1. However, in my opinion, the technical contributions are still a little weak. I agree with the first challenge that bounding the magnitude of states requires novel components in continuous systems. However, the second one that the authors have mentioned still seems to be a pretty natural operation, which uses lazy updates to achieve delicated parameter tuning. I do not see much challenge about this point. Besides, I think that the comparisons with previous assumptions in the discretized systems (A2 and A3) are necessary to help readers better understand whether the assumptions here are strong or not. If there are not enough spaces in the main paper, I suggest that the authors could put them in the appendix. Based on this, I am more inclined to believe another round of polishment would be better. Therefore I keep my current score. At last, thank the authors again for the detailed responses.