Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: Strengths:
1. The perturbation bound for finite-horizon optimal control looks interesting and original. 
2. Several different settings are unified using the proposed approach. 
3. New results have been obtained for both LTV and nonlinear cases.

Weaknesses:
1. 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. 
2. The assumptions are very strong: stability is assumed in the first place. That seems quite unreasonable. 
3. 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?

questions: My main questions are:

1)  Is there any way to justify the assumptions for practical problems? How realistic is it to assume the stability in nonlinear setting?

 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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 
strengths_and_weaknesses: Strengths:

(1) The paper is well-written and clear.

(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.

Weaknesses:

(1) Theorem 5.1 relies on a strong assumption and restricts its implications.

(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.

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,

(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?

(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? 

(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
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: **EDIT:** After reading the author's responses, I am raising my score to a borderline accept. 

**Strengths:**

The authors tackle a very challenging problem of controlling the regret of MPC in constrained nonlinear settings.

**Weaknesses:**

It is unclear how much the presented results advance our understanding of MPC. Specifically:

- 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.

- 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. 

- 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}$.

I 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. 

questions: Line 39: Can the authors elaborate on what this “counter-intuitively large re-planning window” refers to?

Line 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.

Algorithm 1, Line 4: The notation $\psi_t^{t’}(\cdot)_{v_t}$ is confusing. Consider something like $\psi_t^{t’}(\cdot)[0]$ instead.

Definition 3.1: What happens when the solutions $\psi_t^T$ are not unique? Does the definition just rely on picking an arbitrary optimal solution?

Lines 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]$.

Equation (4): What does the $y_t/v_t$ subscript mean?

Property 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}^*$?

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.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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):
1. Obtain perturbation bounds w.r.t the uncertainty parameters (1.a.) and w.r.t. the initial state (1.b.),
2. 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),
3. Use #2 to obtain a dynamic regret bound.

The key contribution is a "Pipeline Theorem" which takes any input from step #1 and translates it to a dynamic regret bound.

They also showcase the abilities of this pipeline by employing it to:
- extend existing dynamic regret guarantees in linear time-varying systems to handle prediction errors on costs, dynamcis and disturbances,
- provide regret bounds in nonlinear dynamics and constraints, albeit under potentially stringent assumptions.
strengths_and_weaknesses: Strengths:
- Successfully formalizes an analysis pipeline which I believe is quite creative/original and elegant,
- The paper is presented very well, with a lot of intuitions and very clear statements,
- The pipeline is also employed to obtain new results, which is evidence of the pipeline's usefulness.

Weaknesses:
- 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?),
- No formal 'Conclusion' section.
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]
- 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.
- Depending on the reply to the question above regarding 'tightness', I may suggest the authors consider adding a remark regarding this point.

Minor Typo:
- line 59: 'Theorm' -> 'Theorem'
review_title: null

Meta-review: metareview: The paper studies MPC and proposes a general analytic framework to bound dynamic regret. The approach is to achieve a perturbation bound for the MPC problem per step and then obtain a regret bound. 

Overall the paper saw a lot of discussion, with the reviewers initially questioning the non-triviality of the results, but those questions were sufficiently addressed. Finally, the reviewers have liked the theoretical contributions of the paper, however the practical insight or impact has been particularly questioned. The lack of results on Robust MPC has been a talking from the point of view of whats used in practice, under these assumptions. The paper from the reviewer's assessments lay on the borderline, but the theoretical contributions are strong and that leads to me to a recommendation of marginal accept. 

However, this recommendation comes with a strong plea to the authors regarding improving the manuscript, especially improving discussion and presentation of recent results on regret analysis of MPC. This is important so that readers can fully comprehend and understand the contribution of the paper. 
confidence: Less certain
Decision: Accept