# Improper Learning for Non-Stochastic Control

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

## Key facts

- Cited by 83 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jan 2020.

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

- [Statistical Learning Theory for Control: A Finite Sample Perspective](https://mlsanity.com/paper/2209.05423/) (2022)
- [Recurrent Equilibrium Networks: Flexible Dynamic Models with Guaranteed Stability and Robustness](https://mlsanity.com/paper/2104.05942/) (2021)
- [PAC Reinforcement Learning for Predictive State Representations](https://mlsanity.com/paper/2207.05738/) (2022)
- [Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systems](https://mlsanity.com/paper/2206.12020/) (2022)
- [Non-stationary Online Learning with Memory and Non-stochastic Control](https://mlsanity.com/paper/2102.03758/) (2021)
- [Stabilizing Dynamical Systems via Policy Gradient Methods](https://mlsanity.com/paper/2110.06418/) (2021)
- [Future-Dependent Value-Based Off-Policy Evaluation in POMDPs](https://mlsanity.com/paper/2207.13081/) (2022)
- [Optimal Exploration for Model-Based RL in Nonlinear Systems](https://mlsanity.com/paper/2306.09210/) (2023)
- [Task-Optimal Exploration in Linear Dynamical Systems](https://mlsanity.com/paper/2102.05214/) (2021)
- [Adversarial Tracking Control via Strongly Adaptive Online Learning with Memory](https://mlsanity.com/paper/2102.01623/) (2021)
- [Learning over All Stabilizing Nonlinear Controllers for a Partially-Observed Linear System](https://mlsanity.com/paper/2112.04219/) (2021)
- [Butterfly Effects of SGD Noise: Error Amplification in Behavior Cloning and Autoregression](https://mlsanity.com/paper/2310.11428/) (2023)
- [Online Control of Unknown Time-Varying Dynamical Systems](https://mlsanity.com/paper/2202.07890/) (2022)
- [Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddings](https://mlsanity.com/paper/2206.12081/) (2022)
- [Safe Adaptive Learning-based Control for Constrained Linear Quadratic Regulators with Regret Guarantees](https://mlsanity.com/paper/2111.00411/) (2021)
- [Regret Lower Bounds for Learning Linear Quadratic Gaussian Systems](https://mlsanity.com/paper/2201.01680/) (2022)
- [On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluation](https://mlsanity.com/paper/2402.14703/) (2024)
- [Learning from Censored and Dependent Data: The case of Linear Dynamics](https://mlsanity.com/paper/2104.05087/) (2021)
- [Optimal Comparator Adaptive Online Learning with Switching Cost](https://mlsanity.com/paper/2205.06846/) (2022)
- [Provable Sim-to-real Transfer in Continuous Domain with Partial Observations](https://mlsanity.com/paper/2210.15598/) (2022)
- [Smoothed Online Learning for Prediction in Piecewise Affine Systems](https://mlsanity.com/paper/2301.11187/) (2023)
- [A Regret Minimization Approach to Iterative Learning Control](https://mlsanity.com/paper/2102.13478/) (2021)
- [On the Sample Complexity of Decentralized Linear Quadratic Regulator with Partially Nested Information Structure](https://mlsanity.com/paper/2110.07112/) (2021)
- [Optimal Rates for Bandit Nonstochastic Control](https://mlsanity.com/paper/2305.15352/) (2023)
- [Regret Analysis of Distributed Online LQR Control for Unknown LTI Systems](https://mlsanity.com/paper/2105.07310/) (2021)
- [Provable Regret Bounds for Deep Online Learning and Control](https://mlsanity.com/paper/2110.07807/) (2021)
- [Deep inference of latent dynamics with spatio-temporal super-resolution using selective backpropagation through time](https://mlsanity.com/paper/2111.00070/) (2021)
- [Kalman Filtering with Adversarial Corruptions](https://mlsanity.com/paper/2111.06395/) (2021)
- [Optimal Dynamic Regret in LQR Control](https://mlsanity.com/paper/2206.09257/) (2022)
- [Towards a Theoretical Foundation of Policy Optimization for Learning Control Policies](https://mlsanity.com/paper/2210.04810/) (2022)

## Abstract (arXiv)

We consider the problem of controlling a possibly unknown linear dynamical system with adversarial perturbations, adversarially chosen convex loss functions, and partially observed states, known as non-stochastic control. We introduce a controller parametrization based on the denoised observations, and prove that applying online gradient descent to this parametrization yields a new controller which attains sublinear regret vs. a large class of closed-loop policies. In the fully-adversarial setting, our controller attains an optimal regret bound of √T-when the system is known, and, when combined with an initial stage of least-squares estimation, T2/3 when the system is unknown; both yield the first sublinear regret for the partially observed setting. Our bounds are the first in the non-stochastic control setting that compete with all stabilizing linear dynamical controllers, not just state feedback. Moreover, in the presence of semi-adversarial noise containing both stochastic and adversarial components, our controller attains the optimal regret bounds of poly(log T) when the system is known, and √T when unknown. To our knowledge, this gives the first end-to-end √T regret for online Linear Quadratic Gaussian controller, and applies in a more general setting with adversarial losses and semi-adversarial noise.