Distributed Reinforcement Learning for Decentralized Linear Quadratic Control: A Derivative-Free Policy Optimization Approach

1.1 Our contributions

• ZODPO combines zero-order gradient estimation, approximate policy perturbation sampling, and consensus-based global-cost estimation for distributed local-policy updates.The method is designed to limit communication and local-policy storage.Source: §1.1 · p. 2
• The sample complexity to reach a stationary point is polynomial in problem dimensions and inverse error tolerance, and generated policies are stabilizing with high probability.The analysis addresses additional errors from approximate perturbation sampling and spatial-temporal cost estimation, and uses gradient truncation under unbounded Gaussian process noise.Source: §1.1 · p. 2
• ZODPO is numerically tested on multi-zone HVAC systems to demonstrate the optimality and safety of its generated controllers.Source: §1.1 · p. 2

1.2 Related work

• Prior decentralized LQ learning often uses centralized learning or asymptotic analysis; a distributed nonasymptotic method requires storing and updating the whole-system model [22].Source: §1.2 · p. 3
• Unlike cooperative Dec-POMDP work that commonly gives agents global reward signals, this setting uses local costs to minimize their average.The cited comparison assumes global state and action signals.Source: §1.2 · p. 3

2 Problem Formulation

• The global system evolves as x(t + 1) = Ax(t) + Bu(t) + w(t), with i.i.d. Gaussian disturbances and agents observing only fixed subsets of the state.The disturbance has zero mean and positive-definite covariance.Source: §2 · p. 4
• Each agent's admissible controller is a static linear function of its current local observation, yielding a global gain M(K) that is often sparse.Source: §2 · p. 4
• Agents receive quadratic local stage costs that may depend on the global state and action; the objective is their averaged infinite-horizon cost.Source: §2 · p. 4
• Agents communicate small numbers of scalars only with network neighbors over a connected, undirected graph.The associated communication matrix is nonnegative and doubly stochastic.Source: §2 · p. 5
• The assumptions require controllability, positive-definite aggregate control costs, and the existence of at least one stabilizing policy.Without a stabilizing policy, the paper says the problem lacks a reasonable solution even with known parameters.Source: §2 · pp. 5–6

3.1 Review: Zero-Order Policy Gradient for Centralized LQR

• The centralized zero-order estimator uses perturbed-policy cost values and random directions; under smoothness conditions, its bias can be controlled by smoothing radius r.Source: §3.1 · p. 6

3.2 Our Algorithm: Zero-Order Distributed Policy Optimization

• ZODPO lets agents update their local controllers in parallel using zero-order partial-gradient estimates when they can sample perturbations and obtain the perturbed global objective.The update uses each agent’s perturbation together with the global cost at the perturbed policy.Source: §3.2 · p. 6
• If Assumption 2 fails but the system is stabilizable, more general controller structures, including linear dynamic or nonlinear controllers, are outside this paper’s scope.Source: §3.2 · p. 6
• SampleUSphere uses independent Gaussian matrices and consensus on squared norms to make concatenated perturbations approximately uniform on the unit sphere for sufficiently large TS.The approximation is supported by the analysis described in the passage.Source: §3.2 · p. 7
• GlobalCostEst combines neighbor consensus with local stage costs to estimate the global objective, with µ_i(TJ) approximating J(K) for sufficiently large TJ.Agents exchange their estimates with neighbors while observing their local costs.Source: §3.2 · p. 7
• Each agent shares only scalar µ_i(t) and q_i(t) per communication round and stores and updates only its local policy K_i.Source: §3.2 · p. 8
• ZODPO requires sufficiently many subroutine iterations for accurate gradients; using fewer iterations with safe-policy switching is proposed, but its theoretical analysis is left for future work.The safe policy is used when states become too large, with learning resumed when they are small.Source: §3.2 · p. 8

Theoretical Analysis

• J(K) is continuously differentiable on the stabilizing region, with compact nonempty sublevel sets and locally bounded gradient variation.The gradient variation bound applies to nearby controllers within the specified sublevel-set conditions.Source: §4 · p. 9
• All generated controllers are stabilizing with probability at least 0.9−0.05c, and a uniformly sampled iterate has an optimality bound with probability at least 0.875−0.05(c+c^-1).The optimality guarantee is stated for a uniformly randomly selected controller from the iterates.Source: §4 · p. 9
• As TG grows, stability probability can decrease, while the probability of optimality guarantees first rises and then falls as iteration benefits trade off against destabilization risk.The text attributes the stability-risk increase to accumulated gradient-estimation bias and variance.Source: §4 · pp. 9–10
• The sample complexity for guaranteeing the averaged squared-gradient criterion depends polynomially on the inverse error tolerance, policy dimension nK, and agent count N.The bound also includes terms associated with consensus and approximating the infinite-horizon averaged cost.Source: §4 · p. 10
• Although the sample-complexity expression has explicit linear dependence on state dimension n, its actual dependence is complicated because several constants also depend on n.The constants β0, J(K0), φ0, and ξ0 are among those affected by system dimension.Source: §4 · p. 10
• ZODPO explores only the stabilizing component containing K0, so initialization affects which stationary points it can reach; exploring other components remains open.The paper identifies choosing K0 and effectively exploring other components as future challenges.Source: §4 · p. 10

5 Proof of Theorem 1

• Unlike centralized LQR analyses, this proof handles approximate perturbation sampling, unbounded Gaussian noise, spatial averaging, and an objective lacking gradient dominance.The lack of gradient dominance leads the authors to use general nonconvex analysis and more conservative parameter choices.Source: §5 · p. 11

5.1 Bounding the Sampling Inaccuracy

• The proof bounds the error from the distributed method’s approximate sampling of the uniform-sphere perturbation distribution.The authors note that exact sampling is unavailable in the distributed setting.Source: §5 · p. 11, §5.1 · p. 12

5.2 Bounding the Global Cost Estimation Error

• The analysis bounds each agent’s global-cost estimation error and the effect of truncating that estimate, with expectations over process noise.The cost-estimation bounds characterize the properties of output controllers because the algorithm’s outputs lie in Q0 ⊆ Q1 with high probability.Source: §5.2 · p. 12

5.3 Bounding the Gradient Estimation Error

• The gradient-estimation analysis accounts for both zero-order bias and errors from estimated costs and approximate perturbation sampling.The estimator uses estimated rather than exact objective values, and its perturbation distribution only approximates the uniform-sphere distribution.Source: §5.3 · pp. 13, 15

5.4 Analysis of One-Step Stochastic Gradient Update

• Each policy update is analyzed as stochastic gradient descent with biased gradient estimates, bounding objective change while keeping the next iterate in Q1.The stated update guarantee assumes the current iterate is in Q0.Source: §5.4 · p. 16

5.5 Proving Stability of the Output Controllers

• With probability at least 9/10 − c/20, all controllers generated by ZODPO are stabilizing under the theorem’s conditions.The proof bounds the probability that an iterate leaves Q0, then uses Q0’s relation to the stabilizing-controller set.Source: §5 · p. 11, §5.5 · p. 17

5.6 Proving the Performance Bound in Theorem 1.

• Theorem 1’s performance bound applies to an output controller selected uniformly at random from the generated iterates.The proof first bounds accumulated gradient norms and controls the probability of leaving Q0 before deriving the bound.Source: §5 · p. 11, §5.6 · pp. 18–19

6 Numerical Studies

• The numerical section tests ZODPO on HVAC systems in both theoretically analyzed time-invariant cases and more realistic time-varying cases.The authors focus on ZODPO because they are not aware of another learning algorithm directly applicable to their problem.Source: §6 · p. 19

6.1 Thermal Dynamics Model

• The HVAC model represents each zone’s temperature, control input, outdoor temperature, external heat, random disturbances, and thermal resistances between zones and outdoors.Each zone has a sensor for local temperature and adjusts its associated HVAC supply-air flow rate.Source: §6.1 · p. 19

6.2 Time-Invariant Cases

• For the four-zone system, more policy-gradient iterations produce controllers that stabilize temperatures faster and bring them closer to the desired temperature.The comparison uses controllers after TG = 50, 150, and 250 iterations with TJ = 300.Source: §6.2 · p. 20, Figure 2 · p. 20
• Across 500 repeated simulations, ZODPO’s infinite-horizon averaged costs decreased as TG increased over 50 ≤ TG ≤ 500; larger TJ coincided with lower averaged costs and narrower confidence intervals.Figure 3’s shaded regions represent 70% confidence intervals.Source: §6.2 · p. 21, Figure 3 · p. 21

6.3 Larger Scale Systems

• In a 20-zone building, the controller learned after 4,800 iterations keeps all room temperatures around the 22°C desired temperature.This run uses TJ = 500 and constant outdoor temperature of 30°C.Source: §6.3 · p. 21, Figure 4 · p. 22

6.4 Varying Outdoor Temperature

• With time-varying outdoor temperatures, ZODPO finds a controller that roughly maintains room temperature at the desired level.The study uses data from the Harvard HouseZero Program and fixes outdoor temperature within each policy-gradient iteration during training.Source: §6.4 · pp. 21–22

7 Conclusions and Future Work

• ZODPO combines policy-gradient, consensus, and zero-order optimization ideas to learn decentralized controllers, with high-probability stability and sample-complexity guarantees.The paper also tests the algorithm on HVAC systems.Source: §7 · p. 22
• Future work includes better initialization, exploration of other stabilizing components, richer history-based controllers, alternative gradient estimators, and actor-critic algorithms.The authors identify these as directions for approaching global optima, exploiting additional structure, improving sample complexity, or reducing per-iteration running time.Source: §7 · p. 22

A Additional Notations and Auxiliary Results

• The global control gain M(K) is an injective linear map from the policy-parameter space to global control gains.The passage gives the domain and codomain as R^nK and R^(n×m), respectively.Source: A Additional Notations and Auxiliary… · p. 22
• An auxiliary lemma gives a continuous function ϕ from the stabilizing-controller set to [1, +∞).The supplied passages also state that a sequence converges and satisfies a Lyapunov equation, but do not specify its relationship to this function.Source: A Additional Notations and Auxiliary… · p. 23
• The appendix states that a continuous function ϕ(K) is defined over stabilizing controllers.The preceding passage identifies continuity over K ∈ Kst.Source: A Additional Notations and Auxiliary… · p. 23

• Gaussian isotropy gives the stated uniform-sphere distribution.Source: B Proof of Lemma 2 · p. 23
• The update q(t) = Wq(t − 1) preserves 1⊤q(t), as W is doubly stochastic.Source: B Proof of Lemma 2 · pp. 23–24
• The proof uses ∥Nv − 1∥ ≤ N for nonnegative v whose entries sum to one.Source: B Proof of Lemma 2 · p. 24

• The estimate µi(TJ), also denoted ˜Ji(K), is represented as a quadratic form in an auxiliary Gaussian vector.Source: C Proof of Lemma 3 · p. 24
• The proof analyzes the estimate's bias and variance using properties of quadratic Gaussian variables and the matrices ΦρW and Φ1.Source: C Proof of Lemma 3 · pp. 26–28
• The finite constant β0 depends only on system parameters and the initial cost J(K0), and its substitution proves (15) for K ∈ Q1.Source: C Proof of Lemma 3 · p. 28

• The concentration argument applies Proposition 2 to a standard Gaussian vector and a symmetric positive definite matrix.Source: D Proof of Lemma 4 · p. 28
• The proof splits ε into ε1 = 4ε/5 and ε2 = ε/5 when combining the bounds.Source: D Proof of Lemma 4 · p. 30
• The final step invokes Lemma 10 and the condition on J̄ to obtain the stated bound.Source: D Proof of Lemma 4 · p. 31