Introduction to Online Nonstochastic Control

Elad Hazan, Karan Singh

Cover of the foundational text "Introduction to Online Control" by Elad Hazan and Karan Singh.

Abstract

This text presents an introduction to an emerging paradigm in control of dynamical systems and differentiable reinforcement learning called online nonstochastic control. The new approach applies techniques from online convex optimization and convex relaxations to obtain new methods with provable guarantees for classical settings in optimal and robust control. The primary distinction between online nonstochastic control and other frameworks is the objective. In optimal control, robust control, and other control methodologies that assume stochastic noise, the goal is to perform comparably to an offline optimal strategy. In online nonstochastic control, both the cost functions as well as the perturbations from the assumed dynamical model are chosen by an adversary. Thus the optimal policy is not defined a priori. Rather, the target is to attain low regret against the best policy in hindsight from a benchmark class of policies. This objective suggests the use of the decision making framework of online convex optimization as an algorithmic methodology. The resulting methods are based on iterative mathematical optimization algorithms, and are accompanied by finite-time regret and computational complexity guarantees.

Introduction: Rethinking the Steering Wheel

Traditional control theory has long been divided into two primary philosophies. Optimal Control, exemplified by the Linear Quadratic Regulator (LQR), operates under the assumption that noise is stochastic—typically Gaussian and independent. While mathematically elegant, this is often an unrealistically optimistic view of the world; environmental factors like wind gusts hitting a drone or complex traffic patterns do not follow neat bell curves. Conversely, Robust Control ($H_\infty$ control) prepares for the absolute worst-case scenario. While safe, this approach is frequently overly conservative, resulting in sluggish performance that fails to adapt to actual conditions.

Online Nonstochastic Control addresses the gap between these extremes. It asks: How can we design a controller that performs nearly as well as if it knew future disturbances in advance, without making rigid assumptions about the nature of those disturbances? By framing control as a repeated game and applying the principles of Online Convex Optimization (OCO), this framework develops algorithms that provide provable performance guarantees even in the face of adversarial disturbances or unknown environments.

Methodology and Algorithmic Foundations

The core of this approach bridges control theory with machine learning, treating the environment as an adversary in a sequential decision-making process. Several key techniques enable this transition:

Regret Minimization and OCO

Instead of seeking an absolute global optimum, the objective is to minimize regret—the difference between the total cost incurred by the controller and the cost of the best fixed policy chosen in hindsight. This shift allows the system to handle unpredictable, non-stochastic noise that would typically cause a standard Kalman filter to fail.

Disturbance Action Control (DAC)

A significant technical hurdle in control is that the cost function is often non-convex with respect to standard control parameters. The authors introduce a clever re-parameterization called Disturbance Action Control. By expressing the control input as a linear function of past disturbances rather than just current states, the cost function becomes convex. This transformation is the "aha moment" of the framework, allowing the use of efficient Online Gradient Descent (OGD) to update the controller in real-time.

Spectral Filtering for Unknown Systems

For systems where the underlying dynamics are unknown or unstable, the framework employs spectral filtering. Using Hankel matrices and spectral decompositions, the controller can learn a predictive model. A unique advantage of this method is that its computational complexity does not scale with the system's hidden dimensions or stability constants, effectively bypassing the "curse of dimensionality."

Experimental Framework and Applications

As a foundational theoretical work, the methods are validated through a diverse set of dynamical system simulations that represent both classic challenges and modern engineering needs:

  • Medical Ventilators: Controlling lung pressure (PEEP) to assist breathing, where disturbances are highly non-stochastic.
  • Aircraft Dynamics: Managing the longitudinal motion of a Boeing 747 under varying atmospheric conditions.
  • Epidemiological Models: Simulating vaccine administration strategies using the SIR model.
  • Robotics Basics: Standard benchmarks including the Double Integrator and Pendulum Swing-Up problems.

Key Results and Insights

The framework yields several powerful theoretical and practical results:

  1. Sublinear Regret: The Gradient Perturbation Controller (GPC) achieves $O(\sqrt{T})$ regret. This ensures that as time ($T$) progresses, the average performance of the controller becomes indistinguishable from the best possible fixed policy in the benchmark class.
  2. Handling the Unknown: In scenarios where the system physics (the $A$ and $B$ matrices) are unknown, a "method of moments" identification procedure combined with GPC yields $O(T^{2/3})$ regret. The performance hit reflects the necessary cost of exploration.
  3. Computational Efficiency: Unlike traditional dynamic programming, which scales poorly with state space, these gradient-based methods feature per-step complexity that is linear in the number of parameters and logarithmic in time.

Discussion and Future Directions

While Online Nonstochastic Control represents a leap forward in adaptive systems, several frontiers remain. Current theory largely relies on the system being "stabilizable," and performance guarantees are strongest when the system does not exhibit immediate divergent behavior. Furthermore, while the text discusses linearization via Taylor expansions, a robust global theory for highly non-linear, non-convex dynamics is still under development.

Finally, the "projection cost"—the computational effort required to ensure a controller stays within safe operational bounds—can be significant for complex constraint sets. Future research into more efficient projection-free methods or specialized constraint handling will be vital for deploying these algorithms in high-frequency real-world robotics.

Summary updated

Abstract

This text presents an introduction to an emerging paradigm in control of dynamical systems and differentiable reinforcement learning called online nonstochastic control. The new approach applies techniques from online convex optimization and convex relaxations to obtain new methods with provable guarantees for classical settings in optimal and robust control. The primary distinction between online nonstochastic control and other frameworks is the objective. In optimal control, robust control, and other control methodologies that assume stochastic noise, the goal is to perform comparably to an offline optimal strategy. In online nonstochastic control, both the cost functions as well as the perturbations from the assumed dynamical model are chosen by an adversary. Thus the optimal policy is not defined a priori. Rather, the target is to attain low regret against the best policy in hindsight from a benchmark class of policies. This objective suggests the use of the decision making framework of online convex optimization as an algorithmic methodology. The resulting methods are based on iterative mathematical optimization algorithms, and are accompanied by finite-time regret and computational complexity guarantees.
BibTeX
@misc{hazan2022introduction,
  author = {Elad Hazan and Karan Singh},
  title = {{Introduction to Online Nonstochastic Control}},
  year = {2022},
  eprint = {2211.09619},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2211.09619},
}
Figure