Distributed Online Linear Quadratic Control for Linear Time-invariant Systems

Shahin Shahrampour; Ting-Jui Chang

REVIEW 2 major objections 3 minor 28 references

Distributed Online Linear Quadratic Control for Linear Time-invariant Systems

T0 review · 2 major / 3 minor · reviewed 2026-08-27 · deepseek-v4-flash

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

Pith's one-line read Distributed online LQ control achieves square-root regret

desk verdict First distributed online LQ algorithm with a plausible O(√T) regret claim, but the proof as printed has a sqrt-η variation bound and a threshold mismatch that need fixing before the rate is established. read the letter →

arxiv 2009.13749 v1 pith:XE6RSSKE submitted 2020-09-29 math.OC cs.LGcs.SYeess.SY

Ting-Jui Chang , Shahin Shahrampour This is my paper · ORCID

classification math.OCcs.LGcs.SYeess.SY MSC 93C0593A1490C22

keywords onlinelinearquadraticcontroldistributedoptimizationregretminimizationmulti-agentsystemssemidefiniteprogrammingstrongstabilityconsensustime-varyingcosts

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

This paper proves that a network of identical linear systems, each with its own time-varying quadratic cost revealed online, can be controlled in a fully distributed way while remaining competitive with the best fixed centralized controller in hindsight. Each agent runs a projected online gradient step on a semidefinite programming relaxation of the linear quadratic regulator, exchanges its iterate with neighbors, and extracts a randomized linear controller. The individual regret of every agent after T rounds is bounded by the square root of T, so average performance converges to the centralized benchmark and agents reach consensus. The result extends the single-agent online LQ framework to multi-agent networks with identical dynamics, using only local communication.

What carries the argument

The object doing the work is the semidefinite programming relaxation of the LQ cost, whose feasible set S consists of state-action covariance matrices Σ satisfying the Lyapunov equation and a trace bound. Each agent performs a distributed online gradient descent step on this SDP using its own revealed cost matrix, projects back onto S, and averages the iterates through the doubly stochastic matrix P; the controller is extracted as K = Σ_{xu}Σ_{xx}^{-1}, with action noise added to keep the empirical covariance aligned with the iterate. The proof's engine is the notion of strong (and sequentially strong) stability, which guarantees that a slowly varying sequence of such controllers keeps the state covariance exponentially close to the ideal steady-state covariance, with an error term proportional to the per-step variation of the SDP iterates.

What would settle it

Run Algorithm 1 with the theorem's parameters and record the maximum of ‖Σ_{t+1}−Σ_t‖ over all t for T set to the stated lower bound; if this maximum exceeds $σ^{4}$/ν, the covariance-convergence estimate used in the proof fails and the O(√T) regret bound is not established by this argument.

Watch

Extended reading notes

Core claim

The central claim is that for any (κ,γ)-strongly stable centralized policy Ks, the expected individual regret of an arbitrary agent running Algorithm 1 is O((1−β)^{-1/2}√T), where β is the second-largest singular value of the doubly stochastic communication matrix. This sublinear regret means that the per-round cost of each agent approaches the cost of the best fixed linear controller chosen with full knowledge of all cost matrices, and that the agents' control sequences asymptotically agree. The proof decomposes the regret into three terms: the distributed online optimization error of the SDP iterates, the tracking error between the true state covariance and the ideal steady-state covariance induced by the algorithm's iterates, and the error of the centralized benchmark's own covariance convergence. Each term is bounded using the strong stability of the extracted controllers and the geometric mixing of the communication graph.

Load-bearing premise

The regret bound rests on the requirement that the SDP iterates change slowly enough between rounds—specifically ‖Σ_{t+1}−Σ_t‖ ≤ $σ^{4}$/ν—so that the extracted controllers stay sequentially strongly stable and the state covariance stays close to the ideal one; the stated lower bound on T is the only guarantee of this condition, and it may not be sufficient as written.

Editorial extensions

If this is right

For large enough T, the average per-round cost of any agent is within a constant of the best fixed strongly stable linear controller in hindsight.
The regret bound degrades as the network's spectral gap shrinks, but remains O(√T) for any fixed β < 1, so even poorly connected networks keep the same time order.
The algorithm requires only local communication and no global knowledge of cost matrices or topology, making it implementable in large-scale networks.
The result implies that consensus among agents is achieved asymptotically: their SDP iterates and hence their controllers converge to a common limiting policy.

Reading between the lines

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

If the slow-variation condition on the SDP iterates can be guaranteed for a wider range of step sizes (or by a different projection scheme), the same proof strategy would extend to unknown dynamics by treating system identification errors as additional perturbations to the covariance recursion.
The approach suggests a template for distributed online semidefinite programming with time-varying linear objectives, where a controlled averaging step is used to achieve both low regret and consensus.
One testable prediction is that the regret constant should scale as (1−β)^{-0.5}; plotting regret against 1/(1−β) for fixed T should reveal a square-root relationship if the bound is tight.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Short version: this is the first distributed online LQ algorithm I know of with an O(√T) individual regret bound for identical LTI systems and time-varying costs. It is a clean extension of Cohen et al.'s SDP relaxation plus Yan et al.'s distributed OGD, and the related work is honest. The proof structure is the right one. But the manuscript as written has a load-bearing error in the variation estimate. Inequality (7) states ||Σ_{j,t+1}-Σ_{j,t}|| ≤ 4√(2mCη)/(1−β). That's √η, not η. Lemma 1 needs the variation to be ≤ σ^4/ν for the extracted policies to be sequentially strongly stable; with √η the covariance error in (9) is O(√η), and summing over T gives O(T^{3/4}) in term (II), not O(√T). The theorem only works if the variation is O(η), which is what OGD normally gives. So either (7) is a typo (missing the η outside the square root) or the main rate is false. There's a matching inconsistency: Theorem 2's lower bound on T omits the factor m that appears in the appendix, and the constant in (9) doesn't match Lemma 4.4's κ^4 = ν^2/σ^4. These are mechanical but they sit at the exact point the proof rests on.

The numerical section is weak evidence: one five-agent cycle, no error bars despite Monte Carlo, and the conclusion that O(√T) 'implies consensus' is not what the theorem shows (it bounds regret, not disagreement). The consensus claim should be stated as asymptotic convergence of averaged regrets, as in Fig. 3.

If the typos are fixed, I'd expect the result to go through; the combination is natural and the authors cite the right sources. Self-citation is fine here. The paper deserves a careful referee, not a desk reject. I'd ask for a corrected proof and more careful experiments. For a reading group, it's a useful example of how small algebra slips can invalidate a rate.

Referee Report

2 major / 3 minor

Summary. The paper studies a distributed online linear quadratic (LQ) control problem for a network of m identical, known LTI systems with decoupled, adversarially time-varying quadratic costs. Each agent runs a distributed online gradient descent with projection onto the feasible set of an SDP relaxation, extracts a linear-Gaussian controller from the maintained covariance iterate, and the authors claim an expected individual regret bound of O(√T) against any (κ,γ)-strongly stable centralized policy, together with asymptotic consensus. Numerical experiments on a five-agent cycle network are provided. The proof follows the single-agent analysis of Cohen et al. by adding the distributed OGD regret machinery of Yan et al.

Significance. If the result were correct, it would be a natural and useful distributed extension of the online LQ framework: the O(√T) rate is the expected optimal rate for online convex optimization with adversarial costs, and the SDP-projection reduction is an appropriate technique. The paper's clear problem formulation and its reduction of the distributed control problem to distributed online convex optimization are strengths. The main issue is that the proof's slow-variation analysis contains a load-bearing algebraic error: the printed variation bound has the wrong scaling in the step size, which prevents the stated O(√T) regret from following. The theorem and appendix also disagree on the validity range of T.

major comments (2)

[Appendix, Eq. (7) and Eq. (14)] The variation bound in Eq. (7) is O(√η). Lemma 1 and Eq. (9) inherit this √η factor, so after summing over time the cumulative error in term (II) is O(√η · T). With η = 1/√(ρT), this is O(T^{3/4}), not O(√T). Eq. (14) absorbs the coefficient of this term into ρηT as if the term were linear in η; the definition of ρ does not change √ηT into ηT. The proof of Theorem 2 therefore does not establish the claimed O(√T) regret unless the variation bound (7) is replaced by an O(η) bound (or the analysis is otherwise changed).
[Theorem 2 vs. Appendix, condition before Eq. (9)] Theorem 2 states the validity threshold as T ≥ (4√(2νC)/(σ^4(1−β)ρ^{1/2}))^2, whereas the appendix requires T ≥ (4√(2mνC)/(σ^4(1−β)ρ^{1/2}))^2 to ensure 4√(2mCη)/(1−β) ≤ σ^4/ν. The missing factor m inside the square root means the theorem's stated range does not guarantee the slow-variation premise required by Lemma 1. Moreover, with the printed √η in (7), even the appendix's threshold does not follow by a direct rearrangement of the stated inequality; the threshold must be recalculated consistently with the actual variation bound.

minor comments (3)

[Theorem 2, Definition 1] Theorem 2 assumes 0 ≤ γ < 1, while Definition 1 requires 0 < γ ≤ 1; since the proof divides by γ in Eq. (13), the boundary case γ = 0 should be excluded.
[Section IV, numerical experiments] The paper says T is set to 30 times the theoretical lower bound but does not report the resulting value of T; without this number, Figures 1–3 cannot be reproduced from the text.
[Appendix, Eq. (9) and Lemma 1] The additive constant in Eq. (9) scales as ν/σ^2, whereas Lemma 1's stated bound contains 4ηκ^4 = 4η(ν/σ^2)^2; please reconcile these expressions so that the constants in the regret bound are internally consistent.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the O(√T) regret bound is derived from external lemmas and independent optimization arguments; the only self-citation is a non-load-bearing remark.

full rationale

The paper's central claim is a regret bound for a distributed online LQ algorithm. The derivation chain is: (i) decompose regret into three terms, (ii) bound the online-gradient-descent term via Lemma 3.3 and Lemma 4.1 of [4] plus the distributed OGD regret bound of [5], (iii) bound the covariance convergence term via Lemma 1 (Lemma 4.4 of [4]) and the variance bound (7), and (iv) bound the benchmark-term via Lemma 3.2 of [4]. None of these ingredients is authored by the present paper's authors, and none of the bounds is defined in terms of the regret it is used to prove. The algorithm's step size and threshold are chosen from the stated constants; the regret bound is not a fitted quantity or a renamed input. The only self-citation is the remark in Section III-B that the spectral-gap dependence 'has been previously observed in distributed online algorithms (see e.g., [28] Corollary 4)'; this is a contextual remark and is not load-bearing for Theorem 2. The skeptical note about the variation bound (7) scaling as √η rather than η, and the apparent missing √m factor in the stated lower bound on T, concerns whether the stated assumptions actually imply the slow-variation condition needed for Lemma 1. That is a correctness or proof-gap issue, not a circularity: the claim is not true by construction and does not reduce to its inputs. Therefore no circular step is identified and the circularity score is 0.

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

The central claim rests on external lemmas from centralized online LQ (Cohen et al. 2018) and distributed online learning (Yan et al. 2012), plus standard assumptions on the network, noise, and cost bounds. No parameters are fitted to data; the constants in the bound are constructed from the problem parameters.

assumptions (6)

standard math Lemmas 3.2, 3.3, 4.1, 4.3, and 4.4 from Cohen et al. (2018) for covariance convergence, steady-state trace bound, and sequential strong stability.
External results that underpin the stability and convergence parts of the proof; cited but not re-proven.
standard math Distributed online gradient descent regret bound from Yan et al. (2012).
External result used to bound the online learning term in the regret decomposition.
domain assumption Network is connected and the communication matrix P is doubly stochastic with second largest singular value β < 1.
Required for consensus and for the (1−β) dependence in the regret bound; stated in Section II-B.
domain assumption Noise covariance W satisfies W ≽ σ²I and Tr(W) ≤ λ².
Ensures invertibility of state covariance and finiteness of the benchmark steady-state trace; used to set ν.
domain assumption Cost matrices satisfy Tr(Q_i,t), Tr(R_i,t) ≤ C for all i,t.
Provides bounded gradients for the online optimization and is needed for the regret bound constants.
domain assumption There exists a (κ,γ)-strongly stable linear policy for the benchmark class.
The benchmark policy class is defined as the set of strongly stable controllers; existence is assumed.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Distributed Online Linear Quadratic Control for Linear Time-invariant Systems." pith.science (2026). https://pith.science/paper/XE6RSSKE

@misc{pith2026200913749,
  author       = {Pith},
  title        = {Pith review of: Distributed Online Linear Quadratic Control for Linear Time-invariant Systems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XE6RSSKE}},
  note         = {Machine review of arXiv:2009.13749}
}

read the original abstract

Classical linear quadratic (LQ) control centers around linear time-invariant (LTI) systems, where the control-state pairs introduce a quadratic cost with time-invariant parameters. Recent advancement in online optimization and control has provided novel tools to study LQ problems that are robust to time-varying cost parameters. Inspired by this line of research, we study the distributed online LQ problem for identical LTI systems. Consider a multi-agent network where each agent is modeled as an LTI system. The LTI systems are associated with decoupled, time-varying quadratic costs that are revealed sequentially. The goal of the network is to make the control sequence of all agents competitive to that of the best centralized policy in hindsight, captured by the notion of regret. We develop a distributed variant of the online LQ algorithm, which runs distributed online gradient descent with a projection to a semi-definite programming (SDP) to generate controllers. We establish a regret bound scaling as the square root of the finite time-horizon, implying that agents reach consensus as time grows. We further provide numerical experiments verifying our theoretical result.

Figures

Figures reproduced from arXiv: 2009.13749 by the authors.

**Figure 2.** This plot shows that the individual regret of agent 1 is of [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

**Figure 3.** The averaged regrets over time for all agents converge as [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 25 canonical work pages

[1]

Linear optimal control,

B. D. O. Anderson, J. B. Moore, and B. P. Molinari, “Linear optimal control,” IEEE Transactions on Systems, Man, and Cybernetics , vol. SMC-2, no. 4, pp. 559–559, 1972

work page 1972
[2]

D. P. Bertsekas, Dynamic programming and optimal control , vol. 1, no. 2

work page
[3]

K. Zhou, J. C. Doyle, K. Glover et al. , Robust and optimal control . Prentice hall New Jersey, 1996, vol. 40

1996
[4]

Online linear quadratic control,

A. Cohen, A. Hasidim, T. Koren, N. Lazic, Y . Mansour, and K. Talwar, “Online linear quadratic control,” in International Conference on Machine Learning, 2018, pp. 1029–1038

work page 2018
[5]

Distributed autonomous online learning: Regrets and intrinsic privacy-preserving properties,

F. Yan, S. Sundaram, S. Vishwanathan, and Y . Qi, “Distributed autonomous online learning: Regrets and intrinsic privacy-preserving properties,” IEEE Transactions on Knowledge and Data Engineering , vol. 25, no. 11, pp. 2483–2493, 2012

work page 2012
[6]

Distributed lqr design for identical dynamically decoupled systems,

F. Borrelli and T. Keviczky, “Distributed lqr design for identical dynamically decoupled systems,” IEEE Transactions on Automatic Control, vol. 53, no. 8, pp. 1901–1912, 2008

work page 1901
[7]

Synchronization of autonomous agents by an optimal networked controller,

A. Mosebach and J. Lunze, “Synchronization of autonomous agents by an optimal networked controller,” in 2014 European Control Conference (ECC), 2014, pp. 208–213

work page 2014
[8]

Optimal linear-consensus algorithms: An lqr perspective,

Y . Cao and W. Ren, “Optimal linear-consensus algorithms: An lqr perspective,” IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 40, no. 3, pp. 819–830, 2010

work page 2010

Show all 28 references

[9]

A suboptimality approach to distributed linear quadratic optimal control,

J. Jiao, H. L. Trentelman, and M. K. Camlibel, “A suboptimality approach to distributed linear quadratic optimal control,” IEEE Trans- actions on Automatic Control , vol. 65, no. 3, pp. 1218–1225, 2020

2020
[10]

Distributed linear quadratic optimal control: Compute locally and act globally,

——, “Distributed linear quadratic optimal control: Compute locally and act globally,” IEEE Control Systems Letters , vol. 4, no. 1, pp. 67–72, 2020

2020
[11]

Distributed q-learning for dynam- ically decoupled systems,

S. Alemzadeh and M. Mesbahi, “Distributed q-learning for dynam- ically decoupled systems,” in 2019 American Control Conference (ACC). IEEE, 2019, pp. 772–777

2019
[12]

Efﬁcient learning of distributed linear-quadratic controllers,

S. Fattahi, N. Matni, and S. Sojoudi, “Efﬁcient learning of distributed linear-quadratic controllers,” arXiv preprint arXiv:1909.09895 , 2019

1909 arXiv
[13]

Learning the globally optimal distributed lq regulator,

L. Furieri, Y . Zheng, and M. Kamgarpour, “Learning the globally optimal distributed lq regulator,” in Learning for Dynamics and Control, 2020, pp. 287–297

2020
[14]

First order methods for globally optimal distributed controllers beyond quadratic invariance,

L. Furieri and M. Kamgarpour, “First order methods for globally optimal distributed controllers beyond quadratic invariance,” in 2020 American Control Conference (ACC) . IEEE, 2020, pp. 4588–4593

2020
[15]

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,” in International Conference on Machine Learning, 2018, pp. 1467–1476

2018
[16]

Derivative-free methods for policy optimization: Guarantees for linear quadratic systems,

D. Malik, A. Pananjady, K. Bhatia, K. Khamaru, P. Bartlett, and M. Wainwright, “Derivative-free methods for policy optimization: Guarantees for linear quadratic systems,” in The 22nd International Conference on Artiﬁcial Intelligence and Statistics . PMLR, 2019, pp. 2916–2925

2019
[17]

On the linear convergence of random search for discrete-time lqr,

H. Mohammadi, M. Soltanolkotabi, and M. R. Jovanovi, “On the linear convergence of random search for discrete-time lqr,” IEEE Control Systems Letters, vol. 5, no. 3, pp. 989–994, 2021

2021
[18]

Random search for learning the linear quadratic regulator,

H. Mohammadi, M. Soltanolkotabi, and M. R. Jovanovic, “Random search for learning the linear quadratic regulator,” in 2020 American Control Conference (ACC), 2020, pp. 4798–4803

2020
[19]

On the sample complexity of the linear quadratic regulator,

S. Dean, H. Mania, N. Matni, B. Recht, and S. Tu, “On the sample complexity of the linear quadratic regulator,” Foundations of Compu- tational Mathematics, pp. 1–47, 2019

2019
[20]

Learning linear dynamical systems via spectral ﬁltering,

E. Hazan, K. Singh, and C. Zhang, “Learning linear dynamical systems via spectral ﬁltering,” in Advances in Neural Information Processing Systems, 2017, pp. 6702–6712

2017
[21]

Towards provable control for unknown linear dynamical systems,

S. Arora, E. Hazan, H. Lee, K. Singh, C. Zhang, and Y . Zhang, “Towards provable control for unknown linear dynamical systems,” 2018

2018
[22]

Online control with adversarial disturbances,

N. Agarwal, B. Bullins, E. Hazan, S. M. Kakade, and K. Singh, “Online control with adversarial disturbances,” in 36th International Conference on Machine Learning, ICML 2019. International Machine Learning Society (IMLS), 2019, pp. 154–165

2019
[23]

Logarithmic regret for online control,

N. Agarwal, E. Hazan, and K. Singh, “Logarithmic regret for online control,” inAdvances in Neural Information Processing Systems, 2019, pp. 10 175–10 184

2019
[24]

Improper learning for non- stochastic control,

M. Simchowitz, K. Singh, and E. Hazan, “Improper learning for non- stochastic control,” arXiv preprint arXiv:2001.09254 , 2020

2001 arXiv
[25]

The nonstochastic control problem,

E. Hazan, S. Kakade, and K. Singh, “The nonstochastic control problem,” in Algorithmic Learning Theory , 2020, pp. 408–421

2020
[26]

Loga- rithmic regret bound in partially observable linear dynamical systems,

S. Lale, K. Azizzadenesheli, B. Hassibi, and A. Anandkumar, “Loga- rithmic regret bound in partially observable linear dynamical systems,” arXiv preprint arXiv:2003.11227 , 2020

2003 arXiv
[27]

J. S. Liu, Monte Carlo strategies in scientiﬁc computing . Springer Science & Business Media, 2008

2008
[28]

Distributed online optimization in dynamic environments using mirror descent,

S. Shahrampour and A. Jadbabaie, “Distributed online optimization in dynamic environments using mirror descent,” IEEE Transactions on Automatic Control, vol. 63, no. 3, pp. 714–725, 2018

2018

Pith tools

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

[1] [1]

Linear optimal control,

B. D. O. Anderson, J. B. Moore, and B. P. Molinari, “Linear optimal control,” IEEE Transactions on Systems, Man, and Cybernetics , vol. SMC-2, no. 4, pp. 559–559, 1972

work page 1972

[2] [2]

D. P. Bertsekas, Dynamic programming and optimal control , vol. 1, no. 2

work page

[3] [3]

K. Zhou, J. C. Doyle, K. Glover et al. , Robust and optimal control . Prentice hall New Jersey, 1996, vol. 40

1996

[4] [4]

Online linear quadratic control,

A. Cohen, A. Hasidim, T. Koren, N. Lazic, Y . Mansour, and K. Talwar, “Online linear quadratic control,” in International Conference on Machine Learning, 2018, pp. 1029–1038

work page 2018

[5] [5]

Distributed autonomous online learning: Regrets and intrinsic privacy-preserving properties,

F. Yan, S. Sundaram, S. Vishwanathan, and Y . Qi, “Distributed autonomous online learning: Regrets and intrinsic privacy-preserving properties,” IEEE Transactions on Knowledge and Data Engineering , vol. 25, no. 11, pp. 2483–2493, 2012

work page 2012

[6] [6]

Distributed lqr design for identical dynamically decoupled systems,

F. Borrelli and T. Keviczky, “Distributed lqr design for identical dynamically decoupled systems,” IEEE Transactions on Automatic Control, vol. 53, no. 8, pp. 1901–1912, 2008

work page 1901

[7] [7]

Synchronization of autonomous agents by an optimal networked controller,

A. Mosebach and J. Lunze, “Synchronization of autonomous agents by an optimal networked controller,” in 2014 European Control Conference (ECC), 2014, pp. 208–213

work page 2014

[8] [8]

Optimal linear-consensus algorithms: An lqr perspective,

Y . Cao and W. Ren, “Optimal linear-consensus algorithms: An lqr perspective,” IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 40, no. 3, pp. 819–830, 2010

work page 2010