REVIEW 1 major objections 3 minor 36 references
On the Robustness of Derivative-free Methods for Linear Quadratic Regulator
T0 review · 1 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read 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…
desk verdict 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. 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
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$.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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$.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (1)
- [Section III-B, Lemma 4] 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.
minor comments (3)
- [Section III-B, Lemma 4 proof] 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.
- [Corollary 1] 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.
- [Corollary 1] 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.
Circularity Check
No circular derivation: Theorem 1 is built on external smoothness/PL and derivative-free estimation lemmas; the contested Lemma 4 coefficient step is a proof gap, not circularity.
full rationale
The paper's central claim is that, under sufficiently small perturbations, the perturbed derivative-free algorithm converges to an epsilon-neighborhood of the optimal LQR policy. The derivation chain is: Lemma 1 (local Lipschitz properties and Polyak-Lojasiewicz condition) is imported from Fazel et al. [21] and Malik et al. [25]; Lemma 2 (bounds on the variance and magnitude of the one-point and two-point gradient estimators) is imported from Malik et al. [25, Corollaries 9 and 10]; Lemma 3 (smoothed gradient identity and bias bound) is imported from Ghadimi-Lan [35] and Shamir [36]. These are external, parameter-free supporting results, not outputs of the present paper. Lemma 4 then combines these lemmas with an assumed deterministic bound on the perturbation, ||E_s||_F <= delta, to obtain a one-step expected cost decrease; delta is an input to the statement, not a fitted parameter. Theorem 1 substitutes the estimator bounds from Lemma 2 into Lemma 5 and derives the convergence guarantee with explicit conditions on eta, r, delta, and T_s. At no point is the desired conclusion J(K_Ts) - J(K*) < epsilon used as an assumption, nor is any parameter fitted to the data or to the target value. The skeptical reader's concern about Lemma 4 is a genuine mathematical proof gap: the displayed inequality (theta0 - phi0 theta0^2/2)||nabla J(K)||_F^2 <= Delta does not, by itself, justify the replacement coefficient (2/theta0) for all admissible theta0, and this may require a repair. However, that is a correctness or rigor issue, not circularity, because it does not make the theorem's conclusion equivalent to its inputs. The self-citations appearing in the introduction, such as references [28], [30], and [31] by co-authors Jiang and Malikopoulos, are motivational and contextual; they are not used to establish Lemmas 2, 3, 4, 5, or Theorem 1. Therefore the paper's derivation is not circular, and the appropriate circularity score is low.
Assumptions & free parameters
assumptions (6)
- domain assumption Assumption 1: (A,B) stabilizable, Q in S_n^+, R in S_m^{++}, (A,Q^{1/2}) detectable.
- domain assumption Assumption 2: initial state v~D satisfies E[v]=0, E[vv^T]=I_n, and ||v||_2^2 <= C_m a.s.
- standard math Lemma 1: J is locally Lipschitz, has locally Lipschitz gradient, and satisfies the PL inequality mu(J-J*) <= ||nabla J||^2 over the sublevel set.
- standard math Lemma 2: Uniform bounds g_infty and g_2 for one-point and two-point cost-based gradient estimators, from [25, Corollaries 9 and 10].
- standard math Lemma 3: E[G(K)] = nabla J_r(K) and ||nabla J_r(K)-nabla J(K)|| <= phi0 r for the smoothed cost.
- domain assumption Existence of gamma in (0,1) and M>0 such that ||x_t||^2 <= M gamma^{2t} ||x0||^2 for all K in G0.
Cite this review
Pith. "Pith review of On the Robustness of Derivative-free Methods for Linear Quadratic Regulator." pith.science (2026). https://pith.science/paper/DSBT6BJW
@misc{pith2026250612596,
author = {Pith},
title = {Pith review of: On the Robustness of Derivative-free Methods for Linear Quadratic Regulator},
year = {2026},
howpublished = {\url{https://pith.science/paper/DSBT6BJW}},
note = {Machine review of arXiv:2506.12596}
}
read the original abstract
Policy optimization has drawn increasing attention in reinforcement learning, particularly in the context of derivative-free methods for linear quadratic regulator (LQR) problems with unknown dynamics. This paper focuses on characterizing the robustness of derivative-free methods for solving an infinite-horizon LQR problem. To be specific, we estimate policy gradients by cost values, and study the effect of perturbations on the estimations, where the perturbations may arise from function approximations, measurement noises, etc. We show that under sufficiently small perturbations, the derivative-free methods converge to any pre-specified neighborhood of the optimal policy. Furthermore, we establish explicit bounds on the perturbations, and provide the sample complexity for the perturbed derivative-free methods.
Figures
Reference graph
Works this paper leans on
-
[1]
R. S. Sutton and A. G. Barto,Reinforcement learning: An introduction. MIT press Cambridge, 2018
work page 2018
-
[2]
Optimal and autonomous control using reinforcement learning: A survey,
B. Kiumarsi, K. G. Vamvoudakis, H. Modares, and F. L. Lewis, “Optimal and autonomous control using reinforcement learning: A survey,”IEEE Transactions on Neural Networks and Learning Systems, vol. 29, no. 6, pp. 2042–2062, 2017
work page 2017
-
[3]
Real- time self-learning optimization of diesel engine calibration,
A. A. Malikopoulos, D. N. Assanis, and P. Y . Papalambros, “Real- time self-learning optimization of diesel engine calibration,”Journal of Engineering for Gas Turbines and Power, vol. 131, no. 2, 2009
work page 2009
-
[4]
Convergence properties of a computational learn- ing model for unknown Markov chains,
A. A. Malikopoulos, “Convergence properties of a computational learn- ing model for unknown Markov chains,”J. Dyn. Sys., Meas., Control, vol. 131, no. 4, pp. 041 011–7, 2009
work page 2009
-
[5]
——,Real-Time, Self-Learning Identification and Stochastic Optimal Control of Advanced Powertrain Systems. ProQuest, 2011
work page 2011
-
[6]
S. K. S. Nakka, B. Chalaki, and A. A. Malikopoulos, “A multi-agent deep reinforcement learning coordination framework for connected and automated vehicles at merging roadways,” in2022 American control conference (ACC). IEEE, 2022, pp. 3297–3302
work page 2022
-
[7]
F. L. Lewis, D. Vrabie, and V . L. Syrmos,Optimal control. John Wiley & Sons, 2012
2012
-
[8]
Reinforcement learning-based linear quadratic regulation of continuous-time systems using dynamic output feedback,
S. A. A. Rizvi and Z. Lin, “Reinforcement learning-based linear quadratic regulation of continuous-time systems using dynamic output feedback,”IEEE Transactions on Cybernetics, vol. 50, no. 11, pp. 4670– 4679, 2019
2019
Show all 36 references
-
[9]
Jiang and Z.-P
Y . Jiang and Z.-P. Jiang,Robust adaptive dynamic programming. Wiley- IEEE Press, 2017
2017
-
[10]
Reinforcement learning and feedback control: Using natural decision methods to design optimal adaptive controllers,
F. L. Lewis, D. Vrabie, and K. G. Vamvoudakis, “Reinforcement learning and feedback control: Using natural decision methods to design optimal adaptive controllers,”IEEE Control Systems Magazine, vol. 32, no. 6, pp. 76–105, 2012
2012
-
[11]
A decentralized energy-optimal control framework for connected automated vehicles at signal-free intersections,
A. A. Malikopoulos, C. G. Cassandras, and Y . J. Zhang, “A decentralized energy-optimal control framework for connected automated vehicles at signal-free intersections,”Automatica, vol. 93, pp. 244–256, 2018
2018
-
[12]
Separation of learning and control for cyber- physical systems,
A. A. Malikopoulos, “Separation of learning and control for cyber- physical systems,”Automatica, vol. 151, no. 110912, 2023
2023
-
[13]
Combining learning and control in linear systems,
——, “Combining learning and control in linear systems,”European Journal of Control, vol. 80, no. Part A, p. 101043, 2024
2024
-
[14]
Policy gradi- ent methods for reinforcement learning with function approximation,
R. S. Sutton, D. McAllester, S. Singh, and Y . Mansour, “Policy gradi- ent methods for reinforcement learning with function approximation,” Advances in Neural Information Processing Systems, vol. 12, 1999
1999
-
[15]
A survey of actor-critic reinforcement learning: Standard and natural policy gra- dients,
I. Grondman, L. Busoniu, G. A. Lopes, and R. Babuska, “A survey of actor-critic reinforcement learning: Standard and natural policy gra- dients,”IEEE Transactions on Systems, Man, and Cybernetics, part C (applications and reviews), vol. 42, no. 6, pp. 1291–1307, 2012
2012
-
[16]
Trust region policy optimization,
J. Schulman, S. Levine, P. Abbeel, M. Jordan, and P. Moritz, “Trust region policy optimization,” inInternational Conference on Machine Learning. PMLR, 2015, pp. 1889–1897
2015
-
[17]
Policy optimization provably con- verges to nash equilibria in zero-sum linear quadratic games,
K. Zhang, Z. Yang, and T. Basar, “Policy optimization provably con- verges to nash equilibria in zero-sum linear quadratic games,”Advances in Neural Information Processing Systems, vol. 32, 2019
2019
-
[18]
Combining policy gradient and q-learning,
B. O’Donoghue, R. Munos, K. Kavukcuoglu, and V . Mnih, “Combining policy gradient and q-learning,”arXiv preprint arXiv:1611.01626, 2016
2016 arXiv
-
[19]
On the sample com- plexity of the linear quadratic regulator,
S. Dean, H. Mania, N. Matni, B. Recht, and S. Tu, “On the sample com- plexity of the linear quadratic regulator,”Foundations of Computational Mathematics, vol. 20, no. 4, pp. 633–679, 2020
2020
-
[20]
Toward a theoretical foundation of policy optimization for learning control policies,
B. Hu, K. Zhang, N. Li, M. Mesbahi, M. Fazel, and T. Bas ¸ar, “Toward a theoretical foundation of policy optimization for learning control policies,”Annual Review of Control, Robotics, and Autonomous Systems, vol. 6, no. 1, pp. 123–158, 2023
2023
-
[21]
Global convergence of policy gradient methods for the linear quadratic regulator,
M. Fazel, R. Ge, S. Kakade, and M. Mesbahi, “Global convergence of policy gradient methods for the linear quadratic regulator,” inInterna- tional Conference on Machine Learning. PMLR, 2018, pp. 1467–1476
2018
-
[22]
Optimizing static linear feedback: Gradient method,
I. Fatkhullin and B. Polyak, “Optimizing static linear feedback: Gradient method,”SIAM Journal on Control and Optimization, vol. 59, no. 5, pp. 3887–3911, 2021
2021
-
[23]
Convergence and sample complexity of gradient methods for the model-free linear–quadratic regulator problem,
H. Mohammadi, A. Zare, M. Soltanolkotabi, and M. R. Jovanovi ´c, “Convergence and sample complexity of gradient methods for the model-free linear–quadratic regulator problem,”IEEE Transactions on Automatic Control, vol. 67, no. 5, pp. 2435–2450, 2021
2021
-
[24]
Global convergence of policy gradient primal–dual methods for risk-constrained LQRs,
F. Zhao, K. You, and T. Bas ¸ar, “Global convergence of policy gradient primal–dual methods for risk-constrained LQRs,”IEEE Transactions on Automatic Control, vol. 68, no. 5, pp. 2934–2949, 2023
2023
-
[25]
Derivative-free methods for policy optimization: Guarantees for linear quadratic systems,
D. Malik, A. Pananjady, K. Bhatia, K. Khamaru, P. L. Bartlett, and M. J. Wainwright, “Derivative-free methods for policy optimization: Guarantees for linear quadratic systems,”Journal of Machine Learning Research, vol. 21, no. 21, pp. 1–51, 2020
2020
-
[26]
Distributed reinforcement learning for decentralized linear quadratic control: A derivative-free policy optimization approach,
Y . Li, Y . Tang, R. Zhang, and N. Li, “Distributed reinforcement learning for decentralized linear quadratic control: A derivative-free policy optimization approach,”IEEE Transactions on Automatic Control, vol. 67, no. 12, pp. 6429–6444, 2021
2021
-
[27]
Learning-based control: A tutorial and some recent results,
Z.-P. Jiang, T. Bian, W. Gaoet al., “Learning-based control: A tutorial and some recent results,”Foundations and Trends® in Systems and Control, vol. 8, no. 3, pp. 176–284, 2020. 8 IEEE TRANSACTIONS AND JOURNALS TEMPLA TE
2020
-
[28]
Robust policy iteration for continuous-time linear quadratic regulation,
B. Pang, T. Bian, and Z.-P. Jiang, “Robust policy iteration for continuous-time linear quadratic regulation,”IEEE Transactions on Automatic Control, vol. 67, no. 1, pp. 504–511, 2021
2021
-
[29]
Remarks on input to state stability of perturbed gradient flows, motivated by model-free feedback control learning,
E. D. Sontag, “Remarks on input to state stability of perturbed gradient flows, motivated by model-free feedback control learning,”Systems & Control Letters, vol. 161, p. 105138, 2022
2022
-
[30]
Small-disturbance input-to-state stability of perturbed gradient flows: Applications to LQR problem,
L. Cui, Z.-P. Jiang, and E. D. Sontag, “Small-disturbance input-to-state stability of perturbed gradient flows: Applications to LQR problem,” Systems & Control Letters, vol. 188, p. 105804, 2024
2024
-
[31]
Robust reinforcement learning for risk-sensitive linear quadratic gaussian control,
L. Cui, T. Bas ¸ar, and Z.-P. Jiang, “Robust reinforcement learning for risk-sensitive linear quadratic gaussian control,”IEEE Transactions on Automatic Control, 2024
2024
-
[32]
Distributed zero-order algorithms for nonconvex multiagent optimization,
Y . Tang, J. Zhang, and N. Li, “Distributed zero-order algorithms for nonconvex multiagent optimization,”IEEE Transactions on Control of Network Systems, vol. 8, no. 1, pp. 269–281, 2020
2020
-
[33]
B. D. Anderson and J. B. Moore,Optimal control: linear quadratic methods. Courier Corporation, 2007
2007
-
[34]
Distributed policy gradient for linear quadratic net- worked control with limited communication range,
Y . Yan and Y . Shen, “Distributed policy gradient for linear quadratic net- worked control with limited communication range,”IEEE Transactions on Signal Processing, vol. 72, pp. 2087–2100, 2024
2024
-
[35]
Stochastic first-and zeroth-order methods for nonconvex stochastic programming,
S. Ghadimi and G. Lan, “Stochastic first-and zeroth-order methods for nonconvex stochastic programming,”SIAM Journal on Optimization, vol. 23, no. 4, pp. 2341–2368, 2013
2013
-
[36]
An optimal algorithm for bandit and zero-order convex optimization with two-point feedback,
O. Shamir, “An optimal algorithm for bandit and zero-order convex optimization with two-point feedback,”Journal of Machine Learning Research, vol. 18, no. 52, pp. 1–11, 2017
2017
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.