Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulator
We consider adaptive control of the Linear Quadratic Regulator (LQR), where an unknown linear system is controlled subject to quadratic costs. Leveraging recent developments in the estimation of linear systems and in robust controller synthesis, we present the first provably polynomial time algorithm that provides high probability guarantees of sub-linear regret on this problem. We further study the interplay between regret minimization and parameter estimation by proving a lower bound on the expected regret in terms of the exploration schedule used by any algorithm. Finally, we conduct a numerical study comparing our robust adaptive algorithm to other methods from the adaptive LQR literature, and demonstrate the flexibility of our proposed method by extending it to a demand forecasting problem subject to state constraints.
Optimism in the Face of Uncertainty (OFU): Abbasi-Yadkori and Szepesvári [1], Faradonbeh et al. [8], and Ibrahimi et al. [11] employ the Optimism in the Face of Uncertainty (OFU) principle [5], which optimistically selects model parameters from a confidence set by choosing those that lead to the best closed-loop (infinite horizon) control performance, and then plays the corresponding optimal controller, repeating this process online as the confidence set shrinks. While OFU in the LQR setting has been shown to achieve optimal regret O( √ T ), its implementation requires solving a non-convex optimization problem to precision O(T −1/2 ), for which no provably efficient implementation exists.
Thompson Sampling (TS): To circumvent the computational roadblock of OFU, recent works replace the intractable OFU subroutine with a random draw from the model uncertainty set, resulting in Thompson Sampling (TS) based policies [2,4,16]. Abeille and Lazaric [4] show that such a method achieves O(T 2/3 ) regret with high-probability for scalar systems. However, their proof does not extend to the non-scalar setting. Abbasi-Yadkori and Szepesvári [2] and Ouyang et al. [16] consider expected regret in a Bayesian setting, and provide TS methods which achieve O( √ T ) regret. Although not directly comparable to our result, we remark on the computational challenges of these algorithms. Whereas the proof of Abbasi-Yadkori and Szepesvári [2] was shown to be incorrect [15], Ouyang et al. [16] make the restrictive assumption that there exists a (known) initial compact set Θ describing the uncertainty in the system parameters, such that for any system θ 1 ∈ Θ, the optimal controller K(θ 1 ) is stabilizing when applied to any other system θ 2 ∈ Θ. No means of constructing such a set are provided, and there is no known tractable algorithm to verify if a given set satisfies this property. Also, it is implicitly assumed that projecting onto this set can be done efficiently.
The authors propose a polynomial time algorithm for robust adaptive control of unknown linear systems (with quadratic objective functions). The algorithm provides a sublinear regret of O(T^{2/3}) with high probability. Moreover, a lower bound on the expected regret is provided by studying the relation between system parameter estimation and regret minimization problems.   The paper is well written, the problem is relevant, and the authors succeed in effectively placing their work relative to the existing literature. I have to admit that I haven't been able to follow details of many of the technicals developments provided in the supplementary material. Furthermore, several issues should be addressed in the revised version.   High-level comments:  - It would be useful if the authors could please explain why regret provides a proper metric for quantifying performance of an algorithm with uncertain parameters. I recognize that several other references also use regret but I'm not sure why this is a proper metric for evaluating performance of controllers for uncertain systems.   - The paper provides probabilistic guarantees. Since there are many sources of stochastic uncertainty, it would be useful if the authors could please clarify what feature of the problem leads to the results that hold with high probability. I would also like to understand how the choice of parameter \delta in the problem setup affects the algorithm.   - The system-level synthesis appears to be a key technical enabler for the controls part of the paper. This approach leads to an infinite-dimensional synthesis problem and the authors go around this issue by solving a finite-dimensional approximation based on FIR. In contrast to standard LQR, the resulting controller appears to be dynamic and it is not clear how much conservatism FIR restriction introduces and how the FIR truncation length  influences the performance. It would be useful if the authors could provide some additional comments about this.    - Technical comments:  - According to the Appendix G.3, the 8th line of the algorithm which is an infinite-dimensional problem can be brought into a finite-dimensional SDP using an approximation based on FIR. Since solving large SDPs is in general challenging, the computational complexity should be discussed. Please explain how such problems can be handled for large-scale systems.   - While the OFU-based method can achieve an optimal regret in LQR problems, the authors state that there is no efficient algorithm for solving non-convex optimization problems in OFU. Along the same lines as in the previous comment, the authors should provide computational complexity analysis of their algorithm and compare it to OFU for a large-scale system. This is important mainly because of recent developments in solving the non-convex optimization subroutine encountered in OFU. On a related note, the paper would benefit from a larger numerical example in Section 4 to better compare the efficiency of various methods against one another.  - Line 6 of the algorithm uses a least-square approach to find the estimates of the matrices A and B. However, this method does not necessarily provide a correct estimate of A (e.g., the estimate \hat{A} may turnout to be stable for an unstable system which may have a detrimental influence on the performance of the designed controller). Moreover, Theorem A.2 depends on the existence of (I + \hat{\Delta})^{-1}, where \hat{\Delta} is unknown. Since the authors utilize non-standard techniques based on recently introduced system-level synthesis, some additional discussion would be useful on how the tools from robust control theory lead to such an estimate. Please also comment on how this affects the practical aspect of the proposed approach and how one should determine the constants of Algorithm 1 (e.g. C_x, C_u, and \rho) when the dynamics are unknown.   - Showing the performance of various algorithms against the number of iterations can be misleading, especially when the algorithms involve subroutines that require different computational complexity. In addition to Figure 1, please also provide performance curves as a function of computation time.  - Please discuss sensitivity of the performance of the proposed algorithm to the choices of C_\eta, \gamma, and the FIR truncation length F.  - It is stated that the outer minimization in Step 8 of the algorithm can be solved via bisection. For larger values of gamma, the inner minimization problem is relaxed meaning that the optimal objective of the inner minimization becomes smaller. However, the coefficient 1/(1-gamma) in the outer minimization increases. Hence, it is unclear why a bisection can find the optimal gamma.  Minor issues:  - How does the assumption of Gaussian noise influence the results (if at all)?  - Line 226: please provide a reference for the heuristic projected gradient descent implementation of OFU.  - Line 43: please define ’T’.  - It would be useful to explain the choice of parameter \sigma_{\eta,i}^2 inside the algorithm as well.  - Line 34: please explain what is meant by ‘PAC-learnable’.  - Line 103: “thereore” should be “therefore”.  - Line 181: "degredation"  - Line 183: “,” should be “.”.  - Line 383: "problemmmm"