# Optimal Rates for Bandit Nonstochastic Control

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 38 references that are in the map.
- First posted on arXiv 24 May 2023.

## Builds on (most cited first, 21 of 21)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Naive Exploration is Optimal for Online LQR](https://mlsanity.com/paper/2001.09576/) (2020)
- [Online Control with Adversarial Disturbances](https://mlsanity.com/paper/1902.08721/) (2019)
- [Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulator](https://mlsanity.com/paper/1805.09388/) (2018)
- [Improper Learning for Non-Stochastic Control](https://mlsanity.com/paper/2001.09254/) (2020)
- [Online Linear Quadratic Control](https://mlsanity.com/paper/1806.07104/) (2018)
- [The Nonstochastic Control Problem](https://mlsanity.com/paper/1911.12178/) (2019)
- [Black-Box Control for Linear Dynamical Systems](https://mlsanity.com/paper/2007.06650/) (2020)
- [Logarithmic Regret for Adversarial Online Control](https://mlsanity.com/paper/2003.00189/) (2020)
- [Logarithmic Regret for Online Control](https://mlsanity.com/paper/1909.05062/) (2019)
- [Logarithmic Regret for Learning Linear Quadratic Regulators Efficiently](https://mlsanity.com/paper/2002.08095/) (2020)
- [Online Learning with Optimism and Delay](https://mlsanity.com/paper/2106.06885/) (2021)
- [Making Non-Stochastic Control (Almost) as Easy as Stochastic](https://mlsanity.com/paper/2006.05910/) (2020)
- [Non-Stochastic Control with Bandit Feedback](https://mlsanity.com/paper/2008.05523/) (2020)
- [Efficient Reinforcement Learning for High Dimensional Linear Quadratic Systems](https://mlsanity.com/paper/1303.5984/) (2013)
- [Online Policy Gradient for Model Free Learning of Linear Quadratic Regulators with √T Regret](https://mlsanity.com/paper/2102.12608/) (2021)
- [Bandit Linear Control](https://mlsanity.com/paper/2007.00759/) (2020)
- [Deluca -- A Differentiable Control Library: Environments, Methods, and Benchmarking](https://mlsanity.com/paper/2102.09968/) (2021)
- [Geometric Exploration for Online Control](https://mlsanity.com/paper/2010.13178/) (2020)
- [Robust Online Control with Model Misspecification](https://mlsanity.com/paper/2107.07732/) (2021)
- [A Nonstochastic Control Approach to Optimization](https://mlsanity.com/paper/2301.07902/) (2023)

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

- [Improved Regret for Bandit Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2402.09152/) (2024)
- [Second Order Methods for Bandit Optimization and Control](https://mlsanity.com/paper/2402.08929/) (2024)
- [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)
- [A New Approach to Controlling Linear Dynamical Systems](https://mlsanity.com/paper/2504.03952/) (2025)
- [A Spectral Filtering Approach to Regret Analysis of Distributed Online Control for Linear Dynamical Systems](https://mlsanity.com/paper/2608.02375/) (2026)
- [Block Optimism for Nonstationary Bandits with Latent Linear Dynamics](https://mlsanity.com/paper/2610.00911/) (2026)

## Abstract (arXiv)

Linear Quadratic Regulator (LQR) and Linear Quadratic Gaussian (LQG) control are foundational and extensively researched problems in optimal control. We investigate LQR and LQG problems with semi-adversarial perturbations and time-varying adversarial bandit loss functions. The best-known sublinear regret algorithm of citegradu2020non has a T^frac34 time horizon dependence, and its authors posed an open question about whether a tight rate of √T could be achieved. We answer in the affirmative, giving an algorithm for bandit LQR and LQG which attains optimal regret (up to logarithmic factors) for both known and unknown systems. A central component of our method is a new scheme for bandit convex optimization with memory, which is of independent interest.