Online Control of Linear Systems with Unbounded and Degenerate Noise

Kaito Ito, Taira Tsuchiya

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:

  1. Concentration Inequalities: Using moment bounds to show that while the noise can be large, it is rarely large enough to ruin cumulative performance.
  2. 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.

Comparison of regret bounds and noise assumptions between this work and existing literature.

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

Abstract

This paper investigates the problem of controlling a linear system under possibly unbounded and degenerate noise with unknown cost functions, known as an online control problem. In contrast to the existing work, which assumes the boundedness of noise, we reveal that for convex costs, an $ \widetilde{O}(\sqrt{T}) $ regret bound can be achieved even for unbounded noise, where $ T $ denotes the time horizon. Moreover, when the costs are strongly convex, we establish an $ O({\rm poly} (\log T)) $ regret bound without the assumption that noise covariance is non-degenerate, which has been required in the literature. The key ingredient in removing the rank assumption on noise is a system transformation associated with the noise covariance. This simultaneously enables the parameter reduction of an online control algorithm.
BibTeX
@misc{ito2024online,
  author = {Kaito Ito and Taira Tsuchiya},
  title = {{Online Control of Linear Systems with Unbounded and Degenerate Noise}},
  year = {2024},
  eprint = {2402.10252},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2402.10252},
}
Figure