On Globally Optimal Stochastic Policy Gradient Methods for Domain Randomized LQR Synthesis

1. Problem Statement

The paper addresses the Domain Randomized Linear-Quadratic Regulator (DR-LQR) synthesis problem.

• Context: Domain Randomization (DR) is a popular technique in robotics and reinforcement learning to bridge the "sim-to-real" gap by training controllers on randomized system parameters (e.g., mass, friction, geometry) rather than a single fixed model.
• The Challenge: While DR is empirically successful, theoretical principles for optimizing DR policies are limited. Existing methods often rely on surrogate cost functions (e.g., sample-average approximations on a fixed set of systems) which can lead to suboptimal controllers or high variability.
• The Objective: The authors aim to solve the DR-LQR problem directly: finding a feedback gain $K$ that minimizes the expected LQR cost over a distribution of system parameters $\theta \in \Theta$, subject to the constraint that $K$ stabilizes all systems in the support of the distribution.
  $$\min_{K} \mathbb{E}_{\theta}[J(K, \theta)] \quad \text{s.t.} \quad \sup_{\theta \in \Theta} J(K, \theta) < \infty$$
• Difficulty: The problem is non-convex in the policy $K$, and the objective function and its gradient cannot be computed exactly (only estimated via sampling).

2. Methodology

The authors propose a Minibatched Stochastic Policy Gradient Descent (SGD) algorithm (Algorithm 1) that resamples new system instances at every gradient step, rather than using a fixed set of samples.

Key Theoretical Components:

1. Gradient Dominance (Polyak-Łojasiewicz Condition):
   The paper establishes that the DR-LQR cost function satisfies a gradient dominance property (specifically, a quadratic growth condition) within a specific neighborhood of the optimal solution. This property is crucial because it allows non-convex gradient descent to converge to a global optimum, bypassing local minima.

   • They prove that under specific heterogeneity conditions (bounded diameter of the parameter set $\Theta$), the true expected cost $J_{DR}(K)$ inherits this property from the underlying LQR structure.

2. Local Smoothness and Coercivity:

   • Coercivity: The cost function grows unbounded as the controller $K$ approaches instability, ensuring the existence of a minimum.
   • Local $L$-Smoothness: While the cost is not globally smooth (due to the singularity at the stability boundary), the authors prove it is $L$-smooth on any sublevel set $S_c = \{K : J_{DR}(K) \leq c\}$. This allows for the selection of step sizes that guarantee the iterates remain within the feasible (stabilizing) set.

3. Convergence Analysis of SGD:

   • The authors analyze the convergence of the minibatched SGD where gradients are estimated by sampling $M$ new systems at each iteration.
   • They derive explicit conditions for the minibatch size ($M$), step size ($\eta$), and number of iterations ($N$) required to achieve an $\epsilon$-suboptimal solution with high probability ($1-\delta$).
   • A key technical contribution is bounding the gradient estimation error using Matrix Bernstein inequalities, ensuring that the stochastic updates do not push the controller out of the stabilizing region.

3. Key Contributions

1. First Proof of Linear Convergence for DR-LQR: The paper provides the first theoretical proof that minibatched SGD converges linearly to an $\epsilon$-suboptimal solution for the DR-LQR problem.
2. Direct Optimization vs. Surrogate: Unlike previous works (e.g., Fujinami et al.) that optimize a surrogate sample-average cost on a fixed set of systems, this work optimizes the true expected cost directly via stochastic gradients.
3. Hyperparameter Characterization: The authors provide explicit, problem-dependent formulas for the required minibatch size and step sizes to guarantee convergence, linking the sampling budget to the desired suboptimality level.
4. Implicit Regularization: They demonstrate that with appropriate step sizes, the algorithm maintains feasibility (stability) without needing explicit projection steps, relying on the "implicit regularization" property of the cost landscape.

4. Experimental Results

The authors validate their theory using a Cart-Pole system with randomized pendulum lengths, masses, and friction coefficients.

• Convergence Speed: Increasing the minibatch size ($M$) leads to more accurate gradient estimates and faster convergence, consistent with standard SGD theory.
• Performance Comparison (DR vs. Sample-Average):
  • The proposed DR-SGD method (resampling at every step) was compared against the Sample-Average (SA) method (fixed set of 8 systems, as used in prior work).
  • Result: DR-SGD achieved lower final costs and significantly lower variability in the final controller performance.
  • Variance Reduction: The histogram of the $L_2$ norm of the final controllers showed that DR-SGD produces much more consistent controllers compared to the SA method.
• Computational Efficiency:
  • The DR method took only a 22% increase in runtime (40.5s vs 33.1s on an A100 GPU) compared to the SA method.
  • This marginal computational cost yielded controllers that were not only higher-performing but also more reliable and robust.

5. Significance and Impact

• Theoretical Validation of DR: This work bridges the gap between the empirical success of Domain Randomization in robotics and rigorous control theory. It proves that DR is not just a heuristic but a mathematically sound approach for finding globally optimal robust controllers.
• Efficiency of Resampling: The paper demonstrates that resampling systems at every iteration is superior to using a fixed dataset. Since sampling is computationally cheap (especially with GPU parallelism), the "fresh" gradients provide better convergence properties and lower variance than static approximations.
• Practical Applicability: The results suggest that for robust control synthesis, practitioners should utilize stochastic gradient descent with dynamic resampling rather than static scenario-based optimization, as it yields more reliable controllers with minimal additional computational overhead.
• Future Directions: The authors note that relaxing the strict heterogeneity conditions required for gradient dominance and extending the analysis to globally convergent SGD (beyond $\epsilon$-suboptimality) are promising avenues for future research.

In summary, this paper establishes that stochastic policy gradient descent with dynamic resampling is a theoretically guaranteed, globally convergent, and practically superior method for synthesizing robust controllers in domain-randomized linear-quadratic settings.