Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 3: Clear rejection
review_content: summary: The paper studies RL policies for linear time-varying systems. 
main_review: Most of the points discussed in the first round of reviewing are not addressed in the rebuttal. Further, the explanations in the rebuttal together with the antagonistic responses of the authors show that the manuscript suffers from serious presentation issues.
___________________________________________________________________
I think that the work is in an early stage of preparation and so cannot be recommended for publication. In general, connections to relevant literature and where this work stands in a bigger picture is missing, presentation is hard to read and harder to grasp for an expected reader, and motivations of the work and the directions along which it can be helpful are not clear.

To the reader, the technical parts look isolated and different pieces do not connect well to deliver the potential messages. The authors rely too much on the supplementary file so that the paper lost its self-sufficiency. Accordingly, the language is too strong and super confident while the writing suffers from a sub-standard presentation by leaving the burden of decoding multiple claims in every line and justifying them to the reader. I suggest rewriting major portions and providing more concise presentation, using google scholar to find more-relevant literature and clearly and comprehensively discussing the connections. Unfortunately, the impression of the reader from the current version is that the manuscript focuses on technicalities and details of a problem, while presenting as if it is providing deep conceptual understandings of an extensive area.

From a technical point of view, the results are expected, e.g., if the environment keeps changing, then clearly it is not learnable! The adaptive regret that the manuscript relies on in several places is not sufficiently controlled, and the assumptions appear to be so rich for the presented results. I think it is good that some classes of policies are compared, but to provide a nice tutorial to the reader, the current presentation is too compact and needs more intuitions and insights. The premises are not clear not to be very restrictive. E.g., in (2.1), the benchmark has general notation but later in the manuscript, it depends on the interval under study. It is said that the disturbance is revealed to the learner, which is a consequential assumption. 

Most of the discussions on pages 6, 7, 9 are in a different context than that of the problem under study on pages 1-5.

Finally, there are multiple typos and frequent unclear sentences that I refrain mentioning here due to abundance.



limitations_and_societal_impact: NA
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies LTV systems control, which is a very challenging problem in my opinion. A set of interesting results have been obtained, including the non-equivalence between different control classes, and algorithms with adaptive regret bounds against different controller classes. Computational complexity in achieving sublinear regret against state-feedback controller has also been discussed. 

In general, I think this paper makes interesting contributions. However, I have some reservations on the notion of "adaptive regret". Further, I find some places in the presentation that need more discussions and clarifications. 

I will be happy to revise the score after rebuttal if these points are clarified. 
main_review: On adaptive regret:

- In (2.1), the algorithm $\mathcal{A}$ is not allowed to depend on interval I, correct?
- In the second term in (2.1), the $u_t^\pi$ and $x_t^\pi$ is obtained by applying $\pi$ from the very beginning t=0, although the summation in (2.1) is only on the interval I? 
- Why in the benchmark, one needs to consider a policy class? Why can’t we compare to the optimal offline solution when everything is known in hindsight?
- Also, in the second term in (2.1), the policy $\pi$ appears to be time-invariant, i.e. the policy parameters $M^{[i]}$ is not allowed to depend on the time instances  $t \in I$, is this correct? If so, if one only cares about $I = [T]$, the entire horizon, then comparing against a static, time-invariant policy doesn’t seem to make sense. 
- I find it not straightforward to understand adaptive regret. Can a low adaptive regret guarantee stability, i.e. the state size does not blow up as T grows? 

Assumptions: I find the open-loop stable assumption 1 to be strong. One of the basic (and oftentimes challenging) tasks in control is stabilization, yet this is put as an assumption. More discussions are needed. 

Results: I find Theorem 2.1 to be very interesting. Is there any intuition about this result? Having more discussions will be highly helpful. 

The control algorithm used in Algorithm 2 is DRC-OGD, but very few details are provided in the main text. I suggest adding more details here in the main text, e.g. what the algorithm is based on, and what is its guarantee for known systems. One question is does the control algorithm has to be DRC-OGD, or any algorithm that satisfies a certain regret guarantee for knonw systems will work? 

Thm 4.1: under a suitable stabilization assumption? What is the meaning? 

Line 313: What is the “nonparametric rate of regret” in the paragraph after Thm 4.1?

I am not sure what’s the point Thm 4.2 is trying to make. The paragraph before Thm 4.2 suggests the purpose of Thm 4.2 is to show the computational intractability in Thm 4.1 may be hard to avoid. But Thm 4.2 only shows the NP-hardness of finding the optimal state feedback control $K$. If I understand correctly, if one tries to compare against the best state feedback control, but the strategy is not limited to searching over a state feedback control, but search over some larger controller class instead, maybe it is still possible to achieve computational efficiency and sublinear regret? 

In the paragraph after Thm 4.2, it says “…there may be more clever convex relaxations (other than DRC and DAC, which provably cannot work)…” I guess the reason that DRC and DAC would not is due to Thm 2.1, if I understand correctly? 

limitations_and_societal_impact: More discussions on the notion of adaptive regret should be included, including its limitations.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies online control in linear time-varying (LTV) systems where the dynamics are unknown. The performance metric is the adaptive regret against three common classes of policies. When the benchmark policy class is DRC/DAC, the authors show a lower bound of the adaptive regret of any online controllers that grows linearly with respect to the length of horizon. This negative result demonstrate that the unknown LTV setting is qualitatively harder than either unknown linear time invariant (LTI) or known LTV, where sublinear regrets are achievable. On the other hand, they also propose an online control algorithm whose adaptive regret matches the lower bound in the same setting.  When the benchmark policy class is static feedback controllers, they show that although sublinear regret is achievable under some restrictive assumptions, planning over this policy class is computational inefficient in general.
main_review: This paper makes original and significant contribution to the online control literature. The problem setting under consideration is very important. As the authors discussed in the introduction section, since many positive results on adaptive regret have come out in either unknown linear time invariant (LTI) or known LTV settings, it is natural to ask whether these results extend to the unknown LTV setting, which is more common in practice. A negative lower bound result in this setting helps to demonstrate the hardness of this problem, and prompts us consider other performance metrics (e.g. competitive ratio) as discussed in Section 5. A limitation is that Assumption 1 and 2 seem to be restrictive. Although Appendix A.2 says the results still hold if a nominal stabilizing controller is known, it is unclear why such controller must exist and how to find it.

The paper is well-organized and written clearly. All claims are supported by theoretical results, and the assumptions are stated clearly. Although I did not check the proof in detail, the results look technically sound to me.

limitations_and_societal_impact: Yes. I did not see any potential negative societal impact of this work.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper studies the online control of unknown Linear Time-Varying (LTV) systems in the nonstochastic control setting. They present in-depth theoretical results given the aforementioned problem setting that shows the following (in the order presented in the paper):
1. Statement that the regret for the DAC/DRC policies cannot scale sub linearly in the time horizon (lower bound)
2. An algorithmic upper-bound for online prediction
3. Applying (2) to the online control problem
4.Theoretical analysis showing that sublinear regret is possible but in non-polynomial time (computationally inefficient) unless P=NP)
main_review: Quality: 
+The authors provide a comprehensive yet concise literature survey, distinguishing the results by problem setting (i.e. LTV/LTI, known/unknown dynamics, nonstochastic/stochastic noise, full-state/partial-state observation) 
+ The authors provide in-depth theoretical results
+ The authors are very clear on the assumptions made in their analysis
- The paper could be improved to have simulation results similar to citation #16 (Adaptive regret for control of time-varying dynamics) though I understand that the main result is sufficient.
- It would be helpful to note that citation #20 (The nonstochastic control problem) studies unknown time-invariant dynamics (to clarify the difference with the authors’ work)


Clarity:
+ Overall, the paper is well written and organized (the flow is readable i.e. 1. Statement that the regret for the DAC/DRC policies cannot scale sub linearly in the time horizon (lower bound) -> 2. Proposing algorithmic upper-bound for online prediction -> 3.Applying this algorithm to the online control problem -> 4.Theoretical analysis showing that sublinear regret is possible but in non-polynomial time (computationally inefficient) unless P=NP)
+ They provide very detailed theoretical analysis

Originality:
+ After a brief search, it does appear that they are the first to look at the setting: Unknown LTV system dynamics in the non stochastic control setting. 
+ The results of studying and comparing the three classes of the controllers are novel, fresh, and interesting. The reviewer also gains new insights about the three classes of controllers. 


limitations_and_societal_impact: No issues were noted.
review_title: null

Meta-review: Three of the four reviews were quite positive.  There was one negative review, and I think the authors response was adequate to address concerns raised.
Decision: Accept (Poster)