# Black-Box Control for Linear Dynamical Systems

arXiv: https://arxiv.org/abs/2007.06650 · HTML: https://mlsanity.com/paper/2007.06650/

## Key facts

- Cited by 43 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jul 2020.

## Built on by (most cited first, 30 of 43)

- [Stabilizing Dynamical Systems via Policy Gradient Methods](https://mlsanity.com/paper/2110.06418/) (2021)
- [Linear Systems can be Hard to Learn](https://mlsanity.com/paper/2104.01120/) (2021)
- [Neural Operators of Backstepping Controller and Observer Gain Functions for Reaction-Diffusion PDEs](https://mlsanity.com/paper/2303.10506/) (2023)
- [Streaming Linear System Identification with Reverse Experience Replay](https://mlsanity.com/paper/2103.05896/) (2021)
- [SABLAS: Learning Safe Control for Black-box Dynamical Systems](https://mlsanity.com/paper/2201.01918/) (2022)
- [Generative Models in Decision Making: A Survey](https://mlsanity.com/paper/2502.17100/) (2025)
- [Butterfly Effects of SGD Noise: Error Amplification in Behavior Cloning and Autoregression](https://mlsanity.com/paper/2310.11428/) (2023)
- [Online Policy Gradient for Model Free Learning of Linear Quadratic Regulators with √T Regret](https://mlsanity.com/paper/2102.12608/) (2021)
- [Learning to Control Linear Systems can be Hard](https://mlsanity.com/paper/2205.14035/) (2022)
- [Deluca -- A Differentiable Control Library: Environments, Methods, and Benchmarking](https://mlsanity.com/paper/2102.09968/) (2021)
- [Provable Sim-to-real Transfer in Continuous Domain with Partial Observations](https://mlsanity.com/paper/2210.15598/) (2022)
- [Thompson Sampling Achieves tilde O(√T) Regret in Linear Quadratic Control](https://mlsanity.com/paper/2206.08520/) (2022)
- [Optimal Rates for Bandit Nonstochastic Control](https://mlsanity.com/paper/2305.15352/) (2023)
- [Towards a Theoretical Foundation of Policy Optimization for Learning Control Policies](https://mlsanity.com/paper/2210.04810/) (2022)
- [Best of Both Worlds in Online Control: Competitive Ratio and Policy Regret](https://mlsanity.com/paper/2211.11219/) (2022)
- [Learning the Uncertainty Sets for Control Dynamics via Set Membership: A Non-Asymptotic Analysis](https://mlsanity.com/paper/2309.14648/) (2023)
- [Controlgym: Large-Scale Control Environments for Benchmarking Reinforcement Learning Algorithms](https://mlsanity.com/paper/2311.18736/) (2023)
- [The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective](https://mlsanity.com/paper/2501.15910/) (2025)
- [Universal Sequence Preconditioning](https://mlsanity.com/paper/2502.06545/) (2025)
- [Rate-Optimal Online Convex Optimization in Adaptive Linear Control](https://mlsanity.com/paper/2206.01426/) (2022)
- [Second Order Methods for Bandit Optimization and Control](https://mlsanity.com/paper/2402.08929/) (2024)
- [Predictive Linear Online Tracking for Unknown Targets](https://mlsanity.com/paper/2402.10036/) (2024)
- [Universal Learning of Nonlinear Dynamics](https://mlsanity.com/paper/2508.11990/) (2025)
- [Robust Online Control with Model Misspecification](https://mlsanity.com/paper/2107.07732/) (2021)
- [Efficient Online Linear Control with Stochastic Convex Costs and Unknown Dynamics](https://mlsanity.com/paper/2203.01170/) (2022)
- [A Nonstochastic Control Approach to Optimization](https://mlsanity.com/paper/2301.07902/) (2023)
- [Joint Learning-Based Stabilization of Multiple Unknown Linear Systems](https://mlsanity.com/paper/2201.01387/) (2022)
- [Actor-Critic based Improper Reinforcement Learning](https://mlsanity.com/paper/2207.09090/) (2022)
- [Combining Federated Learning and Control: A Survey](https://mlsanity.com/paper/2407.11069/) (2024)
- [Learning Stabilizing Policies via an Unstable Subspace Representation](https://mlsanity.com/paper/2505.01348/) (2025)

## Abstract (arXiv)

We consider the problem of controlling an unknown linear time-invariant dynamical system from a single chain of black-box interactions, with no access to resets or offline simulation. Under the assumption that the system is controllable, we give the first efficient algorithm that is capable of attaining sublinear regret in a single trajectory under the setting of online nonstochastic control. This resolves an open problem on the stochastic LQR problem, and in a more challenging setting that allows for adversarial perturbations and adversarially chosen and changing convex loss functions. We give finite-time regret bounds for our algorithm on the order of 2^tildeO(L) + tildeO(poly(L) T2/3) for general nonstochastic control, and 2^tildeO(L) + tildeO(poly(L) √T) for black-box LQR, where L is the system size which is an upper bound on the dimension. The crucial step is a new system identification method that is robust to adversarial noise, but incurs exponential cost. To complete the picture, we investigate the complexity of the online black-box control problem, and give a matching lower bound of 2Omega(L) on the regret, showing that the additional exponential cost is inevitable. This lower bound holds even in the noiseless setting, and applies to any, randomized or deterministic, black-box control method.