Online Control of Unknown Time-Varying Dynamical Systems
Authors: Edgar Minasyan
Paula Gradu
Max Simchowitz
Elad Hazan
Venue: NeurIPS 2021 Poster (2021)
Keywords: online control
linear time-varying systems
adaptive regret

Abstract: We study online control of time-varying linear systems with unknown dynamics in the nonstochastic control model. At a high level, we demonstrate that this setting is \emph{qualitatively harder} than that of either unknown time-invariant or known time-varying dynamics, and complement our negative results with algorithmic upper bounds in regimes where sublinear regret is possible. More specifically, we study regret bounds with respect to common classes of policies: Disturbance Action (SLS), Disturbance Response (Youla), and linear feedback policies. While these three classes are essentially equivalent for LTI systems, we demonstrate that these equivalences break down for time-varying systems. 

We prove a lower bound that no algorithm can obtain sublinear regret with respect to the first two classes unless a certain measure of system variability also scales sublinearly in the horizon. Furthermore, we show that offline planning over the state linear feedback policies is NP-hard, suggesting hardness of the online learning problem. 

On the positive side, we give an efficient algorithm that attains a sublinear regret bound against the class of Disturbance Response policies up to the aforementioned system variability term. In fact, our algorithm enjoys sublinear \emph{adaptive} regret bounds, which is a strictly stronger metric than standard regret and is more appropriate for time-varying systems. We sketch extensions to Disturbance Action policies and partial observation, and propose an inefficient algorithm for regret against linear state feedback policies.

Online Control of Unknown Time- Varying Dynamical Systems
Edgar Minasyan
Paula Gradu
Princeton University, Google Al Princeton
UC Berkeley
minasyan@princeton.ccm edu
pgradu@berkeley.com edu
Max Simchowitz MIT
Elad Hazan
Princeton University, Google Al Princeton
msimchow@mit.ccm
ehazan@princeton edu
Abstract
We study online control time-varying linear systems with unknown dynamics the nonstochastic control model. At a high level, demonstrate that this setting is qualitatively harder than that of either unknown time-invariant or known time- varying dynamics, and complement our negative results with algorithmic upper bounds in regimes where sublinear regret is possible. More specifically, we study regret bounds with respect common classes of policies: Disturbance Action (SLS), Disturbance Response (Youla), and linear feedback policies. While these three classes are essentially equivalent for LTI systems, we demonstrate that these equivalences break down for time-varying systems.
We prove lower bound that no algorithm obtain sublinear regret with respect to the first two classes unless a certain measure of system variability also scales sublinearly in the horizon. Furthermore, we show that offline planning over the state linear feedback policies is NP-hard, suggesting hardness of the online learning problem.
On the positive side, we give an efficient algorithm that attains a sublinear regret bound against the class of Disturbance Response policies up the aforementioned system variability term. In fact, our algorithm enjoys sublinear adaptive regret bounds, which is strictly stronger metric than standard regret and is more ap- propriate for time-varying systems. We sketch extensions to Disturbance Action policies and partial observation, and propose an inefficient algorithm for regret against linear state feedback policies.
Introduction
The control of linear time-invariant (LTI) dynamical systems is well-studied and understood. This includes classical methods from optimal control such LQR and LQG, well robust Ho control. Recent advances study regret minimization and statistical complexity for online linear control, in both stochastic and adversarial perturbation models. Despite this progress, rigorous mathematical guarantees for nonlinear control remain elusive: nonlinear control is both statistically and computationally intractable in general.
In the face of these limitations, recent research has begun to study the rich continuum of settings which lic between LTI systems and generic nonlincar ones. The hope is to provide efficient and robust algorithms to solve the most general control problems that are tractable, and at the same time, to characterize precisely at which degree of nonlinearity no further progress can be made.
35th Conference on Neural Information Processing Systems (NcurIPS 2021), virtual.

---

This paper studies the control of linear, time-vary vary-ng (LTV) dynamical systems as one such point along this continuum. This is because the first-order Taylor approximation to the dynamics of any smooth nonlinear system about a given trajectory is an LTV system. These approximations are widely popular because they allow for efficient planning, as demonstrated by the success of iL.QR and iLQG methods for nonlinear receding horizon control. We study online control of discrete-time LTV systems, with dynamics and time-varying costs
It+1 = A + Bru, + wt, (e(x;, We) u))
(.c,u)+3 R.
(1.1)
Above, 24 is the state of the system, u, the control input, we the disturbances, and A., B, the system matrices. Our results extend naturally to partial-state observation, where the controller observes linear projections of the state y/. = C, We focus on the challenges introduced when the system matrices A,, B, and perturbations w,, are not known to the learner in advance, and can only be determined by live interaction with the changing systems.
In this setting, we find that the overall change in system dynamics across time characterizes the difficulty of controlling the unknown LTV system. We define a measure, called system variability, which quantifies this. We show both statistical and computational lower bounds as well as algorithmic upper bounds in terms of the system variabilility. Surprisingly, system variability does not impede the complexity of control when the dynamics are known [16].
1.1 Contributions
We consider the recently popularized nonstochastic model of online control, and study regret bounds with respect to common classes of policies: Disturbance Action (DAC/SLS [44]), Disturbance Response (DRc/Youla [46]), and linear feedback policies. Planning over the third class of feedback policies in LTI systems admits efficient convex relaxations via the the first two parametrizations, DAC and DRC. This insight has been the cornerstone of both robust [49, 44) and online [3, 39] control.
Separation of parametrizations. For linear time-varying systems, however, we find that equiva- lences between linear feedback, DAC and DRC fail to hold: we show that there are cases where any one of the three parametrizations exhibits strictly better control performance than the other two.
Regret against convex parametrizations. Our first set of results pertain to DAC and DRC parametrizations, which are convex and admit efficient optimization. We demonstrate that no algorithm can obtain sublinear regret with respect to these classes when faced with unknown, LTV dynamics unless certain measure of system variability also scales sublinearly in the horizon. This true even under full observation, controllable dynamies, and fixed control cost. This finding is in direct contrast to recent work which shows sublinear regret is attainable over LTV system dynamics they are known [16].
We give an efficient algorithm that attains sublinear regret against these policy classes up to an additive penalty for the aforementioned system variability term found in our lower bound. When the system variability is sufficiently small, our algorithm recovers state-of-the-art results for unknown LTI system dynamics up to logarithmic factors.
In fact, our algorithm enjoys sublinear adaptive regret [21], a strictly stronger metric than standard regret which is more appropriate for time-varying systems. We also show that the stronger notion of adaptivity called strongly adaptive regret [1 1] is out of reach in the partial information setting.
Regret against state feedback. Finally, we consider the class of state feedback policies, which are linear feedback with memory length one. We show that full-information optimization over state feedback policies is computationally hard. This suggests that obtaining sublinear regret relative to these policies may be computationally prohibitive, though does not entirely rule out the possibility of improper learning. However, improper learning cannot be done via the DRC DAC relaxations in light of our policy class separation results. Finally, we include an inefficient algorithm which attains sublinear (albeit nonparametric-ratte regret against state feedback control policies.
Paper Structure
Discussion of relevant literature and relation to our work can be found in Section 1.2. In Section 2, we formally introduce the setting of LTT nonstochastic control, the policy classes we study and our key result regarding their non-equivalence in the LTV setting (Theorem 2. Motivated by this

---

non-equivalence, the remainder of the paper is split into the study of convex policies (Section 3) and of state feedback policies (Section 4). In Section 3, we show that regret against the DAC and DRC classes cannot be sublinear unless the metric system variability (Definition 3.1) itself is sublinear (Theorem 3.1), and also propose Algorithm 2 whose adaptive regret scales at the rate of our lower bound plus T term (Theorem 3.4). On the other hand, in Section 4 we show sublinear regret against state feedback policies is technically possible ( (Theorem 4.1) with a computationally inefficient algorithm, but also provide a computational lower bound (Theorem 4.2) for planning which reveals significant difficulties imposed by the LTV dynamics in this scenario as well. Finally, in Section 5 we pose several future directions, concerning both questions in LTV control, as well as the extension to nonlinear control.
1.2 Related Work
Our study of LTV systems is motivated by the widespread practical popularity of iterative linearization for nonlinear receding horizon control; c.g., the iLQR [40], iLC [29], and iLQG [41] algorithms. Recent research has further demonstrated that near-optimal solutions to LTV approximations of dynamics confer stability guarantees onto the original nonlinear system of interest [45].
We study algorithms which enjoy sublinear regret for online control of LTV systems; that is, whose performance tracks given benchmark of policies up to term which is vanishing relative to the problem horizon. [1] initiated the study of online control under the regret benchmark by introducing the online LQR problem: where learner is faced with an unknown LTI system, fixed costs and i.i.d. Gaussian disturbances, and must attain performance relative to the LQR-optimal policy. Bounds for this setting were later improved and refined in [12, 26, 10, 38], and extended to partial-state observation in [25, 24]. Our work instead adopts the nonstochastic control setting [3], where the adversarially chosen (i.c. non-Gaussian) noise is considered to model the drift terms that arise in linearizations of nonlinear terms, and where costs may vary with time. [3] consider known system dynamics, later extended to unknown systems under both full-state [20] and partial-state observation [39, 37J. The study of nonstochastic control of known LTV dynamics was taken up in [16], with parallel work by [32] considering known LTV dynamics under stochastic noise.
Low-Regret Control:
Unknown LTV dynamics: Our work is the first to consider online (low-regret) control of unknown LTV systems in any model. There is, however, rich body of classical work on adaptive control of LTV systems [28, 42]. These guarantees focus more heavily error sensitivity and stability; they only permit dynamical recovery up to error that scales linearly in system noise, and thus guarantee only (vacuous) sneear----oorzoo regret. More recent work has studied identification (but not online control) of an important LTV class called switching systems [31, 35].
Online Convex Optimization: We make extensive use of techniques from the field of online convex optimization [9, 18]. Most relevant to our work is the literature on adapting to changing environments in online learning, which starts from the works of [22, 6]. The notion of adaptive regret was introduced
in [21] and significantly studied since as a metric for adaptive learning in OCO [2, 47). [11] proposed
to strengthen adaptive regret and the stronger metric has been shown to imply results over dynamic
regret [48].
Recent nonlinear control literature: Recent research has also studied provably guarantees in various complementary (but incomparable) models: planning regret in nonlinear control [4], adaptive nonlinear control under linearly- parameterized uncertainty [5], online model-based control with access to non-convex planning oracles [23], and control with nonlinear observation models [27, 13].
2 Problem Setting
We study control of a linear tame-varying (LTV) system Eq. (1.1) with state x, E Rd,, control input ue E Rdd.. chosen by the learner, and the external disturbance wi E dhd chosen by Nature. The system is characterized by time-varying matrices A, E Rd B, E Rd,,dd, For simplicity, the initial state is I1 0. At each time f, oblivious' adversary picks the system matrices (A,, B,), disturbances w, and cost functions C. Rd. Rdd + R. The dynamics (A,, B,) are unknown the leamer: one observes only the next state r1+1 and current cost ce(:-)) after playing control u.
An oblivious adversary chooses the matrices, costs and perturbations prior to the control trajectory.
3

---

Adaptive Regret. The goal of the learner is to minimize regret w.r.t policy class II, i.e. the difference between the cumulative cost of the learner and the best policy x* E II in hindsight. Formally, the regret of an algorithm A with control inputs w1rr and corresponding states 21,7, over an interval / rr, C [7), is defined as
Regret, (A; Ees(Ee, colar, ue)
inf Σ Ea(aI u.) TEll EE7
(2.1)
EET
Here ,, 2 indicate the control input and the corresponding state when following policy æ. For randomized algorithm A, we consider the expected regret. this work, we focus on designing control algorithms that minimize adaptive regret, i.c. guarantee a low regret relative to the best-in-hindsight policy 7 E II on any interval S [T]] This performance metric of adaptive regret is more suitable for control over LTV dynamics given its agility to compete against different local optimal policies
r7 E II at different times [16].
Key objects. A central object in our study is the sequence of Nature's 's x's 21.7 that arises from playing zero control imput u, at each i.]. क,41 A w, [39]. define the following operators for all 4,
t-h+1
0 =I, va E (1,1), a = II AR. WE c a. B k=t
where the matrix product IT, with 2 is taken in the indicated order & = ......
r. the following identities give an alternative representation for the Nature's x's x and state x, with control input
uy in terms of the Markov operator at time t, G. |G] liz0:
l:20:
T Wi-i Fe+1 1++1 Σ
Gf
1=0
These operators and the alternative representation capture the dynamics by decoupling the disturbance and the control action effects.
Assumptions. We make the three basic assumptions: we require from (i) the disturbances to not blow up the system with no control input, (ii) the system have decaying effect over time, and (iii)
the costs to be well-behaved and admit efficient optimization. Formally, these assumptions are:
Assumption 1. For all E [T]. assume || || S Raat-
Assumption 2. Assume there exist RG 2 and p E (0, 1) s.t. for any h 2 0 and for all / E (T)
Σ [|G| 1lop S RG p² == (h). $24
Assumption 3. Assume the costs o: RRd x Rd + R are general convex functions that satisfy the conditions 0 S ce u) S max I, ||==|| + ||]]]"]]
and (I, || S L max(1, ||~||| + [|u]]] for
some constant L > 0, where V denotes any subgradient [7].
The conditions in Assumption 3 allow for functions whose values and gradient grow as quickly as quadratics (e-g. the costs in LQR), , and the max(1, (1 term ensures the inclusion of standard bounded and Lipschitz functions as well. Assumptions 1 and 2 arise from the assumption our LTV system is open-loop stable; Appendix A.2 extends to the case where nominal stabilizing controller known, as in prior work [3, 39J. While these two assumptions may seem unnatural at first, they can be derived from the basic conditions of disturbance norm bound and sequential stability.
Lemma 2.1. Suppose that there exist C₁ 2 1, P1 E (0,1) such that || lnp S p for any h 2 O and all E [T], and suppose that max; |[well < R.. Then, Assumption 1 holds with Ruat G. T-p1 R..
and Assumption 2 holds with P1 and RG = max max, || B, llop
Note that Assumption 2 implies that |e. Eiz0 | llop S RG. It also suggests that for sufficiently large h the effect of iterations before t are negligible round This prompts introducing a truncated Markov operator: denote G [ to be the I-truncation of the true Markov operator G,. It follows that their difference is ||G] Gellé, = Ei>n ||op I (hh) negligible in operator norm for sufficiently large h. Define the bounded set of h-truncated Markov operators to be Gh,, Re) {G [G")]osee ||G]le, I R&} with Gh. (h, R&) for all t.

---

2.1 Benchmarks and Policy Classes
The performance of an algorithm, measured by Eq. (2.1), directly depends on the policy class II that is chosen as benchmark to compete against. In this work, we consider the following three policy classes: DRC, DAC, and linear feedback. DRC parameterizes control inputs in terms of Nature's x's atpat, DAC does so in terms of the disturbances w, and linear feedback in terms of the states dt.- We express all three in terms of length-m parameter M- = [M]'] in bounded ball M(m, RM):
M(n, Ras) {(M ,..., M/mm-1): Σ - |M S RM}.
TM Definition 2.1 (DRC policy class), A DRC control policy Tàre of length m is given by up Ei M x where M [M]] icmm is the parameter of the policy. Define the bounded DRC policy class Imr RAr) - (Trre M MMm,, Ry))}
Definition 2.2 (DAC policy class). A DAC control policy da of length m is given by u. Σ M where M = [ the parameter of the policy. Define the bounded DAC policy class as dao (m, RM) dm . E M(m, RM))-
Definition 2.3 (Feedback policy class). A feedback control policy =feed of length m is given by u. = - Li= -n-1 M x; where M = [ is the parameter of the policy. Define the bounded feedback policy class as Ieed (m, RMa) = { feed
M M E M(m, Ru)). In the special case of
memory 1, denote the state feedback policy class State = [oed (m =
Convexity. Both the DRC and DAC policy classes are convex parametrizations: policy ı E Tare U The outputs controls that are linear in the policy-independen sequences 11. and w1.r, and thus the mapping from parameter M to resulting states and inputs (resp. costs) affine (resp. convex). Hence, we refer to these as the convex classes. In contrast, feedback policies select inputs based on policy-dependent states, and are therefore non-convex [15].
We drop the arguments m, Ryi when they are clear from the context. The state feedback policies Iastate encompass the H2 and Hos optimal control laws under full observation. For LTI systems, DRC and DAC are equivalent [46, 44] and approximate all linear feedback policies to arbitrarily high precision [3, 39]. However, we show that these relationships between the classes break down for LTV systems: there exist scenarios where any one of the three classes strictly outperforms the other two. Theorem 2.1 (Informal). For each class II in [Taree Iaa H[eed there exists a sequence of well- behaved (A,, B,, We, C.) such that policy x² E II suffers O cumulative cost, but each of the other TI suffers (2(T)) cost on all their constituent policies π E TT'.
two classes IT' E (Mare; Iaae: Usead)
The formal theorem that includes the definition of a behl--e instance sequence and the final statement dependence on m, Ras along with its proof can be found in Appendix F.I.
Notation. The norm ||- refers to Euclidean norm unless otherwise stated, [vx] is used as shorthand for m). 7 is used as subscript shorthand for (T]. The asymptotic notation (-),, ((-) suppress all terms independent of T, Ō(-) additionally suppresses terms logarithmic in T. We define (+()) to suppress absolute constants, polynomials in Rmat, Re, R& and logarithms in T.
3 Online Control over Convex Policies
This section considers online control of unknown LTV systems compete with the convex DRC and DAC policy classes. The fundamental quantity which appears throughout our results is the system variability, which measures the variation of the time-varying Markov operators G, over intervals I.
Definition 3.1. Define the system variability of an LTV dynamical system with Markov operators G G over a contiguous interval / C [7] to be
Vary(G) = min [
Σ G G. G. = I TET EEl
where || ||,,FF indicates the E2 norm of the fully vectorized operator and G |1| Eter G₁ is the empirical average of the operators that correspond to I. Recall that Varr (G) corresponds to I [T].
5

---

Our results in this section for both upper and lower bounds focus on expected regret: high probability results are possible as well with more technical effort using standard techniques.
3.1 A Linear Regret Lower Bound
Our first contribution is a negative one: that the regret against the class either DAC or DRC policies cannot scale sublinearly in the time horizon. Informally, result shows that the regret against these classes scales as To, where o² is the system variability.
More precisely, for any o² E (0, 1/8), we construct distribution D. over sequences (A,, Bt, Ct, we), formally specified in Appendix F.2. Here, we list the essential properties of D,: (i) Ar = O, (ii) C is a fixed cost satisfying Assumption 3 with L I 4. (iti) the matrices (B,) are i..d.. with |Bellop & 2 almost surely, and [| -[l = o², and (iv) |[we|| & 4 for all t. These conditions imply that Assumptions and hold for RG = p 0, Rmat 4. The condition A, 0 implies that xtaa = w/ for all 1, so the classes DRC and DAC are equivalent and the lower bound holds over both. Moreover, by Jensen's 's inequality, this construction ensures that
B[ (G)] = ||| E mmin Ever ||G G2
| 1/1-'E(min E[min Eter | B:ll < Bi E[B.JI =
In particular, E[Varr (G)) < o². For the described construction, we show the following lower bound:
Theorem 3.1. Let C be a universal, positive constant. For any (0,1/8) and any online control algorithm A, there exists DRC policy x² (1, s.l. expected regret incurred by A under the distribution Da and cost c(x, u) is at least
( fo "I C To [[
full construction and proof of Theorem 3.1 is given in Appendix F.2. In particular, for a = 1/8, we find that no algorithm can attain less than Q(T)) expected regret; stark distinction from either unknown LTI [39, 20] or known LTV [16] systems.
3.2 Estimation of Time- Varying Vector Sequences
To devise an algorithmic upper bound that complements the result in Theorem 3.1, we first consider the setting of online prediction under a partial information model. This setting captures the system identification phase of LTV system control and is used derive the final control guarantees. Formally, consider the following repeated game between a learner and an oblivious adversary: at each round t E (T), the adversary picks target vector z E K. from convex decision K. contained in O-centered ball of radius Rz; simultaneously. the learner selects an estimate 2, E and suffers quadratic loss (²,) = ||a, 2t The only feedback the learner has access is via the following noisy and costly oracle.
Oracle (Noisy Costly Oracle). At each time E [T], the learner selects a decision b, E {0, 1) indicating whether a query is sent to the oracle. If b, 1, the learner receives an unbiased estimate 2, response such that | < R₂ and E/2, Fi, b = 1] z, The filtration Fi is the sigma algebra generated by 21.t-1 1, bi:t-1 and the choices of the oblivious adversary žं.-- completed query results in unit cost À > 0 for the learner.
The performance metric an online prediction algorithm Apred is expected quadratic loss regret along with the extra cumulative oracle query cost. It is defined over each interval I = [r. C [T] as
Regret, (Apredd X) Esir
Σ (((2)) LET
min Σ z
(()
+
b SET
(3.1)
To attain adaptive regret, i.e. bound Eq. (3.1) for each interval 1, we propose Algorithm constructed as follows. First, suppose we wanted non-adaptive (i.e. just / [T] guarantees. In this special case, we propose to sample b, ~ Bernoullip)) for an appropriate parameter E (0, 1), and perform
gradient descent update on the importance-weighter square loss (z) 2/ 1 1) |z 2. To

---

Algorithm 1 Adaptive Estimation Algorithm (ADA-PRED)
1: Input: parameter p. decision set K.
2: Initialize: 2(t) E K. working dictionary S = {(1 (2) 91 (1)
parameter a
p (R, R,)
3: for t 1..... T do
4: Play iterate 2, = - (1.z Js, 9t
(6) 2()
5: Draw/Receive b, Bernoullip)
6: if by = 1 then
7: Request estimate 2, from Oracle 1
8: Let (z) 2p1 žel1 and V. p (z 2)
9:
else
10:
Let 2N t 9 and (z) = 0 and V. =0
Update predictions (3)
1,+ Projk (6) nh v.) for all (i, (1, St
11:
12:
Form new dictionary Si+1 = (i, 217 (ickeys(S,)
13:
Construct proxy new weights de+1
(i)
t
Ejelayatt ( -ot((())) for all i keys(S.)
de -atrc())
Add new instance S.+1 + U 1, 2,2 (1+2)) for arbitrary (((+1) K with de+1 F+1
(t+1)
14:
15:
Prune S form S,+1 (see Appendix C.I)
(8) Normalize 96+1 Ejelnya(S
16:
extend this method to enjoy adaptive regret guarantees, we adopt the approach of [21]: J: the core idea in this approach is to initiate an instance of the base method at each round t and use weighted average of the instance predictions as the final prediction (Line 4). The instance weights are multiplicatively updated according to their performance (Line 13). To ensure computational efficiency, the algorithm only updates instances from working dictionary S: (Line 11). These dictionaries are pruned each round (Line 15) such that |Sel = OOlog T) (see Appendix C.1 for details).
Theorem 3.2. Given access to queries from Oracle I and with stepsizes te 1 enjoys the following adaptive regret guarantee: for all I = [r, s) S (T].
8-i+1 Algorithm I
(ADAett(ADD-PRED;/)) A) < 2(R: + R2) (1 + log log M App
(3.2)
p
When I [T]. the optimal choice of parameter p log T XT yields regret scaling roughly as / A2' log".. Unfortunatelly, this gives regret scaling as /T for all interval sizes: to attain [ regret on interval I, the optimal choice of would yield ~ T/ T/vlI| regret on [T', which is considerably worse for small [[]. One may ask there exists strongly adaptive algorithm which adapts as well, so as to enjoy regret polynomial in [Z] for all intervals I simultaneously [11]. The following result shows this is not possible:
Theorem 3.3 (Informal). For all 7 > 0 and access to Oracle that enjoys strongly adaptive regret of Regret, (A; Ö(117-7))
there exists no online algorithu A with feedback
Hence, in sense, Algorithm is as adaptive as one could hope for: it ensures a regret bound for all intervals I, but not strongly adaptive one. The lower bound construction, formal statement, and proof of Theorem 3.3 are given in Appendix C.2.
3.3 Adaptive Regret for Control of Unknown Time-Varying Dynamies
We now apply our adaptive estimation algorithm (Algorithm 1) to the online control problem. Our proposed algorithm, Algorithm 2, takes in two sub-routines: a prediction algorithm Apred which enjoys low prediction regret in the sense of the previous section, and a control algorithm Actrl which has low regret for control of known systems. Our master algorithm trades off between the two in epochs 7 1, 2... of length h; each epoch corresponds to one step of Apred indexed by [r].
7

---

At each epoch, the algorithm receives Markov operator estimates from Apred (Line 3) and makes a binary decision bizj Bernoullipp). If bir] 1. then it explores using i.i.d. Rademacher inputs (Line 7), and sends the resulting estimator to Apred (Line 14). This corresponds to one query from Oracle 1. Otherwise, it selects inputs in line with Actrl (Line 9), and does not give a query Apred (Line 16). Regardless of exploration decision, the algorithm feeds costs, current estimates of the Markov operator and Nature's x Is based on the Markov operator estimates to Actrl (Lines 10-12), which it uses to select inputs and update its parameter.
The prediction algorithm Apred is taken to be ADA- PRed with the decision set G(h, RG): the projection operation onto it and the ball IB Roos is done by clipping when the norm of the argument exceeds the indicated bound. The control algorithm Acul is taken be DRC-OGD [39] for known systems.
log'T log logp-1 p T-1/3 and m S VT, on any contiguous interval [T].
Theorem 3.4. For h
Algorithm 2 enjoys the following adaptive regret guarantee:
E (aarrctyADD-CTLLL) (m, RM)) s Ō- (Lm (alrE//ar,(Gi)) d,T2/3))
(3.3)
Proof Sketch. The analysis proceeds by reducing the regret incurred to that over known system, accounting for: 1) the additional exploration penalty (O(p)T))), 2) the system misspecification induced error (~~ Eter ||G; 1 op.)), and 3) truncation errors (~~ (f)) I). Via straightforward computations, the system misspecification error can be expressed in terms of the result in Theorem 3.2, ultimately leading to an error contribution |/|y //l/B/Var/ +p 1 ||/2 The analysis is finalized
by noting that the chosen p ideally balances p/4| and p 1/2 1/21//1//2 12/2, and that the chosen ensures that the truncation error is negligible. The full proof can be found in Appendix D.
The adaptive regret bound in Eq. (3.3) has two notable terms. Note that the first term / E| E[ (G (G) for / = [2] matches the regret lower bound in Theorem 3.1. Furthermore, our algorithm is adaptive in this term for all intervals /. On the other hand, for unknown LTI systems with Vary ( (G) 0, the algorithm recovers the state-of-the-ee bound of T2/3 [20]. However, the T223 term is not adaptive to the intervals consistent with the lower bound against strongly adaptive algorithms in Theorem 3.3.
Algorithm 2 DRC-OGD with Adaptive Exploration (ADA-CTRI)
1: Input: p, h, Apred + ADA-PRED(P, Go, Gh,, RG)), Act + DRC-OGD(m, RM) D let t, = (T 1)h +
2: for T ===1 -I...,,T/h
3: Set Gr,, Gr, Gr +h-1 equal to 7-th iterate G|r] from Apred
4:
Draw b[r) ~ Bernoulli(p)
5:
for t.
f, h do
6:
if byr = then
7:
Play control [=1]d.
8:
else
9:
Play control according to the 1-th input chosen by Actrl
10:
Suffer cost ot (21, ux) observe state Iz-1
Extract apat = ProjaR... auot ( Eiz Ald ue-i)
11:
Feed cost, Markov operator and Nature's x estimates (Ct, Ge, snae) to Actri- then
13:
if biz]
Feed (b(r). G(r) to Apred, where G/4 21,th +h-i i = 0, 1........ .. 1.
14:
15:
else
16:
Feed (b|=). G(+) to Apred, where G(+) +-
4
Online Control over State Feedback
Given the impossibility of sublinear regret against DRC/DAC without further restrictions on system variability, this section studies whether sublinear regret is possible against the class of linear feedback

---

policies. For simplicity, we focus on the state feedback policies = Kx,, that is, linear feedback policies with memory m = 1 (Definition 2.3). We note that state feedback policies were the class which motivated the relaxation to DAC policies in the first study of nonstochastic control [3].
We present two results, rather qualitative in nature. First, we show that obtaining sublinear regret is, in the most literal sense, possible. The following result considers regret relative to class K of static feedback controllers which satisfy the restrictive assumption that each K E К. stabilizes the time varying dynamics (A,, B:); see Appendix E for the formal algorithm, assumptions, and guarantees. We measure the regret against this class K:
T
T Ca( u KEK 1=1
Regrety (1C) = Σ um) t=1
inf
where (x. ut K. are the iterates arising under the control law 04 Kxt.
Theorem 4.1 (Sublinear regret against state-feedback) Under suitable stabilization assumption,
there exists computationally inefficient control algorithm which attains sublinear expected regret:
E E[Regrety S (dd2d.12) .T Kdgdy
Above, 22()) suppresses a universal constant and exponent base, both of which are made explicit in a formal theorem statement in Appendix E. The bound follows by running the EXP3 bandit algorithm on a discretization of the set IC (high probability regret can be obtained by instead using EXP3.P [8]) The guarantee in Theorem 4.1 is neither practical nor sharp; its sole purpose is to confirm the possibility of sublinear regret. Due to the bandit reduction and exponential size of the cover of K. C Rd.xxd, the algorithm is computationally inefficient and suffers nonparametric rate of regret [33]: e-regret requires T A(dimension)
One may wonder if one can do much better than this naive bandit reduction. For example, is there structure that can be leveraged? For LTV systems, we show that there is strong evidence to suggest that, at least from a computational standpoint, attaining polynomial regret (e.g. T- for a > independent of dimension) is computationally prohibitive.
Theorem 4.2. There exists a reduction from MAX-3SAT on m-clauses and n-literals to the problem of finding a feedb-fe controler which is within small constant factor of optimal for the cost Ei=1 Ca (x xx on a sequence of sequentially stable LTV systems and convex costs (A,, Bi, (t) with no disturbance (w; 0), with state dimension 1+1, input dimension 2, and horizon T (mm). Therefore, unless P NP, the latter cannot be solved in time polynomial in n [17].
A more precise statement, construction, and proof are given in Appendix F.4. Theorem 4.2 demon- strates that solving the offline optimization problem over state feedback controllers K to within constant precision is NP-Hard. In particular, this means that any sublinear regret algorithm which is proper and convergent, in the sense that ut = K, for some sequence Ke converges to a limit as T-x,, must be computationally inefficient. This is true even if the costs and dynamics are known in advance. Our result suggests it is computationally hard to obtain sublinear regret, but it does not rigorously imply it. For example, there may be more clever convex relaxations (other than DRC and DAC, which provably cannot work) that yield efficient and sublinear regret. Secondly, this lower bound does not rule out the possibility of an computationally inefficient algorithm which nevertheless attains polynomial regret.
5 Discussion and Future Work
This paper provided guarantees for and studied the limitations of sublinear additive regret in online control of unknown, linear time-varying (LTV) dynamical system.
Our setting was motivated by the fact that the first-order Taylor approximation (Jacobian linearization) of smooth, nonlinear systems about any smooth trajectory is LTV. One would therefore hope that low-regret guarantees against LTV systems may imply convergence to first-order stationary points of general nonlinear control objectives [34), which in turn may enjoy stability properties [45]. Making this connection rigorous poses several challenges. Among them, one would need to extend our low-regret guarantees against oblivious adversaries to hold against adaptive adversaries, the latter

---

modeling how nonlinear system dynamics evolve in response to the learner's 's control inputs. This may require parting from our current analysis, which leverages the independence between exploratory inputs and changes in system dynamics.
Because show that linear-in-7 regret is unavoidable for changing systems with large system variability, at least for the main convex policy parametrizations, it would be interesting to study our online setting under other measures of performance. In particular, the competive ratio, or the ratio of total algorithm cost to optimal cost in hindsight (as opposed to the difference between the two measured by regret) may yield a complementary set of tradeoffs, or lead to new and exciting principles for adaptive controller design. Does system variability play the same deciding roles in competive analysis as it does in regret? And, in either competitive or regret analyses, what is the correct measure of system variability (e.g. variability in which norm/geometty. or of which system parameters) which best captures sensitivity of online cost to system changes?
Acknowledgments
Elad Hazan and Edgar Minasyan have been supported in part by NSF grant #1704860. This work was done in part when Paula Gradu was at Google AI Princeton and Princeton University. Max Simchowitz is generously supported by an Open Philanthropy AI fellowship.
References
[1] Yasin Abbasi- Yadkori and Csaba Szepesvári. Regret bounds for the adaptive control of linear quadratic systems. In Proceedings of the 24th Annual Conference on Learning Theory, pages 1-26, 2011.
[2] Dmitry Adamskiy, Wouter M Koolen, Alexey Chernov, and Vladimir Vovk. A closer look at adaptive regret. The Journal of Machine Learning Research, 17(1):70--766, 2016.
[3] Naman Agarwal, Brian Bullins, Elad Hazan, Sham Kakade, and Karan Singh. Online control with adversarial disturbances. In International Conference on Machine Learning, pages 111- 119, 2019.
[4] Naman Agarwal, Elad Hazan, Anirudha Majumdar, and Karan Singh. regret minimization approach to iterative learning control. arXiv preprint arXiv:2102.1 13478, 2021.
[5] Nicholas M. Boffi Stephen Tu, and Jean-Jacques E. Slotine. Regret bounds for adaptive nonlinear control, 2020.
[6] Olivier Bousquet and Manfred K Warmuth. Tracking small set of experts by mixing past posteriors. Journal of Machine Learning Research, 3(Nov):363-39) 2002.
[7] Stephen Boyd, Stephen Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[8] Sébastien Bubeck and Nicolo Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. arXiv preprint arXiv: 124.551,24, 2012.
[9] Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[10] Alon Cohen, Tomer Koren, and Yishay Mansour. Learning linear-quadratic regulators efficiently with only VT regret. In International Conference on Machine Learning, pages 1300-1309, 2019.
[11] Amit Danicly, Alon Gonen, and Shai Shalev-Shward Strongly adaptive online learning. In Francis Bach and David Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 1405-1411, Lille, France, 07-09 Jul 2015. PMLR.
[12] Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. Regret bounds for robust adaptive control of the linear quadratic regulator. Advances Neural Information Processing Systems, pages 4188-4197, 2018.
10

---

[13] Sarah Dean and Benjamin Recht. Certainty equivalent perception prrception-based control. arXiv preprint arXiv:2008. 12332, 2020.
[14] Eyal Even-Dar, Sham M Kakade, and Yishay Mansour. Experts in a markov decision process. In Advances in neural information processing systems, pages 401-408, 2005.
[15] Maryam Fazel, Rong Ge, Sham Kakade, and Mehran Mesbahi. Global convergence of policy gradient methods for the linear quadratic regulator. In International Conference on Machine Learning, pages 1467-1476, 2018.
[16] Paula Gradu, Elad Hazan, and Edgar Minasyan. Adaptive regret for control of time-varying dynamics. arXiv preprint arXiv:2007.04393 2020.
[17] Johan Hästad. Some optimal inapproximability results. Journal of the ACM (JACM), 48(4):7988 859, 2001.
[18] Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Opti- mization, 2(3-4):157 325, 2016.
[19] Elad Hazan. Introduction to online convex optimization, 2019.
[20] Elad Hazan, Sham Kakade, and Karan Singh. The nonstochastic control problem. In Proceedings of the 31st International Conference Algorithmic Learning Theory, pages 408-421, PMLR, 2020.
[21] Elad Hazan and Comandur Seshadhri. Efficient learning algorithms for changing environments. In Proceedings of the 26th annual international conference on machine learning, pages 393-400.
ACM, 2009.
[22] Mark Herbster and Manfred K Warmuth. Tracking the best expert. Machine learning, 32(2):151-
178, 1998.
[23] Sham Kakade, Akshay Krishnamurthy, Kendall Lowrey, Motoya Ohnishi, and Wen Sun. Infor- mation theoretic regret bounds for online nonlinear control. arXiv preprint arXiv:2006. 12466. 2020.
[24] Sahin Lale, Kamyar Azizzadenesheli, Babak Hassibi, and Anima Anandkumar. Logarithmic regret bound in partially observable linear dynamical systems, 2020.
[25] Sahin Lale, Kamyar Azizzadenesheli, Babak Hassibi, and Anima Anandkumar. Regret mini- mization in partially observable linear quadratic control, 2020.
[26] Horia Mania, Stephen Tu, and Benjamin Recht. Certainty equivalence efficient for linear quadratic control. In Advances in Neural Information Processing Systems, pages 10154-10164, 2019.
[27] Zakaria Mhammedi, Dylan J Foster, Max Simchowitz, Dipendra Misra, Wen Sun, Akshay Krishnamurthy, Alexander Rakhlin, and John Langford. Learning the linear quadratic regulator from nonlinear observations. arXiv preprint arXiv:2010.03799, 2020.
[28) Richard H Middleton and Graham Goodwin. Adaptive control of time-varying linear systems. IEEE Transactions on Automatic Control, 33(2):150-1555 1988.
[29] Kevin L Moore. Iterative learning control for deterministic systems. Springer Science & Business Media, 2012.
[30] Samet Oymak and Necmiye Ozay. Non-asymptotic identification of Iti systems from a single trajectory. In 2019 American control conference (ACC), pages 5665-5661. IEEE, 2019.
[31] Neemiye Oray, Constantino Lagoa, and Mario Sznaier. Set membership identification of switched linear systems with known number of subsystems. Automatica, 51:180-191, 2015.
[32] Guannan Qu, Yuanyuan Shi, Sahin Lale, Anima Anandkumar, and Adam Wierman. Stable online control of Itv systems stable online control of linear time-varying systems. arXiv preprint vrXiv:2104.1411 1021.
11

---

[33] Alexander Rakhlin and Karthik Sridharan. Online non con-paametric regression. In Conference on Learning Theory, pages 1232-1264. PMLR, 2014.
[34] Vincent Roulet, Siddhartha Srinivasa, Dmitriy Drusvyatskiy, and Zaid Harchaoui. Iterative linearized control: stable algorithms and complexity guarantees. In International Conference on Machine Learning, pages 5518-550 5527. PMLR, 2019.
[35] Tuhin Sarkar, Alexander Rakhlin, and Munther Dahleh. Nonparametric system identification of stochastic switched linear systems. In 2019 IEEE 58th Conference Decision and Control (CDC), pages 3623-3628. IEEE, 2019.
[36] Tuhin Sarkar, Alexander Rakhlin, and Munther A Dahleh. Finite-time system identification for partially observed Iti systems of unknown order. arXiv preprint arXiv:1902.01848, 2019.
[37] Max Simchowitz. Making non-stochastic control (almost) as easy as stochastic, 2020.
[38] Max Simchowitz and Dylan Foster. Naive exploration optimal for online lqr. International Conference Machine Learning, pages 3937-8948 PMLR, 2020.
[39] Max Simchowitz, Karan Singh, and Elad Hazan. Improper learning for non-stochastic control, 2020.
[40] Y. Tassa, T. Erez, and E. Todorov. Synthesis and stabilization of complex behaviors through online trajectory optimization. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 4906-4913, 2012.
[41] Emanuel Todorov and Weiwei Li. A generalized iterative lęg method for locally-optimal feedback control of constrained nonlinear stochastic systems. In Proceedings of the 2005, American Control Conference, 2005., pages 300-306. IEEE, 2005.
[42] Kostas S Tsakalis and Petros A Ioannou. Linear time-varying systems: control and adaptation. Prentice- Hall, Inc., 1993.
[43] Roman Vershynin. #ligh-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018
[44] Yuh-Shyang Wang, Nikolai Matni, and John C Doyle. A system-level approach controller synthesis. IEEE Transactions on Automatic Control, 64(10):4079 4093, 2019.
[45] Tyler Westenbroek, Max Simehowitz, Michael I Jordan, and S Shankar Sastry. On the stability of nonlinear receding horizon control: a geometric perspective. arXiv preprint arXiv:2 /5010, 2021.
[46] Dante Youla, Hamid Jabr, and Jr Bongiorno. Modern wiener-hopf design of optimal controllers- part i:: The multivariable case. IEEE Transactions on Automatic Control, 21(3):319-33,, 1976.
[47] Lijun Zhang, Tie- Yan Liu, and Hui-Hua Zhou. Adaptive regret of convex and smooth functions. arXiv preprint arXiv: 1904. / 1681, 2019.
[48] Lijun Zhang, Tianbao Yang, rong jin, and Zhi-Hua Zhou. Dynamic regret of strongly adaptive methods. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 5882-5891. PMLR, 10-15 Jul 2018
[49] Kemin Zhou, John Comstock Doyle, Keith Glover, et Robust and optimal control, volume 40. Prentice hall New Jersey, 1996.
12


Reviews:
[{"review_id": "lIM2o0FrXIY", "reviewer": "Reviewer_vpa4", "summary": "This paper studies online control in linear time-varying (LTV) systems where the dynamics are unknown. The performance metric is the adaptive regret against three common classes of policies. When the benchmark policy class is DRC/DAC, the authors show a lower bound of the adaptive regret of any online controllers that grows linearly with respect to the length of horizon. This negative result demonstrate that the unknown LTV setting is qualitatively harder than either unknown linear time invariant (LTI) or known LTV, where sublinear regrets are achievable. On the other hand, they also propose an online control algorithm whose adaptive regret matches the lower bound in the same setting.  When the benchmark policy class is static feedback controllers, they show that although sublinear regret is achievable under some restrictive assumptions, planning over this policy class is computational inefficient in general.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "This paper makes original and significant contribution to the online control literature. The problem setting under consideration is very important. As the authors discussed in the introduction section, since many positive results on adaptive regret have come out in either unknown linear time invariant (LTI) or known LTV settings, it is natural to ask whether these results extend to the unknown LTV setting, which is more common in practice. A negative lower bound result in this setting helps to demonstrate the hardness of this problem, and prompts us consider other performance metrics (e.g. competitive ratio) as discussed in Section 5. A limitation is that Assumption 1 and 2 seem to be restrictive. Although Appendix A.2 says the results still hold if a nominal stabilizing controller is known, it is unclear why such controller must exist and how to find it.\n\nThe paper is well-organized and written clearly. All claims are supported by theoretical results, and the assumptions are stated clearly. Although I did not check the proof in detail, the results look technically sound to me.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. I did not see any potential negative societal impact of this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "J-N-B39KQjt", "reviewer": "Reviewer_kAKa", "summary": "The paper studies RL policies for linear time-varying systems. ", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Most of the points discussed in the first round of reviewing are not addressed in the rebuttal. Further, the explanations in the rebuttal together with the antagonistic responses of the authors show that the manuscript suffers from serious presentation issues.\n___________________________________________________________________\nI think that the work is in an early stage of preparation and so cannot be recommended for publication. In general, connections to relevant literature and where this work stands in a bigger picture is missing, presentation is hard to read and harder to grasp for an expected reader, and motivations of the work and the directions along which it can be helpful are not clear.\n\nTo the reader, the technical parts look isolated and different pieces do not connect well to deliver the potential messages. The authors rely too much on the supplementary file so that the paper lost its self-sufficiency. Accordingly, the language is too strong and super confident while the writing suffers from a sub-standard presentation by leaving the burden of decoding multiple claims in every line and justifying them to the reader. I suggest rewriting major portions and providing more concise presentation, using google scholar to find more-relevant literature and clearly and comprehensively discussing the connections. Unfortunately, the impression of the reader from the current version is that the manuscript focuses on technicalities and details of a problem, while presenting as if it is providing deep conceptual understandings of an extensive area.\n\nFrom a technical point of view, the results are expected, e.g., if the environment keeps changing, then clearly it is not learnable! The adaptive regret that the manuscript relies on in several places is not sufficiently controlled, and the assumptions appear to be so rich for the presented results. I think it is good that some classes of policies are compared, but to provide a nice tutorial to the reader, the current presentation is too compact and needs more intuitions and insights. The premises are not clear not to be very restrictive. E.g., in (2.1), the benchmark has general notation but later in the manuscript, it depends on the interval under study. It is said that the disturbance is revealed to the learner, which is a consequential assumption. \n\nMost of the discussions on pages 6, 7, 9 are in a different context than that of the problem under study on pages 1-5.\n\nFinally, there are multiple typos and frequent unclear sentences that I refrain mentioning here due to abundance.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "FbAwkGIrwl", "reviewer": "Reviewer_w6Bk", "summary": "This paper studies the online control of unknown Linear Time-Varying (LTV) systems in the nonstochastic control setting. They present in-depth theoretical results given the aforementioned problem setting that shows the following (in the order presented in the paper):\n1. Statement that the regret for the DAC/DRC policies cannot scale sub linearly in the time horizon (lower bound)\n2. An algorithmic upper-bound for online prediction\n3. Applying (2) to the online control problem\n4.Theoretical analysis showing that sublinear regret is possible but in non-polynomial time (computationally inefficient) unless P=NP)", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Quality: \n+The authors provide a comprehensive yet concise literature survey, distinguishing the results by problem setting (i.e. LTV/LTI, known/unknown dynamics, nonstochastic/stochastic noise, full-state/partial-state observation) \n+ The authors provide in-depth theoretical results\n+ The authors are very clear on the assumptions made in their analysis\n- The paper could be improved to have simulation results similar to citation #16 (Adaptive regret for control of time-varying dynamics) though I understand that the main result is sufficient.\n- It would be helpful to note that citation #20 (The nonstochastic control problem) studies unknown time-invariant dynamics (to clarify the difference with the authors’ work)\n\n\nClarity:\n+ Overall, the paper is well written and organized (the flow is readable i.e. 1. Statement that the regret for the DAC/DRC policies cannot scale sub linearly in the time horizon (lower bound) -> 2. Proposing algorithmic upper-bound for online prediction -> 3.Applying this algorithm to the online control problem -> 4.Theoretical analysis showing that sublinear regret is possible but in non-polynomial time (computationally inefficient) unless P=NP)\n+ They provide very detailed theoretical analysis\n\nOriginality:\n+ After a brief search, it does appear that they are the first to look at the setting: Unknown LTV system dynamics in the non stochastic control setting. \n+ The results of studying and comparing the three classes of the controllers are novel, fresh, and interesting. The reviewer also gains new insights about the three classes of controllers. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No issues were noted. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9 hours"}, "extra_text": {}}, {"review_id": "D-a898m8mBV", "reviewer": "Reviewer_xwEp", "summary": "This paper studies LTV systems control, which is a very challenging problem in my opinion. A set of interesting results have been obtained, including the non-equivalence between different control classes, and algorithms with adaptive regret bounds against different controller classes. Computational complexity in achieving sublinear regret against state-feedback controller has also been discussed. \n\nIn general, I think this paper makes interesting contributions. However, I have some reservations on the notion of \"adaptive regret\". Further, I find some places in the presentation that need more discussions and clarifications. \n\nI will be happy to revise the score after rebuttal if these points are clarified. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "On adaptive regret:\n\n- In (2.1), the algorithm $\\mathcal{A}$ is not allowed to depend on interval I, correct?\n- In the second term in (2.1), the $u_t^\\pi$ and $x_t^\\pi$ is obtained by applying $\\pi$ from the very beginning t=0, although the summation in (2.1) is only on the interval I? \n- Why in the benchmark, one needs to consider a policy class? Why can’t we compare to the optimal offline solution when everything is known in hindsight?\n- Also, in the second term in (2.1), the policy $\\pi$ appears to be time-invariant, i.e. the policy parameters $M^{[i]}$ is not allowed to depend on the time instances  $t \\in I$, is this correct? If so, if one only cares about $I = [T]$, the entire horizon, then comparing against a static, time-invariant policy doesn’t seem to make sense. \n- I find it not straightforward to understand adaptive regret. Can a low adaptive regret guarantee stability, i.e. the state size does not blow up as T grows? \n\nAssumptions: I find the open-loop stable assumption 1 to be strong. One of the basic (and oftentimes challenging) tasks in control is stabilization, yet this is put as an assumption. More discussions are needed. \n\nResults: I find Theorem 2.1 to be very interesting. Is there any intuition about this result? Having more discussions will be highly helpful. \n\nThe control algorithm used in Algorithm 2 is DRC-OGD, but very few details are provided in the main text. I suggest adding more details here in the main text, e.g. what the algorithm is based on, and what is its guarantee for known systems. One question is does the control algorithm has to be DRC-OGD, or any algorithm that satisfies a certain regret guarantee for knonw systems will work? \n\nThm 4.1: under a suitable stabilization assumption? What is the meaning? \n\nLine 313: What is the “nonparametric rate of regret” in the paragraph after Thm 4.1?\n\nI am not sure what’s the point Thm 4.2 is trying to make. The paragraph before Thm 4.2 suggests the purpose of Thm 4.2 is to show the computational intractability in Thm 4.1 may be hard to avoid. But Thm 4.2 only shows the NP-hardness of finding the optimal state feedback control $K$. If I understand correctly, if one tries to compare against the best state feedback control, but the strategy is not limited to searching over a state feedback control, but search over some larger controller class instead, maybe it is still possible to achieve computational efficiency and sublinear regret? \n\nIn the paragraph after Thm 4.2, it says “…there may be more clever convex relaxations (other than DRC and DAC, which provably cannot work)…” I guess the reason that DRC and DAC would not is due to Thm 2.1, if I understand correctly? \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "More discussions on the notion of adaptive regret should be included, including its limitations. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Three of the four reviews were quite positive.  There was one negative review, and I think the authors response was adequate to address concerns raised.
Decision: Accept (Poster)