# Making Non-Stochastic Control (Almost) as Easy as Stochastic

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jun 2020.

## Built on by (most cited first, 24 of 24)

- [Non-stationary Online Learning with Memory and Non-stochastic Control](https://mlsanity.com/paper/2102.03758/) (2021)
- [Adversarial Tracking Control via Strongly Adaptive Online Learning with Memory](https://mlsanity.com/paper/2102.01623/) (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)
- [Regret-optimal Estimation and Control](https://mlsanity.com/paper/2106.12097/) (2021)
- [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)
- [A Regret Minimization Approach to Iterative Learning Control](https://mlsanity.com/paper/2102.13478/) (2021)
- [Optimal Rates for Bandit Nonstochastic Control](https://mlsanity.com/paper/2305.15352/) (2023)
- [Optimal Dynamic Regret in LQR Control](https://mlsanity.com/paper/2206.09257/) (2022)
- [Best of Both Worlds in Online Control: Competitive Ratio and Policy Regret](https://mlsanity.com/paper/2211.11219/) (2022)
- [Predictive Linear Online Tracking for Unknown Targets](https://mlsanity.com/paper/2402.10036/) (2024)
- [Efficient Online Linear Control with Stochastic Convex Costs and Unknown Dynamics](https://mlsanity.com/paper/2203.01170/) (2022)
- [Adaptive Online Non-stochastic Control](https://mlsanity.com/paper/2310.02261/) (2023)
- [Optimistic Online Non-stochastic Control via FTRL](https://mlsanity.com/paper/2404.03309/) (2024)
- [Online Control in Population Dynamics](https://mlsanity.com/paper/2406.01799/) (2024)
- [Combining Federated Learning and Control: A Survey](https://mlsanity.com/paper/2407.11069/) (2024)
- [A Simple, Optimal and Efficient Algorithm for Online Exp-Concave Optimization](https://mlsanity.com/paper/2512.23190/) (2025)
- [Optimal Competitive-Ratio Control](https://mlsanity.com/paper/2206.01782/) (2022)
- [Online Nonstochastic Model-Free Reinforcement Learning](https://mlsanity.com/paper/2305.17552/) (2023)
- [Tight Rates for Bandit Control Beyond Quadratics](https://mlsanity.com/paper/2410.00993/) (2024)
- [Explore-then-Commit for Nonstationary Linear Bandits with Latent Dynamics](https://mlsanity.com/paper/2510.16208/) (2025)
- [Learning to Seek: Multi-Agent Online Source Seeking Against Non-Stochastic Disturbances](https://mlsanity.com/paper/2305.00154/) (2023)
- [Online Multi-Agent Control with Adversarial Disturbances](https://mlsanity.com/paper/2506.18814/) (2025)

## Abstract (arXiv)

Recent literature has made much progress in understanding online LQR: a modern learning-theoretic take on the classical control problem in which a learner attempts to optimally control an unknown linear dynamical system with fully observed state, perturbed by i.i.d. Gaussian noise. It is now understood that the optimal regret on time horizon T against the optimal control law scales as widetildeTheta(√T). In this paper, we show that the same regret rate (against a suitable benchmark) is attainable even in the considerably more general non-stochastic control model, where the system is driven by arbitrary adversarial noise (Agarwal et al. 2019). In other words, stochasticity confers little benefit in online LQR. We attain the optimal widetildeO(√T) regret when the dynamics are unknown to the learner, and poly(log T) regret when known, provided that the cost functions are strongly convex (as in LQR). Our algorithm is based on a novel variant of online Newton step (Hazan et al. 2007), which adapts to the geometry induced by possibly adversarial disturbances, and our analysis hinges on generic "policy regret" bounds for certain structured losses in the OCO-with-memory framework (Anava et al. 2015). Moreover, our results accomodate the full generality of the non-stochastic control setting: adversarially chosen (possibly non-quadratic) costs, partial state observation, and fully adversarial process and observation noise.