{"id":"9b5dc9e6-d37f-43f8-944c-f0bc1115aff2","arxiv_id":"2506.12596","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Bounded perturbations of size O(sqrt(epsilon)) still allow derivative-free LQR policy optimization to reach an epsilon-optimal policy with high probability, with sample complexity O(1/epsilon^2 log(1/epsilon)) (one-point) or O(1/epsilon log(1/epsilon)) (two-point).","lead":"This paper proves that derivative-free (cost-sampling) policy optimization for linear quadratic regulator problems still converges near the optimal controller when the cost measurements are corrupted by small perturbations. It gives explicit bounds on tolerable noise and on the number of samples needed to reach a given accuracy.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4's gradient-norm bound is not implied by the displayed inequality; the constant 2/θ0 can be too small when θ0>3, so Theorem 1's proof is incomplete as written.","rationale":"The paper's strongest claim, Theorem 1, asserts that derivative-free LQR methods converge to an ε-neighborhood of the optimal policy under perturbations bounded by δ=O(√ε). The proof chain is Lemma 4, Lemma 5, Theorem 1, and Lemma 4 is where the bias and perturbation terms are controlled. The reader identified the unsupported gradient-norm bound in Lemma 4 as the weakest assumption; I agree, and the precise failure condition is θ0>3. Because θ0 = min{1/(2φ0), ρ0/λ0} can be made arbitrarily large by scaling the cost matrices Q and R, this is not a degenerate edge case but a real gap in the stated proof. I do not see a more load-bearing concern: the variance bounds, stopping-time argument, and parameter scalings are otherwise internally consistent, and the theorem gives the expected one-point O(1/ε² log(1/ε)) and two-point O(1/ε log(1/ε)) sample complexities. The issue is a proof gap rather than a demonstrated false claim, since replacing 2/θ0 with the correct constant changes only constant factors in the bounds on r and δ and should preserve the asymptotic perturbation bound δ=O(√ε). Thus the appropriate verdict remains CONDITIONAL, matching the reader's assessment; no further adjustment is needed.","tokens_in":12343,"tokens_out":19289,"duration_ms":222107,"concrete_test":"Re-derive Lemma 4(ii) replacing the asserted bound with the valid consequence ‖∇J(K)‖ ≤ sqrt(4/(3θ0))√Δ, and check whether the recurrence E[Δ_{s+1}|F_s] ≤ (1−ημ/4)Δ_s + η²φ0g2 + ημϵ/120 still holds after absorbing constants into the conditions on r and δ. A simpler algebraic check: for θ0=4, the displayed inequality is consistent with ‖∇J‖=0.6 and Δ=1, while the claimed bound requires 0.6 ≤ 0.5, so the step is not a valid algebraic consequence of the preceding line.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central convergence theorem rests entirely on Lemma 4(ii). In the proof of Lemma 4, the authors establish (θ0−φ0θ0²/2)‖∇J(K)‖² ≤ Δ and then replace the resulting coefficient ((θ0−φ0θ0²/2))^{-1/2} with 2/θ0. Since θ0 ≤ 1/(2φ0), the displayed inequality only yields ‖∇J(K)‖ ≤ sqrt(4/(3θ0))√Δ. The claimed bound ‖∇J(K)‖ ≤ (2/θ0)√Δ is valid only for θ0 ≤ 3; for θ0 > 3 it is stronger than what the preceding line proves and can be false. Such parameter values are within the theorem's scope: scaling all costs (Q,R) by a small positive constant c scales φ0, λ0, and Δ linearly and leaves ρ0 unchanged, so θ0 scales as 1/c and can be made arbitrarily large while Assumptions 1 and 2 still hold. The subsequent Young-inequality term 4η(φ0r+δ)²/(μθ0²) and the δ,r conditions in Lemma 4(ii) depend on this coefficient, so the proof of Theorem 1 does not go through as written. The gap appears patchable by carrying the correct coefficient through Lemma 4(ii) and adjusting the constant factors, but that repair must be performed before the theorem is accepted.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper considers an infinite-horizon LQR problem with unknown dynamics and analyzes the robustness of derivative-free (zero-order) policy optimization when the cost evaluations used to estimate gradients are perturbed. The authors propose a perturbed one-point and two-point estimator scheme, and their main result (Theorem 1) states that if the stepsize, smoothing radius, and perturbation magnitude satisfy explicit bounds, then the algorithm returns a policy whose cost gap to the optimum is below any prescribed tolerance epsilon with probability at least 3/4. They also provide a rollout length for finite-horizon cost truncation (Corollary 1) and a table summarizing the perturbation tolerance and sample complexity. The analysis builds on local Lipschitz and smoothness properties of the LQR cost, the Polyak-Lojasiewicz inequality, a stopping-time argument to keep iterates in the stabilizing region, and a supermartingale concentration argument.","tokens_in":12606,"tokens_out":16373,"duration_ms":187553,"significance":"If the proof gap identified below is repaired, the paper would provide a clean robustness guarantee for derivative-free LQR: small cost perturbations do not destroy convergence to any pre-specified accuracy, with explicit order-sqrt(epsilon) tolerance on the perturbations. This goes beyond existing small-disturbance ISS results for exact gradient flows by treating the biased, high-variance zero-order estimators. The explicit formulas for the smoothing radius, stepsize, perturbation bound, and sample complexity are a strength, as is the inclusion of a rollout-length analysis for the practically relevant case of truncated infinite-horizon costs. The numerical experiments corroborate the predicted sqrt(epsilon) scaling of the perturbation bound. The claimed result is plausible and the proof strategy is a natural extension of prior work on derivative-free LQR, but the correctness of the main theorem currently rests on an unsupported gradient-norm bound in Lemma 4.","major_comments":[{"comment":"The proof of Lemma 4 asserts the bound ||grad J(K_s)||_F <= (2/theta0) sqrt(Delta_s) after deriving (theta0 - phi0 theta0^2/2)||grad J||^2 <= Delta_s. Since theta0 <= 1/(2 phi0), the displayed inequality implies only ||grad J|| <= sqrt(1/(theta0 - phi0 theta0^2/2)) sqrt(Delta_s) <= (2/sqrt(3 theta0)) sqrt(Delta_s). The claimed coefficient 2/theta0 is smaller than 2/sqrt(3 theta0) when theta0 > 3, and such parameter values are within the theorem's scope: scaling Q and R by a small positive constant c scales phi0, lambda0, and Delta linearly and leaves rho0 unchanged, so theta0 scales as 1/c and can be made arbitrarily large while Assumptions 1 and 2 remain satisfied. For a quadratic cost with small curvature the claimed bound can even contradict the true gradient norm. Because this gradient bound is used in the Young-inequality step that produces (12) and in the delta and r conditions of Lemma 4(ii), the proof of Theorem 1 does not go through as written. The gap appears repairable by carrying the exact factor sqrt(1/(theta0 - phi0 theta0^2/2)) through the subsequent algebra and re-deriving the constants in Lemma 4(ii) and Theorem 1, but this repair must be performed explicitly. Relatedly, the proof switches from 'let theta be a scalar such that theta ||grad J|| <= rho0' to setting theta = theta0 without showing that theta0 has this property; this can be fixed by noting that ||grad J|| <= lambda0 (from the Lipschitz bound in Lemma 1) and theta0 <= rho0/lambda0, but the argument should be stated.","section":"Section III-B, Lemma 4"}],"minor_comments":[{"comment":"The display 'eta(phi0 r + delta) 2/theta0 Delta_s^{1/2}' is ambiguous; it should be written as eta (phi0 r + delta) (2/theta0) sqrt(Delta_s) to make the Young-inequality step readable.","section":"Section III-B, Lemma 4 proof"},{"comment":"The proof refers to '(13)' for the rollout-length condition, but no equation is numbered in the text; the inequality appears only inside the proof. Please number the displayed inequalities or cite them by their location.","section":"Corollary 1"},{"comment":"The stated rollout-length condition involves the random quantity ||x0||_2^2. Since Assumption 2 provides ||x0||_2^2 <= C_m almost surely, the statement should use C_m (or explicitly state that the bound holds conditionally on the realized initial state with probability 1) so that T_delta is a deterministic function of the model parameters.","section":"Corollary 1"}],"recommendation":"major_revision","confidential_remarks":"The main technical gap in Lemma 4 is localized and appears fixable by carrying the correct gradient-norm coefficient through the derivation and adjusting the constants in Lemma 4(ii) and Theorem 1. I do not see evidence of circularity or circular fitting in the argument; the perturbation results are derived from the PL inequality and smoothing lemmas rather than reverse-engineered. The paper is an incremental but potentially valuable contribution to the model-free LQR literature, fitting the journal's scope. I would support acceptance after the repair is carried out and the resulting constants are verified."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a legitimate extension of the derivative-free LQR literature — explicit perturbation budgets, a clean one-point vs two-point complexity comparison, and a rollout-length corollary that makes the perturbation model concrete. The main theorem is plausible and the proof architecture is standard. But Lemma 4 contains a genuinely unsupported bound, and as written Theorem 1 does not go through.\n\nWhat's new: the paper adds a bounded perturbation term to the derivative-free algorithm of Malik et al. and derives explicit δ bounds that scale like √ε, plus the sample complexity comparison (one-point O(1/ε² log), two-point O(1/ε log)). That is useful, and the corollary connecting rollout length to perturbation size is a nice touch. The numerical figures are simple but consistent with the claims.\n\nThe soft spot is in Lemma 4. From the descent inequality the authors obtain (θ0 − φ0θ0²/2)‖∇J‖² ≤ Δ, and then state that ‖∇J‖ ≤ (2/θ0)√Δ. Given θ0 ≤ 1/(2φ0), the displayed inequality only yields ‖∇J‖ ≤ sqrt(4/(3θ0))√Δ, which is larger than (2/θ0)√Δ whenever θ0 > 3. That regime is reachable by scaling costs, so it is not a degenerate case. The subsequent Young inequality and the δ, r conditions in Lemma 4(ii) depend on that coefficient, so the proof of Theorem 1 is incomplete. The gap is patchable — carry the correct constant through and the qualitative conclusions (δ ~ √ε, the complexity table) survive with different constants. But as written, the central claim is not proven.\n\nAlso worth noting: no code or data, and the numerics are illustrative. Not a serious issue for a math.OC paper, but it is a limitation.\n\nWho this is for: researchers working on model-free policy optimization for LQR who need robustness guarantees. The complexity table and perturbation bounds are the takeaway, once the constant issue is fixed. It deserves a serious referee; an editor should send it out, and the referee should ask for the repair in Lemma 4.","headline":"Genuinely useful perturbation bounds for derivative-free LQR, but Lemma 4's gradient-norm bound is unproved and Theorem 1 needs a repair before it is proven.","tokens_in":13149,"tokens_out":5111,"would_cite":false,"duration_ms":51588,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C56"],"pacs":[],"model":"deepseek-v4-flash","headline":"Derivative-free LQR policy search converges near-optimally even with noisy cost samples, provided the perturbation stays below an explicit bound of order the square root of the target error; the paper also gives stepsize, rollout length…","keywords":["derivative-free methods","policy optimization","linear quadratic regulator","robustness","perturbation analysis","sample complexity","zero-order methods"],"falsifier":"Choose a concrete LQR instance, compute the true gradient $\\nabla J(K)$ and the suboptimality gap $J(K)-J(K_*)$ for many stabilizing policies $K$ sampled densely inside $\\mathcal{G}_0$, and test whether $\\|\\nabla J(K)\\|_F \\le (2/\\theta_0)\\sqrt{J(K)-J(K_*)}$ holds with $\\theta_0 = \\min\\{1/(2\\phi_0), \\rho_0/\\lambda_0\\}$; a single counterexample would invalidate Lemma 4 and hence Theorem 1.","tokens_in":12133,"feed_emoji":"🎛️","tokens_out":9693,"duration_ms":106973,"temperature":0.7,"pith_summary":"This paper establishes a robustness result for derivative-free (zero-order) policy optimization in the infinite-horizon linear quadratic regulator (LQR) problem. When the cost evaluations used to estimate policy gradients are perturbed—by rollout truncation, measurement noise, or approximation error—the paper shows that the perturbed stochastic gradient update still converges to any pre-specified neighborhood of the optimal policy, provided the perturbations are at most on the order of the square root of the target suboptimality. It gives explicit choices of stepsize, smoothing radius, and rollout length, and states the resulting sample complexity for both one-point and two-point gradient estimators. If the claim is right, practitioners using model-free LQR can tolerate small cost inaccuracies without losing convergence guarantees.","feed_headline":"Small cost noise still allows near-optimal LQR policies","feed_subtitle":"Explicit bounds on perturbation, stepsize, and rollout length say when a zero-order policy search keeps converging.","key_machinery":"The mechanism is a biased stochastic-gradient analysis of the perturbed update $K_{s+1}=K_s-\\eta G(K_s)+\\eta E_s$, where $G(K_s)$ is a zeroth-order gradient estimate built from either one or two sampled cost values along a random direction. The argument rests on three ingredients: the Polyak–Łojasiewicz inequality $\\mu(J(K)-J(K_*))\\le \\|\\nabla J(K)\\|_F^2$ for the LQR cost, a smoothing lemma showing the estimator's expected gradient is the gradient of the smoothed cost with bias bounded by $\\phi_0 r$, and variance bounds for the estimators over the sublevel set $\\mathcal{G}_0$. These are combined through a supermartingale argument to show that, with high probability, the iterates stay inside $\\mathcal{G}_0$ while the expected suboptimality gap contracts geometrically down to a floor set by $r$ and $\\delta$.","core_discovery":"The central discovery is a convergence-with-high-probability theorem: for any error tolerance $\\epsilon>0$, if the perturbation in each iterate satisfies $\\|E_s\\|_F \\le \\delta$ with $\\delta$ bounded by a constant times $\\sqrt{\\epsilon}$, and the stepsize $\\eta$ and smoothing radius $r$ are chosen within explicit ranges, then Algorithm 1 returns a policy $K_{T_s}$ with $J(K_{T_s})-J(K_*)<\\epsilon$ with probability at least $3/4$. The same guarantee extends to the practically important case where the infinite-horizon cost is replaced by a finite-horizon approximation, with a corollary giving a sufficient rollout length $T_\\delta$. The theorem covers both the one-point estimator (6) and the two-point estimator (7), with the two-point version achieving a sample complexity of $O(\\frac{1}{\\epsilon}\\log\\frac{1}{\\epsilon})$ versus $O(\\frac{1}{\\epsilon^2}\\log\\frac{1}{\\epsilon})$ for the one-point version.","pith_inferences":["The $\\sqrt{\\epsilon}$ scaling of the admissible perturbation implies an information-theoretic noise floor: in this setting, no implementation can tolerate a fixed absolute level of cost noise while driving the suboptimality gap to zero; the noise must decay as the target shrinks.","The same biased-stochastic-gradient framework may extend to other control problems whose cost satisfies the PL condition and whose zeroth-order estimators have controlled bias and variance, such as continuous-time LQR or policy optimization with risk constraints; the paper only treats the discrete-time LQR case.","A direct numerical check of the load-bearing inequality $\\|\\nabla J(K)\\|_F \\le (2/\\theta_0)\\sqrt{J(K)-J(K_*)}$ over the sublevel set $\\mathcal{G}_0$ would empirically validate the proof's crucial step; the paper does not report such a check."],"forward_implications":["If the theorem is correct, an implementation that truncates infinite-horizon costs to finite-horizon rollouts can achieve any desired $\\epsilon$ accuracy, as long as the rollout length $T_\\delta$ meets the explicit logarithmic bound in Corollary 1.","The two-point gradient estimator allows a stepsize of order $\\epsilon$ and yields sample complexity $O(\\frac{1}{\\epsilon}\\log\\frac{1}{\\epsilon})$, so it is preferable when extra cost evaluations are affordable.","The allowable perturbation magnitude $\\delta$ scales as $\\Theta(\\sqrt{\\epsilon})$; therefore, reducing the target suboptimality gap by a factor of four requires roughly halving the maximum tolerable noise.","The explicit parameter choices give practitioners a concrete tuning recipe for stepsize, smoothing radius, and perturbation tolerance for a given target accuracy $\\epsilon$."],"supporting_citations":[{"why":"Supplies the PL inequality, smoothness, and local bounds for the LQR cost (Lemma 1) that the entire convergence proof builds on.","marker":"[21]"},{"why":"Provides the variance and magnitude bounds for one-point and two-point derivative-free estimators (Lemma 2), used to pick stepsize and sample complexity.","marker":"[25]"},{"why":"Gives the smoothing lemma relating the expected zero-order estimator to the gradient of the smoothed cost (Lemma 3(i)) and the bias bound in Lemma 3(ii).","marker":"[35]"},{"why":"Supplies the two-point estimator smoothing properties (also cited for Lemma 3), supporting the two-point convergence theorem.","marker":"[36]"}],"fun_headline_variants":["Zero-order LQR handles small perturbations","Derivative-free LQR stays near-optimal under noise","Small cost noise doesn't derail LQR policy search","Explicit perturbation bounds for robust LQR learning","Perturbed zero-order methods converge for LQR"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof's key step is an inequality that bounds the norm of the cost gradient by a constant times the square root of the suboptimality gap, used in Lemma 4 to control the cross-term between the true gradient and the smoothed estimator; this inequality is asserted without derivation, and if it fails for some stabilizing policies in the sublevel set, the geometric contraction argument no longer goes through.","fun_headline_variants_meta":{"raw":{"variants":["Zero-order LQR handles small perturbations","Derivative-free LQR stays near-optimal under noise","Small cost noise doesn't derail LQR policy search","Explicit perturbation bounds for robust LQR learning","Perturbed zero-order methods converge for LQR"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000179,"raw_usage":{"total_tokens":1260,"prompt_tokens":868,"completion_tokens":392,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":484,"completion_tokens_details":{"reasoning_tokens":318}},"tokens_in":484,"tokens_out":392,"duration_ms":5075,"temperature":1.0,"reasoning_tokens":318,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T00:47:23.326807+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Choose a concrete LQR instance, compute the true gradient $\\nabla J(K)$ and the suboptimality gap $J(K)-J(K_*)$ for many stabilizing policies $K$ sampled densely inside $\\mathcal{G}_0$, and test whether $\\|\\nabla J(K)\\|_F \\le (2/\\theta_0)\\sqrt{J(K)-J(K_*)}$ holds with $\\theta_0 = \\min\\{1/(2\\phi_0), \\rho_0/\\lambda_0\\}$; a single counterexample would invalidate Lemma 4 and hence Theorem 1.","supporting_citations":[],"review_version":1}