Bounded-Regret MPC via Perturbation Analysis: Prediction Error, Constraints, and Nonlinearity
Authors: Yiheng Lin
Yang Hu
Guannan Qu
Tongxin Li
Adam Wierman
Venue: NeurIPS 2022 Accept (2022)
Keywords: Model Predictive Control
Regret
Perturbation Analysis
Prediction Error

Abstract: We study Model Predictive Control (MPC) and propose a general analysis pipeline to bound its dynamic regret. The pipeline first requires deriving a perturbation bound for a finite-time optimal control problem. Then, the perturbation bound is used to bound the per-step error of MPC, which leads to a bound on the dynamic regret. Thus, our pipeline reduces the study of MPC to the well-studied problem of perturbation analysis, enabling the derivation of regret bounds of MPC under a variety of settings. To demonstrate the power of our pipeline, we use it to generalize existing regret bounds on MPC in linear time-varying (LTV) systems to incorporate prediction errors on costs, dynamics, and disturbances. Further, our pipeline leads to regret bounds on MPC in systems with nonlinear dynamics and constraints.

Bounded-Regret MPC via Perturbation Analysis: Prediction Error, Constraints, and Nonlinearity
Yiheng Lin California Institute of Technology Pasadena, CA, USA yihengl tea...ch...hhceeeeeeeeeeee edu
Yang Hu
Harvard University Cambridge, MA, USA yanghuōg. harvard.
Guannan Qu
Tongxin Li
Carnegie Mellon University Pittsburgh, PA, USA gqučandrew. cmu edu
The Chinese University of Hong Kong (Shenzhen) Shenzhen, Guangdong, China
litongxin@cuhk. edu. cn
Adam Wierman
California Institute of Technology
Pasadena, CA, USA adamw@caltech. edu
Abstract
We study Model Predictive Control (MPC) and propose a general analysis pipeline to bound its dynamic regret. The pipeline first requires deriving a perturbation bound for finite-time optimal control problem. Then, the perturbation bound used to bound the per-step етгог of MPC, which leads regret. Thus, our pipeline reduces the study of MPC to the well-studied problem of perturbation analysis, enabling the derivation of regret bounds of MPC under a variety of settings. To demonstrate the power our pipeline, we use it to generalize existing regret bounds MPC in linear time-vary vvrring (LTV) systems incorporate prediction errors on costs, dynamics, and disturbances. Further, our pipeline leads regret bounds MPC in systems with nonlinear dynamics and constraints.
bound the dynamic
Introduction
Model Predictive Control (MPC) is optimal control approach that solves Finite-Time Optimal Control Problem (FTOCP) using future predictions in a receding horizon manner [0] It is a flexible approach that is able accommodate nonlinear and time-varying dynamics, state and actuation constraints, and general cost functions (255 As a result, it is broadly applied in wide spectrum of
control problems, including robotics C 10 autonomous vehicles (1H17 power systems [18
process control 27) etc.
Despite the popularity of MPC, its theoretic analysis has been quite challenging. Early works along this line focused on the stability and recursive fcasibility MPC been tremendous interest in providing finite-time dearning-theoreti performance guarantees for MPC, such as regret and/or competitive ratio bounds 332 33
[1) More recently, there has
For example, progress has recently been
"This work supported by NSF Grants CNS 2146814, CPS-2136197. CNS 2106403, NGSDI-2105648. EPCN-2154171, with additional support from Amazon AWS, Yiheng Lin was supported by Kortschak Scholars program. Tongxin Li was supported by the start-up up funding UDF01002773 of CUHK-Sh Shenzhen.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

made toward (i) regret analysis of MPC in linear time-invariant (LTT) systems with prediction errors on the trajectory to track [34]. (ii) the dynamic regret and competitive ratio bounds of MPC under linear time-varying (LTV) dynamics with exact predictions [35. and (iii) exponentially decaying perturbation bounds of the finite-time optimal control problem in time-varying, constrained, and
37 Beyond MPC, providing regret and/or competitive ratio guarantees for a variety of (predictive) control policies has been a focus in recent years. Examples include RHGC !0 for online control/optimization with prediction horizons, OCO-based controllers 44 for no-regret online control, and variations of ROBD for competitive online
non-linear systems [66
B8 [3] and AFHC 12
control without predictions
4 with delayed observations 44 In addition, regret lower bounds have been studied in known LTI systems [46] and unknown LTV systems (7).
[
A promising analysis approach that has emerged from the literature studying MPC and, more generally, predictive control, is the use of perturbation analysis techniques, or more particularly, the use of so-called exponential decaying perturbation bounds. Such techniques underlie the results in This research direction is particularly promising since perturbation bounds exist for FTOCP in many dynamical systems, e.g., 52,, and thus it potentially allows the derivation of regret and/or competitive ratio bounds in a variety of settings. However, to this point the approach has only yielded results in unconstrained linear systems with no prediction errors (e.g.. 135), and often requires adjusting MPC to include a counter- souuter-intuitivlly large re- re-planning window due to technical challenges in the analysis (e.g.. 48
Thus, though perturbation analysis techniques might seem promising, many important questions about applying them for the study of predictive control remain open. Firstly, one of the major reasons for the extensive application of MPC is its flexibility in incorporating constraints and nonlinear dynamics 533 However, none of the existing results and approaches can analyze the performance of MPC under constraints and/or nonlinear dynamics. In fact, the anlyasis of MPC under constraints or nonlinearity has long been known to be challenging because of the intractable form of cost-to-go functions and optimal solutions. Secondly, prediction error is inevitable for real-world implementations of MPC due to unpredictable noise and model mismatch, yet the analysis of MPC subject to prediction errors is limited. Thirdly, existing approaches analyze MPC in a case- by-c manner and, in most cases, the analysis framework is specific to the assumptions of the particular case (e.g. quadratic costs, perfect predictions, etc) in a way that does not generalize to other settings B3
Contributions. In this paper, we propose general analysis pipeline (Section 3 that converts perturbation bounds for an FTOCP into dynamic regret bounds for MPC across a variety of settings. More specifically, the pipeline consists of three steps (see Figure Dp. In Step I, we obtain the required perturbation bounds for the specific setting. In Step 2, as shown in Lemma 3. the perturbation bounds are used to bound the per-step error, which is defined to be the error of the MPC action against the clairvoyant optimal action (see Definition 3.T.. In Step 3, the per-step error bound is converted to dynamic regret bound for MPC, as shown in Lemma 32 The full pipeline is summarized into a Pipeline Theorm (Theorem 3.3). which directly converts perturbation bounds into bounds on the dynamic regret of MPC in general settings, including those with time-variation prediction error, constraints, and nonlinearities. The key technical insight that enables the pipeline is the following recursive relationship between Step 2 and Step 3 (Lemma 3.] and Lemma 3.2p: Step 2 guarantees a "small" per-step error e once the current state 24 of MPC "near" the offine optimal trajectory (OPT), while Step 3 guarantees the next state 1 of MPC will be near OPT if all previous per-step errors (fer Fre)) are small. Thus Step 2 and Step 3 work together to guarantee MPC states are always near OPT and thus MPC per-step errors are always small (Theorem 3.3).
To demonstrate the power of the proposed pipeline, we apply it to a range of settings, as summarized Our first applications are to two settings with linear time-varying (LTV) dynamics and
in Table I prediction errors on (i) disturbances, Section 4.1 and (ii) the dynamical matrices and cost functions, results in the LTV setting of the disturbances and of the dynamics. To the best of our knowledge, our work provides the first regret result for MPC with prediction error on the dynamics (see Theorem 4.2 result that enables
Section 4.2 The
(35), which requires exact knowledge
the bounds in settings where MPC is applied to learned dynamics
Our second application is to setting with nonlinear dynamics and constraints (Section 5 We show the first dynamic regret bound for MPC under state and actuation constraints in nonlinear systems with general costs (Theorem 5.1. Very few prior results exist for MPC in this setting, even with nonlinear dynamics or constraints individually. The most related works are 48), which studies constrained
2

---

MPC, and 4 which studies nonlinear MPC. In both cases, counter- intuitive re re-planning window added MPC facilitate the analysis, downside that our pipeline could avoid. Besides, FX and 49 require exact predictions of the cost functions, dynamics, and constraints for the exponential convergence property of MPC to hold, while our result can apply to more general noisy predictions.
2 Preliminaries
In this section, we first introduce the general predictive online control problem including the settings, the objective, available information, and the predictive controller class. Then, introduce the MPC algorithm, which is a widely-used predictive controller that we focus on this work. Specifically, consider general, finite-horizon, discrete-time optimal control problem with fime-varying costs, dynamics and constraints, namely
min SorT:MorT--
Σ fa ue: Ei) + Fr(er:
s.t. 1 (xr, uri Ei),
vO <t 4A STT
8e (4: S S0,
(1)
250 x()).
Here, I; E R" is the state, ut IR is the control input or action; fr is a time-varying stage cost function, 9t time-varying dynamical function, and 5t is time-varying constraint function, all parameterized by ground-truth parameter ç (unknown to an online controller); and Fr is terminal cost function parameterized by ς that regularizes the terminal state.
The offline optimal trajectory OPT is obtained by solving ① with the full knowledge of the true parameters Süzz- In contrast, an online controller can only observe noisy estimations of the parameters fixed prediction horizon to decide its current action u, at each time step For example, MPC picks by calculating the optimal sub-trajectory confined to the prediction horizon. The objective to design an online controller that can compete against the offline optimal trajectory OPT. We use dynamic regret as the performance metric, which is widely used to evaluate the performance of online controllers/algoriims in the literature of online control 32
35 and online optimization 38 4 555. Specifically, for concrete problem instance (x:0), (i.r), let cost(OPT) denote the
total cost incurred by OPT, and cost (Ast(A denote the total cost incurred by an online controller ALG. The dynamic regret is defined the worst-case additional cost incurred by ALG against OPT, ie., SUPx(00)6G. (cost(ALG) (ALG) - cost(OP) (OPT))
The formulation in I general enough to include a variety of challenging settings. In this paper, we consider three important settings illustrate how to apply our analysis pipeline. The settings differ (a) the form of costs, dynamics, and constraints, and (b) the quantities in the system to be predicted (i.e., parameterized by {?), and the prediction error allowed. An overview of the settings is presented in Table below.
Table 1: Overview of the settings considered in this paper
Section
Costs
Dynamics
Constraints
Prediction &
Prediction error arbitrary
4.1
dccomposable
LTV
none
disturbance: wt
cost: Qe, Re, R.
4.2
quadratic
LTV
none
dynamics: Ar, B:
sufficiently small
cost: ft
non-linear time-varying
non non-linear stage constraint
general
dynamics: g+
sufficiently small
constraints: 88:
In each setting, we impose different assumptions cost functions, dynamical systems, constraints, and properties of the predicted quantities as functions of parameter & In general, we require well- defined costs, Lipschitz and uniformly controllable dynamics, and Lipschitzness of the predicted quantities with regard to & For constraints, additional assumptions characterizing the active con- straints along and near the optimal trajectory imposed. Detailed definitions and statements deferred to Appendix B and Sections B and [ To facilitate the statement of the pipeline, we assume the following universal properties hold throughout the paper:
Stability of OPT: there exists a constant D=- such that ||أح||| || S Dr- for every state at on the offline optimal trajectory OPT.
3

---

Lipschitz dynamics: the ground truth dynamical function 9e(,, (7) is Lipschitz in action; i.e. for any feasible 2t, u, u/e 9t. satisfies [9: u4: E2) gr (Tt, u/: 57) I Lg l|4, -4i1-
Well-conditioeed costs: every stage cost fe(' * and the terminal cost (r) are nonnega- tive, convex, and E-smooth in (22,, ue) and Fr, respectively.
2.1 Predictive Online Control
While Step (Lemma 3.2 in our pipeline can be generally applied to all online controllers, in the subsequent applications focus Model Predictive Control (MPC), popular classical controller. In this subsection, we first define the available information (predictions) as well as its quality (prediction power), and how general predictive online controllers make decisions. Then, define useful optimization problem called FTOCP, and introduce MPC as a predictive online controller.
We represent the uncertainties in cost functions, dynamics, constraints, and terminal costs as function families parameterized by &r: Jr == { uri Er) & E E.h. = {ge (Iz, uei &t) & E Er), S, == {Sr(Z,, Mei & Ex), and FT = (Tr(TT {T) ET E ET}. The online controller knows the function families Fo.T, G0.T-1, and SO.T-1 as prior knowledge, but does not know the true parameters fürr E II - E, Instead, at time step t. the online controller has access to noisy predictions of these parameters for the future k time steps (where is called the prediction horizon), represented by Stæ+Rje= E II E,. The parameter space E, at each time step may have different dimensions.
We formally define the quality of predictions by introducing the following notion of prediction error. Definition 2.1. The prediction ervor is defined as Pt.r == ||EE++| Ei+zll for an integer T 2 0. The power of r-step-away predictions (for parameter {) is defined as P(r) = Ei pt.
Under this noisy prediction model, a general predictive online controller ALG decides the control action based on the current state and the latest available predictions of future parameters. We formally define the class of predictive online controllers considered in this paper in Definition 2.2 which includes MPC as a special case.
Definition 2.2. A predictive online controller ALG is a function that takes the current state I, and the available predictions bu:c+/ee inputs at time and outputs the current control action wt iee.
21
ALG( R()) We use 20
_ - ui denote the offline optimal trajectory OPT.
I1
WT denote the trajectory achieved by 161 wP-1
ALG, and use xo xi
Mo
wi
core component of both the design of online controllers and our analysis is the following finite-time optimal control problem (FTOCP). Given time interval [t, t2l, the FTOCP solves the optimal sub-trajectory subjected to the given initial state 2, terminal cost F, and sequence of (potentially noisy) parameters E1,:t=11, Sta formalized in the following definition.
Definition 2.3. The finite-imee optimal control problem (FTOCP) over the horizon [ti t2), with initial stute z, parameters Etytt-11 and Sty, and terminal cost F(::), is defined as
b21 Σ Se (x) + ((UtsiSe))
min Weisty 1erttt- 1 t=
s.1. Me+1 = 9r(u,, 0z; Ex),
4h S < l2,
81 se Uzj E.) < 0, y/ =
4h S l2,
and corresponding optimal solution as V/3 (z, -1, Stz F). We shall use the shorthand notation Vi (z, Eti:ti F) = V En:ttt11111.. Fx;; when the context is clear.
Note that the formulation of the FTOCP in Definition 2.3 does not include a terminal constraint set. To compensate for this, we allow the terminal cost F(; to take value +oo in some subset of R., and G12 is not necessarily element in E,g- For example, terminal cost function that we frequently use later is the indicator function of the terminal parameter Stg, where Go RR... We use to denote such indicator terminal cost (i.c., 1( Gra) 0 if yt, Sta and 1(yt St,) + otherwisc).

---

Finally, given the definition of the FTOCP, we are ready to formally introduce MPC. The pseudocode of this online controller is given in Algorithm [ Basically, at time step t, MPC; solves k-step predictive FTOCP using the latest available parameter predictions, and commits the first control action in the solution. When there are only fewer than & steps left, MPC, directly solves (T ()-step FTOCP at time until the end of the horizon, using the predicted real terminal cost Pr(::TTj) This MPC controller (and its variants) has a wide range of woal-world applications.
Algorithm Model Predictive Control (MPCs)
Require: Specify the terminal costs F; for & SL<T.
1: for = 0, 1, ....,
1 do
2: t' 4 min(t + k. T
3: Observe current state 2t and obtain predictions St:a//e-
4: Solve and commit control action u, == vi (Ze, Etarles Fv vv..
3
The Pipeline: Bounded Regret via Perturbation Analysis
The goal of this section is to give an overview of a novel analysis pipeline that converts perturbation bound into bound on the dynamic regret. We begin by highlighting the form of perturbation bounds required in the pipeline, and then describe the 3-step process of applying the pipeline. In subsequent sections, we apply this pipeline to obtain new regret bounds for MPC different settings.
3.1 Per-Step Error and Perturbation Bounds
key challenge when comparing the performance of an online controller against the offline optimal trajectory is that the online controller's state mı is different from the offline optimal state x; at time step 1. Due to such discrepancy in states, we cannot simply evaluate the online controller's 's action we via comparison against the offline optimal action ut. To address this challenge, our pipeline uses the notion of per-step error (Definition 3.T inspired by the performance difference lemma and its proofs in reinforcement learning (RL) 551 Specifically,
compare u, the clairvoyant optimal action one may adopt at the same state x; if all true future parameters fir are known, which leads to the definition of per-step error as follows.
Definition 3.1. The per-step error incurred by a predictive online controller ALG at time step t is defined as the distance between its actual action u, and the clairvoyant optimal action, i.e.,
E = ||ue oe (æx, Eiri Fr)v, II where = ALG E1.++))).
The clairvoyant optimal trujectory starting frottnngfommmm Dy is defined as T = w/ (Iets Steri FT Frr
Note that the clairvoyant optimal trajectory can be viewed as being generated by an MPC controller with long enough prediction horizon and exact predictions. This notion highlights the reason why MPC can compete against the clairvoyant optimal trajectory, since the per-step error in system controlled by MPC; becomes e = || w (zz, &nit+ Ft+*).. vi (z,, Etr: Fr) || Intuitively, the per-step eтror converges to zero as the prediction horizon & increases and the quality of predictions improves (i.e. [ &
0).
This intuition highlights the important role of perturbation bounds in comparing online controllers against (offline) clairvoyant optimal trajectories. As we have discussed in Section [ many previous 4 49 have established (local) decaying sunsitivity/perturaaioo bounds for different instances of the FTOCP These bounds may take different forms, but for the application of our pipeline we require two types of perturbation bounds that are both common in the literature:
works 36 37
(a) Perturbations of the parameters Et,:t given a fixed initial state
12 qt t1)6e Σ 1=t1
|i (z, Eeidei F)
Utt (z, Shi F)
||
(e - t1
t=
(3)
where 6, = 16. - Eill for / E [4, (2), and scalar functions zi and qo satisfy lom (i(1) = 0.
Σe (1) S C, for constants C, 2 1, 1.2. This perturbation bound is useful in bounding the per-step error ex, we will discuss in Lemma
5

---

(b) Perturbation of the initial state given fixed parameters Et1:t2
wh (tagt Fyv/o. Ph (z's Etrctgi v./vv - qs(t - 11) 2/1,, for t E [21, (4)
where the scalar function 9s satisfies Ei=o (s(t) S C3 for some constant C3 2 1. This bound is useful in preventing the accumulation of per-step errors e, throughout the horizon (see Lemma 3.2) Compared with @ the right hand side of has a simpler form.
Existing perturbation bounds usually combine the above two types (G and (4 into single equation that characterizes perturbations on 2 and Et tt simultaneously, e.g., 35
Here, we decompose them into two separate types because they are used in different parts of our pipeline.
3.2 A 3-Step Pipeline from Perturbation Bounds to Regret
Step 1. obtain perturbation bounds &
An overview of the pipeline is given in Figure DI which illus- trates the high-level ideas of the pipeline that starts by obtaining perturbation bounds, proceeds to bound the per-step error using perturbation bounds, and finally combines the per-step error and perturbation bounds to bound the dynamic regret. In the following we describe each step in detail.
The Pipeline Theorem
Step 2. bound the per-step error e, (Lemma 3.1
Obtain the perturbation bounds given in and The form of the perturbation bounds depends heavily the specific form of the FTOCP, and thus the derivation requires case-by-case study (c.g., see Section 4 and Section 5 However, off-the-shelf bounds are available in most cases, as there has been rich literature on perturbation analysis of control systems (e.g.,
Step I:
Step 3. bound dynamic regret (Lemma 3.2
dynamic regret bound
(3 48 4 and the references therein). The following property summarizes precisely what is expected to be derived for bounds G and in Steps 2 and 3.
Figure 1: Illustrative diagram of the 3-step pipeline from perturbation analysis to bounded regret.
Property 3.1. Suppose there exists a positive constant R such
that the perturbation bound 3 holds for the following specifications: with t and t k for t < T k. holds for F + I. be the identity function II, and
2 E B R); Sritk-1 E 1, = -E.44--1 EetRs S.tk E B( R) CR::
with t1 = t and tr = for 2 k. B holds 2 E B(x,, R); SET E EuT, = Fieri F Fr. Further, perturbation bound holds any 2, 2,2' B(x R) and Etrd2 Elg:tz''
As remark, note that for the first specification of Property 3.1 with t1 = t and to + k. fi+h and Eit live in the state space 1=" rather than Ei+* because they represent the target terminal state of the FTOCP solved by MPC.. Intuitively. Property 3.1 states that perturbation bounds ( and g hold in a small neighborhood (specifically, a ball with radius R) around the offline optimal trajectory OPT, which is much weaker than the global exponentially decaying perturbation bounds required by previous work (e.g.. 35
the following sense: (i) in the general settings where the dynamical function is linerrneer, or where there are constraints on states and actions, one cannot hope the
perturbation bound to hold globally for all possible parameters 33
49 50
(ii) the decay functions
1=,,3,, are only required to converge to zero and satisfy E (T) S C., which means the
exponential decay rate as in 35 is not necessary - fact, polynomial decay rates can also satisfy
these properties, which greatly broadens the applicability of our pipeline.
Step Bound the per-step error et. The core of the analysis is to apply the perturbation bounds to bound the per-step error. For MPC,, under Property 3.1 this step can be done in a universal way, as summarized in Lemma 3.1 below. A complete proof of Lemma 3..mm....eaa..............ee can be found in Appendix C
Lemma 3.1. Let Property terminal cost Fi+ of MP is set to be the indicator function of some state T(E++Mae) that satisfies
3. hold. Suppose the current state Ie satisfies x; E B(xt RR/Cs) and the
v((++R)) E B(Iū+k for <T - k. Then, the per-step error of MPC, is bounded by
4.
R C3
(T) + va((t) Pt. + 2R (G++Da)) -2)(k) + +0z(k)) (5)
+D.
T=U

---

Lemma 5.1 is straight forward implication of perturbation bound (3) specified in Property 3.1 To
see this, for T k. note that the per-step error e, can be bounded by
ct
| (Ii, Sect+- (C== D) v/? (Ie, Ser; Fr)
(6a)
with (st, 1e
w/t (anss Ch 11 Totlee meel
(6b)
R-1 Σ (|æae|] (T) + 92(())) + (I|xell qu (k) + (2())) (E(++R1))- - 27 siamel
(6c)
Here, we apply the principle of optimality to conclude that the optimal trajectory from to +2+
(i.e., (Ix, Sii4 11 11) in 6b
is a sub-trajectory of the clairvoyant optimal trajectory
from xe (i.e., v% (Iz, T.:: Fr) in 66 and (6)) is obtained by directly applying perturbation bound
G
Note that ||a2||| S C. + Dx., and that both (((+++1))) and + are in (z ++: R) by assumption
and by perturbation bound (4) specified in Property 3.1] we conclude that 5 hold for t < T k. The case t > T - k can be shown similarly. We defer the detailed proof to Appendix
Step 3: Bound the dynamic regret by Σt=o ez. This final step builds upon perturbation bound ( and aims at deriving dynamic regret bounds in a universal way, as stated in Lemma 3.2 below. Specifically, under the assumption that local decaying perturbation bound in the form of holds around the offline optimal trajectory OPT, and the property that per-step errors e, are suffccintly small, we can show that the online controller will not leave the "safe region" near the offline optimal trajectory as specified in Property 3.1 and thus the dynamic regret of AL is bounded as in 7 (note that ALG is not confined MPC, but is allowed to be any algorithm with bounded per-step errors). complete proof of Lemma
3.2 can be found in Appendix D
Lemma 3.2. Let Property 3.1 hold. If the per-step errors of ALG satisfy er S R Lg) for all time steps T < t, the trajectory of ALG will remain close to OPT at time t, iee It E B( R/Ca).
Further, ez S R/(C3Lg) for all < T, the dynamic regret of ALG is upper bounded by
cost(ALG) - cost((PT))))) = (v (Cost(OPT)
T-1
T-1 +
Σ 1=
c +
(7)
Summary. Combining Steps and 3 of the pipeline yields the following Pipeline Theorem for MPC, (see Theorem 3.3). Basically it states that, when the prediction horizon & is sufficiently large and the prediction errors Pt.r are sufficiently small, Lemma 3.1 and Lemma 3.2 can work together to make sure that MPC, never leaves (R/C3) -ball around the offline optimal trajectory OPT: thus we obtain dynamic regret bound.
Theorem 3.3 (The Pipeline Theorem). Let Property 3. hold. Suppose the terminal cost Fitk of MPC, is set to be the indicator function of some state ūlE++kp) that satisfies ((Cr+R)e) E B(x R) for all time steps t < T Further, suppose the prediction errors Pt.r are sufficiently small and the prediction horizon k is sufficiently large, such that
k.
Σ
(G. T=
&
(
R
(T(T) + =2(()) Pr.r + 2R
De-
9.(()) .9((k)))()))))))))))) + 92(())
R
O3
C
Then, the trajectory of MPCr will remain close to OPT, i.e. 2, B(2j,R// R/C3), for all time steps t, and the dynamic regret of MPC, is upper bounded by
cost cost (MPC,)) cost(OPT) O (OCT))==((Vo((PFFFF /coost(OPTT E -E).
(8)
where = -K=1 ( P(r) + (1)) + (2())) T.
The proof of Theorem 3.3 can be found in Appendix E
To interpret the dynamic regret bound in note that we have cost (PPT) O(T) as result of our model assumptions. Thus, the dynamic regret of ALG is in the order of VTE + E. When there is no prediction error, the regret bound Ol(2) (k) + (2()) 7) reproduces the result in (35, and the bound will degrade as the prediction error increases. is also worth noticing that, when the prediction power improves over time as the
online controller learns the system better and & = I(In)) the dynamic regret can be o(T).
7

---

Unconstrained LTV Systems
We now illustrate the use of the Pipeline Theorem by applying it in the context of (unconstrained) LTV systems with prediction errors, either on disturbances or the dynamical matrices.
4.1 Prediction Errors on Disturbances
In this section, consider the following special case of problem 1 where the dynamics is LTV and the prediction error can only occur on the disturbances wy:
T-1 Σ (F((z))
min
f((u)) + (T(TT)
E0
s.L. Jt+1 = A + B + we(())
4A stt<<
(9)
To (0))
All necessary assumptions on the system are summarized below in Assumption
Assumption 4.1. Assume the following holds for the online control problem instance
Cost functions: [ ( Fr are nonnegative p-strongly convex and E-smooth. And we assume (0) = Jt (0) = (T) = 0 without the loss of generality.
Dynamical systems: the LTV system {A,, B.} is o-uniform controllable with controllability index
d, and [|Ar]] S a, BB S. 6, and || [B|| < hold for all t, where Bi denotes the Moore-Penree
inverse of matrix Br.. The detailed definitions can be found in Assumption F. in Appendix FF Predicted quantities: [[=)(E))] S Dw holds for all & E E, and all t. For every time step t, we((s) is Lu-Lipschitz Lipnchitz,uunctin in &u i.e., [[,)(r)) wc(Ei)l S L l15. Eill VG,, E, E
Under Assumption we can again apply the perturbation bounds shown in [65] to show Property
3.1 In particular, already know that for some constants Hi and X (0, 1), perturbation
bounds ( and 4 hold globally for qı (t) = 0, (2(() H1 and (t()) = H Since both of
these perturbation bounds hold globally, radius R in Property J. can can be arbitrarily, and shall
take R = max Da-,, Hf
[I-X,)² } so that Theorem 3.3 can be applied to MPC, with terminal cost
F Eej(+k) = I(-; O). This leads to the following dynamic regret bound:
Theorem 4.1. In the unconstrained LTV setting under Assumption 4.1 when the prediction horizon k is sufficiently large such that k 2 (1
/In(1/A1), the dynamic regret of MPC, I(::0) is bounded by cost cost <
La
(1-x1)²
(Algorithm)) 7h with terminal cost Fi+a(t; Espt+()))))))))))))))))))))))))s
o E X2 Σ XTP(T))
A complete proof of Theorem 4.1 can be found in Appendix F When there are no prediction errors, the bound in Theorem 4.1 reduces to OA}TT), which reproduces the result of (35 Further, is also worth noticing that due to the form of discounted sum Σ D P(T). prediction errors for the near future matter more than those for the far future.
4.2 Prediction Error on Costs and Dynamical Matrices
We now consider prediction errors on cost functions and dynamics, rather than disturbances. Specifi- cally, we consider the following instance of problem
min MOO:T
Σ ((x) (T (z(E7) T.((E)) :x(ET)) 1=0
u. (.)))) + Fr (x2:
s.t. Z++1 = A((E:) + B.(g.) + wy (E:);
6A <<t<T, TT (10)
Zg = x0))
where the terminal cost is given by (x( { = (z- -r (17
All necessary assumptions on the system are summarized below in Assumption
8

---

Assumption 4.2. Assume the following holds for the online control problem instance
T0
Cost: pl 3 (r(Si) 3 ET, μT 3 Re(E.) 3 (T, and pl PE(ET) 3 EI, VE, E Er, Vt.
Dynamical systems: both the ground-truth LTV system {A,(E)). B,(E)) T-1 and any predicted
LTV system {Ar(Er+rit), (5((+++1)))= (for all &. E E and all t) satisfy the controllability assumptions in Assumption C.1 in Appendix
Predicted quantities: bounds (S)]l S Dun [[Te( S Da, (E))))) S a. (.,() hold for all & E 5t and all t. LA is uniform Lipsckitz constant such that [| -A,(E)) S
LAlls: l|& - 2/ll VL,, E2 E holds for all t, and LB, Lqq Ln, La, I are defined similarly.
E
Under Assumption 4.2 we can show that for some constants H2 2 1 and X2 E (0, perturbation bounds 3 and hold globally for qı (t) H2 ge(t) H2 and (t( Hg under the
specifications of Property 3.1 Thus, Property 3.1 holds for arbitrary R, and we can set R D + Dz
so that Theorem 3.3 can be applied MPC; with terminal cost F++
I[: (E)))+))),
which leads to the following dynamic regret bound:
Theorem 4.2. In the unconstrained LTV setting 10 under Assumption 4.2 when the prediction
horizon k 2 ((1) D and the prediction errors satisfy Σ A
pe, S 11) for all I, the dynamic regret of MPC, (Algorithm D with terminal cost Fetk (eleth) ((;5((((((+)))) is bounded by
cost (MPM cost cost((OT) IO (V (VT MP(() T2 + E#=D
The exact constants and complete proof of Theorem 4.2 can be found in Appendix G Compared with Theorem 4.1 Theorem 4.2 additionally requires the discounted total prediction errors Σド= X3. Pt.r to be less than or equal to some constant. This actually expected, and emphasizes the critical difference between the prediction errors dynamical matrices (Ar, B,) and the prediction errors on W/, since an online controller cannot even stabilize the system when the predictions on (A,, B,) can be arbitrarily bad. It is worth noting that Assumption 4.2 requires the uniform controllability to hold for the unknown ground-trun truth LTV dynamics and any predicted dynamics. The goal is to ensure the perturbation bounds for KKT matrix inverse hold in Lemma G.2
Intuitively, this
assumption is necessary because otherwise the solution of MPC (by solving FTOCP induced by the predicted dynamics) be unbounded. We provided two examples (Example G.4 and G.5) that
satisfy Assumption 4.2 while the true dynamics are unknown.
5 General Dynamical Systems
We now move beyond unconstrained linear systems to constrained nonlinear systems given by the
general online control problem I in Section 2 All necessary assumptions are summarized in
Assumption H.T in Appendix H Perhaps surprisingly, decaying perturbation bounds can hold even in this case. In particular, using Theorem 4.5 in 550 we can show that there exists a small constant
Rt such that, for some constants 113 2 1 and aa E (0, 1). perturbation bounds ( and hold for (t) = O, Q2 (t) = Hz and qa(t)= = Ha Thus, Property 3.1 holds (see Appendix H for formal statements) and we can apply Theorem 3.3 to obtain the following dynamic regret bound:
Theorem 5.1. In the general system J. under Assumption H.I in Appendix H Property 3.1 holds for some positive constant R and gi (t( = O. 92(t) Hz and (t(t)) Hz Suppose the terminal cost Fe4 of MPC; is set to be the indicator function of some state ū(Ex+me) that sat-
isfies T(S++M4)) E B( R) for t < T k. k. Suppose the prediction errors Pt,r are sufficiently
small and the prediction horizon & is sufficiently large such that H3 E+=1 Noper + 2RHz2 S (1-2a)2R R H3L,
Then, the dynamic regret of MPC; upper bounded by cost cost(MPCx) - cost(OPT) S
O (VT T. X2 ++= (
complete proof of Theorem 5.1 can be found in Appendix H An assumption in Theorem 5.1 that is difficult to satisfy in general is that the reference terminal states s(Er+xj)) of MPC, must be close enough to the offline optimal state zi i..., ((E++e))) E B( R),, while the offline optimal state xf is generally unknown. This can be achieved in some special cases, for example, when we
When we say O(1), we mean there exists O(1) such that x 2 holds.

---

know |571 is sufficiently small. In this case, one can first solve FTOCP 2i (Io, O; Fr) and use it the terminal states of MPC This intuition is formally shown in Appendix [
as reference Another limitation is that Theorem 5.1 is only a bound on the cost of MPC, not its feasibility. There are many ways to guarantee recursive feasibility of MPC [3] which we leave as future work. We also discuss how to verify Assumption H.T in two simple examples that arise from a simple inventory dynamics in Appendix | The first positive example shows that Assumption H. is not vacuous, and the second negative example shows exponentially decaying perturbation bounds may not hold when Assumption H.l is not satisfied.
References
[1] Carlos E. Garcia, David M. Prett, and Manfred Morari. Model predictive control: theory and practice survey. Automatica, 25(3):335-348, 1989.
[2] Ugo Rosolia and Francesco Borrelli, Learning model predictive control for iterative tasks: data-driven control framework. IEEE Transactions on Automatic Control, 63(7):1883-189) 1896, 2017.
[3] Milan Korda and Igor Mezić. Linear predictors for nonlinear dynamical systems: Koopman operator meets model predictive control. Automatica, 93:149-160, 2018.
[4] Frank Allgöwer and Alex Zheng. Nonlinear model predictive control, volume 26. Birkhäuser, 2012.
[5] Paolo Falcone, Manuela Tufo, Francesco Borrelli, Jahan Asgari, and H. Eric Tseng. A linear time varying model predictive control approach to the integrated vehicle dynamics control problem in autonomous systems. In 2007 46th IEEE Conference on Decision and Control, pages 2980-2985. IEEE, 2007.
[6] Pierre-brice Wieber. Trajectory free linear model predictive control for stable walking in the presence of strong perturbations. In 2006 6th TEEE-RAS International Conference Humanoid Robots, pages 137-142, 2006.
[7] Dongbing Gu and Huosheng Hu. Receding horizon tracking control of wheeled mobile robots. IEEE Transactions on Control Systems Technology, 14(4):743-749, 2006.
[8] David H. Shim. H. Jin Kim, and Shankar Sastry. Decentralized nonlinear model predictive control of multiple flying robots. In 42nd IEEE International Conference on Decision and Control (IEEE Cat. No.03CH37475), volume 4, pages 3621-3626, 2003.
[9] Holger Diedam, Dimitar Dimitrov, Pierre-Brice Wieber, Katja Mombaur, and Moritz Diehl. Online walking gait generation with adaptive foot positioning through linear model predictive control. In 2008 JEEE/RSJ International Conference on Intelligent Robots and Systems, pages 1121-1126, 2008.
[10] Michael Neunert, Cédric de Crousaz, Fadri Furrer, Mina Kamel, Farbod Farshidian, Roland Siegwart, and Jonas Buchli. Fast nonlinear model predictive control for unified trajectory optimization and tracking. In 2016 IEEE International Conference on Robotics and Automation (ICRA), pages 1398-1408 1404, 2016.
[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, 1725 2014.
[12] Arthur Richards and Jonathan P. How. Robust variable horizon model predictive control for vehicle maneuvering. International Journal of Robust and Nonlinear Control, 16(7):333-351, 2006.
[13] Stefano Di Cairano, Diana Yanakiev, Alberto Bemporad, Ilya V. Kolmanovsky, and Davor Hrovat. An MPC design flow for automotive control and applications to idle speed regulation. In 2008 47th IEEE Conference Decision and Control, pages 5686-5691, 2008.
10

---

[14] Gregory Stewart and Francesco Borrelli. A model predictive control framework for industrial turbodiesel engine control. In 2008 47th IEEE Conference on Decision and Control, pages 5704-5711 5711, 2008.
[15] Rachid Amari, Mazen Alamir, and Paolino Tona. Unified MPC strategy for idle-speed control, vehicle start-up and gearing applied to an automated manual transmission. IFAC Proceedings Volumes, 41 41(2):779--7085 2008.
[16] Takeshi Hatanaka, Teruki Yamada, Masayuki Fujita, Shigeru Morimoto, and Masayuki Okamoto. Explicit Receding Horizon Control of Automobiles with Continuously Variable Transmissions, pages 561-569. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009.
[17] Stefano Di Cairano, H. Eric Tseng, Daniele Bernardini, and Alberto Bemporad. Vehicle yaw stability control by coordinated active front steering and differential braking in the tire sideslip angles domain. IEEE Transactions on Control Systems Technology, 21((): (eep::12662244 1248, 2013.
[18] Patricia Hidalgo-Gonzalez,
Gonzalez, Rodrigo Blerrique-Aubal 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.
[19] 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: A review. Engineering Reports, (66)e121788 2020.
[20] Minghong Lin, Zhenhua Liu, Adam Wierman, and Lachlan L. H. Andrew. Online algorithms for geographical load balancing. In Proceedings of the International Green Computing Conference (IGCC), pages 1-10, 2012.
[21] Xiaoyan Li, Chenghui Zhang, Alian Chen, Xiangyang Xing, and Guangxian Zhang. Model predictive direct current control strategy for three-level T-type rectifier under unbalanced grid voltage conditions. In 2018 IEEE Applied Power Electronics Conference and Exposition (APEC), pages 1514-1519, 2018.
[22] Ahmed A. Shetaya, Amr M. A. Amin, and Omar H. Abdalla. Model predictive control based power system operation planning of grid connected high share renewable energy. In 2017 Nineteenth International Middle East Power Systems Conference (MEPCON), pages 1500- 1504, 2017.
[23] Alessandra Parisio, Evangelos Rikos, and Luigi Glielmo. A model predictive control approach microgrid operation optimization. IEEE Transactions on Control Systems Technology, 2215) 2014.
[24] Venkata Yaramasu and Bin Wu. Predictive control of a three-level boost converter and an NPC inverter for high-power PMSG-based medium voltage wind energy conversion systems. IEEE Transactions on Power Electronics, 29(10):5308-533 -3222, 2014.
[25] Tong Wang, Huijun Gao, and Jianbin Qiu. A combined adaptive neural network and nonlinear model predictive control for multirate networked industrial process control. IEEE Transactions on Neural Networks and Learning Systems, 27(2):416 2016.
[26] D. W. Clarke. Application of generalized predictive control to industrial processes. IEEE Control Systems Magazine, 8(2):49555, 1988.
[27] Matthew Ellis, Helen Durand, and Panagiotis D. Christofides. tutorial review of economic model predictive control methods. Journal of Process Control, 24(8):115--113 2014.
[28] Moritz Diehl, Rishi Amrit, and James B. Rawlings. A Lyapunov function for economic optimizing model predictive control. IEEE Transactions on Automatic Control, 7607)703-7777 2010.
[29] David Angeli, Rishi Amrit, and James B. Rawlings. On average performance and stability of economic model predictive control. IEFE transactions on automatic control, 167))1615-1166 2011.
11

---

[30] 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.
[31] Lars Grüne and Simon Pirkelmann. Economic model predictive control for time-varying system: Performance and stability results. Optimal Control Applications and Methods, 41(1):22-64 2020.
[32] Chenkai Yu, Guanya Shi, Soon-Jo Chung, Yisong Yue, and Adam Wierman, Competitive control with delayed imperfect information. arXiv preprint arXiv:0000.11677 2020.
[33] 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.
[34] Runyu Zhang, Yingying Li, and Na Li. On the regret analysis of online LQR control with predictions. arXiv preprint arXiv:2102.01309 2021.
[35] Yiheng Lin, Yang Hu, Haoyuan Sun, Guanya Shi, Guannan Qu, and Adam Wierman. Perturbation-barl based regret analysis of predictive control in linear time varying systems. arXiv preprint arXiv:2106. 10497, 2021.
[36] Sungho Shin, Victor M. Zavala, and Mihai Anitescu. Decentralized schemes with overlap for solving graph-structured optimization problems. IEEE Transactions Control of Network Systems, 123):2225-12333 2020.
[37] Sungho Shin and Victor M. Zavala. Controllability and observability imply exponential decay of sensitivity in dynamic optimization. PapersOnns,,, 54(6):179- 184, 2021.
[38] 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, 66(10):4761-4768 2020.
[39] 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.
[40] Niangjun Chen, Anish Agarwal, Adam Wierman, Siddharth Barman, and Lachlan L. H. Andrew. Online convex optimization using predictions. ACM SIGMETRICS Performance Evaluation Review, 43(1):191-204, 2015.
[41] Naman Agarwal, Brian Bullins, Elad Hazan, Sham Kakade, and Karan Singh. Online control with adversarial disturbances. In International Conference on Machine Learning, pages 111-119. PMLR, 2019.
[42] Naman Agarwal, Elad Hazan, and Karan Singh. Logarithmic regret for online control. Advances in Neural Information Processing Systems, 32, 2019.
[43] 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, 18:5587-1885, 2019.
[44] 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-20641 2020.
[45] Weici Pan, Guanya Shi, Yiheng Lin, and Adam Wierman. Online optimization with feedback delay and nonlinear switching cost. arXiv preprint arXiv:2111.00095, 2021.
[46] Gautam Goel and Babak Hassibi. The power of linear controllers in LQR control. Proceedings of Machine Learning Research vol TBD, 1:13, 2020.
[47] Edgar Minasyan, Paula Gradu, Max Simchowitz, and Elad Hazan. Online control of unknown time-varying dynamical systems. Advances in Neural Information Processing Systems, 34, 2021.
12

---

[48] Wanting Xu and Mihai Anitescu. Exponentially convergent receding horizon strategy for constrained optimal control. Vietam Journal of Mathematics, 47(4):897-929. 2019.
[49] Sen Na and Mihai Anitescu. Superconvergence of online optimization model predictive control. arXiv preprini arXiv:2001.03707, 2020.
[50] Sungho Shin, Mihai Anitescu, and Victor M. Zavala. Exponential decay of sensitivity in graph-structured nonlinear programs. arXiv preprint arXiv:2101.03067 2021.
[51] G. M. Lee, N. N. Tam, and N. D. Yen. Continuity of the solution map in quadratic programs under linear perturbations. Journal of optimization theory and applications, 129(3):415-423, 2006.
[52] Anthony V. Fiacco and Yo Ishizuka. Sensitivity and stability analysis for nonlinear programming. Annals of Operations Research, 27(1):215-235, 1990.
[53] Francesco Borrelli, Alberto Bemporad, and Manfred Morari. Predictive control linear and hybrid systems. Cambridge University Press, 2017.
[54] Dimitris Papadimitriou, Ugo Rosolia, and Francesco Borrelli. Control of unknown nonlinear systems with linear varying MPC. In 2020 59th IEEE Conference on Decision and Control (CDC), pages
IEEE, 2020.
[55] 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.
[56] YP Hong and C-T Pan. lower bound for the smallest singular value, Linear Algebra and its Applications, 172:27-32, 1992.
13

---

Checklist
1. For all authors...
(a) Do the main claims made the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See Contributions in Section | and the references within.
(b) Did you describe the limitations of your work? [Yes] See the last paragraph of Section S
(c) Did you discuss any potential negative societal impacts of your work? [N/A] The goal of our work is to advance the theoretical understanding for predictive online controllers. We did not see any potential negative societal impacts of our work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Ys]] We did not find any aspect of our work that may lead to ethics violations.
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Assumption 4.
and 4.2 in the main body, Appendix B and Assumption F.T G.T and H. in the appendix.
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendices for complete proofs of our results. We also add references to the relevant sections of the Appendix when introduced each theorem or lemma.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material URL)? [N/A]
(b) Did you specify the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect the random seed after running experiments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you't 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "T--Ni8rt3-x", "reviewer": "Reviewer_qCVx", "summary": "This paper studies how to bound the dynamic regret for MPC. The analysis is built upon a new perturbation bound for finite-horizon optimal control.  Per-step error of MPC is bounded for regret analysis. The proposed analysis covers a variety of settings. Some existing results for the LTV case has been recovered and strengthened. New results have also been obtained for the nonlinear case.", "questions": "My main questions are:\n\n1)  Is there any way to justify the assumptions for practical problems? How realistic is it to assume the stability in nonlinear setting?\n\n 2) What new insights for algorithm design are brought by the proposed regret analysis? ", "limitations": "Yes, the authors have discussed the limitations in the end of Section 5. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The perturbation bound for finite-horizon optimal control looks interesting and original. \n2. Several different settings are unified using the proposed approach. \n3. New results have been obtained for both LTV and nonlinear cases.\n\nWeaknesses:\n1. The presentation is not that clear. Section 2 may be revised with the focus on MPC. The connections between Problem (1) and MPC need more explanations. \n2. The assumptions are very strong: stability is assumed in the first place. That seems quite unreasonable. \n3. It seems that the regret analysis does not lead to any end-to-end algorithms for practical MPC. Any insights can be obtained for algorithm design?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ScRoe_dqH-L", "reviewer": "Reviewer_UZES", "summary": "The authors provide an analysis of dynamic regret in model predictive control by identifying how perturbation bounds for finite-time optimal control problems affect the closed-loop dynamic regret in MPC. The authors then instantiate their pipeline theorem on two examples with linear time-varying (LTV) dynamics, and one general nonlinear dynamics with constraints example.", "questions": "Line 39: Can the authors elaborate on what this “counter-intuitively large re-planning window” refers to?\n\nLine 127: Is it assumed that the true parameters $\\xi_t^* \\in \\Xi_t$? I presume so, otherwise the prediction error cannot be driven arbitrarily small.\n\nAlgorithm 1, Line 4: The notation $\\psi_t^{t’}(\\cdot)_{v_t}$ is confusing. Consider something like $\\psi_t^{t’}(\\cdot)[0]$ instead.\n\nDefinition 3.1: What happens when the solutions $\\psi_t^T$ are not unique? Does the definition just rely on picking an arbitrary optimal solution?\n\nLines 181-182: Regarding “the per-step error converges to zero as the prediction horizon $k$ increases and the quality of predictions improves (i.e., $\\|\\xi_{t:t+k|t} - \\xi^*_{t:t+k}\\| \\to 0$)”: it seems that as $k$ grows, $\\|\\xi_{t:t+k|t} - \\xi^*_{t:t+k}\\|$ should grow as well (and not tend to zero), since the predictor is being asked to predict over a longer horizon $[t:t+k]$ using only the information at times $[0:t]$.\n\nEquation (4): What does the $y_t/v_t$ subscript mean?\n\nProperty 3.1: I think $\\xi_{t+k}, \\xi’_{t+k} \\in \\mathcal{B}(x_{t+k}^*, R)$ is a typo. Furthermore, on Line 218, “perturbation bound (4) holds for any $z,z’ \\in \\mathcal{B}(x_t^*, R)$”, is this for the true parameters $\\xi_{t}^*$?\n", "limitations": "The authors acknowledge (in Lines 344-351) that their analysis in Theorem 5.1 (a) does not tackle the question of recursive feasibility for MPC, and (b) the algorithm is not actually practical since it requires setting the terminal state $\\bar{y}(\\zeta_{t+k|t}) \\in \\mathcal{B}(x_{t+k}^*, R)$, but the optimal trajectory $x_t^*$ is not known.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**EDIT:** After reading the author's responses, I am raising my score to a borderline accept. \n\n**Strengths:**\n\nThe authors tackle a very challenging problem of controlling the regret of MPC in constrained nonlinear settings.\n\n**Weaknesses:**\n\nIt is unclear how much the presented results advance our understanding of MPC. Specifically:\n\n- Regarding Section 4.1, Theorem 4.1: In Line 298, it is noted that when there are no prediction errors, this result recovers the existing result in [35]. On the other hand, when there are prediction errors, the term $\\sum_{\\tau} \\lambda_i^\\tau P(\\tau)$ needs to be $o(T)$ for the dynamic regret to be $o(T)$. It is not clear when this can happen, given that the prediction error is over the disturbance term $w_t(\\xi_t^*)$ in Eq. (9). The two most common cases of modeling disturbances are (a) iid stochastic terms, and (b) bounded oblivious/adversarial terms. In either case, it seems that $P(\\tau) = \\Omega(T)$, since past observations give no information about future observations.\n\n- Regarding Section 4.2, Theorem 4.2: In addition to the previous paragraph, Assumption G.1 on the unknown dynamics $\\{ (A_t(\\cdot), B_t(\\cdot)) \\}$ seems quite restrictive, by asking for uniform controllability over all uncertainty parameters $\\xi_t$. In practice, this may substantially limit the uncertainty set $\\Xi_t$ so that the parameters $\\{ (A_t, B_t) \\}$ are effectively known. \n\n- Regarding Section 5, Theorem 5.1: Assumption H.1 is stated in purely technical terms, and no examples of even toy systems are given that satisfy all the assumptions. One very practical setting which seems like it cannot be handled by the theory is when one of the constraints is active, i.e., $s_t(x_t, u_t, \\zeta_t^*) = 0$. Intuitively, it seems like Property 3.1 cannot hold in that case, since small perturbations in either the parameters $\\zeta_t$ or the initial condition $x_0$ may cause the MPC problem to be either infeasible or jump to a very different solution. Furthermore, it is not clear the condition $H_3 \\sum_{\\tau=0}^{k-1} \\lambda_3^\\tau \\rho_{t,\\tau} + 2 R H_3 \\lambda_3^k \\leq \\frac{(1-\\lambda_3)^2 R}{H_3^2 L_g}$ can be practically satisfied; as $\\lambda_3 \\to 1$, this condition becomes more stringent, requiring increasingly accurate prediction errors $\\rho_{t,\\tau}$.\n\nI am open to changing my score if the authors can construct some specific systems which satisfy all the technical assumptions, specifically in Theorem 4.2 and Theorem 5.1. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RuJpYFZh8iE", "reviewer": "Reviewer_g7LT", "summary": "The paper formalizes a general pipeline to transform perturbation bounds into dynamic regret guarantees for model predictive control. Concretely, the pipeline has three steps (of which only one is non-immediate when employing it, see below):\n1. Obtain perturbation bounds w.r.t the uncertainty parameters (1.a.) and w.r.t. the initial state (1.b.),\n2. Use #1 to bound the per-step error of MPC (i.e. the distance between the actual action taken by the controller and the clairvoyant optimal action),\n3. Use #2 to obtain a dynamic regret bound.\n\nThe key contribution is a \"Pipeline Theorem\" which takes any input from step #1 and translates it to a dynamic regret bound.\n\nThey also showcase the abilities of this pipeline by employing it to:\n- extend existing dynamic regret guarantees in linear time-varying systems to handle prediction errors on costs, dynamcis and disturbances,\n- provide regret bounds in nonlinear dynamics and constraints, albeit under potentially stringent assumptions.", "questions": "- Do we expect the resulting dynamic regret to be tight? In which cases would the analysis be prone to yielding a sub-optimal regret bound? [answered by authors]\n- 1.(b) requires a bound on $y_t/v_t$, right? Is this standard? (i.e. the existing combined bounds bound this as a sub-step?) [answered by authors]", "limitations": "- The authors appropriately address the potential stringency of the assumptions required for the results concerning MPC with nonlinear dynamics and constraints.\n- Depending on the reply to the question above regarding 'tightness', I may suggest the authors consider adding a remark regarding this point.\n\nMinor Typo:\n- line 59: 'Theorm' -> 'Theorem'", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Successfully formalizes an analysis pipeline which I believe is quite creative/original and elegant,\n- The paper is presented very well, with a lot of intuitions and very clear statements,\n- The pipeline is also employed to obtain new results, which is evidence of the pipeline's usefulness.\n\nWeaknesses:\n- While the writing is very clear, the notation summary is deferred to the appendix which may compromise readability a bit (e.g. maybe could add a reference to the Appendix in the preliminaries before the notations start being used so people can click and be redirected?),\n- No formal 'Conclusion' section.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "C3wDhdDo1T", "reviewer": "Reviewer_MMqe", "summary": "This paper proposes a general analysis pipeline to bound the dynamic regret of MPC problem. The proposed pipeline has 3 steps: (1) obtain the perturbation bounds  which relies on the specific form of MPC formulation, (2) bound the per-step error using the perturbation bounds, (3) bound the dynamic regret by perturbation bounds. The proposed pipeline is then applied to generalize existing regret bounds on MPC. ", "questions": "For readers who are not closely following the recent advances on finite-time analysis of MPC, like me, can authors clarify the technical contributions of the paper with respect to the existing works. For example,\n\n(1) How different are the three-steps analysis in the proposed pipeline with the dynamic regret analysis for MPC in the literatures? The authors just summarized and abstracted the existing analysis techniques or come up with a new set of techniques?\n\n(2) What are the technical challenges for MPC problems considered in section 4 and 5 such that no existing works solve them? For example, can the technique in [35] be extended to the problem (9) by adding the prediction error and using some common inequalities? \n\n(3) How valuable is Theorem 5.1 given its slighly strong assumption and the fact that the FTOCP can not be guaranteed to be solved to the globally optimal solution for constrained nonlinear systems.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n(1) The paper is well-written and clear.\n\n(2) A novel analysis pipeline to bound the dynamic regret of MPC problem. This analysis pipeline not only unifies the previous results but also generalize to the new settings which have not been well-studied.\n\nWeaknesses:\n\n(1) Theorem 5.1 relies on a strong assumption and restricts its implications.\n\n(2) The technical challenge of the proposed pipeline and the new settings considered in Section 4 and 5 are not clear. Without these, it is hard to evaluate the technical contributions of the paper.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept