mlsanityData to 7 Oct 2026

Optimal Rates for Bandit Nonstochastic Control

arXiv 2305.15352 ↗First posted 24 May 2023cs.LG cs.SY eess.SYcited by 7

Not on the map. Why?

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.

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

Builds on

21 of 38 references.

References · 21

  1. 2019Introduction to Online Convex Optimizationcited by 793
  2. 2020Naive Exploration is Optimal for Online LQRcited by 111
  3. 2019Online Control with Adversarial Disturbancescited by 92
  4. 2018Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulatorcited by 86
  5. 2020Improper Learning for Non-Stochastic Controlcited by 83
  6. 2018Online Linear Quadratic Controlcited by 55
  7. 2019The Nonstochastic Control Problemcited by 52
  8. 2020Black-Box Control for Linear Dynamical Systemscited by 43
  9. 2020Logarithmic Regret for Adversarial Online Controlcited by 41
  10. 2019Logarithmic Regret for Online Controlcited by 38
  11. 2020Logarithmic Regret for Learning Linear Quadratic Regulators Efficientlycited by 33
  12. 2021Online Learning with Optimism and Delaycited by 33
9 more
  1. 2020Making Non-Stochastic Control (Almost) as Easy as Stochasticcited by 24
  2. 2020Non-Stochastic Control with Bandit Feedbackcited by 17
  3. 2013Efficient Reinforcement Learning for High Dimensional Linear Quadratic Systemscited by 13
  4. 2020Bandit Linear Controlcited by 10
  5. 2021Deluca -- A Differentiable Control Library: Environments, Methods, and Benchmarkingcited by 10
  6. 2021Online Policy Gradient for Model Free Learning of Linear Quadratic Regulators with √T Regretcited by 10
  7. 2020Geometric Exploration for Online Controlcited by 9
  8. 2021Robust Online Control with Model Misspecificationcited by 4
  9. 2023A Nonstochastic Control Approach to Optimizationcited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 3; 2025: 1; 2026: 2.

7 papers.

  1. 2024Improved Regret for Bandit Convex Optimization with Delayed Feedbackcited by 8
  2. 2024Second Order Methods for Bandit Optimization and Controlcited by 5
  3. 2023Online Nonstochastic Model-Free Reinforcement Learningcited by 2
  4. 2024Tight Rates for Bandit Control Beyond Quadraticscited by 2
  5. 2025A New Approach to Controlling Linear Dynamical Systemscited by 2
  6. 2026A Spectral Filtering Approach to Regret Analysis of Distributed Online Control for Linear Dynamical Systemscited by 0
  7. 2026Block Optimism for Nonstationary Bandits with Latent Linear Dynamicscited by 0