Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper addresses the unconstrained stochastic linear-quadratic dual control problem with online parameter identification in an online setting, where a near-optimal control policy is sought to minimize the infinite-horizon quadratic cost (i.e. stabilizing the linear dynamical system) while learning the initially unknown matrices A and B. Instead of deriving a regret bound with a high probability done in the standard certainty equivalent learning schemes, this paper focuses on the almost sure convergence to the optimal control performance. The presented main contribution is the proposed switched control strategy (a stability-augmented certainty equivalent controller) and a parameter inference scheme that estimates the impulse response of the dynamical system in contrast of the matrices A and B. Theoretical analysis of the convergence rate of inference error and control performance is provided. Simulation results on the Tennessee Eastman Process (TEP) are given to validate the proposed LQ dual control algorithm. 
main_review: The studied problem of online learning for LQR control is a very interesting topic and has gained significant attention lately. There are many existing results on the regret analysis in a probabilistic setting, e.g. using certainty equivalent control strategy. Compared to that line of work, the key difference in this paper is the modified version of the standard certainty equivalent control strategy, by allowing the system to take zero action for a certain amount of time and avoid potential destabilization. While the reviewer found this idea intriguing, there are places where further clarification is needed to better justify the claims. Please see detailed comments as follows:

- Safety v.s. stability: it is a bit confusing to use the notion of safety rather than stability in the paper, since safe learning often refers to a different problem where a dynamical system is expected to avoid entering certain risky states during learning. The reviewer would suggest to use stable/stability that better describe the discussed problem here. 

- Motivation of using Markov parameter inference: while the convergence of parameter inferences looks good, it is unclear why not use the standard least square estimation that directly estimate the matrices A and B. Or in other words, will it disrupt performance and estimation guarantees if switching to the least square approach?

- Proof of theorem 1: One key claim is that all policies derived from the proposed learning process is stable, which seems to mainly rely on the assumption of the innate stability of the system without external control input. However, it is difficult to see how this could be justified given the switching control strategy which also has the normal certainty equivalent control component with exploration noise. For example, it seems the proof of Theorem 1 (Section A.2) only discusses the innate stability analysis when \norm{x_i} is larger than log k. Also, given the assumption of the innate stability with the matrix A, wouldn’t that be straightforward to simply take no-action and thus converging to the origin easily?

- Correspondence to optimal rates with high probability: While it is claimed that the derived performance match up with the known optimal regret in the high probability regime, the reviewer does not find the analysis. Authors are encouraged to provide more details in the main context to help build the connections. For example, it is still unclear to me how the almost sure performance is achieved despite the stochastic noise in the dynamics. 

- Experimental results: there are no comparison results to other work (e.g. standard certainty equivalent control), which is a weakness to the reviewer. 

===== After Rebuttal ======
I appreciate the authors’ responses and revised content. Given the remaining concerns from the reviewer, additional feedback has been provided in the detailed response to help strengthen and justify the technical contribution further.

summary_of_the_review: The paper is in general well-written, but the reviewer still has several critical concerns over the justification of the claimed property due to lack of enough details. Authors are encouraged to provide more discussion in the main context to justify how the proposed components lead to the improvement compared to the standard approaches. More comparative results to other baseline algorithms are necessary to demonstrate the claimed significance of the proposed algorithm.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies an adaptive control for LQR and provides an algorithm to converge to the optimal policy almost surely in an asymptotic sense, where the convergence rate is also provided. The paper assumes that the system is open-loop stable, and switches to zero control input (with exponentially decaying excitation noises) for a while when the state or control gain is larger than O(log(k)), which can steer the state to a smaller neighbourhood of 0 due to the open-loop stability of the original system. Theoretically, the paper shows that any switched policy generated by the algorithm guarantees a finite infinite-horizon-averaged cost, which is called "safe" in this paper. Further, the paper establishes the strong consistency of the Markov parameter estimation in Alg 3 with an error convergence rate. Besides, the paper shows that the learned policies converge to the optimal policy at a rate of O(1/sqrt(k)) in terms of the infinite-horizon-averaged cost. Lastly, the performance is evaluated with different parameter choices of the algorithm.
main_review: The question asked by the paper is very intriguing: establishing a.s. guarantees instead of w.h.p. guarantees for learning-based control is indeed very important for safe implementation on physical systems. Hence, I read the paper with great interest and checked the proofs of the paper. The paper is well-written. However, I have several concerns listed below.

1. [Def 2] My biggest concern on the safety definition is on Def 2. In this paper, a time-varying sequence of policies is considered, thus inducing a time-varying system. It is well-known that the stability of individual time-invariant systems does not guarantee the stability of the time-varying systems, even for linear systems, i.e. even if Ak is stable for all k, the linear time-varying system x_{k+1}=Ak x_k can no longer be stable. In fact, this is one of the major difficulties in adaptive control, i.e. how to guarantee stability while updating the policies. One approach to get around this is by considering piecewise-constant policies (or episodic based policies) as in most papers on learning-based LQR. But this paper updates the policy at every step, which calls for other ways to ensure closed-loop stability (e.g. slowly varying policies), hence I found it weird to define stability/safety purely on individual policies. 

2. [Def 1 and Theorem 1] Further, for Def 1, the definition makes sense for linear systems because a finite stochastic LQR's cost happens to coincide with the stability of a linear policy u=Kx. However, the policy designed in Algo 2 is essentially a nonlinear policy or piecewise linear policy. For nonlinear policies, a more common stability notion is input-to-state stability (ISS), which essentially requires that if the noises are small, then the states will be small. However, Def 1 does not seem to capture this. Further, Def 1 does not seem to require the stability of K used when |x|< log(k) for some index k in the policy structure considered in Algo 2. This suggests that a safe policy according to Def 1 may constantly steer the state to a distant though bounded location even when the system noises w are very small. Hence, I found the safe definition in Def 1 quite weak and it can be satisfied by merely adding this switch-to-0 policy structure without implying any stability property on the system.

3. [Algo 3 and Theorem 2] The Markov parameter estimation is very interesting. But I hope the authors can provide more explanation on why using Markov parameter estimation instead of the traditional least-square estimation directly on A, B. For output-feedback, it is more intuitive to learn markov parameters, but for full-state-feedback, learning markov parameters seem to increase the number of parameters to be learned, thus increasing the sample complexity and slower the learning. The only reason I can imagine from reading the paper is that the authors are able to establish the a.s. convergence rate of Alg 3, while the current literature on least-square estimation usually gives results on finite-sample confidence bound with some probability p<1, e.g. [Dean et al. 2018]. That being said, those literature focuses on the finite-sample case, but this paper considers the asymptotic case, so I am struggling to compare the results in this paper and in the literature. From one side, since ordinary least square also has strong consistency, so least square estimation should also result in a.s. convergence in the asymptotic sense, right? From the other side, how does Theorem 2 extend to the non-asymptotic case? I guess the result will still look like confidence bound with some probability in (0,1)? I would really love to hear the authors' thoughts on this.

4. [Theorem 3] The authors compare Theorem 3 with the regret analysis in (Simchowitz & Foster (2020)), but I found this comparison not straightforward. Notice that J^pi_k does not represent the stage cost, but the infinite-horizon-averaged cost by implementing the policy generated at time k in a separate trajectory for infinitely long. So summing J^pi_k over k does not directly represent the realized cost of the adaptive learning algorithm. Could the authors provide more comments on this difference from the standard regret guarantee? 

5. [Simulation] I appreciate the numerical results provided in this paper. I just wonder how this algorithm compares with existing adaptive learning algorithms? it would be great to show that some scenarios where some existing adaptive learning algorithm does not converge but your algorithm does.

summary_of_the_review: The paper asks a very important question: establishing a.s. guarantees instead of w.h.p. ones for safety. The paper is well-written. However, the safety definitions introduced in this paper do not indicate the stability of the system in any sense, thus I found these safety requirements relatively weak. Further, though the authors compare the results with the regret bounds, Theorem 3's result does not directly reflect the regret, so I hope to see more comments on the connections between Theorem 3 and regret. Lastly, the paper establishes a.s. guarantees only in the asymptotic sense, instead of for finite samples. Since the least square estimation used in the current literature also converges a.s. asymptotically, I am not sure how much progress this paper provides compared with the literature. I think it would be much more interesting to establish a.s. guarantees in non-asymptotic cases (some random example that comes to me right now is  Regret <o(T) a.s. for any finite T, instead of w.h.p., but any other a.s. guarantees would be great, especially in constraint satisfaction, which is also an important requirement for safety).
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper addresses the problem of combining system identification and optimal control in an online framework for stable linear systems with full-state sensing. Despite the restrictions of linearity, stability, and full-state sensing, the proposed problem formulation is still challenging and I am unaware of any results which provide the same optimality guarantees provided by the authors in the online framework. The paper itself is unusually well-conceived, well-written, well-structured, is clear, and makes very efficient use of notation.
main_review: Although my overall impression of the paper is positive, there are several concerns which limit the significance of the result. First, while the definition of a "safe learning process" is clearly articulated in Definition 2, such a definition by itself does not ensure stability, as the act of switching between stable policies may be unstable -- as observed by the authors. While the authors address this issue using inherent stability of the process and implementing what is effectively a kill switch, such an approach is clearly conservative, and, moreover, there is no statement in the main results directly establishing stability of the trajectories (although clearly such trajectories are bounded).

This brings up the second point, which is that the proposed approach is rather cautious. Convergence in the simulation seems to require $~10^8$ time steps - presumably due to the rather large state-dimension of the numerical example.

Another point which I found significant is the omission of the vast literature on the problem of adaptive control (aside from the 1960 paper). While clearly the adaptive control approach is dated and only estimates a few system parameters, it considers precisely the problem formulated by the authors. 

Finally, I would have liked to see more justification for the estimate of the performance metric in the numerical analysis. It is unclear to me that Algorithm 2 actually produces a policy -- as opposed to simply the next input value. Yet computing the objective requires such a policy. What is being done here?

If the issues mentioned above can be satisfactorily addressed, the paper should be suitable for publication.

Notes:
- Why is there no $B_2$ matrix for representing the effect of process noise?
- It is unclear if the numerical examples include process noise and if so, what are the properties of this noise?
- The simulated is system is non-trivial and provides plausible insight into the performance of the algorithm.
- Remark 2: Can the authors support "easily satisfied" with a proof or reference?
- The use of $J^{\pi_k}$ is a bit unclear. Algorithm 2 does not actually return a policy -- only the next input and internal state. How can a policy be extracted from this algorithm? -- a policy which is needed to compute the performance index.
- Define "almost surely" in Theorem 2.
- Typos: "The complete algorithm we propose LQR dual control is presented in Algorithm 1."; "would suffice characterize"; ""

summary_of_the_review: My overall impression of the paper is positive. While the switching between policies seems a bit ad-hoc, the performance and convergence guarantees are solid -- correctly formulated and true. The paper addresses a real problem of current interest and provides a solid theoretical foundation for the proposed method. The numerical simulations are non-trivial and convincing. I have some minor concerns, but they can likely be addressed in the author response.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies reinforcement learning policies for an unknown linear system with quadratic cost functions. It is shown that the presented algorithm provides consistent estimates and the rates are provided.
main_review: Update: After the edits the authors did, together with the edits they promise to do, the paper can be accepted.
_________________________________________________________
Original Review: Regretfully, the manuscript cannot be accepted due to different issues. First, it aims to re-establish existing results. Moreover, there are frequent incorrect and/or incomplete claims in the manuscript. Unfortunately, lack of novelty, lack of connections to existing work, incomplete literature review, unsupported and/or wrong statements, and subpar presentation, prevent the manuscript from being accepted.

The claim that high probability results do not imply almost sure convergence is ONLY true if the failure probability is a design parameter. (Of course, even in this case, by letting it shrink as time grows, we obtain almost sure convergence). So, to see a work that failure probability is not a used in the algorithm, search for "Input perturbations for adaptive control and learning" and see the reference therein. Specially, one of the references exactly establishes the almost sure results this manuscript aims to provide. Further, in the existing literature, the problem is addressed without the assumption of open-loop stability (or initial stabilizer), and I recommend the authors to use google scholar to find the rich literature of adaptive stabilization. 

Here, I mention a few more issues, but there are multiple similar things the authors need to address for resubmitting the manuscript. The existing literature also relaxes the assumptions on the noise so that neither normality nor stationarity are needed. Also, there are results on worst-case performance (ie stochastic sub-optimality) which are stronger than the approach of average-case (ie expected) sub-optimality of the manuscript. I guess by "learning process" in Def 2 the authors mean 'sequence of policies'. It is unclear why line 7 of algorithm 1 is better than the least-squares estimate (although it is very similar). About Lem 10, isn't it an immediate consequence of sub-Gaussianity? Statement of Lemma 1 assumes full accuracy, and so is unacceptable and does not provide consistency (as the authors claim). "It should be noticed ..." on p8 is not accurate. Finally, "TS is in general computationally inefficient" needs justifications.

 
summary_of_the_review: Update: After the edits the authors did, together with the edits they promise to do, the paper can be accepted.
_________________________________________________________
Original Summary: Regretfully, the manuscript cannot be accepted due to different issues. First, it aims to re-establish existing results. Moreover, there are frequent incorrect and/or incomplete claims in the manuscript. Unfortunately, lack of novelty, lack of connections to existing work, incomplete literature review, unsupported and/or wrong statements, and subpar presentation, prevent the manuscript from being accepted.
review_title: null

Meta-review: The main contribution of the paper is in providing an additional layer to standard certainty-equivalent control for LQR dynamics, that essentially prevents the state from exploding exponentially, via forcing a "descent" to a small bounded state space in growing epoch sizes. Theoretically, this is shown to ensure a notion of boundedness which is termed as "bounded cost safety".

Overall, the reviewers raised several concerns in their initial reviews. These included the relevance of the proposed new approach to modeling "safety" here, whether it is actually novel given the assumptions about open loop stability of the original plant, the fact that the learning algorithm could take the state to arbitrarily large states durign the learning process, the significance of the contribution of the paper wherein a "kill switch" is effectively being designed depending on the state norm, whether least squares is an arguably simpler system estimation method compared to the impulse response estimator here, whether existing approaches based on an input failure probability parameter can be used to yield the same result by iteratively taking it down to zero, and other concerns about the technical exposition.

The author(s) provided detailed responses to the reviewers' concerns. Specifically, the safety/stability notion was clarified as being distinct from standard input-to-state stability, that the learning algorithm could, during its operation, drive the system state to arbitrarily large sizes (although asymptotically almost surely this is supposed to not happen), and how this paper's assumptions are different (and lighter) than other related work that achieves almost-sure guarantees.

In the discussion that ensued after the author response period, it was clear that the author responses had helped to address many of the reviewers' concerns. However, the overall impression has still not been convincing enough to recommend acceptance. This is primarily on two fronts, which I hope that the author(s) can address in the future to strengthen the submission: (1) The attempt at expressing "safety of learning" is found to be not satisfactory, in view of the observation that the proposed scheme does not guarantee classical notions of stability while in the process of learning. It also makes the main message of the paper confusing -- the reviewers noted that the words "safety" and "safe learning" still recur in the revised manuscript, creating scope for misinterpretation. (2) The algorithmic contribution appears to be incremental -- its essence is to "apply the brakes when the car runs too fast". This is not to take away from the hard work put in to analyzing the algorithm and deriving guarantees. (3) The experiments benchmarking the proposed strategy are not comprehensive
-- more relevant baselines drawn from existing work, such as the ones
that have emerged from the author response discussion, could be compared against. In fact, it would be compellingly in favor of this submission for the author(s) to show that other approaches fail to offer the same kind of "safe" performance that is expected.

Upon a more careful reading by myself in the recent past, I would also like to bring up a fundamental technical criticism about Theorem 1 and Defn. 2 ("bounded-cost safety"), which I believe must be fixed before the paper's conclusions can be accepted. Defn. 2 states that a learning process if bounded cost safe if for all times $k$, $\pi_k$ is not destabilizing in the sense that its value function is finite. However, the sequence of policies $\pi_k$, $k=1, 2, \ldots$ is a sequence of
*random* objects. So in what sense is Defn. 2 to be interpreted? If
the author(s) mean(s) to say that the event {$\forall k=1, 2, ...: \pi_k$ is not destabilizing} occurs w.p. 1, then this is a very strong requirement and cannot be guaranteed (random noise can cause a 'bad' controller to be learnt and applied at some time t with positive probability). Basically my contention is that Defn. 2 is incomplete for a theory-oriented paper like this, and as a consequence I do not see why Theorem 1 should hold (or more precisely, in what sense it should hold). The proof of Theorem 1 is not clear as well: The expectation in the third sentence of Sec A.2 ought to be taken for a
*fixed* controller $\hat{K}_k$ *always applied* to a system from time
zero until infinity. I do not see why a fixed controller's (standard infinite horizon average) cost should always be finite, leading me to suspect an irregularity in the proof argument. I wish this point could be discussed and resolved earlier in the author response phase, but it is unfortunately too late.
Decision: Reject