Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: 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.

main_review: 
My main comments are as follows:

\begin{enumerate}

\item The analysis based on the assumption that
at each time point, 
 the system coefficients and  random disturbances in the future $k$ time steps 
can be observed exactly for a sufficiently large $k$, depending implicitly on the controllability index of the system.
In my opinion, this is a very strong assumption, especially the exact observation of noise. 
I suggest the authors to 
discuss extensions to inaccurate observations of noises,
or 
give more concrete and practical examples where the random noises in the future time steps
can be exactly observed. 

\item 
In the optimization problem (2), the authors introduce the terminal cost $F(x)=\alpha(\|x\|)$ with $\alpha$ being a convex function. However, the results and assumptions of Theorem 3.3 seem to be independent of $F$. Please clarify the role of $F$. Can we choose $F$ to be the zero function in the algorithm? 

\item I recommend to recall the definition of competitive ratio in the main text for the reader's convenience. 

\item The authors mention in the introduction that the current framework can not handle control constraints. However, it seems that the essential step of the analysis is to establish the Lipschitz stability of the optimizer of a convex optimization problem with respect to the loss function. Is it possible to follow the framework in https://arxiv.org/pdf/2104.09311.pdf, and handle the control constraints as an additional nonsmooth convex cost? 
 \end{enumerate}

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper examines the control of linear time varying systems in which the controller is given predictions of the system matrices, cost functions, and disturbances for a horizon in the future. This setup is motivated by problems, such as power systems, in which reasonably accurate predictions of future dynamics and disturbances are available at least over short horizons. The paper gives two algorithms, one based on model predictive control (MPC), which replans at each time step, and another that only replans once over fixed windows. They bound the dynamic regret and competitive ratios of these algorithms, respectively. For the MPC method, the key technique bounding how the solutions to the optimization sub-problems change when the initial condition, the disturbances, and any possible terminal constraints vary. They use these bounds to analyze stability and dynamic regret in a unified manner. For competitive ratio bounds, they show how the particular algorithm can be viewed as solving a smoothed online convex optimization problem. Then they use the previously derived methods to bound the deviation of the solution they obtained from the optimal solution. 
main_review: This paper describes two methods for controlling linear time-varying systems when finite-horizon predictions of the dynamics, costs, and disturbances are known. While these assumptions limit the scope, the authors convincingly argue that they are realistic in some important scenarios. The paper is insightful and the proofs appear to be rigorous. The key contributions enable precise bounds on stability and suboptimality for these time varying systems when only limited preview information is available. I consider these contributions to be substantial.

The methodology relies on heavily on smoothness and strong convexity of the losses and linearity of the constraints. The assumptions, in particular, guarantee that solutions to the optimal control sub-problems become smooth functions of the problem data. As pointed out by the authors, this precludes the things like inequality constraints on the states or inputs, as the smoothness properties would be lost. In many scenarios, however, these assumptions seem reasonable.

As a minor comment, some of the notation is confusing. For example, sometimes the optimal trajectories are indexed by $h$, and other times by $y_h$. The distinction is never explained, but from reading the proofs, they appear to mean the same thing.
limitations_and_societal_impact: The authors address the limitations of their method adequately. I see no potential negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper considers the control of a linear time-varying system with predictions. The predictions must be accurate and describe both the transition parameters, the noise, and the cost functions. The length of the prediction window must be larger than the system's sequential strong controllability index, i.e., such that it gives the controller the ability to transition perfectly between any two given states in a fixed number of steps without exerting too much control.

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.
main_review: Tackling the control of linear time varying systems is certainly of interest. The main algorithms and the statement of the results are satisfying and easy enough to understand. At a very high level, the proof ideas are also conveyed clearly.

While I'd be very interested to see a sensitivity analysis with respect to the prediction accuracy, it is more than reasonable to leave this for future work. I'd be happy to know if the authors have any ideas regarding this matter.

I do have a few issues:

1. While the exposition made me think the results are plausible, I did not find it sufficiently convincing. I tried looking a bit in the supplementary material, but the proofs there are quite long and technical and will take me very long to go over. Ideally, I would like to see a concrete proof sketch in the main text or perhaps even a full proof composed of informative/technical side lemmas that are proved in the appendix. In any case, it is not currently clear to me how the intermediate results in the main text come together to conclude the main results.

2. The definition of the cost seems non-standard to me. In particular, the additive relation between the state and control costs. Is it necessary? If so, while this includes the standard LQR costs, its necessity should be discussed.

3. Assumption 4 (all costs are minimized at 0 with value 0) is also non-standard. While the authors explain how it may be removed, the explanation is very short. After some thought, I find it likely that their explanation is indeed correct. Nontheless, I think it should be explained in further detail and proved formally. This would likely go to the supplementary material but I think its inclusion is necessary since the assumption is otherwise very restrictive.



Overall I think this is a very good work, but with the non-trivial caveat that I have no reasonable way to verify the veracity of the results.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper establishes both dynamic regret and competitive ratio bounds for online control with time-varying linear dynamics and adversarial perturbative noise, thereby extending past work for time-invariant noise-free dynamics. The analysis is facilitated by a general-purpose sensitive analysis for smoothed OCO. 

Update: The reviewers adequately addressed my concerns, and I am ammending my review to an 8. 
main_review: Overall, I had a very positive impression of the paper. The writing and notation were consistent and clear. Authors establish guarantees both in terms of regret, and competitive ratio, the latter of which I found quite surprising. The reduction to smoothed convex optimization also seems like a useful tool. I encourage acceptance (score of 7), but am I reluctant to award a higher score because the result seems like a (somewhat) incremental extension of Li et al 2019: notably, dynamic regret with a lookahead suffers excess loss lambda^k, where lambda = sqrt(condition number). Certainly this work is more general, is considerably better written, and the analysis relies only on conditioning of the controllability Gramian (rather than Li et al. which work in the rather hideous cannonical controllable form). But the key ideas: lookahead due to banded structure (see below in Major suggestions for more explanation), and the reduction to optimization on a finite window with an extra variable x_{t+p} corresponding to a final state are both fundamentally the contributions of the prior work. In fact, I believe that the latter (the reduction from control to SOCO) could have been better attributed to the predecessor. 

In sum,  I am enthusiastic about acceptance of this paper, but view it more of an improvement of past work than a fundamental breakthrough in its own right.


Major Suggestions
1. I think the sensitivity analysis based on banded diagonal matrices is super interesting. However, in light of past work (Li et al. 2019), there also seems to be an "algorithmic proof" of the same fact. Namely, I can consider the exact optimal solution to some banded optimization problem, and then I can consider the iterates produced by Nesterov's method. Examining the form of the latter, the k-th iterate requires at most k-steps of lookahead, yet exhibits an O(lambda^k) convergence to the optimal.  Then I could argue that any k-look ahead exact solution is also close to the k-step iterate of Nesterov's algorithm. Of course, "under the hood", the analysis of Nesterov's method and the conditioning of banded diagonal matrices reflect more or less the same principle. But I think that, given the use of this algorithm in past work, it would be nice to at least remark that it could be used as an alternate proof.

Minor Suggestions:
1. It took me a while to understand the subscript notation after the psi functions, only to realize that it corresponded to a vector index. I think it would be helpful to explain that upfront.
2. The authors do a good job of keeping notation consistent and avoid overloading. Still, it would have been very helpful to have seen a notation table in the appendix. This is particularly useful for disambiguating hats v.s. tildes. vs no accents, and for remembering that y_t are a state variable like x_t (which is non-standard in control, where y_t are typically system outputs). 

limitations_and_societal_impact: Yes, the authors did.
review_title: null

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