math.OCNov 16, 2026

Polylogarithmic Regret via Certainty Equivalence in Degenerate LQR

Authors: Luca Vignola, Melanie Zeilinger, Bruce D. Lee

Organizations: ETH Zürich, Zürich, Switzerland

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.

Figures & tables

Explore similar work

CardsList
  1. Rate-Optimal Regret for the Safe Learning-based Control of the Constrained Linear Quadratic Regulator

    Apr 24, 2026Spencer Hutchinson, Nanfei Jiang, Mahnoosh AlizadehStochastic Linear Dynamical SystemsStochastic Optimal Control

  2. Optimistic Online LQR via Intrinsic Rewards

    Mar 30, 2026Marcell Bartos, Bruce D. Lee, Lenart Treven +3Linear Quadratic RegulatorRegret Minimization in RL

  3. LQG solution for POMDP without estimating states: A minimum variance approach

    Jul 13, 2026Ranjan Sarkar, Prabhat K. MishraStochastic Optimal ControlFeedback Control