Online Control with Provable Regret Guarantees

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2150 papers184 conceptsfrozen 2026-10-04

In classical control theory, we typically assume we know the "rules of the game"—the differential equations governing a robot's movement or a power grid's flow. When the environment changes, such as a quadrotor encountering sudden wind gusts, we traditionally rely on "robustness" (preparing for the worst case) or "adaptive control" (slowly updating parameters).

However, a new synthesis of control theory and online machine learning has emerged. Instead of just asking if a system is stable, researchers are asking: How much performance do we lose while we are still learning? This shift is centered on the concept of regret, providing a mathematical bridge that allows robots to navigate unknown, adversarial environments with the same efficiency as an expert who knew the future.

The Shift from Stability to Regret

In traditional adaptive control, the goal is asymptotic stability—proving that, eventually, the system will behave. But as Nicholas M. Boffi and Jean-Jacques E. Slotine point out in Regret Bounds for Adaptive Nonlinear Control, this doesn't tell you how much "cost" you accumulate during the learning phase.

By adopting the metric of regret, researchers compare the total cost incurred by an online controller against the cost of the best possible controller in hindsight.

  • Policy Regret: Comparing yourself to the best fixed policy (e.g., the best single LQR gain).
  • Dynamic Regret: Comparing yourself to a "clairvoyant" controller that knew the disturbances in advance and could change its actions at every step.

The goal is sublinear regret (e.g., $O(\sqrt{T})$ or $O(\log T)$). If your total regret grows slower than time $T$, your average mistake per second goes to zero. You are effectively "becoming" the optimal controller.

Control as Online Convex Optimization

The core intuition behind why this works is the reduction of control to Online Convex Optimization (OCO). In OCO, an agent makes a decision, an adversary reveals a cost function, and the agent suffers a loss.

Elad Hazan, Sham M. Kakade, and Karan Singh pioneered this in The Nonstochastic Control Problem. They showed that if you parameterize your control law as a linear function of past disturbances, the control problem becomes a convex optimization problem. This allows the use of Online Gradient Descent (OGD) to update the controller on the fly.

This approach is powerful because it handles nonstochastic environments. Most classical filters (like the Kalman filter) assume noise is Gaussian and "nice." In the nonstochastic framework, the noise can be chosen by an adversary to trip you up. Yet, as Naman Agarwal and colleagues demonstrated in Logarithmic Regret for Online Control, if the costs are strongly convex, we can achieve $O(\log T)$ regret—meaning the controller learns almost instantly.

Why Learning Doesn't "Blow Up" the System

A major fear in online learning for control is that exploration might lead to instability. If you try a "random" action to learn the system, the robot might crash.

The research direction addresses this through two main mechanisms:

  1. The Memoryless Property: Ambuj Tewari and Mohamad Kazem Shirani Faradonbeh argue in Input perturbations for adaptive control and learning that stable systems have a "memoryless" quality. Past bad decisions don't haunt the system forever; their impact decays exponentially, allowing the controller to "revoke" the impact of early estimation errors as it gets smarter.
  2. Buffer Zones: To handle hard safety constraints, Subhro Das and Na Li introduced OGD-BZ in Online Optimal Control with Affine Constraints. By "tightening" the constraints slightly—creating a safety buffer—the algorithm can explore and learn while guaranteeing that even with noise, the system never violates its physical limits.

Bridging Prediction and Control

Modern frameworks like SSI-MPC (Simultaneous System Identification and Model Predictive Control), developed by Hongyu Zhou and Vasileios Tzoumas, integrate these ideas into the predictive control loops used in industry.

In Simultaneous System Identification and Model Predictive Control with No Dynamic Regret, they show that by updating the system model at every time step and using those updates to inform a predictive horizon, the controller can achieve sublinear dynamic regret. This means the robot isn't just getting better at a fixed task; it's getting better at tracking an ever-changing optimal strategy.

The Frontier: Nonlinearity and Continuous Time

While much of the early work focused on linear systems, the field is rapidly expanding:

Ultimately, this research direction proves that we don't need to choose between the performance of reinforcement learning and the safety of control theory. By framing control as a regret-minimization problem, we can build systems that are provably efficient, robust to adversaries, and safe by design.

Papers in this version

Showing 60 of 150 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 172 papers
  2. Version 1 · 2026-10-04 · 150 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_dynamic_regret_minimization_sublinear_dy_f856b64a,
  title = {dynamic regret minimization (sublinear dynamic regret)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dynamic-regret-minimization-sublinear-dynamic-regret/rdr_f856b64a9ed343f69f0df7a867a24617},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_online_control_with_provable_regret_guar_f856b64a_v1,
  title = {Online Control with Provable Regret Guarantees},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/online-control-with-provable-regret-guarantees/rdr_f856b64a9ed343f69f0df7a867a24617/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}