Pith. sign in

REVIEW 2 major objections 5 minor 15 references

Revisiting Regret Benchmarks in Online Non-Stochastic Control

T0 review · 2 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read An online projection rule on steady states achieves $O(\sqrt{T})$ regret against the best fixed input.

desk verdict Nice benchmark and a clean algorithm, but the central theorems are false as stated because Assumption 2 omits convexity of U; the fix is easy and the paper is worth a serious referee. read the letter →

arxiv 2504.16581 v1 pith:3PBBM3SJ submitted 2025-04-23 math.OC cs.SYeess.SY

Vijeth Hebbar , Cédric Langbort This is my paper · ORCID
classification math.OCcs.SYeess.SY MSC 68Q3293C5590C25
keywords onlinenon-stochasticcontrolregretbenchmarksconstantinputbenchmarkprojectedgradientdescentsteady-statemanifoldadversarialdisturbancesconvexcostslineardynamicalsystems
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Most regret guarantees for online non-stochastic control compare the learner against the best-in-hindsight linear feedback controller, a benchmark that can be badly suboptimal when costs are general convex functions. This paper argues that the right static benchmark is the cumulative cost of the best time-invariant (constant) input, and shows that in the disturbance-free case this is equivalent up to a constant gap to minimizing cost over the steady-state manifold. For a strongly stable linear system with bounded adversarial disturbances and smooth convex costs, the paper proves that a simple online projected-gradient-descent rule on target steady states achieves regret at most $(2LD^2/\gamma)(\sqrt{T(1+4\kappa^2)}+2\kappa)$ against this benchmark. The point is that, despite dynamics and adversarial noise, the learner performs almost as well as if it could pick states freely in the steady-state set.

What carries the argument

The carrying object is the steady-state manifold $\mathcal{X}=\{x\in\mathbb{R}^N: x=Ax+Bu,\,u\in U\}$, the set of states that can be held fixed by a constant input, together with Algorithm 1's projected-gradient update on target states $z_t$. Two properties make the argument work: contractivity of the projection $\Pi_{\mathcal{X}}$ onto the convex set $\mathcal{X}$, and the strong-stability estimate $\|A^k\|\le \kappa(1-\gamma)^k$, which forces the actual state $x_t$ to converge exponentially to the current target $z_t$. A superposition decomposition splits the state into a nominal disturbance-free part and a disturbance-driven part, and because the gradient of the shifted cost $g_t(\bar{x})=f_t(\bar{x}+x_t^d)$ at the nominal state equals the observed gradient $\nabla f_t(x_t)$, the algorithm can be run without estimating the disturbance. Lemma 5 converts regret against the best fixed input into regret against the best steady state when disturbances are absent.

What would settle it

Run Algorithm 1 on a one-dimensional strongly stable system $x_{t+1}=ax_t+bu_t+w_t$ with convex quadratic costs and a bounded non-convex input set such as $U=\{-1,1\}$; if the regret against the best fixed input fails to be $O(\sqrt{T})$ or the projection update tracks neither point, the theorem as stated fails. In the disturbance-free case, Lemma 5 claims a constant (independent of $T$) gap between fixed-input regret and steady-state regret; exhibiting convex costs where the gap grows linearly in $T$ would also falsify the reduction.

Watch

Extended reading notes

Core claim

The central claim is that online non-stochastic control with convex costs is tractable against a more meaningful benchmark than the best linear controller: the best fixed input. Concretely, Theorem 8 states that running Algorithm 1 — choose $u_t$ satisfying $Bu_t=(I-A)z_t$ for a target state $z_t\in\mathcal{X}$, incur cost, observe gradient $\delta_t=\nabla f_t(x_t)$, update $z_{t+1}=\Pi_{\mathcal{X}}(z_t-\eta \delta_t)$ — yields regret $R_u(T)\le (2LD^2/\gamma)(\sqrt{T(1+4\kappa^2)}+2\kappa)$ for strongly stable systems. The proof separates regret into an online-gradient-descent term over target states and a tracking-error term that decays exponentially by strong stability, then uses superposition to reduce the disturbance-perturbed problem to a disturbance-free one. With no disturbances, Lemma 5 shows the fixed-input benchmark is equivalent up to an $o(T)$ gap to minimizing cumulative cost over the steady-state manifold $\mathcal{X}=\{x: x=Ax+Bu,\,u\in U\}$, so the benchmark inherits the natural interpretation from online convex optimization. Simulations in the paper show the best fixed input can beat the best disturbance-action (linear-feedback) policy on the tested instances.

Load-bearing premise

The load-bearing premise is that the input set $U$, and therefore the steady-state manifold $\mathcal{X}$ onto which the algorithm projects, is convex; the paper assumes $U$ is bounded and costs are smooth, but never states convexity of $U$, and the projection's contractivity and the tracking-error estimate require it.

Editorial extensions

If this is right

  • The regret rate matches the $O(\sqrt{T})$ rate of ordinary online gradient descent, so dynamics and adversarial disturbances cost only a constant factor plus an additive constant.
  • The algorithm can be deployed with no horizon-memory parameter: the only design choices are the step size and the projection onto the steady-state set.
  • Sublinear regret against the best fixed input gives a sublinear policy-regret statement against the earlier disturbance-action/linear-feedback benchmark in the regimes where a fixed input is the stronger baseline.
  • In the disturbance-free case the benchmark has a clean interpretation: it is the cumulative cost of the best state a clairvoyant controller would stabilize at, up to a constant gap.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the convexity of the input set $U$ should be stated explicitly as an assumption; for non-convex $U$ the projection update is not guaranteed to behave and the theorem's stated scope needs revision.
  • Editorial inference: the same target-state mechanism is likely to extend to strongly convex costs to yield logarithmic regret, the direction the authors list as future work.
  • Editorial inference: the fixed-input benchmark connects this static-regret problem to the dynamic-regret line of work that restricts pointwise optima to the steady-state manifold; comparing both benchmarks on identical instances would show when each is the honest baseline.
  • Editorial inference: for stabilizable but not stable systems, running the same update on a closed-loop system with a fixed stabilizing gain should give an analogous bound whose constants depend on that gain.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper proposes an alternative regret benchmark for online non-stochastic control: instead of comparing against the best-in-hindsight linear (disturbance-action) controller, it compares against the best fixed input and the best achievable steady state. The authors define steady-state regret R_x and constant-input regret R_u, develop a projected online gradient descent algorithm on the steady-state manifold, and claim O(sqrt(T)) regret bounds (Theorems 6 and 8) under strong stability, bounded input/disturbance sets, and bounded-gradient convex costs. They also discuss connections to the DAC framework of Agarwal et al. and provide numerical comparisons.

Significance. Conceptually, the paper addresses a genuine weakness of the existing benchmark: a fixed linear-feedback policy is not a natural comparator for time-varying convex costs. The steady-state/fixed-input benchmark is a sensible analogue of the standard OCO benchmark, and the superposition reduction from the disturbed problem to a disturbance-free nominal problem (Proposition 7) is elegant. The derivations are self-contained, the step size is chosen analytically rather than tuned to data, and the constants are explicit. If the assumptions are corrected, the proposed algorithm gives a clean sublinear-regret guarantee. At present, however, the central theorems are false as stated because the projection onto the steady-state set is used without any convexity assumption, and the proof of Lemma 5 contains a sign error.

major comments (2)
  1. [Section II-A (Assumption 2), Definition 4, Lemma 11, Theorem 6] Assumption 2 only requires U and W to be bounded, so X = (I-A)^{-1}BU (Definition 4) need not be convex or closed. Algorithm 1 projects onto X, and the proofs of Lemma 11 (step (a)) and Theorem 6 (step (a)) invoke contractivity/nonexpansiveness of the projection, a property that fails for a general bounded U. This is not a merely technical gap: take the scalar system A = 1/2, B = 1, U = {-1,1}, so X = {-2,2}; costs f_t(x) = (x-2)^2; and x_1 = z_1 = -2, gamma = 1/2, kappa = 1, L = 4, D = 2, eta = 1/(4 sqrt(5T)) as in Theorem 6. The state stays at -2 for every t, and the projected update z_t - eta*delta_t = -2 + 2/sqrt(5T) projects back to -2, so u_t = -1 and the algorithm incurs cost 16T, while x* = 2 has zero cost. Hence R_x(T) = 16T, contradicting the O(sqrt(T)) bound of Theorem 6; Theorem 8 inherits the failure. Assumption 2 must be strengthened to require U (and hence X) convex and compact, and the proofs must be re-verified under that assumption.
  2. [Appendix II-A (proof of Lemma 5)] The proof of Lemma 5 establishes the reverse of the stated inequality. After defining x* and the corresponding input u*, the displayed chain begins with R(T) - R_u(T) = min_u sum_t f_t(x^u_t) - sum_t f_t(x*) and concludes that this quantity is at most 2 kappa L D^2 / gamma. That is an upper bound on R_x - R_u, whereas the lemma statement claims R_u - R_x <= 2 kappa L D^2 / gamma. The direction is essential because Theorem 8 uses Lemma 5 to pass from the R^g_x bound to the required R^g_u bound. As written, the proof of Theorem 8 is incomplete. The direction of the argument must be corrected and the final constant in Theorem 8 re-derived.
minor comments (5)
  1. [Appendix II-B, Lemma 11] The statement of Lemma 11 omits the factor D: Assumption 3 gives ||delta_t|| <= L D, so the correct bound is ||z_{t+tau} - z_t|| <= eta * tau * L * D. The proof itself uses L D, so this is only a statement typo, but it should be fixed.
  2. [Section IV-B, Eqs. (10) and (11)] The displayed definitions of BM(T) and Bu(T) use max over the policy/input class, but a best-in-hindsight comparator should minimize cumulative cost; the earlier definitions in Eqs. (5) and (6) correctly use min. The max/min signs in Eqs. (10) and (11) should be corrected to avoid confusion.
  3. [Proof of Theorem 8] The proof asserts that ||bar{x}_t|| < D because of BIBO stability of the nominal system (8b), but D was introduced as a bound on the original state x_t. Since x_t = bar{x}_t + x^d_t, BIBO stability of (8b) alone does not imply ||bar{x}_t|| <= D. This can be repaired by defining D to be a common bound on all relevant trajectories, but as written the invocation of Theorem 6 is not fully justified.
  4. [Algorithm 1, Line 2] Line 2 does not specify which u_t is chosen when B has a nontrivial kernel or when several inputs satisfy B u_t = (I-A) z_t. The text should state a fixed selection rule and explicitly require that the chosen u_t belongs to U.
  5. [Appendix I] The gradient notation for input-dependent costs appears to have a typo (the same partial derivative is displayed twice), and the set notation alternates between X_u and X^*_u. These should be made consistent.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the regret bounds are derived against independent benchmarks with no fitted parameters or self-citation chain.

full rationale

The paper's central claims are Theorem 6 and Theorem 8, bounding regret against the best-in-hindsight steady state and the best-in-hindsight constant input. These benchmarks are defined independently of Algorithm 1 (Eqs. (5) and (6) / Definition 4), so the target quantities are not built from the algorithm's own outputs. The step size eta = 2*gamma/(L*sqrt(T(1+4*kappa^2))) is chosen analytically from Assumptions 1-3 to minimize the proof's upper bound, not estimated from data, so no fitted parameter is later relabeled as a prediction. The proof of Theorem 6 uses standard OGD analysis for term (A) and a tracking-error bound for term (B), both of which are derived from the dynamics and Assumption 3 rather than assumed as the conclusion. Theorem 8 reduces the disturbed problem to the disturbance-free nominal problem through Proposition 7, and Proposition 7 follows exactly from the identity g_t(bar x_t)=f_t(x_t) and g_t(bar x^u_t)=f_t(x^u_t); this reduction is algebraic, not circular. Citations to prior work (Agarwal et al., Zinkevich, Hazan) supply standard OCO tools and comparison benchmarks, but these are not invoked as an unverified premise unique to this paper. The identified weaknesses, the unstated convexity of U needed for the projection Pi_X to be contractive in Lemma 11 and the apparent sign direction in the proof of Lemma 5, are correctness gaps, not circular reductions: even if those gaps are repaired or refuted, the derivation does not define its benchmark in terms of its predictor. Hence no pattern in the enumerated list applies.

Assumptions & free parameters 1 free parameters · 6 assumptions · 0 invented entities

The regret bounds rest on strong stability, boundedness, convexity, and smoothness of costs; the only unstated load-bearing item is convexity of U and X. The algorithm introduces no new physical entities; the nominal cost g_t is a derived object from linear superposition.

free parameters (1)
  • step size eta = 2 gamma / (L sqrt(T (1+4 kappa^2)))
    Chosen analytically to minimize the regret bound in Theorem 6; depends on horizon T and problem constants, not fitted to data. Included for completeness as a tunable algorithm parameter.
assumptions (6)
  • domain assumption A is strongly stable: A = H J H^{-1} with ||J|| <= 1 - gamma (Assumption 1).
    Central assumption enabling exponential convergence of states toward the target; the authors argue it is without much loss of generality for stabilizable systems with full observability.
  • domain assumption Input set U and disturbance set W are bounded (Assumption 2).
    Ensures the state remains bounded, defining the constant D used in the regret bounds.
  • domain assumption Cost functions are convex and have uniformly bounded gradients (Assumption 3).
    Gives the convexity inequality and the gradient norm bound LD used throughout the OGD analysis.
  • domain assumption Input set U (and hence steady-state manifold X) is convex.
    Never explicitly stated but required for the projection step in Algorithm 1 and for the contractivity of the projection in Lemma 11 and Theorem 6.
  • domain assumption Main results assume input-independent costs, f_t(x_t).
    Theorems 5, 6 and 8 only cover state-dependent costs; input-dependence is deferred to an appendix sketch.
  • standard math Standard properties of projections onto convex sets and the Neumann series for Schur stable matrices.
    Invoked in Lemma 10 and in the OGD analysis; standard results in convex analysis and linear algebra.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Revisiting Regret Benchmarks in Online Non-Stochastic Control." pith.science (2026). https://pith.science/paper/3PBBM3SJ

@misc{pith2026250416581,
  author       = {Pith},
  title        = {Pith review of: Revisiting Regret Benchmarks in Online Non-Stochastic Control},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3PBBM3SJ}},
  note         = {Machine review of arXiv:2504.16581}
}
read the original 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.

Figures

Figures reproduced from arXiv: 2504.16581 by the authors.

Figure 1
Figure 1. Results of numerical simulations regret consistent with the theoretical results of Agarwal et al. [6]. On the other hand, Heb rapidly outperforms this benchmark, gradually incurring negative regret as the horizon increases. VI. CONCLUSIONS AND FUTURE WORKS a) Conclusions: In this paper, we proposed a novel benchmark for evaluating online non-stochastic control meth￾ods: the performance of the best-in-hindsight fixed… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 12 canonical work pages

  1. [1]

    Online optimal control with affine constraints,

    Y . Li, S. Das, and N. Li, “Online optimal control with affine constraints,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35(10), pp. 8527–8537, 2021

    work page 2021

  2. [2]

    Online Optimization with Memory and Competitive Control,

    G. Shi, Y . Lin, S.-J. Chung, Y . Yue, and A. Wierman, “Online Optimization with Memory and Competitive Control,” in Advances in Neural Information Processing Systems , vol. 33, pp. 20636–20647, Curran Associates, Inc., 2020

    work page 2020

  3. [3]

    Online convex optimization for robust control of constrained dynamical systems,

    M. Nonhoff, E. Dall’Anese, and M. A. M ¨uller, “Online convex optimization for robust control of constrained dynamical systems,” Nov. 2024. arXiv:2401.04487 [eess]

    arXiv 2024

  4. [4]

    Online Nonstochastic Control with Convex Safety Constraints,

    N. Jiang, S. Hutchinson, and M. Alizadeh, “Online Nonstochastic Control with Convex Safety Constraints,” Jan. 2025. arXiv:2501.18039 [math]

    arXiv 2025

  5. [5]

    Introduction to Online Control,

    E. Hazan and K. Singh, “Introduction to Online Control,” Mar. 2025. arXiv:2211.09619 [cs]

    arXiv 2025

  6. [6]

    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 International Conference on Machine Learning , pp. 111–119, PMLR, May 2019. ISSN: 2640-3498

    work page 2019

  7. [7]

    Logarithmic Regret for Online Control,

    N. Agarwal, E. Hazan, and K. Singh, “Logarithmic Regret for Online Control,” in Advances in Neural Information Processing Systems , vol. 32, Curran Associates, Inc., 2019

    work page 2019

  8. [8]

    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 , pp. 3320–3436, PMLR, July 2020. ISSN: 2640- 3498

    work page 2020

Show all 15 references
  1. [9]

    Rate-Optimal Online Convex Optimization in Adaptive Linear Control,

    A. B. Cassel, A. Peled-Cohen, and T. Koren, “Rate-Optimal Online Convex Optimization in Adaptive Linear Control,”Advances in Neural Information Processing Systems , vol. 35, pp. 7410–7422, Dec. 2022

    2022

  2. [10]

    Bandit linear control,

    A. Cassel and T. Koren, “Bandit linear control,” Advances in Neural Information Processing Systems , vol. 33, pp. 8872–8882, 2020

    2020

  3. [11]

    Online Linear Quadratic Control,

    A. Cohen, A. Hasidim, T. Koren, N. Lazic, Y . Mansour, and K. Talwar, “Online Linear Quadratic Control,” in Proceedings of the 35th Inter- national Conference on Machine Learning , pp. 1029–1038, PMLR, July 2018. ISSN: 2640-3498

    2018

  4. [12]

    Online Optimal Control with Linear Dy- namics and Predictions: Algorithms and Regret Analysis,

    Y . Li, X. Chen, and N. Li, “Online Optimal Control with Linear Dy- namics and Predictions: Algorithms and Regret Analysis,” in Advances in Neural Information Processing Systems, vol. 32, Curran Associates, Inc., 2019

    2019

  5. [13]

    Hazan, Introduction to online convex optimization , ch

    E. Hazan, Introduction to online convex optimization , ch. 5. The MIT Press, 2 ed., 2022

    2022

  6. [14]

    Online convex programming and generalized in- finitesimal gradient ascent,

    M. Zinkevich, “Online convex programming and generalized in- finitesimal gradient ascent,” in Proceedings of the Twentieth Interna- tional Conference on International Conference on Machine Learning , ICML’03, (Washington, DC, USA), pp. 928–935, AAAI Press, Aug. 2003

    2003

  7. [15]

    Online learning for adversaries with memory: Price of past mistakes,

    O. Anava, E. Hazan, and S. Mannor, “Online learning for adversaries with memory: Price of past mistakes,” in Advances in Neural Infor- mation Processing Systems , vol. 2015-January, 2015. APPENDIX I EXTENSIONS TO INPUT DEPENDENT COSTS We briefly sketch how our approach can be ...

    2015

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.