Venue: NeurIPS 2022 Conference

Reviews:

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: The paper studies the dynamic regret of online linear quadratic control. It considers single-trajectory LQ control with known, stationary system and cost matrices, and with adversarial disturbances. The paper addresses the problem by studying dynamic regret minimization against disturbance action policies. It first presents a proper online learning algorithm that achieves dynamic regret optimal in the number of steps and path variation, for online minibatch linear regression. The paper proves that this algorithm is also strongly adaptive, in that it achieves logarithmic static regret for any time window. By combining disturbance action policies with the proper online learning procedure, the paper shows a dynamic regret bound that is also optimal in the dependence on the number of steps and path variation. A main technical contribution is the procedure to convert an improper online learning algorithm to a proper one, while maintaining the exp-concavity of the loss function. A nontrivial lower bound is also presented to show the optimal dependencies.
strengths_and_weaknesses: The paper has technical significance. It proves a sharp dynamic regret bound in terms of the number of steps and the path variation, as well as a matching lower bound. The results are built upon earlier results about the reduction from online LQ control to online linear regression, optimal improper online learning with exp-concave losses, and the conversion from improper learners to proper ones, while having new, interesting components, like the new improper to proper learning conversion and lower bounding strategy.

The paper contains a thorough discussion of the literature and is well placed in it. The presentation is in general clear. Please see the Questions section for some suggestions for improvement.

On the weakness side, the dependence on the dimension and system parameters are unlikely to be optimal. Empirical support for the theoretical claims is lacking, which could be informative of the constants hidden in the bounds.
questions: In the abstract, citing the source of the best known rate is recommended.

In some places, the papers uses the notation $\tilde{O}(\log n)$. Here, $\tilde{O}(\cdot)$ does not hide logarithmic dependence on $n$, which had better be noted.

Below Proposition 2, in Lines 133 to 137, the math formulas can be better displayed.

In the definition of exp-concavity (Definition 3), it is not clear how it is related to the name of exp-concavity. Unfamiliar readers would appreciate some more explanation.

In Section 4.2, readers read the algorithm first but do not know what $\mathcal{A}$ is until reading two more paragraphs. I recommend explaining $\mathcal{A}$ earlier.

In Line 326, "notations" -> "notation".

In the Conclusion section, the paper mentions "general strongly convex losses in the LQR problem". If I did not get it wrong, this paper considers positive semidefinite $Q$, $R$, so the cost is not necessarily strongly convex. Hence, strongly convex costs are not strictly more general than quadratic costs. The word "general" can be removed to reduce the ambiguity. And in this case, the problem is no longer a LQR problem, but a linear control problem.
limitations: Limitations are adequately addressed.
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 work studies LQR control problem w.r.t. the dynamic regret measure. The authors propose a ProDR algorithm that achieves an optimal $n^{1/3}$ regret, improving the existing best $n^{1/2}$ regret result. The main idea of their algorithm is to reduce the original LQR problem to an online linear regression problem and adopt a ProDR online linear regression algorithm with an $n^{1/3}$ regret. They further prove an $n^{1/3}$ regret lower bound to suggest the optimality of their algorithm. 
strengths_and_weaknesses: Strengths:

+ The presentation is clear.
+ The proof is technically sound. 
+ The relation between the proposed algorithm and existing baseline algorithms is well discussed.

Weaknesses:

- The importance of the derived result seems not important enough since it heavily depends on an existing algorithm from Baby and Wang (2021). I am not sure if the transferring framework (from LQR to online linear regression) is also a standard process or not. If so, it may further weaken the technical contribution of this work. 
questions: - Can you highlight the main technical difficulties you have faced in applying the algorithms in Baby and Wang (2021) to the LQR setting? I briefly checked Baby and Wang (2021) (https://arxiv.org/pdf/2201.08905.pdf) and it seems that they have already discussed some reduction from the box constraints to the general convex decision sets in their Sec. 4.2. Thus, I am not sure whether your comment from line 228 to 229 are still applicable. 
limitations: The authors have discussed the limitations of their algorithms.
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: The paper proposes an algorithm which attains an $\tilde{O}(n^{1/3} \mathcal{TV}(M_{1:n})$ dynamic regret in the nonstochastic LQR setting, along with a matching lower bound. The analysis builds upon the reduction of nonstochastic quadratic-loss LQR to online linear regression with delayed feedback of Foster and Simchowitz (2020) and the recent algorithm of Baby and Wang (2022) attaining optimal dynamic regret (and $O(\log n)$ strongly adaptive regret) for exp-concave losses under certain assumptions. Hence the main theorem of the paper translates the Baby and Wang (2022) guarantees to the setting of \textit{proper} (i.e. ensuring decisions are within a general convex set) online linear regression with delayed feedback and then instantiates it in the LQR setting. 
strengths_and_weaknesses: Strengths:
- The (main) paper is written very clearly;
- It is placed very naturally within the literature;
- The conversion of Baby and Wang (2022) to an algorithm that works on general convex constraint sets is a nice contribution.

Weaknesses:
- Somewhat limited originality and impact;
- Lack of experimental settings make it hard to gauge if this algorithm would eventually lead to better controllers in practice.
questions: Suggestions/minor remarks:
- On line 294: "static" -> "adaptive";
- line 355: "arise"->"arises"
- Some more text to help the flow of Appendix B (quite terse right now)
- misplaced equation in lines 657-660
- Improve flow of proof of lemma 18 (e.g. bullet points for properties, or just more careful writing + organization)
- line 694: paragraph ends with "We fo" -> fill in the rest of the sentence
- Shorten statement of Corollary 19 to improve readability + maybe some light work on improving flow of proof
- the below.
limitations: I recommend more discussion on finding the correct input parameters for Corollary 10 to hold (line 333) [addressed in rebuttal, I recommend this to be incorporated in camera-ready], as well as discussion of the limits of deploying online learning based controllers in practice (both in general and the particular one proposed by the authors) [I recommend this to be incorporated in discussion section of camera-ready].
review_title: null

Meta-review: metareview: This paper considers the problem of online linear-quadratic control with adversarial noise. Previous work aims to derive regret bounds relative to the best linear controller in hindsight, whereas this work considers *dynamic regret*, where the algorithm ensures regret against all sequences of policies simultaneously, with the regret depending on the variation in the sequence. The main result is to provide an algorithm with policy regret $n^{1/3}\cdot\mathrm{Variation}^{2/3}$, which improves upon the previous state of the art.

The reviewers found this paper to be clear and well-written, and found the paper technically interesting (the main challenge is to extend the dynamic regret guarantees of Baby and Wang (2022) guarantees to the setting of \emph{proper} online learning, so that the reduction from online control to online regression of Foster and Simchowitz (2020) can be applied. For the final revision, the authors are encouraged to incorporate the reviewers' feedback to improve the presentation.
confidence: Less certain
Decision: Accept