betaFeedback

WorksMathematics

Polylogarithmic Regret via Certainty Equivalence in Degenerate LQR

Abstract

Singular input penalties, as in minimum variance control, can reduce what must be identified to control an unknown linear system. In online linear quadratic control, certainty equivalence can achieve polylogarithmic regret when the optimal controller is identifiable from data collected under optimal feedback. With a positive definite input penalty, however, this condition is restrictive, since for an invertible state matrix it requires all unknown parameters to be identifiable under optimal feedback. We show that singular input penalties relax this requirement, expanding the class of problems in which certainty equivalence achieves polylogarithmic regret. Specifically, we prove that a certainty-equivalence algorithm with a short initial exploration phase achieves O(log⁡2T)O(\log^2 T) expected regret over TT interactions whenever controller identifiability holds. We complement this guarantee with an Ω(T)Ω(\sqrt{T}) minimax lower bound for a family containing a system where controller identifiability fails. For minimum variance control, knowing the range of the input matrix suffices for controller identifiability, a weaker requirement than knowing the full input matrix, as assumed in prior work with positive definite input penalties. This condition also covers underactuated systems, as we illustrate with a cart-pole example.

Introduction

Learning to control an unknown system during operation requires balancing exploration, which collects informative data to reduce uncertainty about the dynamics, with exploitation, which uses the available knowledge to achieve good control performance. The linear–quadratic regulator (LQR) with unknown dynamics has become a standard benchmark for studying this trade-off in online control and in reinforcement learning with continuous state and action spaces. In LQR, under a fixed feedback ut=Kxtu_t = Kx_t, the next state xt+1=Axt+But+wtx_{t+1} = Ax_t + Bu_t + w_t depends on (A,B)(A, B) only through the closed loop A+BKA + BK, so models that share this closed loop cannot be distinguished from the collected data. A certainty-equivalence (CE) learner, which always plays the controller that is optimal for a nominal system estimate, may therefore keep collecting data that cannot reveal such model errors. Moreover, classical results show that convergence of self-tuning LQ controllers to the optimal controller generally requires identification of the true parameter [19]. This motivated a variety of exploration strategies [1, 18, 3], which attain the worst-case optimal O~(T)\tilde{O}(\sqrt{T}) regret rate over TT interactions with the unknown system [21]. CE can achieve faster, polylogarithmic rates when additional structure, such as prior knowledge of the dynamics, makes the data generated under optimal feedback sufficiently informative to identify all unknown parameters. In this work, we show that singular input penalties (degenerate LQR) can allow CE to achieve finite-time polylogarithmic expected regret even when the dynamics are not fully identifiable under optimal feedback.

Related Work

Exploration in online LQR. In the finite-time regret formulation of adaptive LQR, Abbasi-Yadkori and Szepesvári [1] obtained the first O~(T)\widetilde{O}(\sqrt{T}) regret bound using optimism in the face of uncertainty, and Cohen et al. [6] subsequently gave the first computationally efficient algorithm attaining the same rate. Mania et al. [18] established this rate for CE with injected input noise, and Simchowitz and Foster [21] proved that the regret rate achieved by such naive exploration cannot be improved in the worst case for fully unknown systems, up to logarithmic factors. These approaches provide O~(T)\widetilde{O}(\sqrt{T}) regret guarantees, but do not capture the faster rates that may be attainable when the data generated under optimal feedback are sufficiently informative.

CE under structured dynamics. With suitable structure in the dynamics, the data generated by a CE controller can be sufficiently informative for learning. CE can then achieve improved regret rates without persistent exploration. For example, a greedy CE algorithm achieves polylogarithmic expected regret when the input matrix B⋆B_{\star} is known, or when the state matrix A⋆A_{\star} is known and the optimal feedback gain is sufficiently non-degenerate [5, 11]. Shirani Faradonbeh et al. [20] showed that an episodic CE scheme attains O(log⁡2T)O(\log^{2} T) asymptotic regret almost surely, assuming that the parameters lie in a known set over which the closed-loop prediction error uniformly bounds the error of the optimal gain. Lee et al. [15] established finite-time polylogarithmic expected-regret bounds for CE with a known linear representation of the dynamics when the optimal controller persistently excites the unknown parameters.

When some parameter directions cannot be detected from data collected under optimal feedback, the consequences depend on whether they affect the optimal controller. For known A⋆A_{\star}, Ziemann and Sandberg [28] established a local asymptotic minimax lower bound of order T\sqrt{T} around uninformative instances, where optimal feedback fails to reveal a parameter direction that changes the optimal gain. Motivated by this result, Liu [17] showed that it suffices to identify the optimal gain rather than the dynamics, and used controller identifiability (CI), which excludes such directions, to separate logarithmic from square-root local minimax regret. These results assume a positive definite input penalty R≻0R \succ0. In this setting, CI requires all unknown parameters to be identifiable under optimal feedback whenever A⋆A_{\star} is nonsingular [17 Corollary 2]. The extent to which singular input penalties relax this requirement remains unaddressed.

CE for degenerate cost functions. A separate line of work studies minimum variance control (MVC). In a related multivariate stochastic regression setting, Lai [13] obtained asymptotically logarithmic regret by combining CE with sparse probing inputs. Lai and Wei [14] extended this approach to MVC of finite-order scalar autoregressive models with exogenous inputs (ARX models). More recently, Singh et al. [23] established finite-time polylogarithmic regret for self-tuning regulation of ARX models, of order log⁡T\log T for bounded noise and log⁡3T\log^{3} T for sub-Gaussian noise. Lin et al. [16] further argued that CE can fail to converge to the optimal controller for cost criteria other than minimum output variance. Together, these results suggest that degenerate input costs can also contribute to making full parameter identification unnecessary. However, the MVC guarantees for ARX models concern scalar-output regulation without an input penalty. They do not provide guarantees for general quadratic state costs in underactuated systems, or for costs that penalize only some input directions.

Contributions

We extend controller identifiability to LQR with potentially singular input penalties, R⪰0R \succeq0, and establish finite-time polylogarithmic expected-regret guarantees for CE. Specifically:

  • In § 3.1, we restate CI in terms of the curvature of the cost, which makes the role of the cost function explicit, and extend it to R⪰0R \succeq0. With mm inputs, a singular RR admits up to mdim⁡ker⁡Rm \dim\ker R additional parameter directions that cannot be detected from data collected under optimal feedback but are harmless for control, so that CI no longer requires full parameter identifiability, even for nonsingular A⋆A_\star.

  • In § 4.1, we prove that CE with a short warm-up achieves O(log⁡2T)O(\log^2 T) expected regret whenever CI holds at the true system. The bound is non-asymptotic and requires only a stabilizing controller and coarse bounds on the system parameters.

  • In § 4.2, we prove a local Ω(T)\Omega(\sqrt{T}) minimax lower bound around a system where CI fails, for any input penalty, including R=0R = 0.

  • In § 5, we specialize these results to MVC and show that CI holds whenever range⁡(B⋆)\operatorname{range}(B_\star) is known. This prior is weaker than knowing B⋆B_\star and covers underactuated systems, as we illustrate on a cart–pole example.

Problem Setting

We use ∥⋅∥\|\cdot\| for the Euclidean vector or spectral matrix norm, ∥⋅∥F\|\cdot\|_F for the Frobenius norm, and ⟨X,Y⟩F=Tr⁡(X⊤Y)\langle X,Y\rangle_F = \operatorname{Tr}(X^\top Y).

Degenerate LQR

Dynamics and model class. We consider the linear system

xt+1=A⋆xt+B⋆ut+wt,t≥1,x1=0,(1)x_{t+1} = A_\star x_t + B_\star u_t + w_t,\qquad t \ge1,\qquad x_1 = 0, \tag*{(1)}

with i.i.d. process noise wt∼N(0,σ2In)w_t \sim\mathcal{N}(0,\sigma^2 I_n) of known variance σ2>0\sigma^2 > 0. The matrices Θ⋆=[A⋆ B⋆]\Theta_\star= [A_\star\ B_\star], with A⋆∈Rn×nA_\star\in\mathbb{R}^{n \times n} and B⋆∈Rn×mB_\star\in\mathbb{R}^{n \times m}, are unknown, but the learner is given an affine model class that contains them,

C={Θ(θ):θ∈Rp},Θ(θ)=Θref+Eθ,\mathcal{C} = \{\Theta(\theta): \theta\in\mathbb{R}^p\},\qquad\Theta(\theta) = \Theta_{\mathrm{ref}} + \mathcal{E}\theta,
Eθ=∑j=1pθjEj,⟨Ei,Ej⟩F=1{i=j},(2)\mathcal{E}\theta= \sum_{j=1}^{p}\theta_j E_j,\qquad\langle E_i,E_j\rangle_F = \mathbf{1}_{\{i=j\}}, \tag*{(2)}

where Θref\Theta_{\mathrm{ref}} and EjE_j are known and Θ⋆=Θ(θ⋆)\Theta_\star= \Theta(\theta_\star) for an unknown θ⋆∈Rp\theta_\star\in\mathbb{R}^p. This class includes fully unknown dynamics, but can also encode prior structural knowledge. Any finite-dimensional affine family admits this representation after removing redundant coordinates and orthonormalizing its directions. In this representation, ∥Eh∥F=∥h∥2\|\mathcal{E}h\|_F = \|h\|_2 and we write [ΔAh ΔBh]=Eh[\Delta A_h\ \Delta B_h] = \mathcal{E}h for h∈Rph \in\mathbb{R}^p.

Cost and optimal controller. Policies are causal; that is, utu_t is chosen based on x1,…,xtx_1,\ldots,x_t, past inputs, and internal randomization that is independent of the process noise. Given known Q≻0Q \succ0 and R⪰0R \succeq0, the stage cost at step tt is

ct=xt⊤Qxt+ut⊤Rut.(3)c_t = x_t^\top Qx_t + u_t^\top Ru_t. \tag*{(3)}

For a model Θ=[A B]\Theta= [A\ B] representing the linear dynamics and a linear controller KK, we then define the following infinite-horizon average cost

JΘ(K):=lim sup⁡T→∞1TEKΘ[∑t=1Tct],(4)J_{\Theta}(K) := \limsup_{T\to\infty} \frac{1}{T}\mathbb{E}^{\Theta}_{K}\left[\sum_{t=1}^{T} c_t\right], \tag*{(4)}

where the expectation is over the noise wtw_t under the dynamics Θ\Theta and the feedback ut=Kxtu_t = Kx_t. We omit this dependence of the expectation when clear from the context and write J(K):=JΘ⋆(K)J(K) := J_{\Theta_\star}(K).

The following assumption ensures that the LQR problem and optimal controller are well defined even when RR is singular.

Assumption 1 (A⋆,B⋆)(A_\star, B_\star) is stabilizable, Q≻0Q \succ0, R⪰0R \succeq0, and ker⁡R∩ker⁡B⋆={0}\ker R \cap\ker B_\star= \{0\}.

Proposition 7 shows that, under Assumption 1, the discrete-time algebraic Riccati equation (DARE)

P=Q+A⋆⊤PA⋆−A⋆⊤PB⋆(R+B⋆⊤PB⋆)−1B⋆⊤PA⋆P = Q + A_\star^\top P A_\star- A_\star^\top P B_\star(R + B_\star^\top P B_\star)^{-1} B_\star^\top P A_\star

admits a unique positive definite stabilizing solution P⋆≻0P_\star\succ0. The same proposition proves that ut=K⋆xtu_t = K_\star x_t is the unique stationary linear feedback minimizing J(K)J(K), with

S⋆=R+B⋆⊤P⋆B⋆≻0,K⋆=−S⋆−1B⋆⊤P⋆A⋆,S_\star= R + B_\star^\top P_\star B_\star\succ0,\qquad K_\star= -S_\star^{-1}B_\star^\top P_\star A_\star,

and ensures that the closed-loop matrix L⋆=A⋆+B⋆K⋆L_\star= A_\star+ B_\star K_\star is Schur stable. The assumption Q≻0Q \succ0 ensures that every nonzero state direction is penalized, and the kernel condition that every unpenalized input direction affects the state; for R=0R = 0, the latter means that B⋆B_\star has full column rank.

Regret and certainty equivalence

Let J⋆:=JΘ⋆(K⋆)J_\star:= J_{\Theta_\star}(K_\star) denote the optimal infinite-horizon average cost. We measure the cost of learning over TT decision rounds by the cumulative regret

RT=∑t=1T(ct−J⋆),(5)R_T = \sum_{t=1}^{T}(c_t - J_\star), \tag*{(5)}

where ctc_t denotes the cost incurred by the learner on the true system Θ⋆\Theta_\star. Our performance criterion is then the expected cumulative regret E[RT]\mathbb{E}[R_T], where the expectation is taken over the process noise and any internal randomization of the learning algorithm.

Remark 1 (Expected regret) Since J⋆J_\star is an average over the noise, whereas each ctc_t depends on its realization, the standard deviation of RTR_T is of order T\sqrt{T}, even under the optimal controller. For this definition of regret, polylogarithmic rates are therefore only meaningful in expectation. Asymptotic almost-sure polylogarithmic rates, such as those of Shirani Faradonbeh et al. [20], are instead stated for a regret that compares the cost of the learner with that of the optimal controller under the same noise realization, so that this contribution of the noise cancels. We also note that, compared to an analysis on a high-probability event, bounding the expected regret additionally requires controlling the cost of rare failures, such as estimates that destabilize the system, which can be very large (Cassel et al., [5]).

Finally, for an estimated model Θ^=[A^ B^]\widehat{\Theta} = [\widehat{A}\ \widehat{B}], we define the certainty-equivalent controller by

K(Θ^)=arg⁡min⁡KJΘ^(K).(6)K(\widehat{\Theta}) = \mathop{\arg\min}_{K} J_{\widehat{\Theta}}(K). \tag*{(6)}

References

  1. [1]Yasin Abbasi-Yadkori and Csaba Szepesvári. Regret Bounds for the Adaptive Control of Linear Quadratic Systems. In Proceedings of the 24th Annual Conference on Learning Theory, pages 1–26. JMLR Workshop and Conference Proceedings, December 2011.
  2. [3]Marcell Bartos, Bruce D. Lee, Lenart Treven, Andreas Krause, Florian Dörfler, and Melanie N. Zeilinger. Optimistic Online LQR via Intrinsic Rewards. arXiv:2603.28938 [eess.SY], August 2026.arxiv.org/abs/2603.28938
  3. [4]Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, March 2004. ISBN 978-0-521-83378-3. doi: 10.1017/CBO9780511804441.DOI
  4. [5]Asaf Cassel, Alon Cohen, and Tomer Koren. Logarithmic Regret for Learning Linear Quadratic Regulators Efficiently. In Proceedings of the 37th International Conference on Machine Learning, pages 1328–1337. PMLR, November 2020.arxiv.org/abs/2002.08095
  5. [6]Alon Cohen, Tomer Koren, and Yishay Mansour. Learning linear-quadratic regulators efficiently with only √T regret. In Proceedings of the 36th International Conference on Machine Learning, pages 1300–1309. PMLR, May 2019.
  6. [7]Augusto Ferrante and Lorenzo Ntogramatzidis. The generalised discrete algebraic Riccati equation in linear-quadratic optimal control. Automatica, 49(2):471–478, February 2013. ISSN 0005-1098. doi: 10.1016/j.automatica.2012.11.006.DOI
  7. [8]Chun-Hua Guo. Newton’s Method for Discrete Algebraic Riccati Equations when the Closed-Loop Matrix Has Eigenvalues on the Unit Circle. SIAM Journal on Matrix Analysis and Applications, 20(2):279–294, June 1998. ISSN 0895-4798, 1095-7162. doi: 10.1137/S0895479897322999.DOI
  8. [9]Daniel Hsu, Sham Kakade, and Tong Zhang. A tail inequality for quadratic forms of subgaussian random vectors. Electronic Communications in Probability, 17:1–6, January 2012. doi: 10.1214/ECP.v17-2079.DOI
  9. [10]Vlad Ionescu and Martin Weiss. On computing the stabilizing solution of the discrete-time Riccati equation. Linear Algebra and its Applications, 174:229–238, September 1992. doi: 10.1016/0024-3795(92)90053-D.DOI
  10. [11]Yassir Jedra and Alexandre Proutiere. Minimal Expected Regret in Linear Quadratic Control. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, pages 10234–10321. PMLR, May 2022.arxiv.org/abs/2109.14429
  11. [12]Ta-Chu Kao and Guillaume Hennequin. Automatic differentiation of Sylvester, Lyapunov, and algebraic Riccati equations. arXiv:2011.11430, November 2020.arxiv.org/abs/2011.11430
  12. [13]T. L. Lai. Asymptotically efficient adaptive control in stochastic regression models. Advances in Applied Mathematics, 7(1):23–45, March 1986. ISSN 01968858. doi: 10.1016/0196-8858(86)90004-7.DOI
  13. [14]T. L. Lai and C. Z. Wei. Asymptotically efficient self-tuning regulators. SIAM Journal on Control and Optimization, 25(2):466–481, March 1987. ISSN 0363-0129. doi: 10.1137/0325026.DOI
  14. [15]Bruce Lee, Anders Rantzer, and Nikolai Matni. Nonasymptotic regret analysis of adaptive linear quadratic control with model misspecification. In Proceedings of the 6th Annual Learning for Dynamics & Control Conference, pages 980–992. PMLR, June 2024.arxiv.org/abs/2401.00073
  15. [16]Woei Lin, P. R. Kumar, and T. I. Seidman. Will the self-tuning approach work for general cost criteria? Systems & Control Letters, 6(2):77–85, July 1985. ISSN 01676911. doi: 10.1016/0167-6911(85)90001-5.DOI
  16. [17]Zhaobo Liu. Controller Identifiability: The Boundary Between Logarithmic and Square-Root Local Minimax Regret in Structured Adaptive LQR. arXiv:2609.37063 [math.OC], September 2026.arxiv.org/abs/2609.37063
  17. [18]Horia Mania, Stephen Tu, and Benjamin Recht. Certainty Equivalence is Efficient for Linear Quadratic Control. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.arxiv.org/abs/1902.07826
  18. [19]J. W. Polderman. On the necessity of identifying the true parameter in adaptive LQ control. Systems & Control Letters, 8(2):87–91, December 1986. ISSN 01676911. doi: 10.1016/0167-6911(86)90065-4.DOI
  19. [20]Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, and George Michailidis. On adaptive Linear–Quadratic regulators. Automatica, 117:108982, July 2020. ISSN 0005-1098. doi: 10.1016/j.automatica.2020.108982.
  20. [21]Max Simchowitz and Dylan Foster. Naive Exploration is Optimal for Online LQR. In Proceedings of the 37th International Conference on Machine Learning, pages 8937–8948. PMLR, November 2020.arxiv.org/abs/2001.09576
  21. [22]Max Simchowitz, Horia Mania, Stephen Tu, Michael I. Jordan, and Benjamin Recht. Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification. In Proceedings of the 31st Conference On Learning Theory, pages 439–473. PMLR, July 2018.arxiv.org/abs/1802.08334
  22. [23]Rahul Singh, Akshay Mete, Avik Kar, and Panganamala Kumar. Finite Time Logarithmic Regret Bounds for Self-Tuning Regulation. In Proceedings of the 41st International Conference on Machine Learning, pages 45571–45636. PMLR, July 2024.
  23. [24]Russ Tedrake. Underactuated Robotics. Course notes for MIT 6.832, 2024.
  24. [25]Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. In Yonina C. Eldar and Gitta Kutyniok, editors, Compressed Sensing, pages 210–268. Cambridge University Press, May 2012. ISBN 978-1-107-00558-7 978-0-511-79430-8. doi: 10.1017/CBO9780511794308.006.DOI
  25. [26]James Wang, Bruce Lee, Ingvar Ziemann, and Nikolai Matni. Logarithmic Regret for Nonlinear Control. In Proceedings of the 7th Annual Learning for Dynamics & Control Conference, pages 552–565. PMLR, May 2025.arxiv.org/abs/2501.10261
  26. [27]Andrew Chi-Chih Yao. Probabilistic computations: Toward a unified measure of complexity. In 18th Annual Symposium on Foundations of Computer Science (SFCS 1977), pages 222–227, Providence, RI, USA, September 1977. IEEE. doi: 10.1109/SFCS.1977.24.DOI
  27. [28]Ingvar Ziemann and Henrik Sandberg. On Uninformative Optimal Policies in Adaptive LQR with Unknown B-Matrix. In Proceedings of the 3rd Conference on Learning for Dynamics and Control, pages 213–226. PMLR, May 2021.arxiv.org/abs/2011.09288
  28. [29]Ingvar Ziemann, Anastasios Tsiamis, Bruce Lee, Yassir Jedra, Nikolai Matni, and George J. Pappas. A Tutorial on the Non-Asymptotic Theory of System Identification. In 2023 62nd IEEE Conference on Decision and Control (CDC), pages 8921–8939. IEEE, 2023. ISBN 979-8-3503-0124-3.arxiv.org/abs/2309.03873

Paper details

vlnc:W_uhkwvnq8
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Generative AI tools

View statement
Looking for related papers…
Contents