Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The authors revisit an old approach to LQR, called RBMLE, and reconcile it with UCB-based methods. They show regret guarantees and good empirical performance.
strengths_and_weaknesses: I want to highlight that I am not familiar with the LQR setting, and I do not know part of the literature that the authors build on, in particular RBMLE approach to LQR. 
I apologize with the authors and the meta-reviewer as I can only offer an educated guess; my review should be appropriately discounted.

The paper appears not to be written in a professional way. There are some inconsistencies both in the fonts and on the overall presentation style. As stated, the sequence of Lemmas is the regret analysis is not useful to understand what is going on. At a minimum, I believe that the paper writing would need to be improved for the paper to be accepted.  

I have some trouble interpreting what the main result aims to convey. What \widetilde O hides here? Any dependence on the dimensionality of the system appears to be missing in the main regret bound. Shouldn’t there be any? I think the authors should try to clarify this point in the rebuttal. To me, this is the most troubling aspect of the paper.

While it appears the algorithm proposed here has better numerical performance, in practice I expect the constants in the construction of confidence intervals to play a leading role in this. I am unsure what choices were made here for this and other algorithms in order to obtain a comparison, but the point here is that the observed numerical performance may be justified by reasons that are different from the theoretical ones expressed in the paper. 

Again, my apologies if I missed some important points in the paper.
questions: See above on the form of the regret bound
limitations: see main review
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper revisits two commonly used approaches in online adaptive LQR control: Reward-Biased Maximum Likelihood Estimate (RBMLE) and Upper Confidence Bound (UCB). The authors show that these two methods can be reconciled, and thereby propose an Augmented RBMLE-UCB algorithm that combines the penalty from the RBMLE method and the confidence interval of the UCB method. Theoretically, the authors establish a $O(\sqrt{T})$ regret upper bound. Empirically, the proposed algorithm outperforms several baselines in online adaptive LQR control.
strengths_and_weaknesses: Strengths: the connection between RBMLE and UCB is interesting and the empirical performance of the proposed augmented RBMLE-UCB algorithm is sound.

Weakness: the theoretical analysis is mainly adopted from the analysis of the UCB method in [3], and the empirical performance is mainly from RBMLE. Therefore the contribution is limited.
questions: Please see the limitation section below.
limitations: Since 2011 (when the paper [3] is published), there are over 1000 papers studying online LQR control via learning-theoretical perspectives. In particular, the 2021 paper by Simchowitz and Foster "Naive Exploration is Optimal for Online LQR" clearly shows that the regret lower bound of online LQR control is $O(d_u^2 d_x \sqrt{T})$. Moreover, a "naive" CE control plus continual exploration (i.e., solve $K$ from OLS and $u=Kx+\mathrm{noise}$) exactly matches this lower bound! Therefore, the reviewer believes that a new paper needs to be novel and impressive enough to be published at a top conference since this field is already very crowded. 

This paper provides a new algorithm for online LQR control with theoretical justification (a $O(\sqrt{T})$ regret bound) and empirical benchmarking. However, it is unclear whether the novelty is enough: Theoretically, the analysis framework is mainly from the classic UCB (OFU) method from [3]. The extra regularization term $\alpha J^*$ from RBMLE seems not fundamentally change the analysis. Empirically, the performance of the proposed augmented RBMLE-UCE approach seems to inherit from RBMLE. In Table 1, the regret numbers of RBMLE and the proposed method are exactly \emph{identical}! Given the fact that there is no regret bound for RBMLE, it seems that the UCB part is only for theoretical analysis, and does not contribute to the empirical performance at all.

Minor points:
1. In Eq. (6) and other related equations, please do not use $()^2$ as the norm of a vector. Please use $||\cdot ||^2$.
2. Assumption 3 is actually very strong. Stabilizable $(A,B)$ only guarantees the spectral radius of $A+BK$ is less than 1, rather than the 2-norm. Please comment on this.
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: This paper proposes RBMLE and ARBMLE algorithms for LQR with unknown dynamics. The authors point out that RBMLE for LQR can be viewed as a penalty version for constrained optimization in UCB for LQR. For theoretical purposes, additional constraints are added to the unconstrained optimization (4) in RBMLE, yielding ARBMLE. An O(sqrt T) regret bound is provided for ARBMLE. Then, several numerical experiments are conducted to show that RBMLE and ARBMLE yield similar performance and achieve better performance than existing methods. 
strengths_and_weaknesses: The paper is very well written. The connection between RBMLE and UCB in the LQR problem is interesting and inspiring. The augmented version ARBMLE achieves the best regret order in terms of T. Numerical results show promising improvements over the existing methods. The appendices are also written clearly. The proof is standard and correct.

However, I have the following concerns and questions.

1. [Tractability] UCB-LQR is known to be intractable when the dimensionality is large due to the involved constrained optimization. Since ARBMLE also involves the constrained optimization, the proposed algorithm also suffers the tractability problem. 

2. [Same numerical results for RBMLE and ARBMLE] The authors claim that numerically, RBMLE and ARBMLE always generate the same theta_t. I found this quite surprising. Does this result still hold for different choices of alpha0 and lambda and beta_t(sigma)? 

3. [Dependence on dimensionality] Though the regret bound is optimal in terms of the dependence on T, the dependence on the dimensionality of the problem is not discussed. It has been shown that CE-type (certainty-equivalence) methods can achieve optimal regret even in terms of n and m. How does the regret of the proposed method compare with the optimal dimensional dependence in the literature?

4. [Numerical results] The authors provide four interesting numerical experiments to demonstrate the improved performance. However, all of the experiments consider a relatively small dimensionality.  How do the algorithms perform for larger dimensions, especially in comparison with CE-type methods?

=== Typos ===
1. Line 168: it should be \mathcal S instead of S.
2. Line 253: furtjer.
questions: See above.
limitations: No
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 addresses the control of a fixed stochastic linear system of known order but unknown parameters with the objective of minimizing a finite horizon quadratic cost. The solution to this problem when the parameters are known (and under certain assumptions) is a well known result. However, when the parameters are unknown, various approaches have been suggested and explored. Many of these are mentioned in the introduction of the paper. 

The paper re-examines an approach that first appeared in 1982 (ref [1]): Reward Biased Maximum Likelihood Estimate (RBMLE) but with a new twist. The new twist is to unite RBMLE with another approach known as upper confidence bound (CB) from 1985 (ref [2]). This allows the authors to show that RBMLE is a penalty version of of the UCB approach; This admits a finite time regret bound for the modified algorithm of $O(\sqrt{T})$, the best bound to date.  

Through a series of simulations using established test-bed systems, the paper verifies that the new algorithm (ARMBLE) outperforms other methods, except RBMLE which achieves comparable performance.

strengths_and_weaknesses: (S) Very well written, with clear explanations and a very solid and insightful analysis of a classic problem. Results in the best regret bound known to date.

(W) This is a somewhat specialized theory result. Perhaps its worth explaining in greater detail its value to the community. 
questions: Line 49: OFU is used before being defined.

Line 141: "synergies to in fact fashion" perhaps simplify to "synergies to fashion"

Line 180: Space after ${\cal F}_t$, 

Line 191: "the the".

Line 192: In equation on next line $min$ should be $\min$

Line 268: $\theta_{ARBMLE}$ should be $\theta_{\rm ARBMLE}$ and $\theta_{OFU}$ should be $\theta_{\rm OFU}.$

limitations: Nothing stands out. One suggestion is listed above. Since this is a somewhat specialized theoretical result. Perhaps its worth explaining in greater detail its value to the community.
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: This paper develops a Reward-Biased Maximum Likelihood Estimate-Upper Confidence Bound (RBMLE-UCB) policy for controlling a stochastic linear system with quadratic costs, when its system parameters are not known to the agent. This problem is sometimes called the adaptive LQ control problem. The authors prove that this policy achieves the best-known square-root-T regret rate, and they empirically show via several numerical experiments that this approach is competitive against existing ones.
strengths_and_weaknesses: The strengths of the paper are that the proposed policy is interesting, the theoretical analysis is excellent, and the numerical experiments are compelling and convincing in the quality of the proposed policy.

I do not think the paper has noticeable weaknesses.
questions: I do not have any questions.
limitations: Not applicable
review_title: null

Meta-review: metareview: Reward-Biased Maximum Likelihood Estimate (RBMLE) is an approach to balance exploration-exploitation that is based on biasing models with smaller cost functions. The paper considers an augmented version of it (ARBMLE) that confines the search of the model to the confidence set used by an Upper Confidence Bound (UCB)-like algorithm. The paper considers the Linear Quadratic Regulation (LQR) with unknown dynamics, provides a regret bound of ARBMLE, which is comparable to that of UCB-based approach. The paper empirically shows that both ARBMLE and RBMLE outperform many other methods, particularly UCB-based ones.

We have both strong support in favour of acceptance of this paper and some less enthusiastic negative reviews. After reading the paper, the reviews, and the discussions, I am inclined to accept the paper. The main reason is that the paper considers a relatively less-known approach to exploration-exploitation problem, provides reasonable analysis (even though the tools might be standard), and shows promising empirical results. However, my recommendation should not be considered as dismissing the concerns of reviewers. I believe many of them are valid. I merely put less weight on them in my evaluation compared to the negative reviewers.

Let me emphasize a few points brought by reviewers and my own reading of this work. I hope the authors consider them in the revision of their paper.

- The writing quality varies a lot. The first two sections are written clearly and have some nice insights and intuitions, but then the writing quality deteriorates. For example, Section 3.2 becomes confusing (we have E_t, E_1, E_2 with different meanings), and Section 5 becomes a series of lemmas without much insight. Sections 6 and 7 are of better quality again.

- The series the sequence of lemmas in Section 5 is not very insightful. The authors have added a paragraph at the beginning of that section, but I believe that is not enough. My suggestion is that authors either provide better intuition behind each of these lemma, or move them to an appendix.

- Be clear about the dependence of the regret bound on the dimension of the system.

- Assumption 3 requires more discussion.

- The issue of tractability of solving the required optimization problem should be discussed explicitly.

- Given that [31] (Mete et al., "Reward biased maximum likelihood estimation for reinforcement learning", 2021) solves an arguably more general problem (RL instead of LQR), a detailed comparison is needed. What are the differences in insight, proof techniques, etc.?
confidence: Certain
Decision: Accept