Abstract
Most online control algorithms assume that stochastic noise is strictly bounded, a condition often violated in real-world systems like power grids or wind turbines. This paper demonstrates that optimal regret bounds—$O(\sqrt{T})$ for convex costs and $O(\text{poly}(\log T))$ for strongly convex costs—can still be achieved under unbounded noise, provided the noise has a finite fourth moment or follows a sub-Gaussian distribution. By establishing high-probability bounds rather than simple expectations, this work provides a more robust theoretical foundation for controlling systems subject to heavy-tailed disturbances.
Introduction
In the field of Online Control, a learner must control a linear dynamical system while facing cost functions that change over time and are only revealed after a control action is taken. The goal is to minimize regret: the difference between the total cost incurred by the learner and the cost of the best fixed controller in hindsight.
Existing literature heavily relies on the assumption that the system's stochastic noise is bounded (i.e., it never exceeds a fixed value $W$). However, real-world "black swan" events or heavy-tailed distributions—such as wind gusts or solar fluctuations—mean noise is often unbounded. If unbounded noise is applied to standard algorithms, theoretical regret bounds often explode to infinity. This research addresses this gap by identifying the minimal statistical requirements for noise to still allow for sublinear regret.
Methodology
The paper utilizes the Disturbance-Action Policy (DAP) framework. In this setup, the control input $u_t$ is determined by a stable linear feedback law plus a weighted sum of past disturbances (noise). To optimize this policy, the authors employ Online Gradient Descent (OGD) on a "surrogate" cost function. Because the true state of the system depends on the entire history of control inputs, optimizing it directly is computationally intractable. The surrogate cost approximates the true cost by considering only a finite window of past disturbances, effectively "forgetting" the distant past.
Overcoming Unbounded Noise
The core challenge with unbounded noise is that the system state $x_t$ and the gradients of the cost function can become arbitrarily large. Standard proofs for OGD require bounded gradients. The authors overcome this by:
- Concentration Inequalities: Using moment bounds to show that while the noise can be large, it is rarely large enough to ruin cumulative performance.
- Regret Decomposition: Carefully breaking down regret into terms that account for the approximation error of the surrogate cost and the convergence of the OGD algorithm under stochastic conditions.
Key Results and Contributions
The paper establishes two primary regret bounds that hold with high probability ($1-\delta$). These results are summarized in the table below, comparing them to previous state-of-the-art methods that required stricter noise assumptions.
1. General Convex Costs + Finite 4th Moment Noise
The authors show that for general convex costs, the noise doesn't need to be Gaussian or even sub-Gaussian. Simply having a finite fourth moment ($\mathbb{E}[\|w_t\|^4] < \infty$) is sufficient to guarantee $O(\sqrt{T} \log^3 T)$ regret with high probability. Notably, this analysis also slightly improves the existing regret bound for bounded noise from $O(\sqrt{T} \log^{3.5} T)$ to $O(\sqrt{T} \log^3 T)$.
2. Strongly Convex Costs + Sub-Gaussian Noise
For strongly convex and smooth costs, the paper achieves a "poly-logarithmic" regret of $O(\log^8 T)$. This is a significant result because it shows that if the costs are well-behaved (curved) and the noise tails decay exponentially, the error relative to the optimal controller grows extremely slowly even when the noise is technically unbounded.
Discussion
This is the first study to explicitly link the regret bound of an online controller to the specific statistical properties (moments and tail behavior) of the noise process. By establishing high-probability bounds rather than "pseudo-regret" (regret in expectation), the authors provide a guarantee that is much harder to prove for unbounded noise, as a single massive outlier could theoretically derail the controller.
Limitations and Future Work
While these results represent a significant advancement, several challenges remain:
- Known System Dynamics: The paper assumes the system matrices $A$ and $B$ are perfectly known. In many real-world scenarios, these must be learned on the fly (the "Adaptive Control" problem).
- Full Observability: The authors assume the controller can see the full state $x_t$ and calculate the exact noise $w_t$. Extending this to partially observed systems remains an open challenge.
- Computational Complexity: The DAP policy requires storing and processing a window of past disturbances, which may be memory-intensive for high-dimensional systems.
The authors suggest that their approach to handling unbounded noise via moment-based analysis could serve as a blueprint for extending other online learning algorithms to more rugged, real-world environments.
Summary updated