Revisiting Regret Benchmarks in Online Non-Stochastic Control
Vijeth Hebbar, Cédric Langbort · 2025
Read Revisiting Regret Benchmarks in Online Non-Stochastic Control by Vijeth Hebbar, Cédric Langbort (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-16581.txt.
Introduction
Vijeth Hebbar and Cedric Langbort re-set the regret bar in live stray control in 2025. A hand picks moves for a line system as stray costs and shocks land round by round. The old bar grades moves against the best line hand in hindsight, which can lag far for bent costs.
Their bar grades against the best fixed push, a wider and more apt mark. A new loop hits slow-growth regret to that bar in proofs. Links to the first frame for the task are drawn, and sim runs weigh both.
Catalog record
| CREATOR | Vijeth Hebbar, Cédric Langbort |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-16581
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Revisiting Regret Benchmarks in Online Non-Stochastic Control Vijeth Hebbar, Cédric Langbort Abstract In the online non-stochastic control problem, an agent sequentially selects control inputs for a linear dynamical system when facing unknown and adversarially selected convex costs and disturbances. A common metric for evaluating control policies in this setting is policy regret, defined relative to the best-in-hindsight linear feedback controller. However, for general convex costs, this benchmark may be less meaningful since linear controllers can be highly suboptimal. To address this, we introduce an alternative, more suitable benchmark—the performance of the best fixed input. We show that this benchmark can be viewed as a natural extension of the standard benchmark used in online convex optimization and propose a novel online control algorithm that achieves sublinear regret with respect to this new benchmark. We also discuss the connections between our method and the original one proposed by Agarwal et al. in their seminal work introducing the online non-stochastic control problem, and compare the performance of both approaches through numerical simulations. I INTRODUCTION The interface between online learning and control theory has become an active area of research, driven by the need to make sequential decisions in dynamic and uncertain environments [ 1 , 2 , 3 , 4 ] . In this paper, we revisit a control problem that lies within this intersection and has garnered increased attention in recent years; the online non-stochastic control problem [ 5 ] . Our contributions are twofold. First, we introduce a new notion of regret, based on a novel benchmark, that provides a more meaningful metric for evaluating performance in this setting. Second, we propose an online control algorithm that achieves sublinear regret with respect to this benchmark. In the online non-stochastic control problem, we are interested in controlling a linear dynamical system when faced with a sequence of unknown and adversarially picked convex cost functions and disturbances. Specifically, we consider the following linear time-invariant system x_{t+1}=Ax_{t}+Bu_{t}+w_{t},\quad t\geq 1, (1) and are interested in designing a learning algorithm \mathcal{A} that picks inputs \{u_{t}\} to minimize the cumulative cost 1 1 1 We consider input-independent costs for ease of exposition, but our methods can be easily extended to input-dependent costs as described in Appendix A . \displaystyle J(\mathcal{A})=\sum_{t=1}^{T}f_{t}(x_{t}). Crucially, the learner has to take action u_{t} at time t before any information about the cost function f_{t} or the disturbance w_{t} is revealed. Consequently, there is no way for the learner to compute the optimal controller. Instead, the standard metric of performance used in such scenarios is policy regret , which compares the cumulative cost incurred by the algorithm against the performance of the best-in-hindsight policy from a certain policy class. Background This setup was first considered by Agarwal et al. [ 6 ] and has since been extended in a multitude of directions – consideration of strongly convex costs [ 7 ] , partial observability of state [ 8 ] , consideration of safety constraints [ 1 , 4 ] and more [ 9 , 10 ] . In all these works, the policy class from which the best-in-hindsight controller is picked is the set of all stabilizing linear feedback controllers \mathcal{K} . Formally, the regret is defined as \displaystyle\mathcal{R}_{\mathcal{K}}(T)=\sum_{t=1}^{T}f_{t}(x_{t})-\min_{K\in\mathcal{K}}\sum_{t=1}^{T}f_{t}(x_{t}^{K}) (2) where \{x_{t}^{K}\}_{t=1}^{T} is the state trajectory generated by the time-invariant linear controller K , i.e., u_{t}=Kx_{t} for all t . The primary motivation for choosing this benchmark class is rooted in the classical linear quadratic regulator (LQR) problem: when costs are fixed quadratic functions and the horizon is infinite, the optimal controller is indeed a fixed linear feedback controller. Now, for a finite-horizon LQR problem with time-varying cost functions, such a fixed linear controller may perform poorly. However, the optimal controller for a finite horizon LQR is “non-causal” in the sense that computing the controller K_{t} at time t requires the knowledge of future costs \{Q_{\tau},R_{\tau}\}_{\tau\geq t} . Since this information is not available in an online learning setup, it is impractical and unfair to compare the learner’s performance against the optimal (yet unattainable) benchmark. Consequently, a fixed linear feedback has become the standard benchmark in online LQR literature [ 11 ] . When considering general convex functions, this benchmark of a fixed linear feedback controller becomes substantially less meaningful. To clearly illustrate this, consider a simplified scenario where no disturbances act on the system ( \{w_{t}\}\equiv\mathbf{0} ), and suppose the cost functions \{f_{t}\} all attain their minimum at some fixed non-zero state x^{*} . Any stabilizing linear feedback controller will quickly drive the system to the origin, leading to a cumulative cost close to \sum_{t}f_{t}(0) . In contrast, a controller that stabilizes the system at or near x^{*} would yield significantly lower cumulative costs. The primary motivation for retaining linear feedback controllers as a benchmark is that we recover established regret guarantees when applying the developed approach to an LQR setup. However, prompted by the limitations of linear controller benchmarks when facing general convex costs, this paper seeks to explore alternative and more suitable benchmarks. A natural option – common in the online convex optimization (OCO) literature – is the optima of the cumulative cost function. Mapping this to our setting, we could propose the following notion of regret: \displaystyle\mathcal{R}_{x}(T)\triangleq\sum_{t=1}^{T}f_{t}(x_{t})-\min_{x\in\mathcal{X}}\sum_{t=1}^{T}f_{t}(x),\vskip-4.26773pt (3) where \mathcal{X} denotes the set of steady-states achievable via constant inputs (formally defined in Definition 4 ). This regret definition is particularly appealing because it captures how well the learner performs relative to an idealized controller that instantly stabilizes the system at the optimal steady-state x^{*}\in\mathcal{X} . This is a powerful notion of regret since it is identical to the one in standard online convex optimization setups - where decisions \{x_{t}\} are chosen independently from \mathcal{X} without any coupling across time. Thus, achieving low regret against this benchmark means that, despite operating under system dynamics, the learner performs almost as well as if the dynamics posed no constraints. However, directly using this benchmark can be challenging when the system is subject to disturbances. In such settings, stabilizing to a single point is not feasible since the disturbance continually pushes the system around. To address this, we work with an alternate regret definition that compares performance against the best constant input: \displaystyle\mathcal{R}_{u}(T)\triangleq\sum_{t=1}^{T}f_{t}(x_{t})-\min_{u\in\mathcal{U}}\sum_{t=1}^{T}f_{t}(x_{t}^{u}),\vskip-4.26773pt (4) where \{x_{t}^{u}\} is the trajectory induced by applying the fixed input u at all times. Crucially, we show that in the absence of disturbances, the two regret definitions in ( 3 ) and ( 4 ) are equivalent in some sense (see Lemma 5 ), thus offering a meaningful interpretation for \mathcal{R}_{u} as well. However, this regret formulation remains meaningful even in the presence of disturbance. We employ both these regret notions in our work. Other Relevant Literature A closely related line of work within the control literature considers dynamic regret , which compares the performance of the learner against that of the optimal clairvoyant controller (i.e., a controller informed by complete knowledge of future disturbances and costs). This is, of course, the strongest benchmark against which any online control policy can be compared. However, unlike static regret bounds (which we focus on in this work), dynamic regret bounds are typically instance-dependent, meaning they depend explicitly on the sequence of costs encountered. Moreover, these results often rely on additional