Polylogarithmic Regret via Certainty Equivalence in Degenerate LQR

Luca Vignola, Melanie Zeilinger, Bruce D. LeearXiv 2026 · arXiv

This paper, "Polylogarithmic Regret via Certainty Equivalence in Degenerate LQR," explores a fundamental trade-off in adaptive control: how much do we really need to know about a system to control it optimally? The authors demonstrate that in many practical scenarios—specifically those with "singular" or zero input penalties—we can achieve near-perfect control much faster than previously thought.

TL;DR

The authors show that for Linear Quadratic Regulator (LQR) problems with singular input penalties (like minimum variance control), a simple "Certainty Equivalence" learner can achieve $O(\log^2 T)$ regret. This means the controller doesn't need to identify the entire system dynamics to perform optimally; it only needs to identify the optimal control law, a much easier task that significantly expands the class of systems where fast learning is possible.

What Problem Does This Paper Address?

In online control, a learner must balance exploration (trying new things to learn the system) and exploitation (using what they know to minimize cost). The standard benchmark is the Linear Quadratic Regulator (LQR), where the goal is to control a linear system with quadratic costs.

A common strategy is Certainty Equivalence (CE): estimate the system parameters and act as if those estimates are perfectly true. However, CE often struggles because "optimal" behavior can be uninformative. If a controller is doing its job well, it might never excite the system in a way that reveals certain hidden parameters. If those hidden parameters actually matter for the optimal control law, the learner gets stuck with a sub-optimal controller, leading to high "regret" (the cumulative extra cost compared to knowing the true system).

Previous work suggested that to get fast, polylogarithmic regret, you usually need to identify the entire system. This paper asks: Can we achieve fast regret rates even if the system is not fully identifiable, provided the "unidentifiable" parts don't actually affect the optimal controller?

Methods

The authors focus on Degenerate LQR, where the input penalty matrix $R$ is singular (i.e., some control directions are "free"). A classic example is Minimum Variance Control (MVC), where the only goal is to keep the state at zero, regardless of the control effort used.

The key technical contributions include:

  1. Extending Controller Identifiability (CI): They generalize the concept of CI to cases where $R \succeq 0$. CI essentially means that any direction in the parameter space that is "invisible" under optimal feedback must also be "harmless" (it doesn't change the optimal control law).
  2. The CE Algorithm: They analyze a Certainty Equivalence algorithm that starts with a short "warm-up" exploration phase using random noise, followed by epochs where the controller is updated using regularized least-squares estimates.
  3. Regret Analysis: They provide a non-asymptotic upper bound on expected regret and a minimax lower bound to show when fast learning is impossible.

Datasets

As a theoretical control paper, it does not use standard machine learning datasets. Instead, the authors evaluate their findings using:

  • A Synthetic Lower-Bound Family: A specific 2D system designed to show that when CI fails, regret must grow at a much faster rate ($\sqrt{T}$).
  • Cart-Pole Case Study: A linearized simulation of the classic "inverted pendulum on a cart" problem. This serves as a practical example of an underactuated system where the "range condition" for identifiability is met.

Key Insights and Ideas

  • Singular Penalties are a Feature, Not a Bug: In standard LQR ($R \succ 0$), identifiability is very restrictive. By allowing $R$ to be singular, the authors show that many more parameter directions become "harmless," making it easier for CE to succeed.
  • The "Range Condition": For Minimum Variance Control, the authors prove that you don't need to know the full input matrix $B$. You only need to know its range (the subspace of the state space that the inputs can affect). This is a much weaker requirement than knowing the exact values of the matrix entries.
  • Invisible vs. Harmless: The paper formalizes the intuition that a learner doesn't need to see everything. If a parameter is "invisible" because the optimal controller suppresses it, but that parameter doesn't change what the optimal controller should be, then the lack of information doesn't hurt performance.

Key Results

  • Upper Bound: If Controller Identifiability holds, the proposed CE algorithm achieves $O(\log^2 T)$ expected regret. This is significantly faster than the $O(\sqrt{T})$ rate typical of systems requiring persistent exploration.
  • Lower Bound: They prove a local minimax lower bound of $\Omega(\sqrt{T})$ for systems where CI fails, confirming that CI is a necessary condition for polylogarithmic regret.
  • Cart-Pole Simulation: In the cart-pole example, a learner that knows the range of the input matrix achieves the predicted polylogarithmic regret, while a learner without this prior knowledge suffers visibly higher regret.

Limitations and Future Work

  • Knowledge of Horizon: The current algorithm requires knowing the total time $T$ to set its parameters (like the warm-up length). The authors suggest this could be relaxed in future work using "doubling tricks" or more adaptive epoch scheduling.
  • Initial Stability: The algorithm assumes the learner starts with a "stabilizing" controller $K_0$. While common in this literature, finding this initial controller for a completely unknown system is a separate challenge.
  • Nonlinear Systems: The authors highlight extending these "identifiability" insights to nonlinear control as a promising and challenging next step.

Summary updated

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^2 T)$ expected regret over $T$ interactions whenever controller identifiability holds. We complement this guarantee with an $Ω(\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.
BibTeX
@misc{vignola2026polylogarithmic,
  author = {Luca Vignola and Melanie Zeilinger and Bruce D. Lee},
  title = {{Polylogarithmic Regret via Certainty Equivalence in Degenerate LQR}},
  year = {2026},
  eprint = {2611.21927},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.21927},
}
Figure