Online Control with Adversarial Disturbance for Continuous-time Linear Systems
Authors: Jingwei Li
Jing Dong
Can Chang
Baoxiang Wang
Jingzhao Zhang
Venue: NeurIPS 2024 poster (2024)
Keywords: control and dynamical system
online learning
continuous-time linear system.
Primary area: online_learning

Abstract: We study online control for continuous-time linear systems with finite sampling rates, where the objective is to design an online procedure that learns under non-stochastic noise and performs comparably to a fixed optimal linear controller. 
We present a novel two-level online algorithm, by integrating a higher-level learning strategy and a lower-level feedback control strategy. This method offers a practical and robust solution for online control, which achieves sublinear regret. Our work provides the first nonasymptotic results for controlling continuous-time linear systems with finite number of interactions with the system. Moreover, we examine how to train an agent in domain randomization environments from a non-stochastic control perspective. By applying our method to the SAC (Soft Actor-Critic) algorithm, we achieved improved results in multiple reinforcement learning tasks within domain randomization environments. Our work provides new insights into non-asymptotic analyses of controlling continuous-time systems. Furthermore, our work brings practical intuition into controller learning under non-stochastic environments.

Baoxiang Wang Online Control with Adversarial Disturbance for Continuous-time Linear Systems
Jingwei Li
Jing Dong The Chinese University of Hong Kong, Shenzhen jingdongelink, cuhk. edu.
III, Tsinghua University Shanghai Qizhi Institute 1jw220mails, tsinghua. edu.
Can Chang
III, Tsinghua University
The Chinese University of Hong Kong. Shenzhen bxiangvang@cuhk. edu. en
cc228mai 1s. tsinghua. edu.
Jingzhao Zhang
IIS, Tsinghua University
Shanghai Qi zhi Institute
j jingzhaoz@mail tsinghua, edu..eduu.co cn
Abstract
We study online control for continuous-tin linear systems with finite sampling rates, where the objective is to design online procedure that learns under non- stochastic noise and performs comparably to a fixed optimal linear controller. We present a novel two-level online algorithm, by integrating higher-level learning strategy and a lower-level feedback control strategy. This method offers practical and robust solution for online control, which achieves sublinear regret. Our work provides the first nonasymptotic results for controlling continuous systems with finite number of interactions with the system. Moreover, examine how to train an agent domain randomization environments from a non-stochastic control perspective. By applying method to the SAC (Soft Actor-Critic) algorithm, we achieved improved results multiple reinforcement learning tasks within domain randomization environments. Our work provides insights into non-asymptotic analyses of controlling continuous-time systems. Furthermore, our work brings practical intuition into controller learning under non-stochastic environments.
linear
1 Introduction
major challenge robotics is deploy simulated controllers into real-world. This process, known as sim-to-real transfer, can be difficult due to misspecified dynamics, unanticipated real-world perturbations, and non-stationary environments. Various strategies have been proposed address these issues, including domain randomization. meta-learning, and domain adaptation [20] 10 21 Although they have shown great effectiveness in experimental results, training agents within these setups poses significant challenge. To accommodate different environments, the strategies developed by agents tend to be overly conservative (26 4 or lead to suboptimal outcomes [4 27].
In this work, we provide an analysis of the sim-to-real transfer problem from an online control perspective. Online control focuses on iteratively updating the controller after deployment (i.e..
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

online) based on collected trajectories. Significant progress has been made in this field by applying insights from online learning to linear control problems 2 19
[6].
Following this line of work, we approach the sim-to-real transfer issue for continuous-time linear systems non-stochastic control problem, as explored in previous works [19 8. These studies
provide regret bounds for an online controller that lacks prior knowledge of system perturbations. However, a gap remains as no previous analysis has specifically investigated continuous-time systems, but real world systems often evolve continuously in time.
Most continuous control research emphasizes the development of model-free fodel--ree algorithms, such as policy iteration, under the assumption of noise absence. Recently, [8] examined online continuous-tim linear quadratic control problem and achieves sublinear regret. However, it relies on the assumption of standard Brownian noise instead of non-stochastic noise that may not always hold true in real-world applications. This leads us to the crucial question:
Existing literature on online continuous control is limited 42
22
13
32
Is it possible to design online non-stochastic control algorithm continuous- time setting that achieves sublinear regret?
Our work addresses this question by proposing a two-level online controller. The higher-level controller symbolizes the policy learning process and updates the policy low frequency to minimize regret. Conversely, the lower-level controller delivers high-frequency feedback control input to reduce discretization error. Our proposed algorithm results in regret bounds for continuous- time linear control in the face of non-stochastic disturbances.
Furthermore, we implement the ideas from our theoretical analysis and test them in several experi- ments. Note that the key difference between our algorithm and traditional online policy optimization is that utilize information from past states with some skips to enable faster adaptation to vironmental changes. Although the aforementioned concepts are often adopted experimentally as frame stacking and frame skipping, there is relatively little known about the appropriate scenarios for applying these techniques. Our analysis and experiments demonstrate that these techniques are particularly effective in developing adaptive policies for uncertain environments. We choose the task of training agents a domain randomization environment to evaluate our method, and the results confirm that these techniques substantially improve the agents' performance.
2 Related Works
The control theory of linear dynamical systems under disturbances has been thoroughly examined in various contexts, such as linear quadratic stochastic control [7]. robust control [37 23 system identification 17 24 255. However, most of these problems are investigated in non-robust settings, with robust control being the sole exception where adversarial perturbations in the dynamic are permitted. In this scenario, the controller solves for the optimal linear controller in the presence of worst-case noise. Nonetheless, the algorithms designed in this context can be overly conservative as they optimize over the worst-case noise, a scenario that is rare in real-world applications. We will elaborate the difference between robust control and online non-stochastic control in Section 3.
Online Control There has been a recent surge of interest in online control, as demonstrate by studies such as [2]. In online control, the player interacts with the environment and updates the policy in each round aiming to achieve sublinear regret. In scenarios with stochastic Gaussian noise, provides the first efficient algorithm with an O(VT)) regret bound. However, in real-worke applications, the assumption of Gaussian distribution is often unfulfilled.
3 pioneers research non-stochastic online control, where the noises can be adversarial. Under general convex costs, they introduce the Disturbance-Actmm Policy Class. Using an online convex optimization (OCO) algorithm with memory, they achieve an O(vT) regret bound. Subsequent studies extend this approach to other scenarios, such as quadratic costs (8). partial observations [36]
35 or unknown dynamical systems [19 [T] Other works yield varying theoretical guarantees like
online competitive ratio [5 33)
Online Continuous Control Compared to online control, there has been relatively little research on model-based continuous-time control. Most continuous control works focus developing model-free

---

algorithms such as policy iteration (e.g. analyzing the system when transition dynamics are represented by differential equations, rather than recurrence formulas, poses significant challenge.
42.22 32 )), typically assuming zero-noise. This is because
Recently, & studies online continuous-time linear quadratic control with standard Brownian noise and unknown system dynamics. They propose an algorithm based on the least-square method. which estimates the system's 's coefficients and solves the corresponding Riccati equation. The papers [34 [4 also focus on online control setups with continuous-time stochastic linear systems and unknown dynamics. They achieve O(vT sampling algorithm learn optimal actions. [14] takes randomized-estimatee policy to balance exploration and exploitation. The main difference between [8] [4 [4] and our paper is that they consider stochastic noise of Brownian motion which can be quite stringent and may fail in real-wort world applications, while the noise in our setup is non-stochastic. This makes our analysis completely different from theirs.
regret by different approaches.
[34 uses the Thompson
Domain Randomization Domain randomization, which is proposed by [39], is commonly used technique for training agents to adapt different (real) environments by training randomized simulated environments. From the empirical perspective, many previous works focus on designing efficient algorithms for learning in a randomized simulated environment (by randomizing environmen- tal settings, such as friction coefficient) such that the algorithm can adapt well in new environment,
30 Other works study how effectively randomize the simulated environment so that the trained algorithm would generalize well in other environments [43] 27 38) However, prior research has not explored how to apply certain theoretical analysis ideas to train agents in fondin-randomized environments. Limited previous works, such as [10 and 211, concentrate on theoretically analyzing the sim-to-real gap within specific domain randomization models but they do not test their algorithms in real domain randomization environments.
29 44 26
28
3 Problem Setting
In this paper, we consider the online non-stochastic control for continuous time linear systems. Therefore, provide brief overview below and define notations.
3.1 Continuous-time Linear Systems
The Linear Dynamical System can be considered specific case of continuous Markov decision process with linear transition dynamics. The state transitions are governed by the following equation:
Se Ax, Bu, + Wh,
where I2 is the state at time 6, u, is the action taken by the controller at time f, and W/ represents the disturbance time f. Follow the setup of [3] we assume Zo 0. We do not make any strong assumptions about the distribution of wy, and we also assume that the distribution of wa is unknown the learner beforehand. This implies that the disturbance sequence w, can be selected adversarially,
When the action u, is applied to the state Tt, a cost (Xz, uz) is incurred. Here, we assume that the cost function c, is convex. However, this cost is not known in advance and is only revealed after the action un is implemented at time t. In the system described above, an online policy π is defined function that maps known states to actions, i.e., Ue TT (<(xe1 [0, +)}). Our goal, then, is to design an algorithm that determines such an online policy to minimize the cumulative cost incurred. Specifically, for any algorithm A, the cost incurred
time horizon T is:
(T(A) = (((A)=/ 1." c,(22,,
In scenarios where the policy is linear (i.e., a linear controller), such that 4s = Krt, we use J(K) to denote the cost of a policy K K. from certain class K.
3.2 Difference between Robust and Online Non-stochastic Control
While both robust and online non-stochastic control models incorporate adversarial noise, it's crucial to understand that their objectives differ significantly.
3

---

The objective function for robust control, seen in 37 23 is defined as:
min max min min max (AA,,
d1 Wir W2 d Whr
Mcanwhile, the objective function for online non-stochastic control, as discussed in B
min (Jx( min Jr(K)). KER
A wir
Note that the robust control approach seeks to directly minimize the function, while online non-stochastic control targets the minimization of regret, which the discrepancy between the actual cost and the cost associated with baseline policy. Additionally, in robust control, the noise each step can depend on the preceding policy, whereas in online non-stochastic control, all the noise is predetermined (though unknown the player).
3.3 Assumptions
We operate under the following assumptions throughout this paper. To be concise, we denote || as the L2 operator norm of the vector and matrix. Firstly, we make assumptions concerning the system dynamics and noise:
Assumption The matrices that govern the dynamics are bounded, meaning ||||| I K, and [B]] KB, where К, and K constants. Moreover, the perturbation and its derivative are both continuous and bounded: ||æce|| ; || S W. with W being a constant.
These assumptions ensure that we can bound the states and actions, as well as their first and second- order derivatives. Next, make assumptions regarding the cost function:
Assumption 2. The costs ea (2 u) are convex in and u. Additionally, if there exists a constant D such that ||~||], ||ul|| I D, then we have the following inequalities of the costs: (c,(z, u)] s
3D2 || ce w)ll ( w)ll < GD, |cs, (z, u) C₁2 (z, u)] S Llt t D2
where B.G and I. are constants corresponding to the cost function. This assumption implies that the differences between states and actions are small, then the error in their cost will also be relatively small.
3.4 Strongly Stable Policy
We next describe our baseline policy class introduced in 12 Note that the continuous system and the discrete system are different. If we consider the approximation over relatively small interval h, we get
14h
4ith 3et +
dd =It
Ax, + Bu, + wyds
==1 Sx, + h(Ax, + Bu, + w.) (1 + hA)x, + hBu, + hw,-
Therefore, we consider the transition of a discrete system 2;+1 = Az; + Bu, + w we get the approximation Ā = I + hA, x hB. Hence, we extend the definition of a strongly stable policy [12 in the discrete system the continuous system follows:
Definition 1. A linear policy K is (x, -trronnly stable if, for any > that sufficiently small, there exist matrices L,, P such that 7 + h(4 BK) PL, P-1, with the following two conditions:
|I S 1 - hy. 2. The controller and transforming matrices are bounded, i.e., ||| < and ||]|| P-1|| S
1. The norm of L, is strictly smaller than unity and dependent on h, i.c.,
The above definition ensures the system can be stabilized by linear controller K.
3.5 Regret Formulation
To evaluate the designed algorithm, follow the setup in 12 and use regret, which is defined as the cumulative difference between the cost incurred by the policy of our algorithm and the cost incurred by the best policy in hindsight. Let IC denotes the class of strongly stable linear policies, i.e. K. = = K : K is (N, -ttrongyyy stable). Then we try to minimize the regret of algorithm:
min max (egret(A) min (JT()) min J (T)))).
WIT
WIT

---

4 Algorithm Design
In this section, outline the design of our algorithm and formally define the concepts involved in deriving our main theorem. We summarize our algorithm design as follows:
First, we discretize the total time period T' into smaller intervals of length h. We use the information at each point Z4, #2h, ... and uh U2h..... to approximate the actual cost of each time interval, leveraging the continuity assumption. This process does introduce some discretization errors
This policy selects the action based on the current time step and the estimations of disturbances from several past steps. This policy can approximate the optimal linear policy hindsight when we choose suitable parameters. However, the optimal policy K is unknown, so we cannot directly acquire the optimal choice. To overcome iteratively adjust the DAC policy parameter
Next, we employ the Disturbance-Actin policy (DAC) [
this, we employ the OCO with memory framework Mj to approximate the optimal solution M*
After that, we introduce the concept of the ideal state yr and ideal action v2 that approximate the actual state I2 and action ue, Note that both the state and policy depend on all DAC policy parameters M1, M2,,M..... Mt. Yet, the OCO with memory framework only considers the previous H steps. Therefore, we need to consider ideal state and action. Yt and U, represent the state the system would reached if it had followed the DAC policy {Mr- Mc) at all time steps from H t, under the assumption that the state H- was 0.
From all the analysis above, can decompose the regret three parts: the discretization error R1, the regret of the OCO with memory R2, and the approximation error between the ideal cost and the actual cost R3-
Then we will formally introduce out method and define all the concepts. In the subsequent discussion, we use shorthand notation to denote the cost, state, control, and disturbance variables Ca., Lit, Uis and wiy as C₁ Di, U4 and Wi respectively.
First, we need to define the Disturbance-Actte Policy Class(DAC) for continuous systems: Definition 2. The Disturbance-Action Policy Class(DAC) is defined as:
U1 = Kx, Σ M
where K is fixed strongly stable policy, a parameter that signifies the dimension of the policy class, M, = {M,.... M,) is the weighting parameter of the disturbance at step f, and tù is the estimated disturbance:
W Ft+1
Ft. h (Ax; + But)
h
We note that this definition differs from the DAC policy in discrete systems 3 as we utilize the estimation of disturbance over an interval [t, + h] instead of only the noise in time t. It counteracts the second-order residue term of the Taylor expansion of a; and also an online policy as it only requires information from the previous state.
Our higher-level controller adopts the OCO with memory framework. A technical challenge lies in balancing the approximation error and OCO regret. To achieve a low approximation error, we desire the policy update interval // to be inversely proportional to the sampling distance h. However, this relationship may lead to large OCO regret. To mitigate this issue, we introduce new parameter m =(A) representing the lookahead window. We update the parameter M, only once every m iterations, further reducing the OCO regret without negatively impacting the approximation error:
IIM (Mr (M)) if mod m == 0,
M
M
otherwise.
Where Sr is function corresponding to the loss function and we will introduce later in Algorithm For notational convenience and to avoid redundancy, we denote Mt/mi M,. We can then define the ideal state and action. Due to the properties of the OCO with memory structure, we need to consider only the previous Hm states and actions, rather than all states. As result, we introduce the definition of the ideal state and action. During the interval /. E [im, (i+ + 1)m- - 1). the learning policy remains unchanged, so could define the ideal state and action follow the definition in [3:
5

---

Definition 3. The ideal state and action at time t E [im, (i + 1)m 1] are defined as
Vr - xz Zr(Mi Mc), vi - Kit +
Σ
M Wi-i-
f=1
where the notation indicates that assume the state xt-H is and that apply the DAC policy (M- M, at all time steps from Hm to t.
We can also define the ideal cost in this interval follow the definition in 3 Definition 4. The ideal cost function during the interval / E [im,, (i + 1)m - 1] is defined as follows:
(++
Si M.............. Mr)
Σ
aa (M.-...... M.) (M.........,. ...,,,,M))
t=
With all the concepts presented above, we are now prepared to introduce our algorithm:
Algorithm 1 Continuous two-level online control algorithm
Input: step size 7, sample distance h. policy update parameters H, parameters K, T.
Define sample numbers n = [T/h]] OCO policy update times p = [n/m].
Define DAC policy update class M M M ... ..MMHm Initialize Mo .M arbitrarily. for O.....P 1 do do
M s 2h (1 - -))=-1
for 0, ...., Denote the discretization time r km + 5,
Use the action u, - Kx, + h Dimm M, during the time period E [rh, (r + 1)h]. Observe the new state 2++1 at time (r + 1)h and record ú, according to Equation (1.
end for Define the function 9u (M) = fa(M.....
Update OCO policy Mr+1 II.M (Mr V (Ma)).
end for
5
Main Result
In this section, we present the primary theorem of online continuous control regret analysis:
Theorem Under Assumption /
a step size of = ((v m ()),, Algorithm altains regret bound of
and a DAC policy update frequency
Th
(A(
min JT JT (K) < O(n((1 hy)) + KeK
With the sampling distance = 0 ()), and the OCO policy update parameter H = O(log(T))
Algorithm Tachieves a regret bound of
Jr( min Jr(K) SO O (VTlog(T))
KeK.
Theorem demonstrates a regret that matches the regret of a discrete system 3. Despite the analysis of continuous system differing from that of a discrete system, we can balance discretization error, approximation error, and OCO with memory regret by selecting an appropriate update frequency for the policy. Here, O-)) and ((.) are abbreviations for the polynomial factors of universal constants in the assumption.
While we defer the detailed proof to the appendix, we outline the key ideas and highlight them below.

---

Challenge and Proof Sketch We first explain why we cannot directly apply the methods for discrete nonstochastic control from 3 to our work. To utilize Assumption
The bound of derivative near the current state
The bound of derivative for the previcus states
2 it necessary first to establish a union bound over the states. In a discrete-time system, it can be easily proved by applying the dynamics in- equality || || S alI=z|1 + (where < 1) and the induction method presented
Current
The bound of the previous states
[3]. However, for a continuous- time system, different approach is nec- essary because we only have the differential equation instead of the state recurrence formula.
Figure 1: Bounding the states and their derivatives separately. We employ Gronwall's 's inequality with the induction method to bound the states.
To overcome this challenge, we employ Gronwall's inequality to bound the first and second-order derivatives in the neighborhood of the current state. We then use these bounded properties, in conjunction with an estimation of previous noise, to bound the distance to the next state. Through iterative application of this method, we can argue that all states and actions are bounded.
Another challenge is that we need to discretize the system but we must overcome the curse of dimensionality caused by discretization. In continuous-time systems, the number of states is inversely proportional to the discretization parameter h, which also determines the size of the OCO memory buffer. Our regret is primarily composed three components: the error caused by discretization Ri, the regret of OCO with memory R2 and the difference between the actual cost and the approximate cost Rg. The discretization error R1 is O(TT), therefore if we achieve O(VT) regret, we must choose h no more than O (T
If we update the OCO with memory parameter at each timestep follow the method in 3 we will incur the regret of OCO with memory R2 = O(H25VT). The difference between the actual cost and the approximate cost R3 O hy) To achieve sublinear regret for the third term, ), but since h is no more than O (T) H will be larger than O(vT)
must choose H ( log T h7
therefore the second term R₂ will definitely exceed O O(VT).
Therefore, we adjust the frequency of updating the OCO parameters by introducing a new parameter m. using two-level approach and update the OCO parameters once in every steps. This will incur the third term R3 O - hr) fm) but keep the OCO with memory regret R2
/T), so can choose H O log T and m O(1) Then the term of R2 is O(VTlog T) and we achieve the same regret compare with the discrete system.
7
6 Experiments
In this section, we apply our theoretical analysis the practical training of agents. First we highlight the key difference between our algorithm and traditional online policy optimization.
1. Stack: While standard online policy optimization learns the optimal policy from the current state u, = oxx)), an optimal non-stochastic controller employs the DAC policy as outlined in Detinition 2 Leveraging information from past states aids the agent in adapting to dynamic environments.
2. Skip: Different from the analysis in [3]. in continuous-time system we update the state information every few steps, rather than updating it at every step. This solves the curse of dimensionality caused by discretization in continuous-time system.
The above inspires us with an intuitive strategy for training agents by stacking past observations with some observations skip. We denote this Stack & skip for convenience. Stack & skip is frequently used as a heuristic in reinforcement learning, yet little was known about when and why such a technique could boost agent performance.
How should we evaluate our algorithm in a non-stochastic environment? We opt for learning an optimal policy within a domain randomization environment. In this context, each model's parameters are randomly sampled from a predetermined task distribution. We train policies to
optimize performance across various simulated models 4 29

---

We observe that learning in Do- main Randomization (DR) sig- nificantly differs from stochas- tie or robust learning problems. In DR, sampling from environ- mental variables occurs at the be- ginning of each episode, rather than every step, distinguish- ing it from stochastic learning where randomness is step-wy wise independent and identically dis- tributed. This episodic sampling approach allows agents in DR to exploit environmental conditions and adapt episodic changes within an episode. On the other hand, robust learning focuses on worst-case scenarios depend- ing on an agent's policy. DR, in contrast, is concerned with the distribution of conditions aimed broad applicability rather than worst-case perturbations.
Replay
Randemized Envirannes
Obtervation
Stack Skip
Observation Angnentation Medhll
RL Agant
Figure 2: Leverage past observation of states with some skip.
In the context of non-stochastic control, the disturbance, while not disclosed to the learner beforehand, remains fixed throughout the episode and does not adaptively respond to the control policy. This setup in non-stochastic control shows clear parallel to domain randomization: fixed yet unknown disturbances in non-stochastic control mirror the unknown training environments DR. As the agent continually interacts with these environments, progressively adapts, mirroring the adaptive process observed in domain randomization. Therefore, we propose evaluating our algorithm within a domain randomization training task. Subsequently, introduce the details of experimental setup:
Environment Setting We conduet experiments on the hopper, half- cheetah, and walker2d benchmarks us- ing the MuJoCo simulator [40]. The randomized parameters include envi- ronmental physical parameters such damping and friction, well as the agent properties such as torso size. We the range of our domain ran- domization to follow a distribution with default parameters as the mean value, shown in [ When train- ing in the domain randomization en- vironment, the parameter is uniformly sampled from this distribution. an- alyze the result of generalization, we only change one of the parameters and keep the other parameters as the mean of distribution in each test environment. We conducted experiments using NVIDIA A40 graphics card.
Environment
Parameters
DR distribution
Joint damping
[0.5, 1.5]
Foot friction
[1,
Hopper
Height of head
[1.2, 1.7]
Torso size
[0.025, 0.075]
Joint damping
[0.005, 0.015]
Half-Cheetah
Foot friction
[3, 7]
Torso size
[0.04, 0.06]
Joint damping
[0.05, 0.15]
Walker2D
Density
[500, 1500]
Torso size
[0.025, 0.075]
Table 1: The DR distributions of environment.
Algorithm Design and Baseline We design practical meta-algorithm that converts any standard deep RL algorithm into a domain-adaptive algorithm, shown in Figure _ this algorithm, we augment the original state observation ogld at time L. with past observations, resulting in opew [ogld ogdd
o -. old (--mh- Here h is the number of past states we leverage and m is the number of states we skip when we get each of the past states. For clarity in our results, we selected the SAC algorithm for evaluation. We use a variant of Soft Actor-Critic (SAC) (3I and leverage past states with some skip as our algorithm. We compare our algorithm with the standard SAC algorithm training on domain randomization environments as our baseline.
Impact Frame Stack and Frame Skip and frame skip number we carried out experiments in the hopper environment with different and m. For each parameter we train with 3 random seeds and take the average. Figure shows that the performance increases significantly when the frame stack number is increased from to 3, and
To understand the effects of the frame stack number

---

remains roughly unchanged when the frame stack number continues to climb up. Figure 4 shows that the optimal frame skip number is 3, while both too large or too small frame skip numbers result in sub-optimal results. Therefore, in the following experiments we fix the parameter h = 3, m = 3. We train our algorithm with this parameter and standard SAC on hopper and test the performance on more environments. Iioos shows that our algorithm outperforms the baseline in all environments.
with mnnvel
SAC tith stack
Interval
340
333
032
300
503
333
300
17
fsot Motion
Teard Jeight
Ioot Fiition
heighs
Figure 3: Impact of frame stack number.
Figure 4: Impact of frame skip number.
350
SAC history
350
SAC history
150
SAC with history
350
SAC history
340
340
340
340
Reward
Reward
Reweard
330
320
320-
320
320-
310
:10
:10
51.0
0.50
0.75
1.00
1.25
1.50
1.0
1.5
2.0
3.0
1.4
1.6
0.03
0.04
0.05
0.56
0.07
joint_ dammingminnggg....
foot_ Mrccion
head haight
torso 522e
Figure 5: Agents' reward in various test environments of hopper.
Results on Other Environments Each algorithm was trained using three distinct random seeds in the half-cheetah and walker2d domain randomization (DR) environments. Consistent with previous experiments, we employed frame stack number of h 3 and frame skip number of 3. The comparative performance of our algorithm and the baseline algorithm, across various domain parameters, is presented in Figure 6 The result clearly demonstrates that our algorithm consistently outperforms the baseline in all evaluated test environments.
SAC
1025
1025
1025
History
1000
1000
975
Danoard
975
Reward
975
950
950-
950
900
900
875
850
.0.000 0.0075 0.0100 0.025 0.0150
850
0.060
0.045
0,050
0,055
0,000
joint damping
foot_ Mcction
torso _izee
400
400
400
SAC
SAC
SAC
330
SAC with hodtry
300
SAC with Nattry
300
SAE with history
360
Rewardd
340
Rewerd
340
Reward
340-
320
320
300
300
260
280
280
260
0.08
0.14
660
800
1000
0.53
0.25
Joint damping
dersity
torso_ 3ioc__seeeee
Figure 6: Performance in half-cheetah(Top) and walker2d(Bottom).
9

---

problem in control 7 Conclusion, Limitations and Future Directions
In this paper, we propose a two-level online controller for continuous- time linear systems with adver- sarial disturbances, aiming to achieve sublinear regret. This approach is grounded in our examination of agent training in domain randomization environments from an online control perspective. At the higher level, our controller employs the Online Convex Optimization (OCO) with memory framework to update policies a low frequency. thus reducing regret. The lower level uses the DAC policy to align the system's s actual state more closely with the idealized setting.
In our empirical evaluation, applying our algorithm's 's core principles to the SAC (Soft Actor-Critic) algorithm led to significantly improved results in multiple reinforcement learning tasks within domain randomization environments. This highlights the adaptability and effectiveness of our approach in practical scenarios.
It is important to note that our theoretical analysis depends the known dynamics of the system and the assumption of convex costs. This reliance could represent a limitation to our method, as may not adequately address scenarios where these conditions do not hold or where system dynamics are incompletely understood. For future research, there are several promising directions in online non-stochastic control of continuous-time systems. These include extending with unknown dynamics, exploring the impact of assuming strong convexity in cost functions, and shifting the focus from regret to the competitive ratio. Further research can also explore how to utilize historical information more effectively to enhance agent training in domain randomization environments. This might involve employing time series analysis instead of simply incorporating parameters into neural network training.
methods systems
References
[1] Yasin Abbasi-Yadkorty Peter Bartlett, and Varun Kanade. Tracking adversarial targets. In International Conference on Machine Learning, 2014.
[2] Yasin Abbasi- and Csaba Szepesvári. Regret bounds for the adaptive control of linear quadratic systems. In Proceedings of the 24th Annual Conference on Learning Theory, 2011 1.
[3] Naman Agarwal, Brian Bullins, Elad Hazan, Sham Kakade, and Karan Singh. Online control with adversarial disturbances. In International Conference on Machine Learning, 2019.
[4] Artemij Amiranashvili, Max Argus, Lukas Hermann, Wolfram Burgard, and Thomas Brox. Pre-training of deep rl agents for improved learning under domain randomization. arXiv preprint arXiv:2104. 14386, 2021.
[5] Oren Anava, Elad Hazan, and Shie Mannor. Online learning for adversaries with memory: price of past mistakes. Advances in Neural Information Processing Systems, 2015.
[6] Lachlan Andrew, Siddharth Barman, Katrina Ligett. Minghong Lin, Adam Meyerson, Alan Roytman, and Adam Wierman. A tale of two metrics: Simultaneous bounds on competitiveness and regret. In Conference on Learning Theory, pages 741-763. PMLR, 2013.
[7] Michael Athans. The role and use of the stochastic Ainear-uadrratic-ee system design. IEEE transactions on automatic control, 16(6):529555, 1971.
[8] Matteo Basei, Xin Guo, Anran Hu, and Yufei Zhang. Logarithmic regret for episodic continuous- time linear-quadratic reinforcement learning over a finite-time horizon. Journal of Machine Learning Research, 2022.
[9] Marco C Campi and PR Kumar. Adaptive linear quadratic gaussian control: the cost-biased approach revisited. SIAM Journal on Control and Optimization, 1696)1880-11977, 1998.
[10] Xiaoyu Chen, Jiachen Hu, Chi Jin, Lihong Li, and Liwei Wang. Understanding domain randomization for sim-to-real transfer. In International Conference on Learning Representations, 2022.
[11] Xinyi Chen and Elad Hazan. Black-box control for linear dynamical systems. In Conference on Learning Theory, 2021.
10

---

[12] Alon Cohen, Avinatan Hasidim, Tomer Koren, Nevena Lazic, Yishay Mansour, and Kunal Talwar. Online linear quadratic control. In International Conference on Machine Learning. 2018.
[13] Tyrone E Duncan, Petr Mandl, and Boženna Pasik-Duncan. On least squares estimation in continuous time linear stochastic systems, Kybernetika, 28(3):169-180, 1992.
[14] Mohamad Kazem Shirani Faradonbeh and Mohamad Sadegh Shirani Faradonbeh. Online reinforcement learning in stochastic continuous-time systems. In The Thirty Sixth Annual Conference Learning Theory, pages 612-656. PMLR, 2023.
[15] Gautam Goel, Naman Agarwal, Karan Singh, and Elad Hazan. Best of both worlds in online control: Competitive ratio and policy regret. arXiv preprint arXi::2211.11211 2022.
[16] Gautam Goel and Adam Wierman. An online algorithm for smoothed regression and lqr control. In The 22nd International Conference Artificial Intelligence and Statistics, pages 2504-2513. PMLR, 2019.
[17] Graham C Goodwin, Peter Ramadge, and Peter E Caines. Discrete time stochastic adaptive control. SIAM Journal on Control and Optimization, 19(6):829 853, 1981.
[18] Elad Hazan. Introduction to online convex optimization. CoRR, abs/ 1901.999.0000 002007, 2019.
[19] Elad Hazan, Sham Kakade, and Karan Singh. The nonstochastic control problem. In Algorithmic Learning Theory, 2020.
[20] Sebastian Höfer, Kostas Bekris, Ankur Handa, Juan Camilo Gamboa, Melissa Mozifian, Florian Golemo, Chris Atkeson, Dieter Fox, Ken Goldberg, John Leonard, et al. Sim2real in robotics and automation: Applications and challenges. IEEE transactions automation science and engineering, 2021.
[21] Jiachen Hu, Han Zhong, Chi Jin, and Liwei Wang. Provable sim-to-real transfer in continuous domain with partial observations. arXiv preprint arXiv:2210. 15598, 2022.
[22] Yu Jiang and Zhong-Ping Jiang. Computational adaptive optimal control for continuous-time linear systems with completely unknown dynamics. Automatica, 2012.
[23] IS Khalil, JC Doyle, and K Glover. Robust and optimal control. Prentice hall, 1996.
[24] PR Kumar. Optimal adaptive control of sateeuarruuurattiggggg systems. SIAM Journal Control and Optimization, 21 1983.
[25] Lennart jjung. System identification. Springer, 1998.
[26] Bhairav Mehta, Manfred Diaz. Florian Golemo, Christopher Pal, and Liam Paull. Active domain randomization. In Conference on Robot Learning. pages 162--177. PMLR, 2020.
[27] Melissa Mozian, Juan Camilo Gamboa Higuera, David Meger, and Gregory Dudek. Learning domain randomization distributions for training robust locomotion policies. In 2020 JEEE/RS] International Conference Intelligent Robots and Systems (IROS), pages 6112-6117. IEEE, 2020.
[28] Fabio Muratore, Christian Eilers, Michael Gienger, and Jan Peters. Data-efficient domain randomization with bayesian optimization. IEFE Robotics and Automation Letters, 6(2):911- 918, 2021.
[29] Fabio Muratore, Michael Gienger, and Jan Peters. Assessing transferability from simulation to reality for reinforcement learning. IEEE transactions on pattern analysis and machine intelligence, 43244:117 2019.
[30] Fabio Muratore, Theo Gruner, Florian Wiese, Boris Belousov, Michael Gienger, and Jan Peters. Neural posterior domain randomization. In Conference on Robot Learning, pages 1532-1542. PMLR, 2022.
11

---

[31] Evgeni Nikishin, Max Schwarzer, Pierluca D'Oro, Pierre- Bacon, and Aaron Courville. The primacy bias deep reinforcement learning, In International Conference on Machine Learning. PMLR, 2022.
[32] Syed Ali Asad Rizvi and Zongli Lin. Output feedback reinforcement learning control for the continuous- time linear quadratic regulator problem. In 2018 Anmual American Control Conference (ACC), 2018.
[33] Guanya Shi, Yiheng Lin, Soon-Jo Chung, Yisong Yue, and Adam Wierman. Online optimization with memory and competitive control. Advances in Neural Information Processing Systems, 33:20636-20647, 2020.
[34] Mohamad Kazem Shirani Faradonbeh, Mohamad Sadegh Shirani Faradonbeh, and Mohsen Bayati. Thompson sampling efficiently learns to control diffusion processes. Advances in Neural Information Processing Systems, 35:3871-383 2022.
[35] Max Simchowitz. Making non-stochastic control (almost) as easy as stochastic, Advances in Neural Information Processing Systems, 10:118318-8838 2020.
[36] Max Simchowitz, Karan Singh, and Elad Hazan. Improper learning for non-stochastic control. In Conference on Learning Theory, pages 3320-3436. PMLR, 2020.
[37] Robert F Stengel. Optimal control and estimation. Courier Corporation, 1994.
[38] Gabriele Tiboni, Karol Amdt, and Ville Kyrki. Dropo: Sim-to-real transfer with offline domain randomization. Robotics and Autonomous Systems, 166:104432, 2023.
[39] Josh Tobin, Rachel Fong, Alex Ray, Jonas Schneider, Wojeiech Zaremba, and Pieter Abbeel. Domain randomization for transferring deep neural networks from simulation to the real world. In 2017 JEEE/RSJ international conference on intelligent robots and systems (IROS), pages 23-30. IEEE, 2017.
[40] Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. 2012 JEEE/RSJ International Conference on Intelligent Robots and Systems, pages 5026 5033,-033,200 2012.
[41] Jonathan Tremblay, Aayush Prakash, David Acuna, Mark Brophy, Varun Jampani, Cem Anil, Thang To, Eric Cameracci, Shaad Boochoon, and Stan Birchfield. Training deep networks with synthetic data: Bridging the reality gap by domain randomization. Proceedings of the IEEE conference on computer vision and pattern recognition workshops, pages 969-977, 2018.
[42] Draguna Vrabie, O Pastravanu, Murad Abu-Khalaf, and Frank I. Lewis. Adaptive optimal control for continuous-time linear systems based on policy iteration. Automatica, 2009.
[43] Quan Vuong, Sharad Vikram, Hao Su, Sicun Gao, and Henrik I Christensen. How to pick the domain randomization parameters for sim-to-real transfer of reinforcement learning policies? arXiv preprint arXiv: 1903. 11774, 2019.
[44] Sergey Zakharov, Wadim Kehl, and Slobodan Ilic. Deceptionnet: Network-driven domain randomization. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 532-541, 2019.
12

---

In the appendix we define as the smallest integer greater than or equal to I and we use the h. shorthand C.h. Tih, ughs and Wihh as Ci 2is ui and wa respectively. First we provide the proof of our main theorem there.
A Proof of Theorem 1
Theorem Under Assumption / 2 a step size of = @(v Th) and a DAC policy update frequency
m = -( Algorithm attains a regret bound of
-1)) (A) min (r(K) - -(nh(1-in)))) O(Vnh) O(Th). O(Th).
KeK
With the sampling distance = @ ( (T)
) and the OCO policy update parameter H = (log((T))
Algorithm achieves a regret bound of
5 (T) min (x) 00 (V(Tloog())
Kek:
Proof. We denote if K x as the optimal state and action that follows the policy specified by K" where K arg maXkex Jr(K).
We then discretize and decompose the regret as follows:
c( u))t L/¹ ca(x d.
Jr(A)
min Jr(K) KER
n-1 Σ
(11))
Ce ue)t Σ J (1+1))
n-
=
(x u1)
-
> c( ui)
+ Ro.
1=0
where Ro represents the discretization error
We define p as the smallest integer greater than or equal m. then the first term can be further decomposed as
n-1
4 (1 u:
Σ
(x uf)
(1+1)m-1
(++1)m-1
Σ
Ca ui)
Σ
f=sm
(++1)m-1 Σ
(++1)--1
p-l
(i+1)m-1
p-
(1+1)m-1
u())) -
Σ
Σ
Σ
ciii, v))
Σ
Σ
c( u;)
j=
j=im
z=mm
1=0
jmmm
(++1m--1
c12,, u4) - H....
f(M H (.....MM
f=
(++1)m-1
min MEM
Σ f( ... M) + min MEM
Σ
fi
M)
Σ
(())
where the last equality is by the definition of the idealized cost function.
13

---

Let us denote
p-1
((+1)m-1
R1
Σ
(i( - So(Mi-H. HI... Mi)
1=0
j=im
p-1
p-1
R2 =
Σ
Si(M ,,,,.,,,,,......... .M))
- min MEM
Σ
J.(M,..., M)
1
p-1
p- Σ
p-+()+)
R3
min MEM
Σ J..
Σ
j=im
Then we have the regret decomposition as
(Tg h(Ri + R2 + R3) OKT)).
We then separately upper bound each of the four terms.
The term Ro represents the error caused by discretization, which decreases the number of sampling points increases and the sampling distance h decreases. This is because more sampling points make our approximation of the continuous system more accurate. Using Lemma we get the following upper bound: Ro O
The term RS represents the difference between the actual cost and the approximate cost. For fixed h, this error decreases as the number of sample points looked ahead m increases, while it increases the sampling distance l decreases. This is because the closer adjacent points are, the slower the convergence after approximation. By Lemma we can bound it as R1 I O(n(1 - -hy)
The term R2 is incurred due to the regret of the OCO with memory algorithm. Note that this term is determined by learning rate 7 and the policy update frequency m. Choosing suitable parameters and using Lemma 5 we can obtain the following upper bound: R₂ & O (O/n/)).
The term R3 represents the difference between the ideal optimal cost and the actual optimal cost. Since the accuracy of the DAC policy approximation of the optimal policy depends on its degree of freedom 1, higher degree of freedom leads to more accurate approximation of the optimal policy. We use Lemma 6 and choose
Hm to bound this error: R3 S O(n(1 Hm)).
By summing these four terms and taking m = O(t), we get:
Regret(T) S O(nh(1 -m) $ + O(vnh) O(TT). Finally, we choose / 0 (
= θ = the regret bounded by Regret(T) s O0VTTolgg
B Key Lemmas
In this section, we will primarily discuss the rationale behind the proof of our key lemmas. First, need to prove all the states and actions are bounded.
Lemma 2. Under Assumption 7 and 2 choosing arbitrary in the interval [0, ho] where hg is constant only depends the parameters in the assumption,
have for any and policy M, l1 I1æell, [|ull] [[x]]] < D. || S D. a| - -ells-lu. - -ell & x² + x))1 - hry) Hm++1 D. In particular, taking all the Mr and K K", we can also obtain the inequality of the optimal solution: | ll. [| & D.
The proof of this Lemma mainly use the Gronwall inequality and the induction method. Then we analyze the discretization error of the system.
14

---

Lemma 3. Under Assumption
2
Algorithm 7
attains the following bound of Ro:
(1+1)h (cr(Ze, uz) ca(2i dt h Σ (c(2,, - c(a,, u,)) & L)
Ro
Σ 6= ih
This lemma indicates that the discretization error is directly proportional to the sample distance h. In other words, increasing the number of sampling points leads to more accurate estimation of system.
Then we analysis the difference between ideal cost and actual cost. The following lemma describes the upper bound of the error by approximating the ideal state and action:
Lemma 4. Under Assumption 7 and Algorithm
1
attains the following bound of Ry:
(++1)-11
c(2,, u.) fo (J (MA-........) <nDD>>2 R) - hry) Bm+)
R1
From this lemma, it is evident that for fixed sample distance h, the error diminishes as the number of sample points looked ahead m increases. However, as the sampling distance h decreases, the convergence rate of this term becomes slower. Therefore, it is not possible to select an arbitrarily small value for in order to minimize the discretization error Rg-
We need to demonstrate that the discrepancy between Ia and yt. as well as uy and us is sufficiently small, given assumption This can be proven by analyzing the state evolution under the DAC policy,
By utilizing Assumption and Lemma we can deduce the following inequality:
Ice (ar, u4) ca [e), S |c (Iee, me) C. (yt, 44) + |ca (ye, ue) ct (yt, vt)l
S SGD yall + GDI 0x |l-
Summing over all the terms and use Lemma we can derive an upper bound for R1.
Next, we analyze the regret of Online Convex Optimization (OCO) with a memory term. To analyze OCO with a memory term, we provide an overview of the framework established by [5] in online convex optimization. The framework considers scenario where, at each time step I, an online player selects point 24 from a set K. TRdd At each time step, a loss function f+ K -> revealed, and the player incurs a loss of Ji (B.-H....,...) The objective is to minimize the policy regret, which is defined as
T Σ fo (z) ( t=
PolicyRegret
... xz)
min
Σ f(
zER
In this setup, the first term corresponds to the DAC policy we choose, while the second term is used to approximate the optimal strongly stable linear policy.
Lemma 5. Under Assumption 1 and choosing m C and n O 7% Algorithm 1 attains the following bound of R2:
Ra Σ J(M,
(MM--,,-.. H M.) min MEM
J(M,..., M)
4a
GGDD>> + 1)WOBB
GDCR 1)WORB + C n
To analyze this term, transform the problem into online convex optimization with memory and utilize existing results presented by [5] for it. By applying their results, we can derive the following bound:
T
Σ Se (at- H,.., min 1=
Je(a,
mek.
1=H
15

---

Taking into account the bounds on the diameter, Lipschitz constant, and the gradient, we can ultimately derive an upper bound for R2.
Lastly, we aim to establish a bound on the approximation error between the optimal DAC policy and the unknown optimal linear policy.
Lemma 6. Under Assumption and Algorithm
attains the following bound of R3:
(++1)m-1
R3
Σ f. M) MEM
min
Σ
Σ j=im
ca(2,, s 3n((1 hr) 1).
The intuition behind this lemma is that the evolution of states leads to approximation of the optimal linear policy in hindsight, where u, = - (K (L) + h(A ))*))' Although the optimal policy K is unknown, such an upper bound attainable because the left-hand side represents the minimum of M E M.
~K* x, we choose M = {M'', where M
C
The evolution of the state
In this section we will prove that using the DAC policy, the states and actions are uniformly bounded. The difference between ideal and actual states and the difference between ideal and actual action is very small.
We begin with expressions of the state evolution using DAC policy:
Lemma 7, We have the evolution of the state and action:
21
21+1 =
Q
:1-1
+
Σ
Ue,
1=0
2Hm
Vi+1 h Σ
V 1
i=0
Hm
11
yt
Mt wr
where Ve, represent the coefficients of is-s;
V = = 1ig Σ
0
1=0
Proof. Define Qn 1 + h(A BK). Using the Taylor expansion of x, and denoting rr as the second-order residue term, have
#1 = 24 + hé, + 1rrr. = In + N((A, + Bu, + we) + 1rr..
Then we calculate the difference between w, and w6;
W F1+1 It h(Ax + But + we) hr
h
16

---

Using the definition of DAC policy and the difference between disturbance, we have
2141 22 Ax4 + B
-Kxt + h
Ma ) + Wi hore
1r
(T + (h+h(A- BK))at+ +
Bh Σ
Mj + wi
Qna +
Bh
Wi + +0g
i=1
1 vi-1 1) + Bh Σ Mp 1/
1h:1111 +
Qi
Bh Σ
Mt
21
=Q++ 2t-1
V t,i 1-
where the last equality is by recursion and Vr,, represent the coefficients of úz-i- Then we calculate the coefficients of uz-; and get the following result:
Ve, Q 1. + h Σ LL
j=0
By the ideal definition of Vt++1 and v,(only consider the effect of the past Hm steps while planning, assume It- Hm 0), taking / = Hm we have
2Hm
Me+1 h
Σ
Y=U
Hm
11
Kyg + h
Mc W
Then we prove the norm of the transition matrix is bounded.
Lemma 8. We have the following bound of the transition matrix:
Prall S a(Ihan + 1)x² (1 - 1r)²=1
Proof. By the definition of strongly stable policy, we know
|Q ( = |IP(In)) s | s ax²(1 h7)²
(2)
By the definition of 12,5, we have
| = 1ist + Σ C.BM
1=0
< <x - hry)* + ah Σ K1 h7) 1-71--111
< x2 (1- hr: + (1 s allhk + ()x2(1- - -
where the first inequality is due to equation assumption and the condition of |Mill S a(1 hy))-1
After that, we can uniformly bound the state and its first and second-order derivative.
17

---

Lemma 9. For any t E. T), choosing arbitrary h in the interval [0, hul where hu is a constant only depends on the parameters in the assumption, we have || D | S Dz, || I D3 and the estimatation of disturbance is bounded by || S Wo. Moreover, Dr. D2, D3 are only depend on the parameters in the assumption.
Proof. We prove this lemma by induction. When / - O, it is clear that zo satisfies this condition. Suppose 2t S D1, it I D2, 3t D3, Wy S Wo for any L S lo, where to = kh the k-th discretization point. Then for I E [lo, to + hl. we first prove that क; S D2. Ht S D3-
By Assumption
| and our definition of ue. we know that for any [to.to to + hl. Thus, we have
| || = A|, + Bug + well
=I1Ax + B(- Kxto + h
M M + wzll
<Al||=el|+ + + 11 + 11)) Wo W
S &nlls=lll + Wo + W,
where the first inequality is by the induction hypothesis ii S Wo for any S to and Mt S
(1 - hy)'-1, the second inequality is by the induction hypothesis Iı S D2 for any t S to-
For any t E [to. to + hl, because we choose the fixed policy = Uto so we have i; = 0 and
ا = ||A + Bü, + r ||Ar, + u ll S KAll + W.
By the Lewton-Leibniz formula, we have for any Ç E [0, h].
Stotc - ito = 1// Tcotede.
Then we have
|| |1 $ || + S/" l|it
S | ll 1 (mal + Wids
= =11itoll + +WC MA 1- |
By Gronwall inequality, we have
| S || + WS (/ (1létoll + wx))xxs(aass---eee =))de
Then we have
WC+ / (11::o0l ll ex)(xp(( | S ||
(11 - W1)( (eXp(RAA))
KA KAI +KDD + Wo
+ +W + wh) (1 + h exp(RAh))
Wo
(RA + BI
+ w + wh (1 (1+ hex((aaa)))
?
Wo
(RA + RBK)D +
+ 2w) (1 + exp(RAA))
7
18

---

where the first inequality is by the relation & S S, the second inequality is by the relation < h and the bounding property of first-order derivative, the third inequality is by the induction hypothesis and the last inequality is due to h 1 1.
By the relation ||all I KA | + W, we have
I| S RAD2 + W. So choose D3 A2 W. By the equation, have
1++1 It h(Az,
But + we)
[0 well
Ft+1 It hate
So (de+e iz) )dE h
So So SxtedgdE
h So So
1| llGGE
hD3,
where in the second line use the Newton-Leibniz formula, the inequality is by the conclusion | < D3 which we have proved before. By Assumption
[
we have
|| S W + hD33
Choosing D3 = KKAD2 + W. W6 = W + hD3 = W + M(AAD2 + W), we get
Wo + 21) + exp((aa)
|itto-ll S +BAA+
7
W + h(xx 22) (xxp(K)))
(IKA + Dz
7
huA (1 + exp((a)))
+ (KA (BA)+ + (1 h h1+ w (1 + exp(xx)))
< D2
?
Using the notation
B1 hKA (1 + +xxp(Ha)))
B2 ((AA+ + 2(1 W)W
(1 + exp(Nx))
When h < [<x(T+oxp<<a)) we have B1 < 3. Taking D2 2,32 we get
|| S 31 D2 + B2 D2.
So we have proved that for any t E [tu, to + h], | S D2, ||te|| S D3, || $ Wo.
Then we choose suitable Dj and prove that for any E [lo, to h1, || S DI.
Using Lemma 7 have
T++1 h
V Wir
<=0
By the induction hypothesis of bounded state and estimation noise in [0, 4o] together with Lemma g we have
| || < h Σ (Thi + 11)=2(1 hx)'(W + hD2))
1=0
(Ths + 1)x2 + +Daz)
<
7
19

---

Then, by the Taylor expansion and the inequality 24 S D2 we have for any Ç E h),
| xetell = [/ A {
detedEll S (h ())- S hD2.
Therefore we have
(WhK + 1) + hD3)) + +1D2
|| s || +12 <
(lhxE + +1)22 +1i
(UiKA + 1)mPRiA +1)
+hD2
(ln + +))2K2
(IE + 1)mPnes +1) + hD2
In the last inequality use h < 1.
By the relation D2 = 92/ (1) and B1 S 2. we know that
(NEA + KBB) (BB)))+ 2(1 + ) (1 + exp(na)).
D2 s
Using the notation
11 2h(KA + KBx) + exp(NA)).
72 (IKg + 2 (1 (1+ +)) (1 exp(xa)) [In 1)12 (1) + 11)
7
7
We have || S Di + +2.
From the equation of 7/1 we know that when S 3(K ((rattant) we have 71 S 2' Then we choose D 272,, we finally get
| S 11 7/ Di.
Finally, set
ho min {1, KA (1 + exp(R>))) 4(RA KBK)(1 exp(Rx))
7
By the relationship Di 222 D2 2,3,, D3 KAD2 W. Wo W + hDss
we can verify the induction hypothesis. Moreover, we know that DI. Dz. D3 are not depend on Therefore we have proved the claim.
The last step is then to bound the action and the approximation errors of states and actions.
Lemma 2. Under Assumption ] and 2 choosing arbitrary in the interval [0, ho] where hg is constant only depends the parameters in the assumption, we have for any and policy M..
|| l| [[yell, I|uell [|oa]] S D. || < D, I| - yell. I|u - vell S x²(1 + x.)(1 - -hy) -hyy) Hm+1 D. In
particular, taking all the Mr and K K*, we can also obtain the inequality of the optimal solution:
| ll || < D.
Proof. By Lemma 8 have
Weall I alIhn + 1)r²(1 -17)
By Lemma 9 we know that for any h in [0, hol, where
7 KA(1 + exp(xx)) 4(KA + KBK)(1 + exp(xA))
ho min
20

---

we have ||aa|| 1 D1.
By Lemma Lemma 8 and Lemma 9 we have
2
11 11 = |1/ Σ
Vr
v6r-1l
==0
2
hWo
Σ
a(IhKB + ()- h7)
aWo(IhnB + 1)x²
D1.
Via the definition of Te. Me. we have
| well 2² 1 hy) Hm+1 ||02- H
Hm S x2 hyy Hm)3 D
For the actions
Hm
Kr, + h
Mf w
i=1
11
Ky
Mf -
we can derive the bound
Hm
Hm
aWo
||elll S KKaell 1
Σ
M -.: S Sx 11 + Woh Σ a(1 - 111-17)*1 S sDD, +
Hm
Hm
a (7)- S xD) + aWo
||eell < |yyell + h Σ
M 0; ||| S <1 + Woh
Σ
1=1
1=1
| vell < |||| 22
well x3 (1h) Hm+ Di.
By Lemma taking D = max D1,
1 D2, D2, xD + -ie kD Wi || ll. l1 Tuull || < D. || s D.
3
}. we get the following inequality:
We also have
||x; well + 1 0//l s -vle
Hm Di - Hm+ D1 & N (1+ hy) Hm D.
In particular, the optimal policy can be recognized taking the DAC policy with all the M, equal to 0 and the fixed strongly stable policy K = K*. So also have || ||uî]| D.
Now have finished the analysis of evolution of the states. It will be helpful to prove the key lemmas this paper.
D Proof of Lemma 3
In this section we will prove the following lemma:
Lemma 3. Under Assumption Algorithm attains the following bound of Ro:
n-
(++1)h
Ro
(ce(xe, us) - ce(a;; u, df
(c, w:) - cu(x;, S (G+ L)DDPTT
i=U
ih
21

---

Proof. By Assumption 2 and Lemma
since we use the unchanged policy in the interval
t [t,, (i+ 1)hb. we have
co(a,, u4) can (Tan, un))
- (1, uz) - ce (Z unn) + cee(Tar: u.n) - can (wens uan) | 2 w)ll 11 - -xill + L(t ih)
- max
GDII / dاd'sl L(I ih)
(G LID - ii)..
Therefore have
(++1)
celxe, uz)dt - h Σ cl uz)l
2=
(1+1))
(Ca(3re) - cen (win, Uahh ddt)
1=0
n-
(i+1jh (t (t- 1 L)+
1
S + D)D2
2 (G + L)DANT
similar bound can easily be established by lemma 2 about the optimal state and policy:
(1+1)
1 (G + L)D²NT
2,) c(2),,,) = 2
Taking sum of the two terms we get Ro (G+ L)D
E Proof of Lemma 4
In this section we will prove the following lemma:
Lemma 4. Under Assumption Mand2 Algorithm attains the following bound of Rı:
1141)m1
M.) S nGDD>>2 k) H
R1
u(),, fe
j=im
Proof. Using Lemma 2 and Assumption 2 have the approximation error between ideal cost and actual cost bounded
Iee (zz, u,) (ve, v1)l < lca (I,, u.) c, (vt, uz) lce (ye, ue) ct (ve. ve)l
< GDI - yill + GD 4 - well (1
hr))+++!
where the first inequality is by triangle inequality, the second inequality is by Assumption 2 2, and the third inequality by Lemma
Lemma
With this, we have
(++1)m1
R
==
Σ
G(z,, u:) - fa(M, 11
Mi)
(++1)=11
(6+1)m-
Σ
C((Ts, - Σ
==
mi
Σ
Σ
GD2 x)(1 1y) Hm
nGDD2> x)(1 hr) Hm+)
j=im
22

---

F Proof of Lemma 5
Before start the proof of Lemma first present overview of the online convex optimization (OCO) with memory framework. Consider the setting where, for every t, an online player chooses some point 24 K C I2, loss function ft K R is revealed, and the learner suffers loss of ft (Z.-H,..., Tt). We assume a certain coordinate-wise Lipschitz regularity on ft of the form such that, for any j E {I,..., H. for any I1, ,..,..,,,,,............. HH E K
Ife
.H) ft (#1,.... 33 "............................... HH) S L Llarr -Byll
In addition, we define fi(x)) fi(....... 2). and we let
Gj = sup rE(1.... T) ME
| Dy=
sup v.ye
|| - y/1
ME
The resulting goal is to minimize the policy regret, which is defined
Regret Σ fe (x H. ................................ x1) min
Σ
f(
aEK
Algorithm 2 Online Gradient Descent with Memory (OGD-M)
Input: Step size 7, functions {fi)r Initialize 2o, ................................ -- E K arbitrarily.
for I. = H...., T do
Play H.. suffer loss (I+ Hy My..., st).
Set x++1 11 [i - (V(()))
end for
To minimize this regret, commonly used algorithm is the Online Gradient descent. By running the Algorithm 2 we may bound the policy regret by the following lemma:
Lemma 10. Let {ft) be Lipschitz continuous loss functions with memory such that ft are convex. Then by runnning algorithm itgenerates a sequence {xe)t=z such that
T
T
D} + +TG LH'
Σ
x1) min f((a, ............................ x) S π
t=H
1=
Furthermore, setting 1)
Dj
implies that
PolicyRegret < /2D//G, (G, T
Proof. By the standard OGD analysis 18 we know that
D3 Σ f(()) < + TG2 n.
min aek t=
t=
In addition, we know by the Lipschitz property, for any / 2 H, we have
Ise (fi- .o.-H....,.4 x1) So (Iis,..,, 25))
L
| x2 L
1--1111 x1-1|
j=1
L
V (x)-)) s LHH?G
and so we have that
T
T
Σ
Je (Tr-H....,
Σ
Si (it)...,
STLH
1=/
23

---

It follows that
D2
Σ (=H
Je (x=-H, H.... .....,.... xz)
min .)) [e( + TG I.H "
1=H H
In this setup, the first term corresponds to the DAC policy we make, and the second term is used to approximate the optimal strongly stable linear policy. is worth noting that the cost of OCO with memory depends on the update frequency H. Therefore, we propose a two-level online controller. The higher-level controller updates the policy with accumulated feedback at a low frequency to reduce the regret, whereas lower-level controller provides high-frequency updates of the DAC policy to reduce the discretization error. In the following part, we define the update distance of the DAC policy as [ = Hm, where m is the ratio of frequency between the DAC policy update and OCO memory policy update. Formally, we update the value M, once every m transitions, where 9i represents loss function.
(IIM (M, 9))) if t%m == M
Mc+1
otherwise.
From now denote Me- Mem for the convenience to remove the duplicate elements. By the definition of ideal cost, we know that it a well-defined definition.
By Lemma we know that
2H m
Vt+1 =
Σ
V w6
i=0
Hm
01 -Ky + h
M úz
where
Ve, Q + h Σ of 44
j=0
So we know that ye and yt are linear combination of M,, therefore
(++1)m-1
Se (M, M.)............... convex in M,. So
Σ ci un
(
(M. M.) ve (M--H,..., .M).
t=mm
use the OCO with memory structure solve this problem.
By Lemma 9 we know that Yt and vi are bounded by D. Then we need to calculate the diameter, Lipchitz constant, and gradient bound of this function fs. In the following, we choose the DAC policy parameter Hm.
Lemma 11. (Bounding the diameter) We have
2a by
Dj
sup M,M.EEM
IIM; - M, <
Proof. By the definition of M, taking (
Hm we know that
Hm
sup M,M.E.M
MM, - M₁ <
Σ
M
-M
k=1
Hm
2a(1 1ry)
Rm1
2a
<
Inn

---

Lemma 12. (Bounding the Lipschitz Constant) Consider two policy sequences
{ {M- ... Mi-k... Mi} and MM-H.... ... Mi-k... Mi} which differ exactly one policy played at a time step k for l E {O...., .....,H) H). Then we have that
Nm
fo (Mi-H... ... Mi-k... M.) (Mi-H... Mi. (.......M)) s SR²K
KB
Σ j=0
- Mi-ell
where C' is a constant.
Proof. By the definition we have
2Hm
Hm
11 - Jell = 1
h Σ j=0
Q B(M M,33) jEll
( Hm] Wi
1=0
2Hm Hm Σ
S k22x2 KB Wo
MM
j=0
112 < Wom
M M/-11
Hm
= hhCR'RBW Wo
Σ
|| -M
1=0
Where the first inequality by |Q S (1- 1- S x² and lemma of bounded estimation disturbance, the second inequality is by the fact that M,- have taken m times, the last equality is by C Furthermore, we have that
Hm
|12 ūell = K (y+- - 0.) S hC Wo
M
Therefore using Assumption] 2 Lemma and Lemma 2 we immediately get that
Hm
[s (M--H Mi M. fa (M-n-... Mi-k- .......M)) s C² (2222kp Wo >
- M/_ell
j=0
Lemma 13. (Bounding the Gradient) We have the following bound for the gradient:
MM.. M)Il < GDC (K + 1)WORB
?
Proof. Since M is matrix, the E2 norm of the gradient V fe corresponds the Frobenius norm of
the Ta fe matrix. So will be sufficient to derive an absolute value bound on V Mir Je(M.... .))
for all p, To this end, consider the following caleulation. Using lemma 9 we get that ye VMM M N..M., (M M) < D. Therefore, using Assumption 2
we have that
()
(y) a + Ov. (.M....) M))
1)
Minl CeM M) SGD
aM
25

---

We now bound the quantities on the right-hand side:
dyd (M ... M)
m
Hm
aQi BM 1-5)
8.M4p
[r]
h
aMp
20
1,
/ 1.
2=0
==1
r4 mm
aQ BM
S ht2
Σ
Wa-
aM
[r]
P-q
hn W
S h22 k WoBB
hy
Similarly,
(M ...M) 0Mp [r]
S Syc(M M))
hR WONB 7
h WoKB
8Mpp [r]
Combining the above incqualities with
(++1)-11
fi (M H......... Mr)
Σ t=mm
aa (u (M..H...., M.. o (M.-.....,,M. M.))
gives the bound that
GDCR2 1)WONB
MIM. M)Il
Finally we prove Lemma 5
Lemma 5. Under Assumption 1 and following bound of R2:
choosing C and n O ((7) Algorithm 1 attains the
1-
R2 = Σ M(M, M.......
M.)
min MEM
Ji( M))
1=
4=0
4a
GDDC>2(K 1)WONB GDOR2(K + 1)WONB + (o Th
7
Proof. By Lemma 10 we have
R₂ 2D, Go, (Gy LHH)
By Lemma Lemma 12 and Lemma 13 we have
Ra s 2D,
Gr (G, GDD/GGrA
LH²)
2a hy
GDCR> - 1)WOKB GDCR?(K + 1)WORB + Wo n
<
< 4a
GDD + 1)WOKB GDCRR(N + 1)WOBB + +3* n
26

---

G Proof of Lemma 6
In this section, will prove the approximation value of DAC policy and optimal policy is sufficiently small. First, we introduce the following:
Lemma 14, For any two (r, -tsoonnyyy stable matrices K K, there exists M = (M ,..,, M m)) where
M (K (K)K))( (1 4(A -B*))
such that
uM)))(M) cx(2,, u() S a + 1)(1 hy)
Proof. Denote (K(K) = I h(A BK), QN(K) = I h(A BK*) By Lemma we have
2 h Σ
2h (K")),
1=
Consider the following calculation for S Hm and M = -KK-K>)(T+M) -K*))
21 MM) (K) + h 2F (K)BM²
= (K() + h
2 (-) (K) -f (KK)
Ø=1
QK(K) + Σ
2 (K)(((())))) - (K(K)) (K*)
|=1
Q (K*),
where the final equality follows as the sum telescopes. Therefore, we have that
(M) = Σ Q "K-K+)++++
V Vi
t= Hm+11
Then we obtain that
[M++ - si+1ll s AWo
Σ i=#++1
Ve (M.) (K*))))
Using Definition annd Lemma 7 we finally get
(M) 2141|| < hWo Σ ((hEB + 1)an? - (17))-11)) 2² hT)
#mm+1
Wlhk + 2)ax² (1 hy)
27

---

We also have
l/ug ue (M/)l
1 Kx [M]]]=
Kr, (M) - h Σ
M
1=0
Hm
=I(Kk Kd) + (Mx - x/) - Σ
M Wi
Hm
II(K - kn) Σ (K + K(xx(M) - -x7)= - Σ
M M will
i=0
= [I(ax((M) - 21) h Σ
(K -K) -
(K*))(
i=#m+1
= =I]Khh
Σ
(V
(KK) h
Σ
(K- K2 (K-))(
i=Hm-1
i= Hm+11
h
Σ
K (O (K*) (KK) + Ve.i) ii:-
H=#++
S Won((1 - hy
Hm + a(lhx + 1)k² (1 (1- h1) Hm)
Won(a(UhsB + 1)x² + 1)(1 17) Hm),
where the inequality by Definition [ and Lemma
Finally, we have
lee (zx (MM, (MM)) (xā, uf]l
< ler (M) (M)) ce (xz ur (.,((() (M)) + lea (x)) - at (z7, ub)
<GD|,, xi1 (M) uzl
LGDDWnn'(lhxa + -1 hy) /y)# Hm
where the second inequality is by Assumption 2
Then we can prove our main lemma:
Lemma 6. Under Assumption 1
andd]
Algorithm 1 attains the following bound of R3:
(i+1)m-1
Rs min
Σ
S.M,...,
J(MM ..... M)
Σ
c,(,,u4)= I 3n(1 GDW a(thR + 1).
MEM 1=0
j=mm
Proof. By choosing
M' (K MA-
We know that
| (K - (I h(A- ( | - 7)
Therefore choose 2n.3 we have M (M*) in the DAC policy update class M.
Then we have the analysis of the regret:
(++1jm-1
Rs min MEM
Σ f(M ..... M)
M(M...,,
Σ Σ
c,,)]u4] uf)
(1+1)m1
(6+1)m-1
min MEM
((a,(M), u
a(at,u4)) +nx x)(1 by) Hm+ D
j=im
S <3n(1 - Ioy Hmm GDW 3
(1hK +1).
where the first inequality is by Lemma 2 and the second inequality is by Lemma 14
28

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We clarify our contributions and basic problem setups in both abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitation of our paper in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]

---

Justification:
We provide the full set of assumptions and a complete proof.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We disclose the experiment details in Section 6
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
30

---

Answer: [No]
Justification: Our code is very simple, just use the traditional SAC algorithm with one line implement. Our main contribution is the theoretical analysis.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm ec/
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.cc/ppp cc/public/guu httgg//ddde/ooSSubnnnnn SttSSuabissioooiiiiiii.oooii for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We specify all the training and test details in
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: For each experiment we use 3 random seeds and take the average.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
31

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We specify all the computational resources 6
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:p/pw./.arrr....o///o//////a
Answer: [Yes]
Justification:
We conform with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work is about the theory on online control, which does not seem to have evident societal impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
32

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We add citations for all datasets we used.
Guidelines:
The answer NA means that the paper does
existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
33

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
34


Reviews:
[{"review_id": "Ls7rxeXIt0", "reviewer": "Reviewer_2dzb", "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.", "questions": "-\tIn 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.\n-\tRegret 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\n-\tAssumption 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\n-\tAssumption 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\n-\tDefinition 1 of a strongly stable linear policy is central to the paper, but the motivation behind this definition is not entirely clear. \n-\tThe 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.\n-\t$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.", "limitations": "-\tStrict assumptions restrict the applicability of finding systems that meet these criteria\n-\tMethod is tailored for non-stochastic disturbances, leaving out scenarios where disturbances might have stochastic elements.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-\tIntroduction of a new two-level online control strategy that manages both policy learning & feedback control\n-\tGood theoretical analysis that achieves sublinear regret\n-\tValidation of theory with practical experiments using domain randomization in various robotic simulation environments", "weaknesses": "-\tThe paper lacks a comprehensive comparative analysis with other state-of-the-art methods.\n-\tExperiments 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", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the reviewer's valuable suggestions. We address the reviewer's questions as follows:\n\n>Q1: The paper lacks comparison with other state-of-the-art methods. \n\n**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. \n\nThe 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. \n\n>Q2: Experiments are conducted in simulated environments. \n\n**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.\n\n>Q3: The assumption of the access to $\\dot{x}_t$ at each time step is strong.\n\n**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.\n\n>Q4: Explain the definition of regret in section 3.4. \n\n**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.\n\n>Q5: Assumption 1 and 2 are quite strict. \n\n**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.\n\n>Q6: The motivation of Definition 1.\n\n**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.\n\n>Q7: The challenge of trading off approximation error & OCO regret in section 4 is subtle. \n\n**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}})$. \n\nIf 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})$.\n\nTherefore, 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.\n\nOnce again, we thank the reviewer for the constructive comments.\n\n**References**\n\n[1] Cohen, Alon, et al. \"Online linear quadratic control.\" International Conference on Machine Learning. PMLR, 2018.\n\n[2] Agarwal, Naman, et al. \"Online control with adversarial disturbances.\" International Conference on Machine Learning. PMLR, 2019.\n\n[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.\n\n[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.\n\n[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.", "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": "FWdrVNsCEE", "reviewer": "Reviewer_ks8t", "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.", "questions": "How the setting studied in this paper is related to the experiments.", "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.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "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.\n\n\n2. There are several minor writing or notation errors that need to be checked carefully. For example:\n\nline 21 they \"has\"\n\nline 36 it \"reliers\"\n\nline 104, missing definition of $\\mathcal{K}$", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our gratitude to the reviewer for the insightful comments. We address the reviewer's concerns belows:\n\n>Q1: There is a gap between the theoretical results and the experimental results. More discussion is needed.\n\n**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 c**ontinuous 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.\n\nWe will provide more detailed explanation below. First, we highlight some definitions of stochastic and robust control problem.\n\nIn 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:\n\\begin{equation}\n\\min_{\\mathcal{A}} \\mathbb{E}_{w_t \\sim \\nu} [J_T(\\mathcal{A})]. \\tag{Stochastic control}\n\\end{equation}\n\nIn 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:\n\\begin{equation}\n\\min_{u_1} \\max_{w_{1: T}} \\min_{u_2} \\ldots \\min_{u_t} \\max_{w_T} J_T(\\mathcal{A}). \\tag{Robust control}\n\\end{equation}\n\nWe 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:\n\\begin{equation}\n    \\min_{\\mathcal{A}} \\max_{\\nu \\in \\mathcal{V}} \\mathbb{E}_{w \\sim \\nu} [J_T(\\mathcal{A})] . \\tag{Domain randomization}\n\\end{equation}\n\nFrom 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.\n\n\nSo 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:\n\\begin{equation}\n    \\min_{\\mathcal{A}} \\max_{w_{1: T}} J_T(\\mathcal{A}) . \\tag{Non-stochastic control}\n\\end{equation}\n\nIn 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.\n\n>Q2: There are several minor writing or notation errors that need to be checked carefully. \n\n**A2:** We sincerely appreciate the reviewers pointing out these minor errors, and we will correct them in the next version of the paper.\n\n\nFinally, 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.\n\n**References**\n\n[1] Cohen, Alon, et al. \"Online linear quadratic control.\" International Conference on Machine Learning. PMLR, 2018.\n\n[2] Khalil, I. S., Doyle, J. C., & Glover, K. (1996). Robust and optimal control (Vol. 2). Prentice hall.\n\n[3] Agarwal, Naman, et al. \"Online control with adversarial disturbances.\" International Conference on Machine Learning. PMLR, 2019.", "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": "wnVt6kd1zv", "reviewer": "Reviewer_H9Pv", "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.", "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)?", "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.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "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, \n- 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.\n- 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- $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\n- 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", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.  \n\n\n\n\n>Q1: Why updating the DAC policy at each time step does not work. \n\n**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.  \n\n\nWe 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}})$. \n\nIf 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})$.\n\nTherefore, 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.\n\n>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. \n\n**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.\" \n\n>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.\n\n**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.\n\n\n>Q4: There are many typos in the proofs in the appendix. Some of the notations in the paper need to be corrected.\n\n**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.\n\n>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.\n\n**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.\n\n\n**References**\n\n[1] Agarwal, Naman, et al. \"Online control with adversarial disturbances.\" International Conference on Machine Learning. PMLR, 2019.", "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": "PvJFDVQHwL", "reviewer": "Reviewer_3oRE", "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.", "questions": "In this part, I list some other questions or suggestions:\n1. 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.\n2. 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.\n3. 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.\n4. 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.\n5. 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.\n6. 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.\n7. In Figure 2, the font sizes of 'Replay' and 'Buffer' seem to be different?", "limitations": "The authors have adequately addressed the limitations and, if applicable, potential negative societal impact of their work.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "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. \n\nSpecifically, 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n\n>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?\n\n**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.\n\nFor 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.\n\nFor 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}})$. \n\nIf 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})$.\n\nTherefore, 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.\n\n>Q2: Definition 1 is a little different from the standard strong stability condition in discretized systems.\n\n**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:\n$$x_{t+1} = Ax_t+Bu_t + w_t.$$\nFor continuous systems, the transition equation is:\n$$\\dot{x}_{t} = \\tilde{A}x_t+\\tilde{B}u_t + \\tilde{w}_t.$$\n\nIf we consider a relatively small time interval $h$, we can approximate it as follows:\n$$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).$$\n\nTherefore, we have \n$$x_{t+h} \\approx (I+h \\tilde{A})x_t+h\\tilde{B}u_t + h\\tilde{w}_t.$$\nThus, we can express the dynamics of the two systems as follows:\n$$A \\approx I+h \\tilde{A}, B \\approx h\\tilde{B}.$$\nAs 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}$.\n\n>Q3: Assumption 1, compared with the standard non-stochastic disturbances in discretized systems, uses an extra condition of the noise.\n\n**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\n$$\nx_{t+h} = x_t + h \\dot{x}_t + \\frac{h^2}{2} \\ddot{x}_m\n$$\nwhere $m$ is a number between $[t,t+h]$.\n\nUsing the notation and analysis in A2, we get the following relation of discrete and continuous system:\n\n$$\nw_{t} = h \\tilde{w}_t + \\frac{h^2}{2} \\dot{\\tilde{w}}_m\n$$\n\nTherefore, 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.\n\n>Q4: The arrangement of Section 3.2, missing citations in Section 4, missing definition of $g_t$.\n\n**A4:** We sincerely appreciate the reviewers pointing out these errors, and we will correct them in the next version of the paper.\n\nWe 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.\n\n**References**\n\n[1] Agarwal, Naman, et al. \"Online control with adversarial disturbances.\" International Conference on Machine Learning. PMLR, 2019.", "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:

Meta-review: Summary: Most of the existing works on online control have been on discrete-time linear systems, except for a handful of works that consider stochastic noise. This paper studies an online control problem with adversarial disturbances for a continuous time linear system. This paper proposes a two-level online controller to solve this problem. The higher-level controller symbolizes the policy learning process and updates the policy at a low frequency to minimize regret. The lower-level controller delivers high-frequency feedback control input to reduce discretization error. The paper shows that the proposed algorithm achieves sublinear regret in the face of non-stochastic disturbances. The performance of the proposed algorithm is illustrated using simulation experiments in the Mujoco setting. 

We received four expert reviews, with the scores 7, 6, 6, 4, and the average score is 5.75. Reviewers are generally positive about the technical contribution and algorithmic novelty. They are also satisfied with the simulation experiments. One reviewer has expressed concerns about two aspects of technical proofs, in particular about the difficulty of analysis and the novel contribution. I believe that the authors have given a detailed and satisfactory answer to this comment. 

The reviewers have given many critical feedback on improving the quality of the paper. The authors have acknowledged them and agreed to incorporate these changes in their revision. Please make sure that you update your paper based on these comments while preparing the final submission.
Decision: Accept (poster)