Optimal Dynamic Regret in LQR Control
Authors: Dheeraj Baby
Yu-Xiang Wang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Online linear regression
Dynamic regret
Individual sequence prediction
Online learning
Online non-paramteric regression
LQR control

Abstract: We consider the problem of nonstochastic control with a sequence of quadratic losses, i.e., LQR control. We provide an efficient online algorithm that achieves an optimal dynamic (policy) regret of $\tilde{O}(n^{1/3} \mathcal{TV}(M_{1:n}^{2/3}  \vee 1)$, where $\mathcal{TV}(M_{1:n})$ is the total variation of any oracle sequence of \emph{Disturbance Action} policies parameterized by $M_1,...,M_n$ --- chosen in hindsight to cater to unknown nonstationarity. The rate improves the best known rate of $\tilde{O}(\sqrt{n (\mathcal{TV}(M_{1:n})+1)} )$ for general convex losses and is information-theoretically optimal for LQR. Main technical components include the reduction of LQR to online linear regression with delayed feedback due to Foster & Simchowitz 2020, as well as a new \emph{proper} learning algorithm with an optimal $\tilde{O}(n^{1/3})$ dynamic regret on a family of "minibatched'' quadratic losses, which could be of independent interest.

Optimal Dynamic Regret in LQR Control
Dheeraj Baby Department of Computer Science UC Santa Barbara dheera jeccsb.rjjuebeee..
Yu-Xiang Wang Department Computer Science UC Santa Barbara yuxiangwecs. ucsb edu
Abstract
We consider the problem of nonstochastic control with sequence of quadratic losses, i.e., LQR control. We provide an efficient online algorithm that achieves an optimal dynamic (policy) regret of Ommxxfn' (M.. 11), where TV(M..)) is the total variation of any oracle sequence of Disturbance Action policies parameterized by MI..., Ma - chosen hindsight to cater to unknown nonstationarity. The rate improves the best known rate of Ó (TVV((T((M + 1)) for general convex losses [Zhao et al., 2022] and prove that it is information- theoretically optimal for LQR. Main technical components include the reduction of LQR to online linear regression with delayed feedback due to Foster and Sim- chowitz [2020], well as proper learning algorithm with optimal On 1/3) dynamic regret on a family of "minibatched" quadratic losses, which could be independent interest.
Introduction
This paper studies the linear quadratic regulator (LQR) control problem which specific instanti- ation of the more general RL framework where the evolution of states follows predefined linear dynamics. each round & E [m]] : {1, .., n). the agent is at state H, E IRd=, Based on the state, the agent select a control input u, Rd.. The next state evolves according to the law:
T++1 Ar, Bu, + Wt:
where and B system matrices known the agent. we R2 is disturbance term that be selected by a potentially adaptive adversary. We assume that || This disturbance term reflects the perturbation from the ideal linear state transition arising due environmental factors that could be difficult to model. The loss suffered by playing the control u at state æ is given by ((x, u) : x R2 x R, where R2 R. & that are apriori fixed and known.
Recently there has been a surge interest in viewing this classical LQR problem under the lens of online learning [Hazan, 2016]. The work of Agarwal al. [2019] places regret of the agent against set of benchmark policies as the central notion to evaluate learner's performance. Following Agarwal et al. [2019], Foster and Simchowitz [2020] we adopt the class of disturbance action policies (DAP) as our benchmark class:
Definition 1. (Disturbance action policies, [Foster and Sinchowitz, 2020]). Let M (M ym denote a sequence of matrices Ml E Xdo, We define the corresponding disturbance action policies (DAP) M as:
M (xx)
Ksott - 9th (Wia-1),
(1)
where gM M (W14-1) Σm Mi and Koc in (4). We are interested in DAPs for which the sequence belongs to the set:
M(m, R, 7) == (M (M || Ry
(2)
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

where m, R. and y are algorithm parameters.
This class known to be sufficiently rich to approximate many linear controllers. policy takes in the past history and current state as input and produces a control signal output. Let's denote M == (M1,-.., Mn) to a sequence of DAP policies such that at time I, the control signal is selected using the policy parameterized by M, (see (I) We denote zi z:M1 i to be the state reached at round by playing the sequence of policies defined by parameters M1--1 in the past. Similarly ut Ma is used to denote the control signal produced by the policy Mc. The universal dynamic regret of the learner against the policy sequence Min is defined as:
R RMM = Σ la (
,1 MMn );
where (aia Ut all) denotes the state and control signal of the learner at round I. Note that the policy sequence Min can be any valid sequence of DAP polices. The main focus of this paper is to design algorithms that can control the dynamic regret against a sequence of reference policies of the time horizon n and the a path variation of the DAP parameters of the comparator Min. We remark that the comparator polices Min. can be chosen in hindsight and potentially unknown to the learner.
function
Whenever M = (M,..., M) for fixed parameter M, we recover the notion of static regret. How- ever the notion of static regret not befitting for non-stationary environments. For best performance under non-stationary environment, controller may have to choose different policies at different time steps that can counter-act the disturbances and guide the dynamics properly. Hence, we aim to control the dynamic regret which allows us to be competent against a sequence of potentially time-varying polices chosen in hindsight. We remark that our algorithm automatically adapts to the level of non-stationarity in the hindsight sequence of policies.
Next, we take digression and discuss a desirable property for the design of algorithms for LQR control.
Proper learning in LQR control. Proper learning is an online learning paradigm where the decisions of the learner are required to obey some user specified safety constraints. On the other hand, improper learning framework allows the learner disregard such safety constraints. The paradigm of improper learning may not be attractive certain applications where safety is a paramount concern. Improper algorithms can possibly take the system through trajectories that deemed to be risky. It is desirable to avoid such behaviours in physical systems such as self driving cars, control of medical ventilators, robotic control [Levine al., 2016] and cooling data centers [Cohen et al., 2018]. When translated into the LQR control problem, we regard the benchmark pool M(m, R, 7) defined in Eq. as a space of safe policies. So avoid risky behaviours, at any round, the learner plays a control signal that is recommended by a DAP policy in the class M(m, R).
Below contributions:
We develop an optimal universal dynamic regret minimization algorithm for the general mini-batch linear regression problem (see Theorem 5).
Applying the reduction of Foster and Simchowitz [2020] from LQR problem online linear regression, the above result lends itself to an algorithm for controlling the dynamic regret of the LQR problem (3) to be Ô* (n 1/3 (TV
where TV denotes the total variation incurred by the sequence of DAP policy parameters hindsight (see Corollary 10). O' hides the dependencies in dimensions and system parameters.
We show that the aforementioned dynamic regret guarantee is minimax optimal modulo dimensions and factors of log (see Theorem 11).
The resulting algorithm is also strongly adaptive, in the sense that the static regret against DAP policy in any local time window O" Ologg)..
Notes on novelty and impact. As discussed before, the reduction of Foster and Simchowitz [2020] casts LQR problem to an instance of proper online linear regression. In the context of regression, proper learning means that the decisions of the learner belongs to a user specified convex domain. The main challenge in developing aforementioned contributions rests on the design of an optimal

---

universal dynamic regret minimization algorithm for online linear regression under the setting of proper learning. We are not aware of any such algorithms in the literature to-date and the problem remains open. However, there exists an improper algorithm from Baby and Wang [2021] for controlling the desired dynamic regret. Given this fact, the design of our algorithm facilitated by coming up with new black-box reductions (see Section 4) that can convert an improper algorithm for statiorai online linear regression to a proper one. There are improper to proper black-box reduction schemes given in the influential work of Cutkosky and Orabona [2018]. However, they are developed to support general convex or strongly convex (see Definition 4) losses. The linear regression losses arising in our setting exp-concave (see Definition 3) which enjoy strong curvature only in the direction of the gradients as opposed to uniformly curved strongly convex losses. Hence the reduction scheme of Cutkosky and Orabona [2018] is inadequate to provide fast regret rates in our setting. In contrast, we develop novel reduction schemes that carefully take the non-uniform curvature of the linear regression losses into account so to facilitate fast dynamic regret rates (see Section 4.2). The construction of this new reduction scheme requires non-trivial adaptation of the ideas in Cutkosky and Orabona [2018]. We remark that the algorithm
conttrll developed in Section can be impactful in general online learning literature. That the non-stationary LQR problem can be optimally solved using ProDR.control is a testament this fact. Further our algorithm is out-of-the-box applicable to more general settings such as non-stationary multi-task linear regression, which is beyond the current scope. The lower bound we provide in Theorem 11 is also applicable to the more general problem of online non cor-pmamettric regression against a Besov space / class of Total Variation bounded functions [Rakhlin and Sridharan, 2014] (see Section for more details). The main contribution here is that we provide new lower bounding strategy that characterizes the correct rate wrt both n and the radius (or path-variation of the non-parametric function class. This is in contrast with Rakhlin and Sridharan [2014] who establish the correct dependency only wrt Attaining the correct dependencies wrt both n and the radius/ path- variation is imperative in implying dynamic regret lower bound for the LQR problem.
The rest of the paper is organized as follows. In Section we cover the necessary preliminaries on LQR control. Section 3 discusses relevant literature. In Section 4, we develop a proper algorithm for non non-stationary online linear regression. Section 5, we apply the results of Section 4 to provide an algorithm for non-sationary LQR control and prove its minimax optimality. This is followed by conclusion and open problems Section 6. We provide concise overview of the results from Baby and Wang [2022] in Appendix A which we build upon. All proofs are given in Appendix B.
2 Preliminaries
We start with brief overview of the LQQ problem for the sake of completeness. The material of this section closely follows Foster and Simchowitz. [2020]. The definitions and notations introduced in this section will be used throughout the paper.
A linear control law is given by said to be stabilizing if p(A BK)= < where p(A BK) is the maximum of the absolute values of the eigenvalues of A - BK. We assume that there exists a stabilizing controller for the system (A, B). For such systems, there exists a unique matrix Poo which is the solution to the equation:
Kr, for a controller K E Rddxxd, A linear controller K is
P= P R2 PB BBP PA.
The solution Poo is called the infinite horizon Lyapunov matrix. It is an intrinsic property of the system (A, B) and characterizes the optimal infinite horizon cost for control in the absence of noise [Bertsekas, 2005]. We also define the optimal state feedback controller
K = (R,, + Po -B P
(4)
the steady state covariance matrix:
Ex R., + BT B.
and the closed loop dynamics matrix: Ad, := BK
Foster and Simchowitz, [2020] shows that the problem of controlling the regret in the LQR problem can be reduced to online linear regression problem with delays. Specifically we have the following fundamental result due to Foster and Simchowitz [2020].
3

---

Proposition 2. Suppose the learner plays policy of the form ne, (2) K - (W1s-1). Let
the comparator policies take the form [t(z)= = x + q Mr (w1=-11 for a sequence of matrices Min chosen in hindsight. Then the dynamic regret against the policies = (TII.... ,n) satisfies:
(T(()) S 00() Σ Ac(M,'s writh) Ac(Me, wrath),
where the parameters involved in the inequality are defined as below: (,, writhh = Ma (wn=t-1) 1) - 2oo, (wees BBsss 4ooth (WE:+++) = -ii+t1 E B" (Ad,oa))-1-1 Poo 20 h ==
2(1-%zo) 1og(n22, (. ). 7o0 ==
- -110-P+00 -1/2R, 2 10 Kx == |P llopl Pro 1/2
PT Napp
B. == m1 Amii RR), (rx))- V. = max (1,1|A|lop Bapp, || RR lapp | Rallop]. r.
max(1, 10
Observe that the losses (M,, Wra+h) == 1 (w1a-1) (woe
Ar wrats)
||% qMd (W1=-1) E/12 fooc ( (was+h)l2 are essentially linear regression losses. The quantity 2 q²d (w11=1) is a linear map from the matrix sequence M to RRd However, there is one caveat in that the bias vector at round L given by Σ1/2 looch (Wes++) is only available at round ++ = + Olog This issue of delayed feedback can be directly handled using the delayed to non-delayed online learning reduction from Joulani et al. [2013].
3 Related work
In this section, review recent progress at the intersection of control and online convex optimization (OCO) that are most relevant to our work.
Online control. The idea of using tools from OCO for general control problem was proposed in Agarwal et al. [2019]. They place the notion of regret against the class of DAP policies as the central performance measure. The DAP class is also shown to be sufficiently rich to approximate a wide class of linear feedbace controllers. Under general convex losses, they propose a reduction to OCO with memory [Merhav et al., 2000, Anava et al., 2015] and derives O(vr) regret when the system matrices (A, B) are known. For the case of unknown system, Hazan et al. [2020] provides (nn//3) regret via system identification techniques. When the losses are strongly convex and sub-quadratic, Simchowitz [2020] strengthens these results to attain Ö(z) regret for known systems and Ö (vn) when the system is unknown. For partially observable systems strong regret guarantees are provided in Simchowitz et al. [2020]. Luo et al. [2022] provides an 3/53 dynamic regret bound for the case when the system matrices (A,, B.) can change over time. Their results are incompatible to ours in that they consider unknown dynamics, stochastic disturbances and the dynamic regret compete with controllers that are pointwise optimal (restricted dynamic regret), while we assume known dynamics, adversarial disturbances and compete with an arbitrary sequence of controllers (i.e., universal dynamic regret).
Next, we clarify the differences from other existing work on the nonstochastic control problems [Gradu et al., 2020a,b, Cassel and Koren, 2020, Zhang et al., 2021b, Shi et al., 2020, Goel and Hassibi, 2021, Zhao et al., 2022].
Gradu al. [2020a], Cassel and Koren [2020] studied online control in the partially observed cases with bandit feedback, but did not consider the problem of non-stationarity with dynamic regret. Gradu al. [2020b]. Zhang al. [2021b] studied the adaptive regret in nonstochastic control problems, which is an alternative metric to capture the performance of the learning controller in non-stationary environments. Our algorithm uses a reduction to adaptive regret too, but is highly nontrivial to show that one can tweak adaptive regret minimizing algorithms into ones that achieve optimal dynamic regret. Moreover, our algorithm the first that achieves logarithmic adaptive regret for nonstochastic LQR control problems too. In contrast, Gradu et al. [2020b], Zhang et al. [2021b] focused on the slower adaptive regret in the general convex loss cases.
To the best of our knowledge, Goel and Hassibi [2021] and Zhao et al. [2022] are the only existing work that considered dynamic regret in non-stochastic control.
Goel and Hassibi [2021] used tools from Hos control and derived controller with exact minimax optimal dynamic regret against an oracle controller that sees the whole sequence of disturbances

---

and chooses an optimal sequence of control actions. But the optimal dynamic regret against the sequence of control actions given by the unrealizable oracle controller linear in in general (see an explicit lower bound from Goel and Hassibi [2020]). It is unclear whether this oracle controller can be realized by a sequence of time-varying DAP controllers. If so, then our results would imply regret bound against the optimal sequence of control actions too. Comparing to the exact minimax regret of the ox style controller, our regret bound would adapt to each problem instance, and is sublinear whenever the approximating sequence of DAP controllers has sublinear total variation.
Zhao et al. [2022] studied the universal dynamic (policy) regret problem similar to ours, but works for a broader family convex loss functions. Their regret bound O O(vn(1+ + Cx)) is optimal for the convex loss family. Our results show that the optimal regret improves to O(n-/3 V 1) when specializing to the LQR problem where the losses are quadratic. On the technical level, Zhao et al. [2022] used reduction to the dynamic regret of OCO with memory, while reduced to the dynamic regret of OCO with delayed feedback.
Dynamic regret minimization in online learning. There is rich body of literature on dynamic regret (5). minimization. As discussed in Section 2, the non-staionary LQR problem can be reduced to an instance of linear regression losses which are exp-concave on compact domains. There is a recent line of research [Baby and Wang, 2021, 2022] that provides optimal universal dynamic regret rates under exp-concave losses. However, the algorithm of Baby and Wang [2021] is improper, in the sense that the iterates of the learner can lie outside the feasibility set. The work of Baby and
Wang [2022] ameliorates this issue to some extend by providing proper algorithms for the particular case of Lo constrained (box) decisions sets. The DAP policy space in Definition 1 is indeed not an Lox ball. We note that if improper learning is allowed in the LQR problem, one run the algorithms of Baby and Wang [2021, 2022] to attain optimal dynamic regret rates. The proper learning algorithms such Zinkevich [2003], Zhang et al. [2018a]] Cutkosky [2020], Jacobsen and Cutkosky [2022] control dynamic regret for general convex losses. However, they are not adequate to optimally minimize dynamic regret under curved losses that are strongly convex or exp-concave. The notion of restrictive dynamic regret introduced in Besbes et al. [2015] competes with a sequence of minimizers of the losses. This notion of regret can sometimes be overly pessimistic
noted in Zhang et al. [201 8a]. There is a series of work in the direction of dynamic regret minimization in OCO such as Jadbabaie et al. [2015]. Yang et al. [2016]. Mokhtari et al. [2016]. Chen al. [2018], Zhang et al. [201 8b). Goel and Wierman [2019]. Baby and Wang [2019]. Zhao et al. [2020]. Zhao and Zhang [2021]. Zhao et al. [2022], Chang and Shahrampour [2021], Baby and Wang [2020], Baby et al. [202]] lb, Chatterjee and Goswami [2022], Baby et al. a). Raj et al. [2020]. However, to the best of our knowledge none of these works are known to attain the optimal universal dynamic regret rate for the setting of online linear regression.
Dynamic regret for OCO Dynamic (Policy) regret for Control. We emphasize that the regret in (3) is dynamic policy regret [Anava et al., 2015, Zhao et al., 2022]. The states visited by the reference policy is counterfactual and is different from that of the learner's trajectory which observe. This is very different from the standard OCO framework where the state of both the learner and adversary are same. So bounding the policy regret seems qualitatively harder than bounding the regret in an OCO setting. Nevertheless, for the LQR problem, the fact that there exists reduction [Foster and Simchowitz, 2020] from the problem of controlling policy regret to the problem of controlling the standard OCO regret is remarkable.
Strongly adaptive regret minimization. There is also a complementary body of literature strongly adaptive algorithms that focus on controlling the static regret in any local time window. For example, the algorithm of Daniely et al. [2015], Jun et al. [2017] can lead to Ō( /[T) static regret in any interval of C [r]] under convex losses. When the losses are exp-concave the algorithm of Hazan and Seshadhri [2007], Adamskiy et al. [2016], Zhang et al. [2021 [0] can lead to O(log n) static regret in any interval.
4 Non-stationary "mini-batch" Linear Regression
In view of Proposition 2, the losses of interest are linear regression type losses. So we take digression in this section and study the problem of controlling dynamic regret in a general linear regression setting.
5

---

4.1
Linear regression framework
Consider the following linear regression protocol.
At round f, nature reveals co-variate matrix A, E Rxxd
Learner plays 2, E D C Rd
Nature reveals the loss f((z) = -
Under the above regression framework, we are interested in controlling the universal dynamic regret against an arbitrary sequence of predictors u1,...;; Un E 'D (abbreviated as W1:n):
Ra (uim)))
- 1=1
(5)
Dynamic regret usually expressed as a function of n and path variational that captures the smoothness of the comparator sequence. We will focus on the path variational defined by:
1
TV(umm)
Σ
1lee Ue 1111-
Below are the list of assumptions made:
Assumption Let de Rd be the jth row vector of A,, We assume that ||a,, S for all & [n]
and E [p]. Further ||b | 5 a for all L.
Assumption 2. For any x E D, || and | R.
We refer this setting as mini-batch linear regression since the loss at round t can be written as sum of batch of quadratic losses: fz(2) Σ.= (z" az b,(
Terminology. For convex loss function f. we abuse the notation and take f to be sub-gradient of f at x. We denote >o {x Rd |ox R).
Linear regression losses belong broad family of convex loss functions called exp-concave losses: Definition 3. convex function is exp-concave in domain D if for all z, D have f(y) 2 f(x) + f(x)" - y) + (V (-
We refer the reaeder to Cesa-Binn Bianchi and Lugosi [2006] and Hazan et al. [2007] for more detailed expositions on exp-concavity.
The losses f((z) ||, - 112 are (2R) exp-concave if f(z) S R for all a E 'D (see Lemma 2.3 in Foster and Simchowitz [2020]).
Definition 4. convex function I is strongly convex wrt ||:1|2 norm in domain 'D if for all x, E we have f(y) 2 f(x) fz) y) - 11lx-y13 v1
We note that if the matrix A, is rank deficient, then the losses fz(2) cannot be strongly convex. Moving forward we do not impose any restrictive assumptions on the rank of A, As mentioned in Remark 12, the covariate matrix that arise in the reduction of the LQR problem linear regression is not in general full rank. So we target a solution that can handle general covariate matrices irrespective of their rank.
4.2 The Algorithm
Starting point of our algorithm design the work of Baby and Wang [2022]. They provide an algorithm that attains optimal dynamic regret when the losses exp-concave. However, their setting works only in a very restrictive setup where the decision set an Loc constrained box. Consequently. cannot directly apply their results to the linear regression problem of Section 4 whenever the decision set is a general convex set.
An online learner is termed proper if the decisions of the learner are guaranteed to lie within the feasibility set D. Otherwise it is called improper. A recent seminal work of Cutkosky and Orabona [2018] proposes neat reductions that can convert improper online learner to proper one, whenever

---

FroDR.control. Inputs Decision set D, G > O, surrogate algorithm A which ensures low dynamic regret under general exp-concave losses against any comparator sequence in some DD' S D. Here 'D' is compact and convex set. Note that such an algorithm A may produce iterates outside D. (See Theorem 5 for a specific choice of ...)
1. At round E, receive wy from A.
2. Receive co-variate matrix A, == [at, [t,,l....... "...,!'.,,,..p'''
Ct.pl"
3. Play Wh E argmin max;= 10, we)l
4. Let fx(w)= = (w) + G. (w)), where fc(w) A| - b,112 and S:(w) mingeD max,
w)
5. Send (ww) to A.
Figure 1: ProDRlcontrol: An algorithm for non-stationary and proper linear regression.
the losses are convex. Following this line of research, we can aim to convert the algorithm of Baby and Wang [2022] that works exclusively on box decision set to one that can support arbitrary convex decision sets by coming up with suitable reduction schemes. However, the specific reduction scheme proposed in Cutkosky and Orabona [2018] is inadequate to yield fast dynamic rates for exp-concave losses. Our algorithm TroDR.contrr (Fig.1, 1, Proper Dynamic Regret.comtrov is by-product of constructing new reduction schemes to circumvent the aforementioned problem for the case of linear regression losses. We expand upon these details below.
In ProDR. control. we maintain a surrogate algorithm A, which is chosen to be the algorithm of Baby and Wang [2022] that produces iterates Wy in an Lo norm ball (box), Doc, that encloses the actual decision set D. We take DD Doo as per the notations in Fig. Since Wt can be infeasible, we play ult obtained via special type of projection of wy onto 'D which is formulated as a min-max problem in Line 3 of 1ig. In Line 4, we construct surrogate losses & to be passed to the algorithm A. The surrogate loss penalises A for making predictions outside D. We will show (see Lemma 15 in Appendix) that the instantaneous regret satisfies fe fwi:) - fe(u,) ) S (e(w)) - & (ut), where u, E D is the comparator at round t. Thus the dynamic regret of the proper iterates wy wrt linear regression losses is upper bounded by the dynamic regret of the surrogate algorithm A on the losses & and box decision set.
The design of the min-max barrier S, is driven ensure exp-concavity of the surrogate losses (w() = f((w) + G Se(w.. We capture its intuition as follows. We start by observing that since V2 ((w) 2A7 Ar, the linear regression losses ft exhibits strong curvature along the row-space of A., denoted by row(A.). Further we have f(( = ft exhibits strong curvature along the direction of its gradient too. This is the fundamental reason behind the exp-concavity of f.. The min-max barrier S,(w) is designed such that its gradient is guaranteed lie in the row(A:) (see Lemma 16 in Appendix for a formal statement). So the overall gradient (w) also lies in the row( (A.). Since the function La already exhibits strong curvature along row(A), we conclude that the sum & (w) = fe(w) + G- Se(w) exhibits strong curvature along its gradient Vl,(w, This maintains the exp-concavity of the losses l, over Doo (see Lemma 17 in Appendix). Such curvature considerations along with the fact that (,(w) has to be sufficiently large to facilitate the instantaneous regret bound f(i)) fe(wz) (e(we) l, (u4) results in functional form for Se(w) displayed in 1.
by) E row(A,). So the loss
Consequently the fast dynamic regret rates derived in Baby and Wang [2022] becomes directly applicable. The reduction scheme used by Cutkosky and Orabona [2018] for producing proper iterates vi and their accompanying surrogate loss design E, also allows one to upper bound the regret wrt linear regression losses Se by the regret of the algorithm A wrt surrogate losses l,- However, the surrogate loss 4 they construct is not guaranteed to be exp-concave and consequently not amenable to fast dynamic regret rates.
4.3
Main Results
We have the following guarantee for contoli
7

---

Theorem 5. Let Ui: E D be any comparator sequence. In Fig.I, choose G such that sup wn ve (t)))(( ([ + w2) 26,lli S G. Let a be as in Assumption Let L be such 2|I ball2 +2222+222 S L for all t E [n]. Choose A as the algorithm from Baby and Wang [2022] (see Appendix A) with parameters y 2GaR////LL + v2L and min{ 16GoRt77 (/ and decision set (R). Under Assumptions 1 and 2, valid of assignment of G and L are 2px + 2a and 6(px + + respectively. Then the algorithm ProDR.control yields a dynamic regret rate of
that >
Σ f((()))) fe(u,) = (Tvna 1),
[=1
where (a V == (a.b.
Remark 6. In view of Proposition 10 in Baby and Wang [2021], the dynamic regret guarantee in Theorem 5 is optimal modulo dependencies in d and log Further the algorithm does not require apriori knowledge of the path length (V(um)).
Proof sketch for Theorem 5. First step is to show that fu( ((r)). This is accomplished by Lipschitzness type arguments. For any u E 'D, one observes that (z(2) (u). So the instantaneous regret of ProDR. ProDR.control, fa (wb:) - (we), ), is upper bounded by the instantaneous regret, (e(w,) (11 (u)) of the surrogate algorithm A. The crucial step is to show the exp-concavity of the losses & across Doo RR). For this, we prove that there is sub-gradient (,w) that is aligned with ot, for some j [p)- This observation followed by few algebraic manipulations (see proof of Lemma 17 in Appendix) allows us show the exp-concavity of over Da (it). Now the overall regret can be controlled if the surrogate algorithm A provides optimal dynamic regret under exp-concave losses and box decision sets, >0 (R). This is accomplished by choosing A as the algorithm in Baby and Wang [2022] which also strongly adaptive.
Since the surrogate algorithm A we used in Theorem 5 is strongly adaptive (see for eg. Appendix A), we also have the following performance guarantee in terms of adaptive regret:
Proposition 7. Consider the instantiation of ProDR.control in Theorem 5. Then for any time window
[a, b] C [m] we have that: Ei=a f(( inf El= fe(u) Ö(d-5 n).
Remark 8. Theorem 5 and Proposition 7 logether makes the algorithm ProDR. conttrll good candidate for performing proper online linear regression in -tatiiaay environments.
4.4 Linear regression with delayed feedback
In this section, we consider a linear regression protocol with feedback delayed by 7 time steps.
At round f, nature reveals a co-variate matrix A E RRxd
Learner plays 2, E D C Rd
Nature reveals the loss fc-r41 (2) b 112-
This delayed setting can be handled by the framework developed in Joulani et al. [2013]. Although these authors focus on bounding the regret as a function of time horizon n, the extension to dynamic regret bounds expressed in terms of both n and TV( can be handled traighh-foorwrdde in the analysis. We include the analysis in Appendix B for the sake of completeness. The entire algorithm is as shown in 2
We have the following regret guarantee for Algorithm ProDR.control.dee Theorem 9. Let It be the prediction of the algorithm in Fig. 2 at time t. Instantiating each ProDR, control instance by the parameter setting described in Theorem 5. Let T be the feedback delay. We have that
Σ fala,) f((u.) = Old 1/3 (V3 V r).
8

---

ProDR.control.deeine Inputs- delay
Maintain separate instances of ProDR.control (Fig.I). Enumerate them by
0, ".l,...,TT!.
At time
1. Update instance (L (6-1) 1) mod with loss ft-r.
Predict using instance (t (t-1) mod т.
Figure 2: ProDR.comtrol.delaedd. An instance of delayed to non-delayed reduction from Joulani et al. [2013]
Further for any interval (a, bj S [n]]:
Σ - 0d
Instantiation for the LQR Problem
In view of Proposition the LQR problem is reduced mini-batch linear regression problem with delayed feedback, where the delay is given by h = O(log n) in Proposition 2. In this section, we provide explicit form of the linear regression losses arising in the LQR problem and instantiate Algorithm ProDR.controd wontool. (Fig.2). First we need to define certain quantities:
For sequence of matrices (M define ( follows: Let M," be the Atth column of M
Let's define
M
E Red
_
and
flatten((M)9))))) =
R mdddd
E
For a sequence of DAP parameters Mi let (V = En= Em I -M,- ll2. We define deflatted the natural inverse operation of flatten. We have the following Corollary of Theorem and Proposition 2.
Corollary 10. Assume the notations in Fig.l and Section 2. Let Exc Uo be the spectral decomposition the positive semi definite (PSD) matrix E.go Bdd.xd.. Let the covariate matrix wi: @ Aot 1/2200 E (.Bduxmdaa xedud, where & denotes the Kronecker product. Let the bias vector b, = 1/22 Toon (Weeth)) Let the delay factor of ProDR.control.c delayed (Fig.2) be T h defined in Proposition and let the decision set given the ProDR. control instances in F be the DAP space defined in (2) Let 2 be the prediction at round I made by the ProDR. contr..corrol algorithm and let M = de deflatten(z)) At round t, we play the control signal ua alg (x+) Mrth (xx)) according to (1) There exists choice of input parameters (see Corollary in Appendix B) for the ProDR. control instances in Fig.2 such that
A₁ =
R(M1.0) = Σ
Exxtt (u - l(x, Min, Min)
E=1
mn de A dhe (T v1)).
=

---

where Mim is a sequence of DAP policies where each M, E M (eq.2)). Further the algorithm ProDR.control.dela.. also enjoys strongly adaptive regret guarantee for any interval [a, - [n]:
eaat u l(a;" ut O((md1d2)) log
for any fixed DAP policy M M.
The following theorem provides nearly matching lower bound.
Theorem 11. There exists an LQR system, a choice of the perturbations wa and a DAP policy class such that:
E|R(M = V1),
sup Min with (V.
where the expectation taken wrt randomness the strategies of the agent and adversary.
We refer the reader to Appendix B for a proof of the above theorem along with its connections to online non- con-pramettric regression framework of Rakhlin and Sridharan [2014].
Remark 12. The covariate matrix A₁ E Rd xmduda that arises in Corollary 10 is rank deficient whenever md2 1. In such cases, the linear regression losses f((w) in Fig.l cannot be strongly convex. So the proper universal dynamic regret minimizing algorithm for strongly convex losses from Baby and Wang [2022] inapplicable general except potentially for the particular setting of m dz 1. Moreover, in the setting of m = dz 1 a non-zero strong convexity parameter can exist only if the magnitude of the perturbations [we] are bounded away from zero which restrictive in its scope.
6 Conclusion and Future Work
In this paper. we proposed new algorithm for minimizing dynamic regret of the non-stationary linear regression problem. We applied this algorithm to obtain non- non-stationary LQR controller. The techniques developed this work can be of independent interest the broader literature of online learning. We defer the task of deriving similar dynamic regret rates for general strongly convex losses the LQR problem as future work.
As mentioned in Section 1, there has been recent surge of interest in applying tools from online learning develop non-stochastic controllers. The present work also falls under this umbrella. However, existing literature lacks experimental studies in this vein. It would be good direction to do thorough survey of the strengths and limitations of various online learning based controllers when deployed in practice.
Acknowledgements
The construction of the lower bound in Theorem 11 is due to early discussion with Daniel Loksh- tanov on a related problem. We also thank the anonymous reviewers for their detailed suggestions in improving the paper.
References
Dmitry Adamskiy, Wouter M. Koolen, Alexey Chernov, and Vladimir Vovk. A closer look at adaptive regret. Journal of Machine Learning Research, 2016.
Naman Agarwal, Brian Bullins, Elad Hazan, Sham Kakade, and Karan Singh. Online control with adversarial disturbances. In Proceedings of the 36th International Conference on Machine Learning, 2019.
Oren Anava, Elad Hazan, and Shie Mannor. Online learning for adversaries with memory: Price of past mistakes. In Advances in Neural Information Processing Systems, 2015.
Dheeraj Baby and Yu-Xiang Wang- Online forecasting of wwt---varraiiioouundedd sequences. In Neural Information Processing Systems (NeurIPS), 2019.
10

---

Dheeraj Baby and Yu-Xiang Wang. Adaptive online estimation of piecewise polynomial trends. Neural Information Processing Systems (NeurIPS), 2020.
Dheeraj Baby and Yu-Xiang Wang. Optimal dynamic regret in exp-coneave online learning. In COLT, 2021.
Dheeraj Baby and Yu-Xiang Wang. Optimal dynamic regret in proper online learning with strongly convex losses and beyond. AISTATS, 2022.
Dheeraj Baby, Hilaf Hasson, and Yuyang Wang. Dynamic regret for strongly adaptive methods and optimality of online kır. ArXiv, abs/2111.11155 2021a.
Dheeraj Baby, Xuandong Zhao, and Yu-Xiang Wang. An optimal reduction of tv-denoising to adaptive online learning. AISTATS, 2021b.
Dimitri P. Bertsekas. Dynamic Programming and Optimal Control. Athena Scientific, 3rd edition, 2005.
Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Operations research, 1227-1422,, 2015.
Asaf Cassel and Tomer Koren. Bandit linear control. In Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020.
Nicolo Cesa-Biame Bianchi and Gabor Lugosi. Prediction, Learning, and Games. Cambridge University
Press, New York, NY. USA, 2006. ISBN 0521841089.
Ting-Jui Chang and Shahin Shahrampour. On online optimization: Dynamic regret analysis of strongly convex and smooth problems. Proceedings of the AAAI Conference on Artificial Intelli- gence, 2021.
Sabyasachi Chatterjee and Subhajit Goswami. Spatially adaptive online prediction of piecewise regular functions. ArXiv, 11622003.6587,, 2022.
Xi Chen, Yining Wang, and Yu-Xiang Wang. Non-stationary stochastic optimization under lp. q-variation measures. 2018.
Alon Cohen, Avinatan Hassidim, Tomer Koren, Nevena Lazic, Y. Mansour, and Kunal Talwar. Online linear quadratic control. In ICMI,, 2018.
Ashok Cutkosky. Parameter free, dynamic, and arongly-adaptive online learning. In ICML, 2020.
Ashok Cutkosky and Francesco Orabona. Black-box reductions for parameter-free online learning in banach spaces. In COLT, 2018
Amit Daniely, Alon Gonen, and Shai Shaley-Shward Strongly adaptive online learning. In International Conference on Machine Learning, pages 1,05-1411,201
Ronald A. DeVore and George G. Lorentz. Constructive approximation. In Grundlehren der mathematischen Wissenschaften, 1993.
Dylan J. Foster and Max Simchowitz. Logarithmic regret for adversarial online control. In ICML, 2020.
Gautam Goel and Babak Hassibi. The power of linear controllers Iqr control. arXiv preprint arXiv:2002.02574, 2020.
Gautam Goel and Babak Hassibi. Regret-optimal estimation and control. Transactions of Automatic Control (TAC), 2021.
Gautam Goel and Adam Wierman. An online algorithm for smoothed regression and lqr control. In Proceedings of the Twenty-Second International Conference Artificial Intelligence and Statistics, 2019.
Paula Gradu, John Hallman, and Elad Hazan. Non-stochastic control with bandit feedback. In Advances in Neural Information Processing Systems, 2020a.

---

Paula Gradu, Elad Hazan, and Edgar Minasyan. Adaptive regret for control of time-varying dynamics. ArXiv, abs/2007.04393 2020b.
Elad Hazan. Introduction to online convex optimization. Foundations and Trends@ in Optimization, 2(3-4):157-325, 2016.
Elad Hazan and Comandur Seshadhri. Adaptive algorithms for online decision problems. In Electronic colloquium computational complexity (ECCC), volume 14, 2007.
Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69(2):169- 192, 2007.
Elad Hazan, Sham Kakade, and Karan Singh. The nonstochastic control problem. In Proceedings of the 31st International Conference Algorithmic Learning Theory, 2020.
Andrew Jacobsen and Ashok Cutkosky. Parameter-free mirror descent. COLT, 2022.
Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan. Online optimization: Competing with dynamic comparators. In Artificial Intelligence and Statistics, pages 398 406, 2015.
Pooria Joulani, András György, and Csaba Szepesvari. Online learning under delayed feedback. In ICML, 2013.
Kwang-Sung Jun, Francesco Orabona, Stephen Wright, and Rebecca Willett. Improved Strongly Adaptive Online Learning using Coin Betting. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, 2017.
Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel. End-to-end training of deep visuomotor policies. 2016.
Yuwei Luo, Varun Gupta, and Mladen Kolar. Dynamic regret minimization for control of non- stationary linear dynamical systems. Proc. ACM Meas. Anal. Comput. Syst., 2022.
N. Merhav, E. Ordentlich, G. Seroussi, and M.J. Weinberger. On sequential strategies for loss functions with memory. In 2000 IEEE International Symposium on Information Theory, 2000.
Aryan Mokhtari, Shahin Shahrampour, A. Jadbabaie, and Alejandro Ribeiro. Online optimization in dynamic environments: Improved regret rates for strongly convex problems. 2016 IEEE 55th Conference on Decision and Control (CDC), pages 7195-7201, 2016.
Anant Raj, Pierre Gaillard, and Christophe Saad. 0as/2011.069577 2020.
Non-stationary online regression. ArXiv,
Alexander Rakhlin and Karthik Sridharan. Online non- parametric regression. In Conference on Learning Theory, pages 1232-1264, 2014.
Guanya Shi, Yiheng Lin, Soon-Jo Chung, Yisong Yue, and Adam Wierman. Online optimization with memory and competitive control. In Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020.
Max Simchowitz. Making non-stochastic control (almost) easy stochastic. In Advances in Neural Information Processing Systems, 2020.
Max Simchowitz, Karan Singh, and Elad Hazan. Improper learning for non-stochastic control. In COLT, 2020.
Tianbao Yang, Lijun Zhang, Rong Jin, and Jinfeng Yi. Tracking slowly moving clairvoyant: optimal dynamic regret of online learning with true and noisy gradient. In International Conference on Machine Learning (ICML-16), pages 447- 2016.
Lijun Zhang, Shiyin Lu, and Zui-Hua Zhou. Adaptive online learning in dynamic environments. In Advances in Neural Information Processing Systems (NeurIPS-18), pages 1323-1333, 2018a.
12

---

Lijun Zhang, Tianbao Yang, Zhi-Hua Zhou, et al. Dynamic regret of strongly adaptive methods, In Interaational Conference on Machine Learning (ICML-18), pages 5877-5886, 2018b.
Lijun Zhang, G. Wang, Wei-Wei Tu, and Zhi-Hua Zhou. Dual adaptivity: A universal algorithm for minimizing the adaptive regret of convex functions. NewrIPS, 2021a.
Zhiyu Zhang, Ashok Cutkosky, and Ioannis Ch. Paschalidis. Strongly adaptive oco with memory. ArXiv, abs/2102.01623. 2021b.
Peng Zhao and Lijun Zhang. Improved analysis for dynamic regret of strongly convex and smooth functions. LADC, 2021.
Peng Zhao, Y. Zhang, I., Zhang, and Hui-Hua Zhou. Dynamic regret of convex and smooth functions. NeurlPS, 2020.
Peng Zhao, Yu-Xin XiaXiang Wang, and Zhi-Hua Zhou. Non-stationary online learning with memory and non-stochastic control. AISTATS, 2022.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In International Conference on Machine Learning (ICML-03), pages 928 2289936,400 2003.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We do not support general strongly convex losses mentioned in Section 6.
(c) Did you discuss any potential negative socictal impacts of your work? [N/A] Paper of theoretical nature.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as URL)? [N/A] Paper of theoretical nature.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'le 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
13

---

(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "r2zwHBgi0ps", "reviewer": "Reviewer_95P1", "summary": "This work studies LQR control problem w.r.t. the dynamic regret measure. The authors propose a ProDR algorithm that achieves an optimal $n^{1/3}$ regret, improving the existing best $n^{1/2}$ regret result. The main idea of their algorithm is to reduce the original LQR problem to an online linear regression problem and adopt a ProDR online linear regression algorithm with an $n^{1/3}$ regret. They further prove an $n^{1/3}$ regret lower bound to suggest the optimality of their algorithm. ", "questions": "- Can you highlight the main technical difficulties you have faced in applying the algorithms in Baby and Wang (2021) to the LQR setting? I briefly checked Baby and Wang (2021) (https://arxiv.org/pdf/2201.08905.pdf) and it seems that they have already discussed some reduction from the box constraints to the general convex decision sets in their Sec. 4.2. Thus, I am not sure whether your comment from line 228 to 229 are still applicable. ", "limitations": "The authors have discussed the limitations of their algorithms. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n+ The presentation is clear.\n+ The proof is technically sound. \n+ The relation between the proposed algorithm and existing baseline algorithms is well discussed.\n\nWeaknesses:\n\n- The importance of the derived result seems not important enough since it heavily depends on an existing algorithm from Baby and Wang (2021). I am not sure if the transferring framework (from LQR to online linear regression) is also a standard process or not. If so, it may further weaken the technical contribution of this work. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ex0ZfoXWxMx", "reviewer": "Reviewer_Eo6g", "summary": "The paper proposes an algorithm which attains an $\\tilde{O}(n^{1/3} \\mathcal{TV}(M_{1:n})$ dynamic regret in the nonstochastic LQR setting, along with a matching lower bound. The analysis builds upon the reduction of nonstochastic quadratic-loss LQR to online linear regression with delayed feedback of Foster and Simchowitz (2020) and the recent algorithm of Baby and Wang (2022) attaining optimal dynamic regret (and $O(\\log n)$ strongly adaptive regret) for exp-concave losses under certain assumptions. Hence the main theorem of the paper translates the Baby and Wang (2022) guarantees to the setting of \\textit{proper} (i.e. ensuring decisions are within a general convex set) online linear regression with delayed feedback and then instantiates it in the LQR setting. ", "questions": "Suggestions/minor remarks:\n- On line 294: \"static\" -> \"adaptive\";\n- line 355: \"arise\"->\"arises\"\n- Some more text to help the flow of Appendix B (quite terse right now)\n- misplaced equation in lines 657-660\n- Improve flow of proof of lemma 18 (e.g. bullet points for properties, or just more careful writing + organization)\n- line 694: paragraph ends with \"We fo\" -> fill in the rest of the sentence\n- Shorten statement of Corollary 19 to improve readability + maybe some light work on improving flow of proof\n- the below.", "limitations": "I recommend more discussion on finding the correct input parameters for Corollary 10 to hold (line 333) [addressed in rebuttal, I recommend this to be incorporated in camera-ready], as well as discussion of the limits of deploying online learning based controllers in practice (both in general and the particular one proposed by the authors) [I recommend this to be incorporated in discussion section of camera-ready].", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The (main) paper is written very clearly;\n- It is placed very naturally within the literature;\n- The conversion of Baby and Wang (2022) to an algorithm that works on general convex constraint sets is a nice contribution.\n\nWeaknesses:\n- Somewhat limited originality and impact;\n- Lack of experimental settings make it hard to gauge if this algorithm would eventually lead to better controllers in practice.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "cMf3iZSQNOG", "reviewer": "Reviewer_63zh", "summary": "The paper studies the dynamic regret of online linear quadratic control. It considers single-trajectory LQ control with known, stationary system and cost matrices, and with adversarial disturbances. The paper addresses the problem by studying dynamic regret minimization against disturbance action policies. It first presents a proper online learning algorithm that achieves dynamic regret optimal in the number of steps and path variation, for online minibatch linear regression. The paper proves that this algorithm is also strongly adaptive, in that it achieves logarithmic static regret for any time window. By combining disturbance action policies with the proper online learning procedure, the paper shows a dynamic regret bound that is also optimal in the dependence on the number of steps and path variation. A main technical contribution is the procedure to convert an improper online learning algorithm to a proper one, while maintaining the exp-concavity of the loss function. A nontrivial lower bound is also presented to show the optimal dependencies.", "questions": "In the abstract, citing the source of the best known rate is recommended.\n\nIn some places, the papers uses the notation $\\tilde{O}(\\log n)$. Here, $\\tilde{O}(\\cdot)$ does not hide logarithmic dependence on $n$, which had better be noted.\n\nBelow Proposition 2, in Lines 133 to 137, the math formulas can be better displayed.\n\nIn the definition of exp-concavity (Definition 3), it is not clear how it is related to the name of exp-concavity. Unfamiliar readers would appreciate some more explanation.\n\nIn Section 4.2, readers read the algorithm first but do not know what $\\mathcal{A}$ is until reading two more paragraphs. I recommend explaining $\\mathcal{A}$ earlier.\n\nIn Line 326, \"notations\" -> \"notation\".\n\nIn the Conclusion section, the paper mentions \"general strongly convex losses in the LQR problem\". If I did not get it wrong, this paper considers positive semidefinite $Q$, $R$, so the cost is not necessarily strongly convex. Hence, strongly convex costs are not strictly more general than quadratic costs. The word \"general\" can be removed to reduce the ambiguity. And in this case, the problem is no longer a LQR problem, but a linear control problem.", "limitations": "Limitations are adequately addressed.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper has technical significance. It proves a sharp dynamic regret bound in terms of the number of steps and the path variation, as well as a matching lower bound. The results are built upon earlier results about the reduction from online LQ control to online linear regression, optimal improper online learning with exp-concave losses, and the conversion from improper learners to proper ones, while having new, interesting components, like the new improper to proper learning conversion and lower bounding strategy.\n\nThe paper contains a thorough discussion of the literature and is well placed in it. The presentation is in general clear. Please see the Questions section for some suggestions for improvement.\n\nOn the weakness side, the dependence on the dimension and system parameters are unlikely to be optimal. Empirical support for the theoretical claims is lacking, which could be informative of the constants hidden in the bounds.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept