Convergence Guarantees of Model-free Policy Gradient Methods for LQR with Stochastic Data

1. Problem Statement

The paper addresses the Linear Quadratic Regulator (LQR) problem for linear time-invariant systems subject to additive stochastic noise. The system dynamics are given by:
$$x_{t+1} = Ax_t + Bu_t + w_t, \quad w_t \sim \mathcal{N}(0, \Sigma_w)$$
where the system matrices $(A, B)$ are unknown (model-free setting). The objective is to minimize the average infinite-horizon cost:
$$C(K) = \lim_{T \to \infty} \frac{1}{T} \mathbb{E} \left[ \sum_{t=0}^{T-1} (x_t^\top Q x_t + u_t^\top R u_t) \right]$$
using Policy Gradient (PG) methods.

Key Challenge: Existing theoretical guarantees for model-free PG methods often assume noise-free data or bounded noise. In real-world scenarios with unbounded Gaussian noise, gradient estimates derived from finite trajectory data (using zeroth-order optimization) are inaccurate. This inaccuracy can lead to algorithm divergence or convergence to suboptimal solutions. The paper aims to provide rigorous probabilistic convergence guarantees and sample complexity bounds for model-free PG methods in the presence of such stochastic noise.

2. Methodology

The authors employ a structured approach combining control theory, optimization, and probabilistic analysis:

A. Theoretical Foundations (Model-Based Analysis)

Before tackling the model-free case, the authors establish properties for the cost function $C(K)$ under the assumption of known dynamics:

• Gradient Domination: They prove that $C(K)$ satisfies the gradient domination property (Polyak-Łojasiewicz condition), ensuring that local improvements lead to global convergence.
• Lipschitz Continuity: They establish that the cost function, its gradient, and the state covariance matrix are locally Lipschitz continuous with respect to the policy gain $K$.
• Adaptive Step Sizes: They propose adaptive step size schemes for Policy Gradient Descent (PGD) and Natural Policy Gradient (NPG). Unlike fixed step sizes, these adapt based on the current cost $C(K_i)$, theoretically offering faster convergence rates.

B. Model-Free Estimation with Zeroth-Order Optimization

Since $(A, B)$ are unknown, gradients and covariances are estimated using zeroth-order optimization (function evaluations):

• Perturbation: The algorithm perturbs the current gain $K$ with random matrices $U_k$ to generate trajectories.
• Finite Horizon Approximation: Infinite-horizon costs are approximated using finite rollout lengths ($l$).
• Noise Handling: The authors introduce an event-based analysis to handle the unbounded nature of Gaussian noise. They define failure probabilities related to state boundedness and use matrix concentration inequalities (e.g., Matrix Bernstein) to bound estimation errors.

C. Variance Reduction

To mitigate the high variance inherent in zeroth-order estimates, the authors introduce a variance reduction technique using a baseline function:

• They estimate a baseline $b(x_0)$ representing the expected cost of the current policy starting from the initial state.
• The gradient estimator is modified to $\hat{\nabla} C_v(K) = \frac{1}{n} \sum \frac{N}{r^2} (\hat{C}_{\bar{K}_k} - \hat{b}) U_k$.
• They prove that this reduces the required number of rollouts (sample complexity) to achieve a specific accuracy.

3. Key Contributions

1. Probabilistic Convergence Guarantees:
   The paper provides the first comprehensive analysis of model-free PG methods for infinite-horizon LQR with additive unbounded stochastic noise. It proves that with appropriate parameter tuning, the algorithms converge to the optimal policy within a desired accuracy gap $\epsilon$ with high probability.

2. Explicit Error Bounds and Sample Complexity:
   The authors derive closed-form expressions for the estimation errors of the gradient and covariance. They explicitly decompose the error into:

   • $\epsilon_d$: Error from noisy data.
   • $\epsilon_l$: Error from finite rollout length.
   • $\epsilon_n$: Error from finite number of rollouts.
   • $\epsilon_r$: Smoothing bias.
     They provide formulas for the required number of rollouts ($n$), rollout length ($l$), and exploration radius ($r$) to satisfy these bounds.

3. Adaptive Step Size Schemes:
   The paper proposes adaptive step sizes for both PGD and NPG that depend on the current cost value. Theoretical analysis shows these schemes improve convergence rates compared to fixed step sizes used in prior literature (e.g., [9]).

4. Variance Reduction with Provable Benefits:
   A novel variance reduction technique using a baseline is introduced for the zeroth-order framework. The authors prove that this technique strictly reduces the total sample complexity required to achieve a target accuracy, even when accounting for the cost of estimating the baseline itself.

5. Robustness Analysis:
   The study characterizes the limitations of model-free PG under noise. It demonstrates that while convergence is guaranteed, the convergence rate is slowed by a factor related to the noise level, and the step size must be reduced as noise increases to prevent divergence.

4. Results

• Theoretical Results:

  • Theorem 1 & 2: Establish global convergence for model-based PGD and NPG with adaptive step sizes.
  • Theorem 4 & 5: Provide high-probability error bounds for gradient and covariance estimates in the model-free setting with noise.
  • Theorem 6 & Corollary 1: Prove that variance reduction leads to a provable decrease in the total number of samples required.
  • Theorem 7 & 8: Extend convergence guarantees to model-free PGD and NPG, showing that the cost converges to $C(K^*) + \epsilon$ with probability $1 - \delta$.

• Simulation Results:

  • Noise Impact: Simulations confirm that high noise levels require smaller step sizes to ensure convergence; otherwise, the algorithm diverges.
  • Variance Reduction: In high-noise scenarios, the variance reduction technique significantly accelerates convergence compared to standard zeroth-order estimation.
  • Adaptive vs. Fixed: Adaptive step sizes consistently outperform fixed step sizes, achieving faster convergence rates across different noise levels.
  • NPG Robustness: The Natural Policy Gradient method demonstrates robustness, maintaining accuracy even as noise increases, provided parameters are tuned correctly.

5. Significance

This work bridges a critical gap in reinforcement learning theory for control systems:

• Realism: It moves beyond the idealized assumption of noise-free data, addressing the practical reality of stochastic disturbances in control systems.
• Rigorous Guarantees: It provides the first probabilistic convergence guarantees and sample complexity bounds for model-free LQR with unbounded noise, offering a theoretical foundation for deploying these algorithms in safety-critical applications.
• Practical Guidelines: The derived formulas for step sizes, rollout lengths, and sample counts provide concrete guidelines for practitioners tuning PG algorithms in noisy environments.
• Future Directions: The paper highlights the potential for extending these results to indirect data-driven methods and model-free Gauss-Newton methods, setting a roadmap for future research in robust reinforcement learning.

In summary, the paper establishes that model-free policy gradient methods are robust and convergent for LQR problems with stochastic noise, provided that adaptive step sizes are used and variance reduction techniques are employed to manage the increased sample complexity caused by noise.