Perturbation-based Regret Analysis of Predictive Control in Linear Time Varying Systems
Authors: Yiheng Lin
Yang Hu
Guanya Shi
Haoyuan Sun
Guannan Qu
Adam Wierman
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Linear time-varying system
Online convex optimization
Predictive control
Sensitivity analysis

Abstract: We study predictive control in a setting where the dynamics are time-varying and linear, and the costs are time-varying and well-conditioned. At each time step, the controller receives the exact predictions of costs, dynamics, and disturbances for the future $k$ time steps. We show that when the prediction window $k$ is sufficiently large, predictive control is input-to-state stable and achieves a dynamic regret of $O(\lambda^k T)$, where $\lambda < 1$ is a positive constant. This is the first dynamic regret bound on the predictive control of linear time-varying systems. We also show a variation of predictive control obtains the first competitive bound for the control of linear time-varying systems:  $1 + O(\lambda^k)$. Our results are derived using a novel proof framework based on a perturbation bound that characterizes how a small change to the system parameters impacts the optimal trajectory.

Perturbation-based Regret Analysis of Predictive Control in Linear Time Varying Systems
Yiheng Lin
Yang Hu Tsinghua University Beijing. China
California Institute of Technology Pasadena, CA, USA yihengl healllllllleheeeeeeee edu
huy18 1oy188mails ls tsinghua edu
Guanya Shi
Haoyuan Sun
California Institute of Technology Pasadena, CA, USA gsh gshi@caltech.cm
California Institute of Technology
Pasadena, CA, USA hsun28calttehh. edu
Guannan Qu California Institute of Technology Pasadena, CA, USA gqu8caltech. edu
Adam Wierman
California Institute of Technology
Pasadena, CA, USA adamw@caltech. edu
Abstract
We study predictive control in setting where the dynamics are cone-varying and linear, and the costs are time-varying and well-conditioned. At each time step, the controller receives the exact predictions of costs, dynamics, and disturbances for the future & time steps. show that when the prediction window & is sufficiently large, predictive control is input-to-state stable and achieves a dynamic regret of (2*7), where the predictive control of linear time-varyinn systems. We also show a variation predictive control obtains the first competitive bound for the control of linear time-varying systems: framework based on a perturbation bound that characterizes how small change to the system parameters impacts the optimal trajectory.
is positive constant. This the first dynamic regret bound
O Our results are derived using novel proof
Introduction
We study the problem of predictive control in a linear time-varying (LTVV system, where the dynamics given by X;-1 A,x, B,u, + wy- Here, X, is the state, u, the control action, and w, is the disturbance or exogenous input. At each time step f, the online controller incurs a time-varying state cost fxx)) and control cost G, (u,-1), and then decides its next control action Hr. In deciding и, the controller makes use of predictions of the next & future disturbances, cost functions, and dynamical matrices, and seeks minimize its total cost on finite horizon Our main results bound the dynamic regret and competitive ratio of predictive controllers in this LTV setting.
Recently, growing literature has sought design controllers that achieve learning guarantees such as static regret 1 2), dynamic regret
and competitive ratio [5] The most relevant
Yiheng Lin, Yang Hu, Haoyuan Sun, Guanya Shi, and Guannan Qu contributed equally to this work. *hhis work supported by NSF grants CNS-2106400 NGSDI-2105648, and AitF 1637-163759 with addi- tional support from Amazon AWS, PIMCO, and the Resnick Sustainability Insitute, Yiheng Lin was supported by Kortschak Scholars program.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

line of work concerns predictive control with learning guarantees, which studies how to leverage the prediction window & to reduce the regret and competitive ratio. This line of work has focused on linear time-invariant (LTTI) systems 3
However, linear time-varying (LTV) systems have received increasing attention in recent years due to their importance in a variety of emerging applications, despite the challenges associated with analysis. For example, in the problem of power grid frequency regulation, the dynamics is determined by the proportion of renewable energy in total power generation, which is time-varying [8 g1. It is also common to use the LTV systems as an approximation of nonlinear dynamics in predictive control and planning 10.13
The current lack of progress toward understanding measures like regret and competitive ratio in LTV settings is due the need for new techniques to generalize the dynamies from LTI to LTV and the costs from quadratic to well- coll-conditioned functions. Specifically, the proof approaches used in previous studies on regret and competitive ratio of predictive control L.TI dynamics with quadratic costs, e.g., G ? require explicitly writing down the cost-to-go function, optimal control actions, and algorithm's actions as functions of the system parameters. This is very difficult, if not impossible, for general cost functions that do not have a quadratic form. A promising approach that does not require such explicit characterizations is to derive results via reductions from optimal control to online convex optimization with multi-step memory, e.g., do not work well for LTV systems due to the need to represent the problem in control canonical form B 15, due to limitations the policy class and comparisons to static benchmarks I55.
5 14 15] However, such reductions usually
Perhaps the most prominent approach for controlling LTV systems is Model Predictive Control (MPC), also known as Receding Horizon Control [16]. Generally speaking, at each time step, an MPC-style algorithm solves a predictive trajectory for the future time steps and commit the first control action in this trajectory. MPC-style algorithms are known to work well in practice, even when
the dynamics are non-linear and time-varying, e.g., [3 1 On theoretical side, the asymptotic behaviors of MPC such as stability and convergence have been studied intensively under general assumptions on dynamics and costs 20 233. However, non-asymptotic guarantees such as regret and competitive ratio of MPC-style policies have been limited. Despite recent work providing such guarantees in the context of LTI systems with quadratic costs, c.g.. 77 the derivation of regret and competitive ratio results for MPC in LTV systems remains open.
Contributions. We provide the first regret and competitive ratio results for a controller in LTV systems with time-varying costs. Specifically, we show that an MPC-style predictive control algorithm (Algorithm [ achieves a dynamic regret that decays exponentially with respect to the length of prediction window k in the LTV system (Theorem 4.2 O(LT)), where the decay rate 2 is a positive constant less than 1. This almost matches the exponential lower bound for improvement from predictions in the LTI setting shown in K in the sense that, to achieve any target regret level, the required length of prediction shown by our bound differs from the theoretical lower bound by at most constant factor. With variation of predictive control (Algorithm 2 also show the first competitive bound in LTV systems with time-varying cell-conditioned costs (Theorem 1 + O22)) ), where the decay rate À is identical with the one in the regret bound.
We develop a novel analysis framework based on a perturbation approach. Specifically, instead of solving for the optimal states and control actions like previous analyses in the LTT setting with quadratic costs, e.g.. 4 we bound how much impact an perturbation to the system parameters can have on the optimal solution. This type of perturbation bound (Theorem 3.3) can be shown even when the optimal trajectory cannot be written down explicitly, which allows it to be applied LTV systems with well-conditioned costs. Then, we utilize this perturbation bound to establish results on dynamic regret and the competitive ratio. In addition, we want to emphasize that the perturbation approach we develop is highly modular and extendable. For instance, if stronger perturbation bound for some specific class of dynamics and/or cost functions can be shown, the dynamic regret of the predictive controller will improve. Similarly, to further generalize the problem setting (e.g., to include additional constraints), one only needs to establish the corresponding perturbation bounds and the regret result will follow.
Another important component of the proof is a novel reduction between LTV control and online optimization. Connections between online optimization and control have received increasing attention in recent years, e.g., [ 5 [5). Existing reductions rely on the canonical form, which does not apply to LTV systems, and/or formulations of online optimization with memory of multiple prior time steps, which makes the online problem more challenging. The reduction we present here relies
2

---

on neither, and is thus fundamentally different approach to connect control and online optimization. Further, this reduction not specific to the predictive control algorithm we study, and we expect it to prove useful for other controllers in future work. A limitation of our reduction framework is that it cannot handle state/control constraints. This limitation is shared by previous works represents a challenging open question in the literature.
and
2 Background and Setting
We consider a finite-horizon discrete-time online control problem with linear time-varying (LTTV dynamics, time-varying costs, and disturbances, namely
Σ (f(())) + cc(())))) [=1
min
Noer
s.t. X2 = A 1- + BB-1 + W1-1.7 I.....T, x(0),
(I)
where x, R", Hy E R" and w, E R" respectively denote state, the control action, and the disturbance of the system at time steps = ,, and x(0) e R" is given initial state. By convention, the hitting cost function assumed to be time-varying and well-conditioned. Define the tuple 8, := (A,, Br, Wr. fre1, Cz41).
R. R4 and control cost function e : R. R4 are
In the classical setting where no predictions are available, after observing state x, time step the algorithm needs to decide the control action u, before observing 9,, which is an unknown random disturbance input. We use the following event sequence to describe this ordering:
Ko, u0, 0o, 41,
-1, -1 -1.
We assume that the algorithm has access the exact predictions of disturbances, cost functions and dynamical matrices the future & time steps (which are time-varying); i.c., the event sequence is
0y ...... --- No. 2x. 0x.1. 11 07 -1, 4T kk. 4T kel...... UT-1-
Here we assume all predictions are exact, and leave the case of inexact predictions for future work. This prediction model has been used in previous works like 4 24 [6] and is available in many real-world applications such disturbance estimation robotics and frequency regulation in power grids. The availability is due to the fact that, in such scenarios as mentioned above, experiments or observations on the dynamics can be conducted repeatedly and consistently, which makes it feasible to train good predictor based on the data collected from repeated trials.
2.1 Assumptions
As is standard in studies of regret and competitive ratio in linear control problems, we assume the cost functions are well-conditioned.
Assumption 2.1 -Well-conditioned Costs), The cost functions satisfy the following constraints:
1. f((-) is -ssroongyyy convexfor I,..,, and Ey -sstrroggyy smooth for I...., T 1.
2. c.(-) is both me-Strongly convex and fe-strongly smooth for I....,
3. fi(-) and c+(-) are twice continuously differentiable for I.....I
4. fi(-) and c-(-) are non-negative, and (0) = c, =0 = 0 I....TT.
Note that assumptions (1) through (3) are quite common common, but can be satisfied via re-parameterization without loss of generality. Specifically, when the minimizers of state cost fr and control cost c, are nonzero, perform the transformation
25
2
Assumption (4) is less
X - X₁ arg min fi (x), ut < u, arg min C,41 (u).
w w, A, arg min fx( arg min C,+1 (u).
The intuition of this transformation that, when the minimizer the cost function for the next step known, always perform translation in the state and control space to align the minimizer

---

with the origin. We refer the interested readers to Example 2.1 for more intuitive explanation of the above transformation.
Additionally, we need to assume the dynamics are controllable. system be steered from arbitrary initial state to arbitrary final state via finite sequence of admissible control actions. For linear time-invariant (LTI) systems, the full-rankness of the controllability matrix completely characterizes the reachability of the state space, which is generally used as a standard assumption for analysis 7 28 29]. This can be generalized to parallel assumptions for LTV systems as follows. We begin with a definition.
crucial that the dynamical
Definition 2.1.
+ B, 11r-1* Wr-1./= ll..=ll.... T, the transition matrix (112,11) E R (from time step I1 to 12) is defined as
For a dynamical system with linear time-varying dynamics X₁ A
@11,,11) A An
1f > f1
1f $ f
and the controllability matrix ((.,)) p) E (Rxx(mp) is defined as (t. [ p,r B) O p.t+ 2) Bi.l...... 4D1 p. p)
The dynamical system is called controllable if there exists constant d Z,, such that the controlla- bility matrix (1, d) is of full row rank for any I = T d. The smallest constant with such property is called the controllability index of the system.
Given the above definition, we can state the key assumption necessary for the analysis of LTV systems. We use a slightly stronger assumption than being merely controllable, which we refer as (d, -unnfform controllability. It is natural generalization of its counterpart for LTI systems (see Assumption in 2231 where (d, σ)) is instead named as (f, y)).
Assumption 2.2. There exists positive constants a, and b', such that
|| | s a, B,l s b, and [BB) s b'
hold for all time steps 1 1= o....., T 1, where B denotes the Moore-Penrose inverse of matrix B, Furthermore, there exists positive constant such that
mrin (M d))
holds for all time steps = 0...... T d, where d denotes the controllability index.
Note that Assumption 2.2 limplies Tmin (M p)) 2 o for all p 2 d because appending more columns to matrix with full row rank will not reduce its minimum singular value.
The LTV setting we consider is more general than the settings which existing results on regret and competitive ratio have assumed [1] 4 77 We highlight the implications of this general setting for enabling applications in the following examples.
Example 2.1 (Trajectory tracking in LTV systems with well-conditioned costs). Consider trajectory tracking problem with LTV dynamics and well-conditions costs, which generalizes the standard linear quadratic tracking problem in 14 30) with LTI dynamics and quadratic costs. We adopt LTV dynamics X441 Aş + B,u, W, and general well-conditioned cost functions f.(),, c.()) (see Assumption 2. With the desired trajectory di:,, we consider a new state &, := X, de and new disturbance W; := w, + A,d,- - -d Thus, using the new state and disturbance, the problem naturally fūs into our problem setting with future predictions of (A,s B,, Wys W f. Cts d(+1). Note that predictive control with LTV dynamics is practical in nonlinear systems M 31 because the nonlinearity could be well approximated by LTV models (37]. Example 2.2 (Power grid frequency regulation). Consider the frequency regulation problem in S where state [ØT w J represent the status of a power plant, and power generation Pin E R. is the control action. The continuous iattinuous-tmme time dynamics is given by
0
0
1
0 c
i
-M(1)-14 -M
1 D
+ M
-1
Pin
m((r)
k(r)
A(O
x(t)
B())

---

Algorithm Predictive Control (PC²)
1: for r= 0, 1......... T- - do
2: Observe current state x, and receive predictions 01.+k-1-
3: Solve and commit control actions u, := o (Xe, Wra+k-1; Pg-
4: At time step 1 = T - k, observe current state X, and receive predictions 0T
5: Solve and commit control actions 4 == v/f (x,, WrT-1i -1T 10
Here M(1) denotes the rotational inertia matrix, which time-varying and determined by the proportion of renewable power in lotal power generation at time i, and can be accurately predicted in a certain time horizon [32 33;; L. and are known system parameters. Using standard discretization discrete-time linear time-varying system Xx+1 Axxx B + Wo
techniques, we can formulate where A, and B, are determined by Å(t) and B(t). The cost functions are quadratic costs which penalizes frequency deviation (8). This setting fits into our predictive control algorithm, since the controllers have accurate predictions of As and B, in the near future due to predictablity of M (1).
2.2 Predictive Control
We study a classical predictive control (PC) algorithm inspired by model predictive control, which solves the optimization problem of k future time steps (where k is called the prediction window). specifically, the algorithm receives the dynamics and disturbances of the next & time steps, calculates the optimal solution, and then applies the first control action of the optimal solution. The PC algorithm with prediction window & is denoted PCK.
More formally, At time step 1 < T k, PC2 solves the optimization problem & (x,, Wrask-1; F). Since we need to consider horizon lengths other than k, for arbitrary 2 and time step we define the optimization problem // FF) as
Σ (
Σ (V+-)++))+ r=1
J.. (x. = arg min
No.p No.p-1 r=1
s.l. yr = A P TT-1, T= =I,...,. I,...,P.
(2)
yo X,
where x R is the initial state, & E (R")² (indexed by O.....P and F R" - R is a standard terminal cost function regularizing the final state. Here additionally require that the terminal cost F has the form Fxx) a [Ixx]), where a : Ra0 - R20 is a convex K- function (i.e. continuous increasing function with 0 the origin, see Appendix A for definition) that is twice continuously differentiable. For each time step r = l...., k, y, E R is the predictive state, and V, R" is the predictive control action. To make the algorithm well-defined, time step = T k, PC₃ can finish the rest of the trajectory optimally by committing -T-A7-1 = (XT W: The pseudo-code of predictive control is given in Algorithm
sequence of disturbances,
also important in our framework to study the behavior of predictive control under some fixed terminal point. So, for prediction length p 2 1 and time step we define an auxiliary optimization problem with a strict terminal constraint yp = Z as follows:
Σ ( & (CtT(Vr-))
(x,(x))) = arg min
Nep- r=1
s.t. yr = A
+ B B
(3)
yo = x.
where the optimal value is denoted by (x, 2). We define this auxiliary optimization problem besides // (x, f; F) because we need to fix both the initial state and the terminal state, for example, when expressing sub-trajectory of the offline optimal trajectory as the solution of an optimization problem. & also allows us to study the impact of the perturbation at the terminal state on the optimal trajectory directly, which will be useful in the proof dynamic regret (Theorem and competitive ratio (Theorem
5

---

Throughout the paper, we use (x))= to denote the trajectory of predictive control, and use ((x), to denote the offline optimal trajectory (i.e., the optimal solution of TD). We also use several standard definitions and notations in linear algebra and optimization, which we detail in Appendix for clarity. In particular, we use vector 2-norms and induced matrix 2-norms throughout this paper unless otherwise specified.
Two standard metrics will be utilized to assess the performance of our predictive control algorithms, namely dynamic regret supx(0).w (cOst(AL.G) cost( PT)) (the additional cost of our algorithm cost(ALGG) against the optimal algorithm) and competitive ratio supx(0),w cIs((OPT) (the worst-case ratio of the cost of our algorithm over that of the optimal algorithm).
3 A Perturbation Approach
In order to study the regret and competitive ratio of controllers in LTV systems, we develop new analysis based on a perturbation approach, which we introduce this section. This approach is based on developing bounds on how much the solutions to 2 and ( change with respect to perturbations to the initial/terminal states and the disturbance sequence. Our perturbation bounds are related to the concept of incremental stability defined in (34. but not exactly the same because we consider the optimal trajectory in finite horizon whereas the incremental stability focuses on asymptotic behavior over infinite horizon. Simply stated, the key our approach is to derive the perturbation bound in Theorem 3.3 which states that if the target variable we are concerned with is the /-th predictive state/control imput, while the perturbation occurs at the r-th time step, then the impact on the target variable is exponentially small with respect to the time difference //t rl.
Proving such a result directly is challenging because of the complexity of the LTV dynamical constraints in 4 and 3 Thus, we develop a novel reduction from LTV systems to fully-actuated systems, i... systems where the controller can steer the system to any state in the whole space R" freely at every time step. This special case a form of online optimization called smoothed online convex optimization (SOCO), and has received considerable attention recently, e.g.. 24
2 35.
We
exploit the controllability of the dynamics to analyze the LTV system in chunks of time steps. A sequence of d time steps combined together can be thought can formulate a SOCO problem, which is (1/d)-times as long as the original LTV system. In this section, we first show the perturbation bound for SOCO in Section 3.1 and then we leverage our reduction to derive a result for general LTV systems in Section 3.2
autla-actuated system and thus
3.1 Smoothed Online Convex Optimization
The classic setting of SOCO is an online game played by an agent against an adversary: at each time step r, the adversary reveals a hitting cost function f. a switching cost function é, and disturbance (or exogenous input) wi, The agent picks a decision point &, E R" and incurs a stage cost of f (i,) + č, & (1))). The agent seeks to minimize the total cost it incurs throughout the game. The offline optimal cost is defined as the minimum cost if the agent has full knowledge of the costs and disturbances at the start of the game. Instead of analyzing the performance of an online algorithm directly, our focus is on studying how the perturbations of the system parameters (initial state, terminal state, and disturbances) impact the offiine optimal solution. These results are critical for deriving the guarantees for predictive control in the online setting in Section
To begin, observe that when the initial state îg, terminal state p. and the disturbances v are given, the optimal p-step trajectory of SOCO can be obtained from the unconstrained optimization problem
$ (Ro. W. &p) := arg min I F.CR..) + Σ (F 17-1,,
(4)
Stp-1 T=1
T=1
where the objective a convex function of the decision variables -1:p-1 Since ④ is an unconstrained optimization problem, the gradient of its objective equals zero at (Ro. &p)))) Using this, we can further show that the directional derivative of V (fo, Φ, &p) along some direction e, denoted by x. satisfies the linear equation Mx = ō. where symmetric matrix M is the Hessian of the objective and vector determined by the direction e. A special structure of the objective of { is that the correlations only occur in two consecutive time steps. This implies that its Hessian M is block

---

given state tri-diagonal. Such tri- ri-diagonal structure of M has been noted by previous work, e.g. [3 and have been leveraged solve the linear equation Mx å quickly. In contrast, we focus on the exponential decay phenomena M exhibits, i.e., the magnitudes of entries decay exponentially with respect to their distances to the main diagonal [37]. Bounding each entry of X = M separately gives us the following perturbation bound. We state this result formally in Theorem 5.1 and its proof can be
found in Appendix B
Theorem 3.1. Given a tuple (Ro, &p) that contains the initial state, the disturbances, and the terminal state in this order, we consider the optimal solution of the SOCO problem
(S0, 180,,,,8 w. == arg min
Σ (2.)+
Ee Wx-1)
Stip-1 T=l
T=l
indexed by I..... P Assume fr R."
B. is u-strongly convex, & RR R" x XB" R is
convex and E-strongly smooth, and both are twice continuously difserentiable for = I,..., . P, then
p-1
(Rg. w. &p), - & (K', 10', x>xx)))l= s Co 28 11:00 - -Eol+
1/4 11-TT-1||
110 - 10,1 2/-1+ 111 - - 8p11
r=0
for all 1 h p- where Co (2 p and do = 1- (VI (2t/m)+1)
As remark, do not require the hitting cost fr to be strongly smooth, or the switching cost &r to be strongly convex in Theorem 3.1 This makes the assumptions on the SOCO costs fr, & weaker than the assumptions on the LTV costs fr. Cr defined in ①I.
3.2 Linear Time- Varying System
We now build upon the SOCO perturbation result to derive a perturbation result for LTV systems. In particular, we show exponentially decayyyin perturbation bound for our LTV system by reducing it to SOCO and apply Theorem 3.1 As we have discussed, LTV systems are more difficult than SOCO because the dynamics prevent the online agent from picking the next state X,+1 freely x, We overcome this obstacle by redefining the decision points as illustrated in Figure | Specifically, given state x, at time step the last decision point, we then ask the online agent to decide state Xy at time step (t + d) rather than X74] at time step (1 ++] 1).
Since d is the controllability index, Xred can be picked freely from the whole space R" regardless of x,. We also utilize the principle of optimality, e.g. if youk, Vo:k-1 is the optimal solution to vh (x, 2), then Yaj- Va-j1 is the optimal solution to //- (yi.Eey-1.),) for any 0 S i < s k. Therefore, the trajectory between time and (7 d) can be recovered by solving (x,, We.rdd11. So we able to formulate a valid SOCO problem on the sequence of time steps 1, + d, + 2d.
Naturally, the hitting cost at time step (t + d) remains the same, while the switching cost becomes ed (Xe, Wrasd-1, Atd)), where the function 5, is defined as E/ (x (x ;= 1,' -rxp)))
(5)
An illustration of the reduction can be found in Figure ! We would like to point out that reduction from optimal control to SOCO is novel in that it leverages the principle of optimality to apply to more general LTV settings, as opposed the reduction via control canonical forms in [3] that is specific to LTI systems. Unlike the switching costs in 14 27 the (z-distance or squared (2-distance, the switching cost el here is defined implicitly as the optimal value of an optimization problem. Lemma 3.2 shows that the switching cost defined in ( satisfies
355
BE which are explicitly defined as
the requirements of Theorem 5.1 which allows to obtain the desired perturbation bound.
Lemma 3.2. Under Assumption and 2.2 for integer 2 d, we have
1. V (x, Z.z) is (p)) in (x. (.);;
2. 5. (x. is conver and L2(p) sttrongyy smooth in (x,5,2)
Here (p()) = C(p)((((((())) C(ppttCC(pp))m)mppp/ Lx(p) = = c(p) C(p)* /me, where = max(ey tc),
((a27)
ifa 1;
C(p)
O(p3)
ifa 1;
0(1)
ifa <
7

---

ed (Ng, wiat---ad)
fd (xa. -22dd-1-2dd
(10-1 (to- Mie- Mo--ddvd---
6168). A9))
82 18))
Ev (y (y-1)
0
0
&1
+
+
82
8v-1
Xy
(3)
Bo-1(R0-1) HI (1--1D
fa (K()
!I
has Oaa
fd (xa- Wazza-1-22 Kad)
dd
ud+l
ud+2
u2d-1
Sd+1
xd+2
X2d
caloa)
cast (maa))
(avz(mavz)
cza-1 (92a-1
fast
faaliza)
Figure 1:
Illustration of the reduction from LTV to SOCO. Here consider simple example where = and = vd. At time step 0, the agent cannot steer the system to an arbitrary target state the next time step due dynamical constraints. However, given (d, -uniform controllability, the controller is able to enforce an arbitrary target state after d time steps, which prompts the transformation SOCO problem with a decision point in every time steps.
In Lemma 3.2 we use O-)) to hide quantities a, b, and 1/or; the precise expression of C(p) and the proof of Lemma 3.n can be found in Appendix [ Using the reduction from LTV to SOCO, we obtain perturbation bound for the LTV systems and 3 in Theorem 3.3 the proof of which is deferred
to Appendix D
Theorem 3.3. Consider the optimization problem defined in and 3 and with a horizon length p d. Under Assumptions 2.1 2.2 given any (x, (. z) and (x', {',²'.
(x.
C 1111x x xx11+
Σ a || 1|= s:ll
lw? (x.6. C s 1p11x-x1111 x Σ
|11-1||k=- <ill 20-0 2'1l]
hold for all time steps 1. Here we define Lo maxdsps2d-1 L2(p), and the constants are given by
A = 11 22 2= +
+1)") (2)
2L.
(1-2(VI+
me
Theorem 3.3 allows us to bound the distance between any two trajectories long as they can be expressed as the optimal solutions of the optimization problem 2 or @ For example, bound the norm of each state in the predictive trajectory J (x F), we only need to set = 0, = 0 in the first inequality because an all zero trajectory can be expressed as J. (0, O; F). The formal statement of this result can be found in Appendix
4 Performance Guarantees for Predictive Control
We now demonstrate the power of the perturbation approach in Section 3.2 by obtaining bounds on regret and competitive ratio. The key intuition behind our analysis if the predictive controller with prediction window & is given the knowledge of x, and x it can fully recover the offline optimal states and control inputs for the future k time steps, x and "Iu+t-1 from # (x/,, x1) However, without the knowledge of the offline optimal states, the predictive controller solves v/² (X,, Wrisk-11, Xy4k) instead, where X744 is implicitly determined by the k-th predictive state of J (xy, Wos+e-1; F). We overcome this gap with our perturbation approach (specifically, Theorem (3.3] and corollaries), which allows us to bound the distance between the controller's s trajectory and the offline optimal trajectory.
following: at time step f,

---

4.1
Dynamic Regret
We first bound the dynamic regret of predictive control. For this analysis, a key observation is that the offline optimal trajectory is given by x Jh (xo. wo 0) Yor Furthermore, the optimal trajectory starting at time step with state x, is equivalent to the trajectory of predictive control with prediction
window (T- () and no terminal cost, i.e. J/ (x,, w -1: yur- Using Theorem 3.3 we can bound
the change in decision points against the change prediction window Lemma Formalizes this:
Lemma 4.1. For any integers p. h such that p h z 1 and time step T p, have
J. (xi, Wrasp-1;;; F),, - -.. (xx, Wro+p; P)
2CAP- CAPIIxIlI+ 2C
2C
sup [I+=l]]
1 osrsT-1
Then, we can follow the road map below to bound the dynamic regret of predictive control PC2:
(a) Given the well-conditioned state/control costs, it suffices to bound the distance between PC2 's trajectory and the offline optimal trajectory (i.e., |||,-xxx
- x; [D] to show the dynamic regret result. (22 and 23 b in Appendix for technical details.
See inequalities
(b) At each time step 1, the optimal next state (under imaginary terminal cost F) from the current state x, is given by (x,, -1; However, reaching the optimal next state from X, requires full knowledge of the future costs, dynamics, and disturbances. Although PCR cannot reach the optimal next state due to incomplete knowledge of the future, it can leverage the predictions of future k steps to decide near-optimal control action from state X,- By cumulatively summing up the bounded difference in Lemma 4.1 and applying Theorem B.3 one can show the suboptimality, measured by the distance ||x+-1 off -t (xx, Wr.T-;;)) is in the order of (2t)). See incquality
19 in Appendix H for technical details.
(c) Using the exponentiall--eccyingg LTV perturbation bound in Theorem 3.3 we can convert the per-step suboptimality bounds global suboptimality bound on ||x, -x x, that is also in the order of (2*). See inequalities
(20 and 21 in Appendix H for technical details.
The ) upper bound on the distance between the algorithm's 's trajectory and the offline optimal trajectory leads to the regret bound Theorem 4.2
Theorem 4.2. Suppose ||w,ll S D for some constant D at each time step t. Let A, C, Lo be the decay If prediction window k z d is sufficiently large, such that
rate and constants defined in Theorem 3.3
1 1 (1-x +a))/ log (1)
2C
k 2 + log
(6)
for some positive constant 5 E (0, 1), then the trajectory of PCR satisfies:
1. (Input-to-state Stability) The norm of each state x₁ is upper bounded by
C (1 8) mmxxx(0.k ||xoll + Ø(1-1)
2C (1
if0 T
1-1
|xx/||
C² 0 (1 8) -2 + |xxol + ooll
20
1
FG PS)
-T-k<Ist
2. (Dynamic Regret) The dynamic regret of PC2 upper bounded by
cost( (C.( (P))(( = =0((s
2t (lxxol D)
a + + 11001
8
where the notation hides quantities a, b', lg,Ce C,1/(1 and Lo-
An implication of Theorem 4.2 is that to obtain o(1) dynamic regret when the norm of disturbances are uniformly upper bounded, it suffices to use a prediction window of length O(log 7). This parallels the result shown in 4 although in a more general setting.
4.2 Competitive Ratio
We now focus on bounding the competitive ratio of predictive control. we study a modification of the predictive control algorithm have considered to this point. In particular, we introduce

---

Algorithm 2 Predictive Control with Replan Window h (P.)))))
Suppose = ngh mig where integers no 2 0, k h mo S
2: for = 0, h.... no 1) do
3: Observe current state x, and receive predictions 0-:++-11-
4: Solve and commit control actions Hy:+hh-1 := ,/ (xy, Wri+k-1; F) P'man-
5: At time step 1 noh, observe current state X, and receive predictions -1---1
6: Solve and commit control actions 4 = 1/t00 (x,, WT Vimg-11
replan window h, as defined in Algorithm which we denote as (R,,))) This style of algorithm has been considered previously in the SOCO literature, where it has been shown to obtain constant competitive ratio in some settings where MPC does not 39
Our analysis approach highlights why this modification is beneficial for competitive ratio. Specifically, we obtain the competitive ratio bound by applying potential method building on [40] We define the
potential function as the squared distance between the algorithm's 's trajectory and the offline optimal
trajectory, i.e., or (Xr, x;) ||a,, - xill² which standard the literature this potential function changes over time. Intuitively, we need to upper bound the increment of this potential function by the offline optimal cost obtain a competitive ratio result. To achieve this, the algorithm needs to "move closer" to the offline optimal trajectory rather than "moving further away"
|E!
27
We study how
from it. Recall that Theorem 3.3 gives that
|| (x,, Wra+k-1; Fy,, - -/ (x), Wratk-1; F)y..l s Ca - -xil--
When the algorithm commits the first predictive state (h 1), the left hand side of 7 might be larger than ||x, x;/| when C. > 1. Thus, the algorithm must "wait" until the right hand side of 7 becomes smaller than ||x, - =;|l- This is accomplished in Algorithm 2 via the replan window ht
Our main result for this section the following competitive ratio bound for PC(K,,)
Theorem 4.3. Let d, C, Lo be the decay rate and constants defined in Theorem 3.3 In Algorithm 2 if the replan window h satisfies h 2 max (log ((1 + s)C)/log (1/A), d) for some positive constant E, and the prediction window satisfies k 2 h d, then it has competitive ratio
cost
1o+00 eg Lo
1/2
sup x(O).M
0 8-1
CCRR--h
COS
m
where the notation only hides small numerical constant.
Note that when the constant & and the replan window are fixed, the competitive ratio is on the order of 1 O(p²) the length of prediction & tends to infinity. One potential line of future work is to understand if the replan window is necessary. It may be possible to either strengthen the constants given in Theorem 3.3 or improve our proof approach as eliminate the requirement on h.
References
[1] Naman Agarwal, Elad Hazan, and Karan Singh. Logarithmic regret for online control. Advances in Neural Information Processing Systems, 32, 2019.
[2] Max Simchowitz and Dylan Foster. Naive exploration is optimal for online LQR. In Interna- tional Conference on Machine Learning, pages 8937-8948 -948. PMLR, 2020.
[3] Yingying Li, Xin Chen, and Na Li. Online optimal control with linear dynamics and predictions: Algorithms and regret analysis. Advances in Neural Information Processing Systems, 32, 2019.
[4] Chenkai Yu, Guanya Shi, Soon-Jo Chung, Yisong Yue, and Adam Wierman. The power of predictions in online control. Advances in Neural Information Processing Systems, 33, 2020.
[5] Guanya Shi, Yiheng Lin, Soon-Jo Chung, Yisong Yue, and Adam Wierman. Online optimization with memory and competitive control. In Advances in Neural Information Processing Systems, pages 20636-20644 2020.
10

---

[6] Chenkai Yu, Guanya Shi, Soon-Jo Chung, Yisong Yue, and Adam Wierman. Competitive control with delayed imperfect information. arXiv preprint arXiv:2010.11637 2020.
[7] Runyu Zhang, Yingying Li, and Na Li. the regret analysis of online LQR control with predictions. arXiv preprint arXiv:2 2021.
[8] Patricia Modalgo--Gozzlle Rodrigo Henriquez-Auba, Duncan Callaway, and Claire Tomlin. Frequency regulation using data-driven controllers in power grids with variable inertia due to renewable energy. In 2019 IEEE Power & Energy Society General Meeting (PESGM), pages 1-5, 2019.
[9] Guannan Qu, Yuanyuan Shi, Sahin Lale, Anima Anandkumar, and Adam Wierman. Stable online control of linear time-varying systems. arXiv preprint arXiv:2102.01.3 100.001990 2021.
[10] Jorge Nocedal and Stephen Wright. Sequential quadratic programming. Numerical optimiza- tion, pages 529-562, 2006.
[11] Daniel Morgan, Soon-Jo Chung, and Fred Y Hadaegh. Model predictive control of swarms of spacecraft using sequential convex programming. Journal of Guidance, Control, and Dynamics, 57(6):725-1740)) 2014.
[12] Guanya Shi, Wolfgang Hönig, Xichen Shi, Yisong Yue, and Soon-Jo Chung. Neural-swarm2: Planning and control of heterogeneous multirotor swarms using learned interactions. arXiv preprint TrXiv::0122005557 2020.
[13] Paolo Falcone, Manuela Tufo, Francesco Borrelli, Jahan Asgari, and Eric Tseng. A linear time varying model predictive control approach to the integrated vehicle dynamics control problem autonomous systems. In 2007 46th IEEE Conference on Decision and Control, pages 2980-2985. IEEE, 2007.
[14] Gautam Goel and Adam Wierman. An online algorithm for smoothed regression and LQR control. In Proceedings of the Machine Learning Research, volume 89, pages 2504-2511 2019.
[15] Naman Agarwal, Brian Bullins, Elad Hazan, Sham Kakade, and Karan Singh. Online control with adversarial disturbances. International Conference on Machine Learning, pages 111-119. PMLR, 2019.
[16] Carlos E Garcia, David M Prett, and Manfred Morari. Model predictive control: Theory and practice survey. Automatica, 25(3):335 348, 1989.
[17] Ugo Rosolia and Francesco Borrelli. Learning model predictive control for iterative tasks. a data-driven control framework. IEEE Transactions on Automatic Control, 63(7):1883-1866 2017.
[18] Milan Korda and Igor Mezić. Linear predictors for nonlinear dynamical systems: Koopman operator meets model predictive control. Automatica, 93:149-160, 2018.
[19] Frank Allgöwer and Alex Zheng. Nonlinear model predictive control, volume 26. Birkhäuser, 2012.
[20] Moritz Diehl, Rishi Amrit, and James B Rawlings. A Ayapunov function for economic optimizing model predictive control. IEEE Transactions on Automatic Control, 56(3):703-707, 2010.
[21] David Angeli, Rishi Amrit, and James Rawlings. On average performance and stability of economic model predictive control. IEEE transactions automatic control, 1767):615--1666 2011.
[22] David Angeli, Alessandro Casavola, and Francesco Tedesco. Theoretical advances on economic model predictive control with time-varying costs. Annual Reviews in Control, 41:218-224, 2016.
[23] Lars Grüne and Simon Pirkelmann. Economic model predictive control for time-varying system: Performance and stability results. Optimal Control Applications and Methods, (1(():22 64, 2020.
11

---

[24] Yiheng Lin, Gautam Goel, and Adam Wierman. Online optimization with predictions and non-convex losses. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 4(1):1-32, 2020.
[25]
Yingying Li, Guannan Qu, and Na Li. Online optimization with predictions and switching costs: Fast algorithms and the fundamental limit. IEEE Transactions on Automatic Control, 2020.
[26] Minghong Lin, Zhenhua Liu, Adam Wierman, and Lachlan LH Andrew. Online algorithms for geographical load balancing. In Proceedings of the International Green Computing Conference (IGCC), pages 1-10, 2012.
[27] Gautam Goel, Yiheng Lin, Haoyuan Sun, and Adam Wierman. Beyond online balanced descent: An optimal algorithm for smoothed online optimization. Advances in Neural Information Processing Systems, 32:1875-1888 2019.
[28) Horia Mania, Stephen Tu, and Benjamin Recht. Certainty equivalence is efficient for linear quadratic control. Advances in Neural Information Processing Systems, volume 32, 2019.
[29] Karl Johan Áström and Richard M Murray. Feedback systems. Princeton university press, 2010.
[30] Brian DO Anderson and John B Moore. Optimal Control: Linear Quadratic Methods. Courier Corporation, 01 2007.
[31] Paolo Falcone, Francesco Borrelli, H Eric Tseng, Jahan Asgari, and Davor Hrovat. Linear time-varying model predictive control and its application active steering systems: Stability analysis and experimental validation. International Journal of Robust and Nonlinear Control: IFAC-Affiliated Journal, 18(8):862-875, 2008
[32] Madasthu Santhosh, Chintham Venkaiah, and D. M. Vinod Kumar. Current advances and ap- proaches in wind speed and wind power forecasting for improved renewable energy integration: review. Engineering Reports, 266)21 2020.
[33] Ruby Nageem and Jayabarathi R. Predicting the power output of grid-connected solar panel using multi-input support vector regression. Procedia Computer Science, 115:723-730, 2017.
[34] Duc N Tran, Björn S Rüffer, and Christopher M Kellett. Incremental stability properties for discrete-time systems. In Proceedings of Conference on Decision and Control (CDC), pages 477-482. IEEE, 2016.
[35] CJ Argue, Anupam Gupta, and Guru Guruganesh. Dimension-free bounds for chasing convex functions. In Conference on Learning Theory, pages 219-241. PMLR, 2020.
[36] Brandon Amos. Ivan Jimenez, Jacob Sacks, Byron Boots, and J. Zico Kolter. Differentiable MPC for End-to-end Planning and Control. In Advances in Neural Information Processing Systems, 2018
[37] Stephen Demko, William F Moss, and Philip W Smith. Decay rates for inverses of band matrices. Mathematics of computation, 43(168):491-499, 1984.
[38] Niangjun Chen, Gautam Goel, and Adam Wierman. Smoothed online convex optimization in high dimensions via online balanced descent. In Proceedings of Conference On Learning Theory (COLT), pages 1574-1594, 2018
[39] Niangjun Chen, Joshua Comden, Zhenhua Liu, Anshul Gandhi, and Adam Wierman. Using predictions in online optimization: Looking forward with an eye on the past. ACM SIGMETRICS Performance Evaluation Review, 44(1):193-25) 2016.
[40] Nikhil Bansal and Anupam Gupta. Potential-function proofs for gradient methods. Theory of Computing, 15(1):1-322 2019.
12


Reviews:
[{"review_id": "u0SSmKOUG4B", "reviewer": "Reviewer_Dpte", "summary": "The paper considers the control of a linear time-varying system with predictions. The predictions must be accurate and describe both the transition parameters, the noise, and the cost functions. The length of the prediction window must be larger than the system's sequential strong controllability index, i.e., such that it gives the controller the ability to transition perfectly between any two given states in a fixed number of steps without exerting too much control.\n\nThe main results are that for, prediction length $k$ large enough, we get dynamic regret $O(\\lambda^k T)$ and competitive ratio $1 + O(\\lambda^k)$.\n\nTo achieve their results, the authors formulate the control as an optimization problem and carry out a sensitivity analysis with respect to both the start and end state as well as the perturbations. They then use this to reduce the problem to smoothed online convex optimization, which then yields the dynamic regret. They also use the sensitivity analysis together with what they describe as standard methods to achieve the competitive ratio result.", "questions": "", "limitations": "", "rating": 6, "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": "Tackling the control of linear time varying systems is certainly of interest. The main algorithms and the statement of the results are satisfying and easy enough to understand. At a very high level, the proof ideas are also conveyed clearly.\n\nWhile I'd be very interested to see a sensitivity analysis with respect to the prediction accuracy, it is more than reasonable to leave this for future work. I'd be happy to know if the authors have any ideas regarding this matter.\n\nI do have a few issues:\n\n1. While the exposition made me think the results are plausible, I did not find it sufficiently convincing. I tried looking a bit in the supplementary material, but the proofs there are quite long and technical and will take me very long to go over. Ideally, I would like to see a concrete proof sketch in the main text or perhaps even a full proof composed of informative/technical side lemmas that are proved in the appendix. In any case, it is not currently clear to me how the intermediate results in the main text come together to conclude the main results.\n\n2. The definition of the cost seems non-standard to me. In particular, the additive relation between the state and control costs. Is it necessary? If so, while this includes the standard LQR costs, its necessity should be discussed.\n\n3. Assumption 4 (all costs are minimized at 0 with value 0) is also non-standard. While the authors explain how it may be removed, the explanation is very short. After some thought, I find it likely that their explanation is indeed correct. Nontheless, I think it should be explained in further detail and proved formally. This would likely go to the supplementary material but I think its inclusion is necessary since the assumption is otherwise very restrictive.\n\n\n\nOverall I think this is a very good work, but with the non-trivial caveat that I have no reasonable way to verify the veracity of the results.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "pbm3587HlX2", "reviewer": "Reviewer_8aU4", "summary": "This article studies finite-time horizon   predictive control for linear systems with time-varying and strongly convex costs.\nThe authors assume that each time points,\n the system coefficients and \nthe random disturbance of the state dynamics\nat the next $k$ time steps can be observed exactly,\nbased on which the controller choose the current action.\nBy reformulating the control problem as an equivalent optimisation problem, \nthe authors establish a perturbation bound of the algorithm, \nand further analyze the dynamic regret and competitive ratio.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "\nMy main comments are as follows:\n\n\\begin{enumerate}\n\n\\item The analysis based on the assumption that\nat each time point, \n the system coefficients and  random disturbances in the future $k$ time steps \ncan be observed exactly for a sufficiently large $k$, depending implicitly on the controllability index of the system.\nIn my opinion, this is a very strong assumption, especially the exact observation of noise. \nI suggest the authors to \ndiscuss extensions to inaccurate observations of noises,\nor \ngive more concrete and practical examples where the random noises in the future time steps\ncan be exactly observed. \n\n\\item \nIn the optimization problem (2), the authors introduce the terminal cost $F(x)=\\alpha(\\|x\\|)$ with $\\alpha$ being a convex function. However, the results and assumptions of Theorem 3.3 seem to be independent of $F$. Please clarify the role of $F$. Can we choose $F$ to be the zero function in the algorithm? \n\n\\item I recommend to recall the definition of competitive ratio in the main text for the reader's convenience. \n\n\\item The authors mention in the introduction that the current framework can not handle control constraints. However, it seems that the essential step of the analysis is to establish the Lipschitz stability of the optimizer of a convex optimization problem with respect to the loss function. Is it possible to follow the framework in https://arxiv.org/pdf/2104.09311.pdf, and handle the control constraints as an additional nonsmooth convex cost? \n \\end{enumerate}\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "1.5 hours"}, "extra_text": {}}, {"review_id": "J8gGLIMmSkQ", "reviewer": "Reviewer_YZqG", "summary": "This paper establishes both dynamic regret and competitive ratio bounds for online control with time-varying linear dynamics and adversarial perturbative noise, thereby extending past work for time-invariant noise-free dynamics. The analysis is facilitated by a general-purpose sensitive analysis for smoothed OCO. \n\nUpdate: The reviewers adequately addressed my concerns, and I am ammending my review to an 8. ", "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": "Overall, I had a very positive impression of the paper. The writing and notation were consistent and clear. Authors establish guarantees both in terms of regret, and competitive ratio, the latter of which I found quite surprising. The reduction to smoothed convex optimization also seems like a useful tool. I encourage acceptance (score of 7), but am I reluctant to award a higher score because the result seems like a (somewhat) incremental extension of Li et al 2019: notably, dynamic regret with a lookahead suffers excess loss lambda^k, where lambda = sqrt(condition number). Certainly this work is more general, is considerably better written, and the analysis relies only on conditioning of the controllability Gramian (rather than Li et al. which work in the rather hideous cannonical controllable form). But the key ideas: lookahead due to banded structure (see below in Major suggestions for more explanation), and the reduction to optimization on a finite window with an extra variable x_{t+p} corresponding to a final state are both fundamentally the contributions of the prior work. In fact, I believe that the latter (the reduction from control to SOCO) could have been better attributed to the predecessor. \n\nIn sum,  I am enthusiastic about acceptance of this paper, but view it more of an improvement of past work than a fundamental breakthrough in its own right.\n\n\nMajor Suggestions\n1. I think the sensitivity analysis based on banded diagonal matrices is super interesting. However, in light of past work (Li et al. 2019), there also seems to be an \"algorithmic proof\" of the same fact. Namely, I can consider the exact optimal solution to some banded optimization problem, and then I can consider the iterates produced by Nesterov's method. Examining the form of the latter, the k-th iterate requires at most k-steps of lookahead, yet exhibits an O(lambda^k) convergence to the optimal.  Then I could argue that any k-look ahead exact solution is also close to the k-step iterate of Nesterov's algorithm. Of course, \"under the hood\", the analysis of Nesterov's method and the conditioning of banded diagonal matrices reflect more or less the same principle. But I think that, given the use of this algorithm in past work, it would be nice to at least remark that it could be used as an alternate proof.\n\nMinor Suggestions:\n1. It took me a while to understand the subscript notation after the psi functions, only to realize that it corresponded to a vector index. I think it would be helpful to explain that upfront.\n2. The authors do a good job of keeping notation consistent and avoid overloading. Still, it would have been very helpful to have seen a notation table in the appendix. This is particularly useful for disambiguating hats v.s. tildes. vs no accents, and for remembering that y_t are a state variable like x_t (which is non-standard in control, where y_t are typically system outputs). \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors did. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "IYMx8x93zPi", "reviewer": "Reviewer_BGJX", "summary": "This paper examines the control of linear time varying systems in which the controller is given predictions of the system matrices, cost functions, and disturbances for a horizon in the future. This setup is motivated by problems, such as power systems, in which reasonably accurate predictions of future dynamics and disturbances are available at least over short horizons. The paper gives two algorithms, one based on model predictive control (MPC), which replans at each time step, and another that only replans once over fixed windows. They bound the dynamic regret and competitive ratios of these algorithms, respectively. For the MPC method, the key technique bounding how the solutions to the optimization sub-problems change when the initial condition, the disturbances, and any possible terminal constraints vary. They use these bounds to analyze stability and dynamic regret in a unified manner. For competitive ratio bounds, they show how the particular algorithm can be viewed as solving a smoothed online convex optimization problem. Then they use the previously derived methods to bound the deviation of the solution they obtained from the optimal solution. ", "questions": "", "limitations": "", "rating": 8, "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 describes two methods for controlling linear time-varying systems when finite-horizon predictions of the dynamics, costs, and disturbances are known. While these assumptions limit the scope, the authors convincingly argue that they are realistic in some important scenarios. The paper is insightful and the proofs appear to be rigorous. The key contributions enable precise bounds on stability and suboptimality for these time varying systems when only limited preview information is available. I consider these contributions to be substantial.\n\nThe methodology relies on heavily on smoothness and strong convexity of the losses and linearity of the constraints. The assumptions, in particular, guarantee that solutions to the optimal control sub-problems become smooth functions of the problem data. As pointed out by the authors, this precludes the things like inequality constraints on the states or inputs, as the smoothness properties would be lost. In many scenarios, however, these assumptions seem reasonable.\n\nAs a minor comment, some of the notation is confusing. For example, sometimes the optimal trajectories are indexed by $h$, and other times by $y_h$. The distinction is never explained, but from reading the proofs, they appear to mean the same thing.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors address the limitations of their method adequately. I see no potential negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers were unanimous in their appreciation of the paper and hence I recommend a clear Accept. I request the authors to look into improving the notation in the paper and re-assessing the paper in terms of clarity of presentation of the proofs etc to improve readability. Suggestions of this form have been laid out in multiple reviews.  
Decision: Accept (Spotlight)