Backend
Polylogarithmic Regret via Certainty Equivalence in Degenerate LQR
arXiv cs.SY0 views
arXiv:2611.21927v1 Announce Type: cross 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 $\Omega(\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.
Source:https://arxiv.org/abs/2611.21927PreviousALOHA Lightning: Learning Fast and Precise ManipulationNextHigher-Order Interaction Reconstruction via Integral Physics-Informed Neural Networks
Related posts
Direct Numerical Simulation of Thermoacoustically Unstable Flames Via Non-Drifting Acoustic Delay Characteristic Boundary Conditions
0arXiv cs.NA
On the sharp linear convergence rate of the circumcentered--reflection method on subspaces
0arXiv cs.NA
Quantum Gibbs sampling through the detectability lemma
0arXiv cs.NA
RustMC: Automated Verification of Real-World Concurrent Rust
0arXiv cs.CR
CyBiasBench: Benchmarking Bias in LLM Agents for Cyber-Attack Scenarios
0arXiv cs.CR
HE-LRM: Encrypted Deep Learning Recommendation Models using Fully Homomorphic Encryption
0arXiv cs.CR