Research map / Bandits and online learning / Online convex optimization and games
Finite Sample Analyses for Continuous-time Linear Systems: System Identification and Online Control
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a finite-observation system identification method for continuous-time linear stochastic systems via discretization and matrix-log inversion, with a matching lower bound, and applies it to an explore-then-commit online LQR algorithm achieving O(sqrt(T)) regret.
Problem
Non-asymptotic system identification for continuous-time linear stochastic dynamics using only finitely many (O(T)) observations on a single trajectory, and online LQR regret for continuous-time linear systems with unknown dynamics.
Approach
Discretize the continuous system at a small interval h chosen from known norm bounds, estimate the discrete transition matrices by least squares, and recover continuous (A,B) by matrix logarithm and an integral inversion, avoiding the O(h) discretization error that forces super-linear sampling in prior work; applies this in an explore-then-commit online LQR scheme with a stabilizer-based divergenc
Key results
- Single-trajectory identification with O(T) samples achieves error O(sqrt(log(1/delta)/T)) (upper bound theorem), with a matching lower bound Omega(1/sqrt(T)) up to constants.
- Online control algorithm achieves O(sqrt(T)) regret on a single trajectory with O(T) observations, improving the O(sqrt(T) log T) bound of prior continuous-time work.
- Simulations with d=p=3 show normalized regret R(T)/sqrt(T) stays roughly constant for T in [600,10000] and outperforms the baseline for large T.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Estimate the matrix exponential directly and recover the continuous-time dynamics instead of using direct discretization | Continuous-time linear system identification · Single stable trajectory | number of observations: \Omega(T^{3/2}) -> \mathcal{O}(T) | Helped |
| Apply the proposed finite-observation identification method in an explore-then-commit controller | Continuous-time online LQR · Single trajectory | regret: \mathcal{O}\left(\sqrt{T}\log(T)\right) -> \mathcal{O}(\sqrt{T}) | Helped |
Limitations
- Requires a known stable controller K for the single-trajectory identification; multi-trajectory variant needed otherwise.
- Assumes stochastic Brownian noise; deterministic or adversarial noise not handled.
- Restricted to linear dynamics; nonlinear systems not addressed.
Experimental setup
Metrics: estimation error ||A_hat - A||_F^2 and ||B_hat - B||_F^2 normalized regret R(T)/sqrt(T)
Baselines: Lale et al. continuous-time online LQR (O(sqrt(T) log T) regret) Euler-discretization system identification
Builds on: discrete-time LQR regret analysis (Abbasi-Yadkori and Szepesvari style) small-ball least squares concentration (Simchowitz et al.) continuous-time online control (Lale et al.)
Closest papers by meaning
- Logarithmic Regret Bound in Partially Observable Linear Dynamical Systems (NeurIPS 2020 · similarity 0.89)
- Robust System Identification: Finite-sample Guarantees and Connection to Regularization (ICLR 2025 · similarity 0.88)
- Near optimal finite time identification of arbitrary linear dynamical systems (ICML 2019 · similarity 0.88)
- Online Control with Adversarial Disturbance for Continuous-time Linear Systems (NeurIPS 2024 · similarity 0.86)
- A Memory Efficient Unified Algorithm for Online Learning of Linear Dynamical Systems (NeurIPS 2026 · similarity 0.86)
- Identification of Analytic Nonlinear Dynamical Systems with Non-asymptotic Guarantees (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.