REVIEW 3 major objections 5 minor 1 cited by
Online Nonstochastic Control with Convex Safety Constraints
T0 review · 3 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash
Pith's one-line read A single online gradient-descent controller can enforce general convex safety constraints at every time step under adversarial bounded disturbances while still achieving $\tilde{O}(\sqrt{T})$ regret against the best safe linear policy in…
desk verdict A real and likely correct extension of online nonstochastic control to convex safety constraints, but Theorem 1 as stated is not proven because the constants in the statement do not match the appendix bounds. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
Disturbance-action controllers with a safe-policy set defined by set shrinkage and expansion. The safe set is $\Omega_\epsilon = \{M \in \mathcal{M}: \mathring{h}_x(M) \bar{B}(w) \subseteq X_\epsilon \text{ and } \mathring{h}_u(M) \bar{B}(w) \subseteq U_\epsilon\}$, where $X_\epsilon$ and $U_\epsilon$ are the $\epsilon$-shrunk constraint sets and $\mathring{h}_x, \mathring{h}_u$ map a fixed policy to worst-case reachable sets for state and input under bounded disturbances. Projecting the online gradient step onto $\Omega_\epsilon$ keeps the actual state and input inside $X$ and $U$ once $\epsilon$ is chosen to cover the exponentially decaying horizon-truncation error and the slowly-changing-policy approximation error. Lemma 2, which contains $\Omega_\epsilon$ between two convex interpolations of the policy set and the strictly safe linear policy $M(K_{ss})$, is the mechanism that turns convexity into distance bounds and removes the constraint-count dependence.
What would settle it
One concrete adversarial test: for an LTI instance satisfying Assumptions 1-2 and a parameter choice satisfying Theorem 1, compute the worst-case disturbance sequence that maximizes, over $t$, the distance of the OGD-BZC state from the boundary of $X$ and the input from the boundary of $U$. If any bounded disturbance sequence drives the state out of $X$ or the input out of $U$, the safety theorem is false.
Extended reading notes
Core claim
The central claim is that a single online algorithm, OGD-BZC, can satisfy general closed convex state and input constraints at all times for an LTI system under adversarial bounded disturbances, and still match the usual unconstrained regret bound. The algorithm maintains a disturbance-action controller and runs projected online gradient descent on an approximate convex cost, projecting at each step onto a set $\Omega_\epsilon$ of policies that keep the surrogate state and input inside the $\epsilon$-shrunk safety sets for all possible disturbances. By choosing the memory $H$, buffer size $\epsilon$, and step size $\eta$ according to the theorem conditions, the paper proves deterministic safety and, for sufficiently large $T$, regret bounded by $\tilde{O}(m^{1.5} n^{1.5} \sqrt{T})$ in Corollary 1. The proof avoids the affine structure used in earlier work by bounding the gap between the safe policy set and the best linear policy through convex set-containment lemmas, so the regret does not scale with the number of constraints.
Load-bearing premise
There exists a fixed linear controller that, under every possible disturbance sequence, keeps the state and input strictly inside the constraints by at least a fixed positive margin for the entire infinite horizon.
Editorial extensions
If this is right
- For any LTI system satisfying the strict safe linear policy assumption, OGD-BZC keeps $x_t$ in $X$ and $u_t$ in $U$ for every $t$ and every bounded disturbance sequence, so safety is deterministic rather than probabilistic or cumulative.
- The regret bound is $\tilde{O}(\sqrt{T})$ under the Corollary 1 parameter choice, matching the unconstrained convex-cost rate up to log factors and dimension and system constants.
- The result covers general closed convex constraints, including nonlinear constraint sets, and the regret expression has no factor counting the number of constraints, improving on the affine-only predecessor.
- For sufficiently large $T$, the theorem's inequalities leave room to choose $H$, $\epsilon$, and $\eta$ whenever an $\epsilon^*$-strictly safe linear policy exists, so the safety and regret guarantees are simultaneously attainable.
Reading between the lines
- Because the regret rate matches the unconstrained setting, the paper suggests that the price of deterministic convex safety is hidden in constants and logarithmic factors rather than in the $T$-dependence; a natural next question is whether similar $\tilde{O}(\sqrt{T})$ guarantees hold for time-varying or partially observable systems, where the strict-margin assumption is harder to satisfy.
- The buffer construction relies on knowing the strict safety margin $\epsilon^*$ of some linear policy, which may be unknown in practice; an adaptive scheme that estimates $\epsilon^*$ online or uses conservative bounds on $H$ and $\eta$ would make the algorithm more directly implementable.
- The projection step onto $\Omega_\epsilon$ may be computationally heavy for high-dimensional convex constraints, a point the paper itself flags as future work; an approximate projection that preserves membership up to a smaller buffer might keep deterministic safety while reducing per-step cost.
- The numerical regret can be negative relative to the best safe linear policy because disturbance-action controllers form a larger policy class, which suggests that measuring regret against the best safe DAC rather than the best linear policy would be a harder and possibly more informative benchmark.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper considers online nonstochastic control of a known linear time-invariant system with convex state and input constraints that must hold at every time step under bounded adversarial disturbances. It proposes OGD-BZC, a projected online gradient descent algorithm over a set of disturbance-action controllers, and claims deterministic safety plus O~(√T) regret with respect to the best safe linear policy in hindsight. The algorithm uses a safe policy set Ω_ϵ defined through set shrinkage/expansion, an approximate convex cost, and a buffer zone whose size is set by Theorem 1. The regret analysis splits the regret into a performance gap, bounded by standard OCO arguments, and a policy-set gap, bounded using new convex-geometric lemmas. Numerical experiments on a two-dimensional double-integrator-like system illustrate safety and regret behavior.
Significance. If correct, the paper would be a meaningful step beyond prior work that handles affine safety constraints: it would provide a deterministic anytime safety guarantee for general convex constraints under adversarial disturbances while retaining a sublinear regret rate. The strategy of using shrinkage/expansion of convex sets to define the safe policy set is a genuinely new analytical ingredient relative to [3], and the derivation is essentially self-contained, with explicit constants and no fitted parameters. The paper also makes concrete, falsifiable predictions: deterministic constraint satisfaction for all disturbance sequences and an O~(√T) regret bound for the stated parameter choices. These strengths make the results worth pursuing, but the mismatches described below currently prevent the stated theorems from being accepted as proven.
major comments (3)
- [§V-A, Theorem 1; Appendix B, Lemma 5] The definition ϵ1(H) := c1 H(1−γ)^H in Theorem 1 is not the quantity proven in Lemma 5, which establishes ∥xt−˜xt∥∞ ≤ c1√(mn) H(1−γ)^H with the constant c1 defined inside the lemma. Since the safety proof closes the containment only through the condition ϵ1(H)+ϵ2(η,H) ≤ ϵ ≤ ϵ*−ϵ1(H)−ϵ3(H), using the smaller Theorem-1 value of ϵ1 can select a buffer ϵ that does not actually compensate for the approximation error, so Theorem 1 as stated is not proven. The mismatch is local and likely fixable by absorbing √(mn) into the constant or into the stated ϵ1, but Corollary 1's choices of H, η, and ϵ must then be re-derived.
- [§V-A, Theorem 1; Appendix B, Lemma 6] Theorem 1 states ϵ2(η,H) := c2√(mn^3)ηH^2, but Lemma 6's derivation yields ∥hx(M_{t−H+1:t})−˚hx(M_t)∥_∞ w ≤ O(√(mn^3))H^2η for the state block and ∥hu(M_{t−H:t})−˚hu(M_t)∥_∞ w ≤ O(mn)H^2η for the input block, and the lemma sets ϵ2 with a √(m^2 n^3) factor, i.e., m n^{3/2}. The stated ϵ2 is therefore smaller by a factor of √m than the guaranteed bound, so the containment (hx−˚hx)·B̄(w) ⊆ B̄(ϵ2) used in the proof of Theorem 1 is not justified with the theorem's parameters. This also propagates to Corollary 1: with the corrected ϵ2, the term ϵT√(m^2n^2)H^3/ϵ* in Theorem 2 becomes O~(m^2 n^{3/2}√T) rather than O~(m^{3/2}n^{3/2}√T), so the stated exponent in Corollary 1 is not established as written.
- [§V-B, Theorem 2, Lemmas 1, 3, and 4] The displayed regret bound in Theorem 2 does not transparently follow from the stated lemmas with the stated exponents. In the proof of Lemma 4, Part i gives O(T mn H^2(1−γ)^H), not the O(T√(m^2 n^3)H^2(1−γ)^H) term displayed in Theorem 2. Lemma 1 gives O(T√(m^2 n^2)H^3(ϵ1+ϵ3+ϵ)/ϵ*), which with ϵ1(H)=c1H(1−γ)^H yields T mn H^4(1−γ)^H/ϵ*, not the term T√(m^2 n^3)H^5(1−γ)^H/ϵ* displayed in Theorem 2. These differences change the H-dependence and the m,n exponents in the final bound; although the O~(√T) rate may survive after a careful re-derivation, the theorem as printed is not a consequence of the supplied lemmas and should be corrected.
minor comments (5)
- [§I-A and §II] There are small typos: "indicater" in the Notations paragraph, and the class K is written as K ⊆ R^{n×m} while the controller ut = −Kxt requires K ∈ R^{m×n}.
- [Definition 3 and Corollary 2] Definition 3 defines ϵ-strict safety only for ϵ > 0, but Corollary 2 states the result for "ϵ0 ≤ 0" and later applies it with ϵ0 = 0; please clarify the convention for non-positive buffer parameters.
- [Appendix D, Lemma 10] The symbol w̄ appears in the display for Gf without definition; it appears to mean the disturbance bound w introduced in Section II.
- [§VI] The numerical experiment parameters H=⌊log T⌋, ϵ=log(T)/√T, and η=1/(√T log T) are not the choices prescribed by Corollary 1, and for T=30 the condition H ≥ log(2κ²)/log((1−γ)^{-1}) may fail; please state explicitly whether the simulation is intended as a heuristic illustration or as a realization of the theorem's parameter selection.
- [§V-B, Theorem 2] The phrase "the hidden constant coefficients is the polynomial" should be "the hidden constants are polynomials", and "This finishs the proof" in Lemma 4 should be corrected to "finishes".
Circularity Check
No significant circularity: the safety and regret derivations are self-contained given the explicit external Assumption 2.
full rationale
The OGD-BZC derivation does not exhibit any of the circular patterns. The safety argument is built from Proposition 1 (adopted from the external DAC literature), explicit disturbance bounds in Lemmas 5-7, and the convex set-shrinkage/expansion calculus whose needed properties are proved in Appendix A (Proposition 2), not merely cited. The only overlap with the authors' prior work is Definition 2, which references [27] for Minkowski subtraction; since the required containment relations are proved in the appendix and the definition is standard, this citation is not load-bearing. Assumption 2 is an explicit external feasibility assumption that guarantees the existence of a strictly safe linear policy; it is an input to the theorem, not a conclusion derived from it. The safe policy set Omega_eps is defined directly from the dynamics and the shrunk constraint sets, and Theorem 1 verifies containment using the paper's own Lemmas 5 and 6. The regret analysis is a standard OGD/dynamics-approximation argument with explicit constants; no parameter is fitted to data and then renamed as a prediction. The numerical experiments are illustrative rather than evidence for the theorems. The skeptic's noted mismatch between the epsilon formulas in Theorem 1 and the bounds proved in Lemmas 5-6 is a correctness or consistency concern about the stated constants, not a circularity, because it does not make any claimed result equivalent to its own input by construction.
Assumptions & free parameters
free parameters (3)
- Memory size H =
H = log((8c1T + 4c3 sqrt(n))/eps*) / log((1-gamma)^-1)
- Step size eta =
eta = 1/(n sqrt(T) H^3)
- Buffer size eps =
eps = eps1(H) + eps2(eta,H)
assumptions (5)
- domain assumption Assumption 2: existence of an infinite-horizon eps*-strictly safe linear policy with eps* > 0
- domain assumption Assumption 1: stage costs are convex, differentiable, with bounded values and gradients on bounded sets
- domain assumption Bounded disturbance set W with known bound w, x0 = 0, A and B known, X and U closed convex sets containing the origin
- domain assumption Strong stability of the nominal controller and comparison class, with known (kappa, gamma)
- standard math Proposition 1 (Lemma 4.3 in [1]): DAC state and input decomposition into the predicted term and the surrogate term
Cite this review
Pith. "Pith review of Online Nonstochastic Control with Convex Safety Constraints." pith.science (2026). https://pith.science/paper/VZ6U75GE
@misc{pith2026250118039,
author = {Pith},
title = {Pith review of: Online Nonstochastic Control with Convex Safety Constraints},
year = {2026},
howpublished = {\url{https://pith.science/paper/VZ6U75GE}},
note = {Machine review of arXiv:2501.18039}
}
abstract
This paper considers the online nonstochastic control problem of a linear time-invariant system under convex state and input constraints that need to be satisfied at all times. We propose an algorithm called Online Gradient Descent with Buffer Zone for Convex Constraints (OGD-BZC), designed to handle scenarios where the system operates within general convex safety constraints. We demonstrate that OGD-BZC, with appropriate parameter selection, satisfies all the safety constraints under bounded adversarial disturbances. Additionally, to evaluate the performance of OGD-BZC, we define the regret with respect to the best safe linear policy in hindsight. We prove that OGD-BZC achieves $\tilde{O} (\sqrt{T})$ regret given proper parameter choices. Our numerical results highlight the efficacy and robustness of the proposed algorithm.
Figures
Forward citations
Cited by 1 Pith paper
-
Revisiting Regret Benchmarks in Online Non-Stochastic Control
An online projected-gradient controller achieves O(sqrt(T)) regret against the best-in-hindsight constant input for adversarial convex costs and disturbances.
Reference graph
Works this paper leans on
-
[3]
Online optimal control with affine constraints,
Y . Li, S. Das, and N. Li, “Online optimal control with affine constraints,” Proceedings of the AAAI Conference on Artificial Intelligence , vol. 35, no. 10, pp. 8527–8537, May 2021
work page 2021
-
[1]
Online control with adversarial disturbances,
N. Agarwal, B. Bullins, E. Hazan, S. Kakade, and K. Singh, “Online control with adversarial disturbances,” in Proceedings of the 36th inter- national conference on machine learning , ser. Proceedings of machine learning research, K. Chaudhuri and R. Salakhutdinov, Eds., vol. 97. PMLR, Jun. 2019, pp. 111–119
work page 2019
-
[2]
Introduction to Online Nonstochastic Control,
E. Hazan and K. Singh, “Introduction to Online Nonstochastic Control,” May 2023, arXiv:2211.09619 [cs, eess, math, stat]
arXiv 2023
-
[4]
Online nonstochastic control with ad- versarial and static constraints,
X. Liu, Z. Yang, and L. Ying, “Online nonstochastic control with ad- versarial and static constraints,” in International conference on machine learning. PMLR, 2023, pp. 22 277–22 288
work page 2023
-
[5]
Online convex opti- mization for robust control of constrained dynamical systems,
M. Nonhoff, E. Dall’Anese, and M. A. M ¨uller, “Online convex opti- mization for robust control of constrained dynamical systems,” arXiv preprint arXiv:2401.04487, 2024
arXiv 2024
-
[6]
Safe Non-Stochastic Control of Control-Affine Systems: An Online Convex Optimization Approach,
H. Zhou, Y . Song, and V . Tzoumas, “Safe Non-Stochastic Control of Control-Affine Systems: An Online Convex Optimization Approach,” IEEE Robotics and Automation Letters , vol. 8, no. 12, pp. 7873–7880, Dec. 2023
work page 2023
-
[7]
H. Zhou and V . Tzoumas, “Safe Control of Partially-Observed Linear Time-Varying Systems with Minimal Worst-Case Dynamic Regret,” in 2023 62nd IEEE Conference on Decision and Control (CDC) . Singapore, Singapore: IEEE, Dec. 2023, pp. 8781–8787
work page 2023
-
[8]
Logarithmic Regret for On- line Control,
N. Agarwal, E. Hazan, and K. Singh, “Logarithmic Regret for On- line Control,” in Advances in Neural Information Processing Systems , vol. 32. Curran Associates, Inc., 2019
work page 2019
Show all 31 references
-
[9]
Logarithmic regret for adversarial online control,
D. Foster and M. Simchowitz, “Logarithmic regret for adversarial online control,” in International conference on machine learning . PMLR, 2020, pp. 3211–3221
2020
-
[10]
Adaptive regret for control of time-varying dynamics,
P. Gradu, E. Hazan, and E. Minasyan, “Adaptive regret for control of time-varying dynamics,” in Learning for dynamics and control conference. PMLR, 2023, pp. 560–572
2023
-
[11]
Online control of unknown time-varying dynamical systems,
E. Minasyan, P. Gradu, M. Simchowitz, and E. Hazan, “Online control of unknown time-varying dynamical systems,” Advances in Neural Information Processing Systems , vol. 34, pp. 15 934–15 945, 2021
2021
-
[12]
Making non-stochastic control (almost) as easy as stochastic,
M. Simchowitz, “Making non-stochastic control (almost) as easy as stochastic,” Advances in Neural Information Processing Systems, vol. 33, pp. 18 318–18 329, 2020
2020
-
[13]
Improper learning for non- stochastic control,
M. Simchowitz, K. Singh, and E. Hazan, “Improper learning for non- stochastic control,” in Proceedings of thirty third conference on learning theory, ser. Proceedings of machine learning research, J. Abernethy and S. Agarwal, Eds., vol. 125. PMLR, Jul. 2020, pp. 3320–3436
2020
-
[14]
Non-stationary online learning with memory and non-stochastic control,
P. Zhao, Y .-H. Yan, Y .-X. Wang, and Z.-H. Zhou, “Non-stationary online learning with memory and non-stochastic control,” The Journal of Machine Learning Research , vol. 24, no. 1, pp. 9831–9900, 2023
2023
-
[15]
A Virtual-Queue-Based Algorithm for Constrained Online Convex Optimization With Applications to Data Center Resource Allocation,
X. Cao, J. Zhang, and H. V . Poor, “A Virtual-Queue-Based Algorithm for Constrained Online Convex Optimization With Applications to Data Center Resource Allocation,” IEEE Journal of Selected Topics in Signal Processing, vol. 12, no. 4, pp. 703–716, Aug. 2018
2018
-
[16]
Trading regret for efficiency: online convex optimization with long term constraints,
M. Mahdavi, R. Jin, and T. Yang, “Trading regret for efficiency: online convex optimization with long term constraints,”The Journal of Machine Learning Research, vol. 13, no. 1, pp. 2503–2528, 2012
2012
-
[17]
Online Convex Optimization with Time-Varying Constraints,
M. J. Neely and H. Yu, “Online Convex Optimization with Time-Varying Constraints,” Feb. 2017, arXiv:1702.04783 [math]
2017 arXiv
-
[18]
Online convex optimization with stochas- tic constraints,
H. Yu, M. Neely, and X. Wei, “Online convex optimization with stochas- tic constraints,” Advances in Neural Information Processing Systems , vol. 30, 2017
2017
-
[19]
Online convex optimization for cumula- tive constraints,
J. Yuan and A. Lamperski, “Online convex optimization for cumula- tive constraints,” Advances in Neural Information Processing Systems , vol. 31, 2018
2018
-
[20]
Robust model predic- tive control of constrained linear systems with bounded disturbances,
D. Q. Mayne, M. M. Seron, and S. V . Rakovi ´c, “Robust model predic- tive control of constrained linear systems with bounded disturbances,” Automatica, vol. 41, no. 2, pp. 219–224, 2005
2005
-
[21]
J. B. Rawlings, D. Q. Mayne, M. Diehl, and others, Model predictive control: theory, computation, and design. Nob Hill Publishing Madison, WI, 2017, vol. 2
2017
-
[22]
Review on model predic- tive control: an engineering perspective,
M. Schwenzer, M. Ay, T. Bergs, and D. Abel, “Review on model predic- tive control: an engineering perspective,” The International Journal of Advanced Manufacturing Technology, vol. 117, no. 5-6, pp. 1327–1349, Nov. 2021
2021
-
[23]
A general safety framework for learning-based control in uncertain robotic systems,
J. F. Fisac, A. K. Akametalu, M. N. Zeilinger, S. Kaynama, J. Gillula, and C. J. Tomlin, “A general safety framework for learning-based control in uncertain robotic systems,” IEEE Transactions on Automatic Control, vol. 64, no. 7, pp. 2737–2752, 2018
2018
-
[24]
A comprehensive survey on safe reinforce- ment learning,
J. Garcıa and F. Fern ´andez, “A comprehensive survey on safe reinforce- ment learning,” Journal of Machine Learning Research , vol. 16, no. 1, pp. 1437–1480, 2015
2015
-
[25]
Learning-based model predictive control for safe exploration,
T. Koller, F. Berkenkamp, M. Turchetta, and A. Krause, “Learning-based model predictive control for safe exploration,” in 2018 IEEE conference on decision and control (CDC) . IEEE, 2018, pp. 6059–6066
2018
-
[26]
Online linear quadratic control,
A. Cohen, A. Hasidim, T. Koren, N. Lazic, Y . Mansour, and K. Tal- war, “Online linear quadratic control,” in International conference on machine learning. PMLR, 2018, pp. 1029–1038
2018
-
[27]
The impact of the geo- metric properties of the constraint set in safe optimization with bandit feedback,
S. Hutchinson, B. Turan, and M. Alizadeh, “The impact of the geo- metric properties of the constraint set in safe optimization with bandit feedback,” in Learning for dynamics and control conference . PMLR, 2023, pp. 497–508
2023
-
[28]
Schneider, Convex bodies: the Brunn-Minkowski theory , second expanded edition ed., ser
R. Schneider, Convex bodies: the Brunn-Minkowski theory , second expanded edition ed., ser. Encyclopedia of mathematics and its applica- tions. New York: Cambridge University Press, 2014
2014
-
[29]
S. P. Boyd and L. Vandenberghe, Convex optimization. Cambridge, UK ; New York: Cambridge University Press, 2004
2004
-
[30]
Robust tube- based MPC for tracking of constrained linear systems with additive disturbances,
D. Limon, I. Alvarado, T. Alamo, and E. Camacho, “Robust tube- based MPC for tracking of constrained linear systems with additive disturbances,” Journal of Process Control , vol. 20, no. 3, pp. 248–260, Mar. 2010
2010
-
[31]
Online convex programming and generalized infinitesi- mal gradient ascent,
M. Zinkevich, “Online convex programming and generalized infinitesi- mal gradient ascent,” in Proceedings of the 20th international conference on machine learning (icml-03) , 2003, pp. 928–936. APPENDIX A. Supporting Lemmas Proposition 2. Let D be a closed convex set in Rd and...
2003
Reviewed August 10, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.