{"id":"d6e4b9be-e2bd-4f9d-bf8d-716e411c6b85","arxiv_id":"2504.16581","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"An online projected-gradient controller achieves O(sqrt(T)) regret against the best-in-hindsight constant input for adversarial convex costs and disturbances.","lead":"This paper proposes a new benchmark for online control: how well an algorithm performs compared to the best fixed input, rather than the best linear feedback policy. It gives a simple online gradient-descent-style algorithm with sublinear regret on that benchmark and tests it numerically.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Boundedness of U does not imply convexity of X, and the projection step in Algorithm 1 requires it; a two-point input set already yields linear regret, so Theorems 6 and 8 are false as stated without an explicit convexity/compactness assumption.","rationale":"The reader's weakest_assumption correctly identifies the missing convexity of U and therefore of X. My stress-test confirms that this is not just a cosmetic gap: with a bounded but nonconvex U, Algorithm 1's projection step is not nonexpansive, Lemma 11 fails, and the regret can be linear. The counterexample above is a minimal instance satisfying every stated assumption except convexity and shows the theorem false as written. Because the intended result is almost certainly valid under the standard addition of 'U compact and convex' to Assumption 2, and because the proof structure is otherwise coherent, the appropriate disposition remains conditional rather than outright rejection. I therefore keep the reader's verdict unchanged.","tokens_in":11283,"tokens_out":24824,"duration_ms":253616,"concrete_test":"Check the counterexample analytically: set A = 1/2, B = 1, U = {-1,1}, x_1 = z_1 = -2, f_t(x) = (x-2)^2, gamma = 1/2, kappa = 1, L = 4, and eta = 1/(4 sqrt(5T)) as in Theorem 6. Since x_t = -2 and delta_t = -8, the pre-projection point is -2 + 2/sqrt(5T), which is strictly closer to -2 than to 2 for every t; hence Pi_X keeps z_t = -2, u_t = -1, and the cumulative cost is 16T against a benchmark cost of 0 at x* = 2. If this computation yields R_x(T) = 16T rather than O(sqrt(T)), the boundedness assumption without convexity is insufficient and the theorem must be amended.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Assumption 2 only states that U and W are bounded. Definition 4 defines X = {(I-A)^{-1}Bu : u in U}, an affine image of U, so X is convex exactly when U is convex; X also needs U closed for the projection Pi_X to be well-defined. Lemma 11 and the proof of Theorem 6 both invoke the contractivity/nonexpansiveness of Pi_X, a property that fails for nonconvex X in a way that breaks the algorithm itself, not merely the proof. A concrete counterexample is: scalar system A = 1/2, B = 1, U = {-1,1}, so X = {-2,2}; costs f_t(x) = (x-2)^2; initial state and target x_1 = z_1 = -2; parameters gamma = 1/2, kappa = 1, L = 4, and eta = 1/(4 sqrt(5T)) as prescribed by Theorem 6. Because the state stays at -2, delta_t = -8, and z_t - eta*delta_t = -2 + 2/sqrt(5T), which lies in (-2,0) for every T >= 1; the projection onto {-2,2} therefore returns -2 at every step. The algorithm thus keeps u_t = -1, incurs cost 16 per step, while the best-in-hindsight steady state x* = 2 incurs cost 0, giving R_x(T) = 16T, contradicting the O(sqrt(T)) bound of Theorem 6, and Theorem 8 inherits the failure. The paper never states convexity of U, so the central claim is false as stated; adding 'U convex and compact' to Assumption 2 is necessary and, together with a corrected sign in the Lemma 5 proof, likely sufficient.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":11692,"tokens_out":16446,"duration_ms":160800,"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":[{"comment":"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.","section":"Section II-A (Assumption 2), Definition 4, Lemma 11, Theorem 6"},{"comment":"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.","section":"Appendix II-A (proof of Lemma 5)"}],"minor_comments":[{"comment":"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.","section":"Appendix II-B, Lemma 11"},{"comment":"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.","section":"Section IV-B, Eqs. (10) and (11)"},{"comment":"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.","section":"Proof of Theorem 8"},{"comment":"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.","section":"Algorithm 1, Line 2"},{"comment":"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.","section":"Appendix I"}],"recommendation":"major_revision","confidential_remarks":"The stress-test concern is valid and central: without a convexity/compactness assumption on U, the projection step in Algorithm 1 is not well behaved and the main regret bounds are false, as the two-point counterexample shows. The sign error in the proof of Lemma 5 compounds the problem for Theorem 8. Both issues seem repairable within the scope of the paper, so I recommend major revision rather than rejection. The conceptual contribution and the superposition argument are strong enough to be worth pursuing once the assumptions and proofs are corrected."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know before you read it. The fixed-input benchmark is a good idea—it connects online non-stochastic control to ordinary OCO—and the algorithm is a clean OGD-on-target-states scheme. But the central theorems, as written, are false. Assumption 2 only says U and W are bounded, yet Algorithm 1 projects onto X, the affine image of U, and the analysis needs X convex. The stress-test counterexample is correct: a scalar system with A=1/2, B=1, U={-1,1}, and costs (x-2)^2 gives constant state at -2 and regret 16T, contradicting the O(sqrt(T)) bound. Add \"U convex and compact\" to Assumption 2 (or directly assume X convex) and the proofs should go through.\n\nWhat is genuinely new: the benchmark itself, the disturbance reduction in Proposition 7, and the comparison with the Agarwal et al. DAC benchmark. The algorithm is a straightforward OGD application, but that is not a vice; it is simple and likely to be adopted. The simulations are honest and show a real difference between the benchmarks. The regret bound is derived without fitted parameters, and the step size is chosen analytically, so the derivation is self-contained.\n\nSoft spots, in proportion: (1) The missing convexity is a real flaw in the stated theorems, not a cosmetic issue—your counterexample proves linear regret for a valid instance. (2) Lemma 5's proof proves a bound on R_x - R_u, while the lemma statement needs R_u - R_x. The direction can be repaired by taking the minimizer u* and using its steady state, but as written the proof is wrong. (3) Minor: simulations would be stronger with error bars, and there are small typos (e.g., \"AGP series\").\n\nWho this is for: people working on online control, especially those bridging control theory and OCO. The fixed-input benchmark will likely be cited and reused. I would not desk-reject this; send it to a serious referee. It needs major revision—mainly the convexity assumption and the Lemma 5 direction—but the core idea is sound and the repair is straightforward.","headline":"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.","tokens_in":12168,"tokens_out":5232,"would_cite":true,"duration_ms":50918,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","93C55","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"An online projection rule on steady states achieves $O(\\sqrt{T})$ regret against the best fixed input.","keywords":["online non-stochastic control","regret benchmarks","constant input benchmark","online projected gradient descent","steady-state manifold","adversarial disturbances","convex costs","linear dynamical systems"],"falsifier":"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.","tokens_in":11122,"feed_emoji":"⚙️","tokens_out":9559,"duration_ms":86404,"temperature":0.7,"pith_summary":"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.","feed_headline":"A simple control rule matches the best fixed input up to O(sqrt T)","feed_subtitle":"Adversarial convex costs and disturbances cost only a constant factor over memoryless online learning.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"defines the original online non-stochastic control problem and the disturbance-action controller benchmark this paper recasts","marker":"[6]"},{"why":"supplies the standard online gradient descent regret analysis used to bound the OGD term in Theorem 6","marker":"[13]"},{"why":"provides the baseline OCO regret bound that motivates the constant-factor interpretation of the dynamics penalty","marker":"[14]"},{"why":"supplies the quantitative strong-stability facts and the online LQR context for the benchmark comparison","marker":"[11]"},{"why":"provides the online convex optimization with memory framework used to position the horizon-free method against the DAC approach","marker":"[15]"}],"fun_headline_variants":["Better benchmark: best fixed input in control","Fixed-input benchmark yields sublinear control regret","Matches best fixed input with O(sqrt T) regret","Sublinear regret against best fixed input","Control regret redefined: fixed inputs instead of linear"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Better benchmark: best fixed input in control","Fixed-input benchmark yields sublinear control regret","Matches best fixed input with O(sqrt T) regret","Sublinear regret against best fixed input","Control regret redefined: fixed inputs instead of linear"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001182,"raw_usage":{"total_tokens":4896,"prompt_tokens":974,"completion_tokens":3922,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":590,"completion_tokens_details":{"reasoning_tokens":3852}},"tokens_in":590,"tokens_out":3922,"duration_ms":24461,"temperature":1.0,"reasoning_tokens":3852,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:00:49.362267+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Online Control with Adversarial Disturbances,","cited_arxiv_id":null,"evidence_quote":"defines the original online non-stochastic control problem and the disturbance-action controller benchmark this paper recasts"},{"cited_title":"Hazan, Introduction to online convex optimization , ch","cited_arxiv_id":null,"evidence_quote":"supplies the standard online gradient descent regret analysis used to bound the OGD term in Theorem 6"},{"cited_title":"Online convex programming and generalized in- finitesimal gradient ascent,","cited_arxiv_id":null,"evidence_quote":"provides the baseline OCO regret bound that motivates the constant-factor interpretation of the dynamics penalty"},{"cited_title":"Online Linear Quadratic Control,","cited_arxiv_id":null,"evidence_quote":"supplies the quantitative strong-stability facts and the online LQR context for the benchmark comparison"},{"cited_title":"Online learning for adversaries with memory: Price of past mistakes,","cited_arxiv_id":null,"evidence_quote":"provides the online convex optimization with memory framework used to position the horizon-free method against the DAC approach"}],"review_version":1}