Perturbation-based Regret Analysis of Predictive Control in Linear Time Varying Systems
Year: 2022

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 : time steps. We show that when the prediction window : is sufficiently large, predictive control is input-to-state stable and achieves a dynamic regret of $ (_:)), where _ < 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 + $ (_: ). 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.

heading: 1 Introduction
text: We study the problem of predictive control in a linear time-varying (LTV) system, where the dynamics is given by GC+1 = CGC + ⌫CDC + FC . Here, GC is the state, DC is the control action, and FC is the disturbance or exogenous input. At each time step C, the online controller incurs a time-varying state cost 5C (GC ) and control cost 2C (DC 1), and then decides its next control action DC . In deciding DC the controller makes use of predictions of the next : future disturbances, cost functions, and dynamical matrices, and seeks to minimize its total cost on a finite horizon ) . Our main results bound the dynamic regret and competitive ratio of predictive controllers in this LTV setting.
Recently, a growing literature has sought to design controllers that achieve learning guarantees such as static regret [1, 2], dynamic regret [3, 4], and competitive ratio [5]. The most relevant
†Yiheng Lin, Yang Hu, Haoyuan Sun, Guanya Shi, and Guannan Qu contributed equally to this work. ‡This work was supported by NSF grants CNS-2106403, NGSDI-2105648, and AitF-1637598, with additional 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 (NeurIPS 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 (LTI) systems [3, 4, 6, 7]. 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, 9]. 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 to the need for new techniques to generalize the dynamics from LTI to LTV and the costs from quadratic to well-conditioned functions. Specifically, the proof approaches used in previous studies on regret and competitive ratio of predictive control in LTI dynamics with quadratic costs, e.g., [4, 6, 7], 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., [1, 3, 5, 14, 15]. However, such reductions usually do not work well for LTV systems due to the need to represent the problem in control canonical form [3, 5], or due to limitations on the policy class and comparisons to static benchmarks [1, 15].
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., [13, 17–19]. 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–23]. 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, e.g., [4, 6, 7], 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 1) achieves a dynamic regret that decays exponentially with respect to the length of prediction window : in the LTV system (Theorem 4.2): $ (_:)), where the decay rate _ is a positive constant less than 1. This almost matches the exponential lower bound for improvement from predictions in the LTI setting shown in [3] 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 a constant factor. With a variation of predictive control (Algorithm 2), we also show the first competitive bound in LTV systems with time-varying well-conditioned costs (Theorem 4.3): 1 +$ (_: ), 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 LTI setting with quadratic costs, e.g., [4, 7], 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 in 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 a 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., [1, 3, 5, 14, 15]. 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
on neither, and is thus a fundamentally different approach to connect control and online optimization. Further, this reduction is 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 [3, 4, 6, 7], and represents a challenging open question in the literature.

heading: 2 Background and Setting
text: We consider a finite-horizon discrete-time online control problem with linear time-varying (LTV) dynamics, time-varying costs, and disturbances, namely
min
G0:) ,D0:) 1 )’ C=1 ( 5C (GC ) + 2C (DC 1))
s.t. GC = C 1GC 1 + ⌫C 1DC 1 + FC 1, C = 1, . . . ,) , (1) G0 = G(0),
where GC 2 R=, DC 2 R<, and FC 2 R= respectively denote the state, the control action, and the disturbance of the system at time steps C = 1, . . . ,) , and G(0) 2 R= is a given initial state. By convention, the hitting cost function 5C : R= ! R+ and control cost function 2C : R< ! R+ are assumed to be time-varying and well-conditioned. Define the tuple oC := ( C , ⌫C ,FC , 5C+1, 2C+1). In the classical setting where no predictions are available, after observing state GC at time step C, the algorithm needs to decide the control action DC before observing oC , which is an unknown random disturbance input. We use the following event sequence to describe this ordering:
G0, D0, o0, G1, D1, o1, G2, . . . , G) 1, D) 1, o) 1, G) .
We assume that the algorithm has access to the exact predictions of disturbances, cost functions and dynamical matrices in the future : time steps (which are time-varying); i.e., the event sequence is
G0, o0, o1, . . . , o: 1, D0, o: , D1, o:+1, . . . , D) : 1, o) 1, D) : , D) :+1, . . . , D) 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–26], and is available in many real-world applications such as disturbance estimation in 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 a good predictor based on the data collected from repeated trials.

heading: 2.1 Assumptions
text: 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. 5C (·) is < 5 -strongly convex for C = 1, . . . ,) , and ✓ 5 -strongly smooth for C = 1, . . . ,) 1. 2. 2C (·) is both <2-strongly convex and ✓2-strongly smooth for C = 1, . . . ,) . 3. 5C (·) and 2C (·) are twice continuously differentiable for C = 1, . . . ,) . 4. 5C (·) and 2C (·) are non-negative, and 5C (0) = 2C (0) = 0 for C = 1, . . . ,) .
Note that assumptions (1) through (3) are quite common [3, 5, 14, 25, 27]. Assumption (4) is less common, but can be satisfied via re-parameterization without loss of generality. Specifically, when the minimizers of state cost 5C and control cost 2C are nonzero, we perform the transformation
G 0 C GC arg min
G
5C (G), D0C DC arg min D 2C+1 (D),
F 0 C FC + C arg min
G
5C (G) + ⌫C arg min D 2C+1 (D).
The intuition of this transformation is that, when the minimizer of the cost function for the next step is known, we can always perform a translation in the state and control space to align the minimizer
with the origin. We refer the interested readers to Example 2.1 for a more intuitive explanation of the above transformation.
Additionally, we need to assume the dynamics are controllable. It is crucial that the dynamical system can be steered from an arbitrary initial state to an arbitrary final state via a 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. Definition 2.1. For a dynamical system with linear time-varying dynamics GC = C 1GC 1+⌫C 1DC 1+ FC 1, C = 1, . . . ,) , the transition matrix (C2, C1) 2 R=⇥= (from time step C1 to C2) is defined as
(C2, C1) := ⇢ C2 1 C2 2 · · · C1 if C2 > C1 if C2  C1 ,
and the controllability matrix " (C, ?) 2 R=⇥(<?) is defined as " (C, ?) := ⇥ (C + ?, C + 1)⌫C , (C + ?, C + 2)⌫C+1, . . . , (C + ?, C + ?)⌫C+? ⇤ .
The dynamical system is called controllable if there exists a constant 3 2 Z+, such that the controllability matrix " (C, 3) is of full row rank for any C = 1, . . . ,) 3. The smallest constant 3 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 to as (3,f)-uniform controllability. It is a natural generalization of its counterpart for LTI systems (see Assumption 2 in [28], where (3,f) is instead named as (✓, a)). Assumption 2.2. There exists positive constants 0, 1, and 10, such that
k C k  0, k⌫C k  1, and k⌫†C k  10
hold for all time steps C = 0, . . . ,) 1, where ⌫† C
denotes the Moore–Penrose inverse of matrix ⌫C . Furthermore, there exists a positive constant f such that
fmin (" (C, 3)) f holds for all time steps C = 0, . . . ,) 3, where 3 denotes the controllability index.
Note that Assumption 2.2 implies fmin (" (C, ?)) f for all ? 3 because appending more columns to a 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, 3, 4, 7]. 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 a trajectory tracking problem with LTV dynamics and well-conditioned costs, which generalizes the standard linear quadratic tracking problem in [4, 30] with LTI dynamics and quadratic costs. We adopt LTV dynamics GC+1 = CGC + ⌫CDC + FC and general well-conditioned cost functions 5C (·), 2C (·) (see Assumption 2.1). With the desired trajectory 31:) , we consider a new state G̃C := GC 3C and a new disturbance F̃C := FC + C3C 3C+1. Thus, using the new state and disturbance, the problem naturally fits into our problem setting with : future predictions of ( C , ⌫C ,FC , 5C , 2C , 3C+1). Note that predictive control with LTV dynamics is practical in nonlinear systems [13, 31] because the nonlinearity could be well approximated by LTV models [31]. Example 2.2 (Power grid frequency regulation). Consider the frequency regulation problem in [8], where state G = [\>,l>]> represent the status of a power plant, and power generation ?in 2 R= is the control action. The continuous-time dynamics is given by §\
§l
|{z} §G (C)
= 
0
" (C) 1! " (C) 1⇡
| {z }
̂(C)
 \
l |{z} G (C)
+  0
" (C) 1
| {z } ⌫̂ (C)
?in|{z} D (C) .
Algorithm 1 Predictive Control (%⇠: ) 1: for C = 0, 1, . . . ,) : 1 do 2: Observe current state GC and receive predictions oC:C+: 1. 3: Solve and commit control actions DC := k̃:C (GC ,FC:C+: 1; )E0 . 4: At time step C = ) : , observe current state GC and receive predictions oC:) 1. 5: Solve and commit control actions DC:) 1 := k̃:C (GC ,FC:) 1; 0)E0:: 1 .
Here " (C) denotes the rotational inertia matrix, which is time-varying and is determined by the proportion of renewable power in total power generation at time C, and can be accurately predicted in a certain time horizon [32, 33]; ! and ⇡ are known system parameters. Using standard discretization techniques, we can formulate a discrete-time linear time-varying system GC+1 = CGC + ⌫CDC + FC , where C and ⌫C are determined by ̂(C) and ⌫̂(C). 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 C and ⌫C in the near future due to predictablity of " (C).

heading: 2.2 Predictive Control
text: We study a classical predictive control (PC) algorithm inspired by model predictive control, which solves the optimization problem of : future time steps (where : 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 as %⇠: .
More formally, At time step C < ) : , %⇠: solves the optimization problem k̃:C (GC ,FC:C+: 1; ). Since we need to consider horizon lengths other than : , for arbitrary ? 1 and time step C, we define the optimization problem k̃?
C (G, Z ; ) as
k̃ ? C (G, Z ; ) := arg min
H0:? ,E0:? 1 ?’ g=1 5C+g (Hg) + ?’ g=1 2C+g (Eg 1) + (H: )
s.t. Hg = C+g 1Hg 1 + ⌫C+g 1Eg 1 + Zg 1, g = 1, . . . , ?, (2) H0 = G,
where G 2 R= is the initial state, Z 2 (R=) ? (indexed by 0, . . . , ? 1) is a sequence of disturbances, and : R= ! R is a standard terminal cost function regularizing the final state. Here we additionally require that the terminal cost has the form (G) = U(kGk), where U : R 0 ! R 0 is a convex Kfunction (i.e. continuous increasing function with 0 at the origin, see Appendix A for definition) that is twice continuously differentiable. For each time step g = 1, . . . , : , Hg 2 R= is the predictive state, and Eg 2 R< is the predictive control action. To make the algorithm well-defined, at time step C = ) : , %⇠: can finish the rest of the trajectory optimally by committing D) ::) 1 = k̃(G) : ,F) ::) 1; 0). The pseudo-code of predictive control is given in Algorithm 1.
It is also important in our framework to study the behavior of predictive control under some fixed terminal point. So, for prediction length ? 1 and time step C, we define an auxiliary optimization problem with a strict terminal constraint H? = I as follows:
k ? C (G, Z , I) := arg min
H0:? ,E0:? 1 ?’ g=1 5C+g (Hg) + ?’ g=1 2C+g (Eg 1)
s.t. Hg = C+g 1Hg 1 + ⌫C+g 1Eg 1 + Zg 1, g = 1, . . . , ?, (3) H0 = G, H? = I,
where the optimal value is denoted by ]? C (G, Z , I). We define this auxiliary optimization problem besides k̃? C (G, Z ; ) because we need to fix both the initial state and the terminal state, for example, when expressing a sub-trajectory of the offline optimal trajectory as the solution of an optimization problem. k 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 of dynamic regret (Theorem 4.2) and competitive ratio (Theorem 4.3).
Throughout the paper, we use {(GC , DC )}) C=1 to denote the trajectory of predictive control, and use {(G⇤ C , D ⇤ C )})
C=1 to denote the offline optimal trajectory (i.e., the optimal solution of (1)). We also use several standard definitions and notations in linear algebra and optimization, which we detail in Appendix A 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 sup
G (0) ,F cost( !⌧) cost($%)) (the additional cost of our algorithm
against the optimal algorithm) and competitive ratio sup G (0) ,F cost( !⌧) cost($%) ) (the worst-case ratio of the cost of our algorithm over that of the optimal algorithm).

heading: 3 A Perturbation Approach
text: In order to study the regret and competitive ratio of controllers in LTV systems, we develop a new analysis based on a perturbation approach, which we introduce in this section. This approach is based on developing bounds on how much the solutions to (2) and (3) 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 a finite horizon whereas the incremental stability focuses on asymptotic behavior over an infinite horizon. Simply stated, the key to 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 input, while the perturbation occurs at the g-th time step, then the impact on the target variable is exponentially small with respect to the time difference |⌘ g |. Proving such a result directly is challenging because of the complexity of the LTV dynamical constraints in (2) and (3). Thus, we develop a novel reduction from LTV systems to fully-actuated systems, i.e., systems where the controller can steer the system to any state in the whole space R= freely at every time step. This special case is a form of online optimization called smoothed online convex optimization (SOCO), and has received considerable attention recently, e.g., [24, 27, 35]. We exploit the controllability of the dynamics to analyze the LTV system in chunks of 3 time steps. A sequence of 3 time steps combined together can be thought as a fully-actuated system and thus we can formulate a SOCO problem, which is (1/3)-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.

heading: 3.1 Smoothed Online Convex Optimization
text: The classic setting of SOCO is an online game played by an agent against an adversary: at each time step C, the adversary reveals a hitting cost function 5̂C , a switching cost function 2̂C , and a disturbance (or exogenous input) F̂C . The agent picks a decision point ĜC 2 R=, and incurs a stage cost of 5̂C (ĜC ) + 2̂C (ĜC , ĜC 1, F̂C 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 offline optimal solution. These results are critical for deriving the guarantees for predictive control in the online setting in Section 4.
To begin, observe that when the initial state Ĝ0, terminal state Ĝ? , and the disturbances F̂ are given, the optimal ?-step trajectory of SOCO can be obtained from the unconstrained optimization problem
k̂(Ĝ0, F̂, Ĝ?) := arg min Ĝ1:? 1 ? 1’ g=1 5̂g (Ĝg) + ?’ g=1 2̂g (Ĝg , Ĝg 1, F̂g 1), (4)
where the objective is a convex function of the decision variables Ĝ1:? 1. Since (4) is an unconstrained optimization problem, the gradient of its objective equals zero at k̂(Ĝ0, F̂, Ĝ?). Using this, we can further show that the directional derivative of k̂(Ĝ0, F̂, Ĝ?) along some direction 4, denoted by j, satisfies the linear equation "j = X, where symmetric matrix " is the Hessian of the objective and vector X is determined by the direction 4. A special structure of the objective of (4) is that the correlations only occur in two consecutive time steps. This implies that its Hessian " is block
tri-diagonal. Such tri-diagonal structure of " has been noted by previous work, e.g. [36], and have been leveraged to solve the linear equation "j = X quickly. In contrast, we focus on the exponential decay phenomena " 1 exhibits, i.e., the magnitudes of entries decay exponentially with respect to their distances to the main diagonal [37]. Bounding each entry of j = " 1X separately gives us the following perturbation bound. We state this result formally in Theorem 3.1, and its proof can be found in Appendix B. Theorem 3.1. Given a tuple (Ĝ0, F̂, Ĝ?) that contains the initial state, the disturbances, and the terminal state in this order, we consider the optimal solution of the SOCO problem
k̂(Ĝ0, F̂, Ĝ?) := arg min Ĝ1:? 1 ? 1’ g=1 5̂g (Ĝg) + ?’ g=1 2̂g (Ĝg , Ĝg 1, F̂g 1)
indexed by 1, . . . , ? 1. Assume 5̂g : R= ! R is `-strongly convex, 2̂g : R= ⇥ R= ⇥ RA ! R is convex and ✓-strongly smooth, and both are twice continuously differentiable for g = 1, . . . , ?, then
k̂(Ĝ0, F̂, Ĝ?)⌘ k̂(Ĝ 00, F̂0, Ĝ 0?)⌘  ⇠0 _ ⌘ 1 0 Ĝ0 Ĝ 00 + ? 1’ g=0 _ |⌘ g | 1 0 F̂g F̂0g + _? ⌘ 1 0 Ĝ? Ĝ 0?
!
for all 1  ⌘  ? 1, where ⇠0 = (2✓)/` and _0 = 1 2 · ⇣p 1 + (2✓/`) + 1 ⌘ 1 .
As a remark, we do not require the hitting cost 5̂g to be strongly smooth, or the switching cost 2̂g to be strongly convex in Theorem 3.1. This makes the assumptions on the SOCO costs 5̂g , 2̂g weaker than the assumptions on the LTV costs 5g , 2g defined in (1).

heading: 3.2 Linear Time-Varying System
text: We now build upon the SOCO perturbation result to derive a perturbation result for LTV systems. In particular, we show an exponentially-decaying 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 GC+1 freely at a given state GC . We overcome this obstacle by redefining the decision points as illustrated in Figure 1. Specifically, given state GC at time step C as the last decision point, we then ask the online agent to decide state GC+3 at time step (C + 3) rather than GC+1 at time step (C + 1). Since 3 is the controllability index, GC+3 can be picked freely from the whole space R= regardless of GC . We also utilize the principle of optimality, e.g. if H0:: , E0:: 1 is the optimal solution to k:C (G, b, I), then H8: 9 , E8: 9 1 is the optimal solution to k 9 8 C+8 (H8 , b8: 9 1, H 9 ) for any 0  8 < 9  : . Therefore, the trajectory between time C and (C + 3) can be recovered by solving k3 C (GC ,FC:C+3 1, GC+3). So we are able to formulate a valid SOCO problem on the sequence of time steps C, C + 3, C + 23, . . . . Naturally, the hitting cost at time step (C + 3) remains the same, while the switching cost becomes b 3
C (GC ,FC:C+3 1, GC+3), where the function b ?C is defined as
b ? C (G, Z , I) := ]? C (G, Z , I) 5C+? (I). (5)
An illustration of the reduction can be found in Figure 1. We would like to point out that our 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 to the reduction via control canonical forms in [3] that is specific to LTI systems. Unlike the switching costs in [14, 27, 35, 38] which are explicitly defined as the ✓2-distance or squared ✓2-distance, the switching cost b ? C here is defined implicitly as the optimal value of an optimization problem. Lemma 3.2 shows that the switching cost defined in (5) satisfies the requirements of Theorem 3.1, which allows us to obtain the desired perturbation bound. Lemma 3.2. Under Assumption 2.1 and 2.2, for integer ? 3, we have
1. k? C (G, Z , I) is !1 (?)-Lipschitz in (G, Z , I);
2. b ? C (G, Z , I) is convex and !2 (?)-strongly smooth in (G, Z , I).
Here !1 (?) = ⇠ (?) (1 + ✓ · ⇠ (?)/<2), !2 (?) = ✓ · ⇠ (?)2 + ✓2 · ⇠ (?)4/<2 , where ✓ = max(✓ 5 , ✓2),
⇠ (?) = 8>>< >>: $ (03?) if 0 > 1; $ (?2) if 0 = 1; $ (1) if 0 < 1.
In Lemma 3.2, we use $ (·) to hide quantities 0, 1, and 1/f; the precise expression of ⇠ (?) and the proof of Lemma 3.2 can be found in Appendix C. Using the reduction from LTV to SOCO, we obtain a perturbation bound for the LTV systems (2) and (3) in Theorem 3.3, the proof of which is deferred to Appendix D. Theorem 3.3. Consider the optimization problem defined in (2) and (3) and with a horizon length ? 3. Under Assumptions 2.1 and 2.2, given any (G, Z , I) and (G 0, Z 0, I0),
k̃
? C (G, Z ; )H⌘ k̃ ? C (G 0, Z 0; )H⌘  ⇠ _ ⌘ kG G 0k + ? 1’ g=0 _ |⌘ g |
Zg Z 0g !
k
? C (G, Z , I)H⌘ k ? C (G 0, Z 0, I0)H⌘  ⇠ _ ⌘ kG G 0k + ? 1’ g=0 _ |⌘ g | Zg Z 0g + _? ⌘ kI I0k
!
hold for all time steps C. Here we define !0 = max3?23 1 !2 (?), and the constants are given by
_ = ✓ 1 2 ⇣p 1 + (2!0/<2) + 1 ⌘ 1◆ 123 1 ,⇠ = 2!0
<2
· ✓ 1 2 ⇣p 1 + (2!0/<2) + 1 ⌘ 1◆ 1 .
Theorem 3.3 allows us to bound the distance between any two trajectories so long as they can be expressed as the optimal solutions of the optimization problem (2) or (3). For example, to bound the norm of each state in the predictive trajectory k̃?
C (G, Z ; ), we only need to set G 0 = 0, Z 0 = 0 in the
first inequality because an all zero trajectory can be expressed as k̃? C (0, 0; ). The formal statement of this result can be found in Appendix E.

heading: 4 Performance Guarantees for Predictive Control
text: 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 is the following: at time step C, if the predictive controller with prediction window : is given the knowledge of G⇤
C and G⇤
C+: , it can fully recover the offline optimal states and control inputs for the future : time steps, G⇤
C+1:C+: and D ⇤ C:C+: 1, from k : C (G⇤ C ,FC:C+: 1, G⇤
C+: ). However, without the knowledge of the offline optimal states, the predictive controller solves k:
C (GC ,FC:C+: 1, GC+: ) instead, where GC+: is implicitly determined by
the :-th predictive state of k̃: C (GC ,FC:C+: 1; ). We overcome this gap with our perturbation approach (specifically, Theorem 3.3 and its corollaries), which allows us to bound the distance between the controller’s trajectory and the offline optimal trajectory.

heading: 4.1 Dynamic Regret
text: We first bound the dynamic regret of predictive control. For this analysis, a key observation is that the offline optimal trajectory is given by G⇤ = k̃)
0 (G0,F0:) 1; 0)H1:) . Furthermore, the optimal trajectory
starting at time step C with state GC is equivalent to the trajectory of predictive control with prediction window () C) and no terminal cost, i.e. k̃) C
C (GC ,FC:) 1; 0)H1:) C . Using Theorem 3.3, we can bound
the change in decision points against the change in prediction window : . Lemma 4.1 formalizes this: Lemma 4.1. For any integers ?, ⌘ such that ? ⌘ 1 and time step C < ) ?, we have k̃?
C
GC ,FC:C+? 1; H⌘ k̃?+1 C GC ,FC:C+?; H⌘
 2⇠_? ⌘ ✓ ⇠_ ? kGC k + 2⇠
1 _ sup 0g) 1
kFg k ◆ .
Then, we can follow the road map below to bound the dynamic regret of predictive control %⇠: :
(a) Given the well-conditioned state/control costs, it suffices to bound the distance between %⇠: ’s trajectory and the offline optimal trajectory (i.e.,
GC G⇤C
) to show the dynamic regret result. See inequalities (22) and (23) in Appendix H for technical details.
(b) At each time step C, the optimal next state (under an imaginary terminal cost ) from the current state GC is given by k̃) CC (GC ,FC:) 1; )H1 . However, reaching the optimal next state from GC requires full knowledge of the future costs, dynamics, and disturbances. Although %⇠: cannot reach the optimal next state due to incomplete knowledge of the future, it can leverage the predictions of future : steps to decide a near-optimal control action from state GC . By cumulatively summing up the bounded difference in Lemma 4.1 and applying Theorem 3.3, one can show the suboptimality, measured by the distance
GC+1 k̃) CC (GC ,FC:) 1; )H1 , is in the order of $ (_: ). See inequality (19) in Appendix H for technical details.
(c) Using the exponentially-decaying LTV perturbation bound in Theorem 3.3, we can convert the per-step suboptimality bounds to a global suboptimality bound on
GC G⇤C
that is also in the order of $ (_: ). See inequalities (20) and (21) in Appendix H for technical details.
The $ (_: ) upper bound on the distance between the algorithm’s trajectory and the offline optimal trajectory leads to the regret bound in Theorem 4.2. Theorem 4.2. Suppose kFC k  ⇡ for some constant ⇡ at each time step C. Let _,⇠, !0 be the decay rate and constants defined in Theorem 3.3. If prediction window : 3 is sufficiently large, such that
: 1 + log ✓ 1 1 X · ⇠ ✓ 2⇠ 1 _ + _ ◆◆ log ✓ 1 _ ◆ (6)
for some positive constant X 2 (0, 1), then the trajectory of %⇠: satisfies: 1. (Input-to-state Stability) The norm of each state GC is upper bounded by
kGC k  8>>< >>: ⇠ X · (1 X)max(0,C :) kG0k + 2⇠ X (1 _)
⇣ 1 + 2⇠
1 _
⌘ ⇡ if 0 < C  ) :
⇠ 2 X · (1 X)) 2:_C+: ) kG0k +
⇣ 2⇠ 2
X (1 _)
⇣ 1 + 2⇠
1 _
⌘ + 2⇠
1 _
⌘ ⇡ if ) : < C  ) .
2. (Dynamic Regret) The dynamic regret of %⇠: is upper bounded by
cost(%⇠: ) cost($%)) = $ ✓ ⇡ + _
: (kG0k + ⇡) X
◆2 _ : ) + _: kG0k2 ! ,
where the notation hides quantities 0, 10, ✓ 5 , ✓2 , ⇠, 1/(1 _) and !0.
An implication of Theorem 4.2 is that to obtain >(1) dynamic regret when the norm of disturbances are uniformly upper bounded, it suffices to use a prediction window of length ⇥(log)). This parallels the result shown in [4], although in a more general setting.

heading: 4.2 Competitive Ratio
text: We now focus on bounding the competitive ratio of predictive control.Here, we study a modification of the predictive control algorithm we have considered to this point. In particular, we introduce a
Algorithm 2 Predictive Control with Replan Window ⌘ (%⇠(: ,⌘) ) 1: Suppose ) = =0⌘ + <0, where integers =0 0, : ⌘ + 1  <0  : . 2: for C = 0, ⌘, . . . , =0 (⌘ 1) do 3: Observe current state GC and receive predictions oC:C+: 1. 4: Solve and commit control actions DC:C+⌘ 1 := k̃:C (GC ,FC:C+: 1; )E0:⌘ 1 . 5: At time step C = =0⌘, observe current state GC and receive predictions oC:) 1. 6: Solve and commit control actions DC:) 1 := k̃<0C (GC ,FC:) 1; 0)E0:< 0 1 .
replan window ⌘, as defined in Algorithm 2 which we denote as %⇠(: ,⌘) . This style of algorithm has been considered previously in the SOCO literature, where it has been shown to obtain a 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 a potential method building on [40]. We define the potential function as the squared distance between the algorithm’s trajectory and the offline optimal trajectory, i.e., qC (GC , G⇤C ) = GC G⇤C 2 , which is standard in the literature [5, 14, 27]. We study how this potential function changes over time. Intuitively, we need to upper bound the increment of this potential function by the offline optimal cost to obtain a competitive ratio result. To achieve this, the algorithm needs to “move closer” to the offline optimal trajectory rather than “moving further away” from it. Recall that Theorem 3.3 gives that
k : C (GC ,FC:C+: 1; )H⌘ k:C (G⇤C ,FC:C+: 1; )H⌘  ⇠_⌘ GC G⇤C . (7) When the algorithm commits the first predictive state (⌘ = 1), the left hand side of (7) might be larger than
GC G⇤C
when ⇠_ > 1. Thus, the algorithm must “wait” until the right hand side of (7) becomes smaller than
GC G⇤C
. This is accomplished in Algorithm 2 via the replan window ⌘. Our main result for this section is the following competitive ratio bound for %⇠(: ,⌘) . Theorem 4.3. Let _,⇠, !0 be the decay rate and constants defined in Theorem 3.3. In Algorithm 2, if the replan window ⌘ satisfies ⌘ max{log ((1 + Y)⇠)/log (1/_), 3} for some positive constant Y, and the prediction window : satisfies : ⌘ + 3, then it has competitive ratio
sup
G (0) ,F
cost(%⇠(: ,⌘) ) cost($%)) = 1 +$ Y 1 ✓ !0 + ✓ 5 < 5 ◆ 1/2 · ⇠_: 1 ⌘ ! ,
where the notation only hides a small numerical constant.
Note that when the constant Y and the replan window ⌘ are fixed, the competitive ratio is on the order of 1 + $ (d: ) as 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 so as to eliminate the requirement on ⌘.

Review summaries:
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.   Update: The reviewers adequately addressed my concerns, and I am ammending my review to an 8. 

This article studies finite-time horizon   predictive control for linear systems with time-varying and strongly convex costs. The authors assume that each time points,  the system coefficients and  the random disturbance of the state dynamics at the next $k$ time steps can be observed exactly, based on which the controller choose the current action. By reformulating the control problem as an equivalent optimisation problem,  the authors establish a perturbation bound of the algorithm,  and further analyze the dynamic regret and competitive ratio. 

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. 

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.  The 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)$.  To 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.