TL;DR
This paper bridges the gap between Stochastic Gradient Descent (SGD) theory and Reinforcement Learning for control by providing a unified framework to analyze data-driven Policy Gradient (PG) methods for the Linear Quadratic Regulator (LQR). By modeling gradient estimates as "biased stochastic oracles," the authors prove that both indirect (system-identification-based) and direct (zeroth-order) methods can achieve last-iterate convergence to the global optimum, moving beyond the suboptimality bounds common in prior literature.
What Problem Does This Paper Address?
The Linear Quadratic Regulator (LQR) is the foundational benchmark for continuous control. While we have known since 2018 that policy gradient methods converge globally for LQR when the system model is known, the "data-driven" setting—where we only have noisy trajectory data—is much messier.
Existing data-driven approaches usually fall into two traps:
- High Sample Complexity: They require a massive number of samples at every single iteration to keep gradient errors small.
- Suboptimality: Most theoretical guarantees only prove that the algorithm gets "close" to the optimal policy (converging to a neighborhood) rather than hitting the exact optimum.
The challenge lies in the fact that gradients estimated from data are inherently biased and noisy. This paper asks: Can we use the well-established machinery of Stochastic Gradient Descent (SGD) to design PG methods that are both sample-efficient and guaranteed to find the true optimal policy?
Methods
The authors propose an SGD-based framework where the policy update follows the standard rule: $K_{i+1} = K_i - \eta_i \hat{\nabla} C(K_i)$. The core of the paper is how $\hat{\nabla} C(K_i)$ is constructed and analyzed.
They evaluate two primary estimation schemes:
- Indirect Method: Uses Recursive Least Squares (RLS) to continuously update an estimate of the system matrices ($A, B$). These estimates are then used to compute a model-based gradient. This method is "off-policy" friendly and reuses all historical data.
- Direct Method: A Zeroth-Order Method (ZOM) that approximates the gradient by perturbing the policy and observing the resulting change in cost. This is a "model-free" approach that requires no knowledge of system dynamics.
The Theoretical Innovation: The authors treat these estimators as biased stochastic gradient oracles. They extend SGD convergence theory to functions that are gradient-dominated (a property of LQR that allows global convergence despite non-convexity) and quasi-smooth (a local version of smoothness). They derive specific conditions on step sizes ($\eta_i$) and bias decay rates that guarantee the algorithm converges to the global optimum $K^*$.
Datasets
As a theoretical control paper, the methods are validated using simulated dynamical systems rather than static datasets:
- 3-State Benchmark System: A standard unstable linear system used in prior RL-for-control literature to compare bias and variance of gradient estimators.
- Boeing 747 Longitudinal Dynamics: A more complex 5-state, 4-input system representing the linearized flight dynamics of an aircraft. This serves as a high-dimensional test for the convergence of the proposed SGD algorithms.
Key Insights and Ideas
- Bias is a Feature, Not Just a Bug: Instead of trying to eliminate bias (which is impossible with finite data), the authors show that as long as the bias decays at a sufficient rate (e.g., $O(i^{-1/2})$), the SGD iterates will still find the optimum.
- The Sample Complexity Gap: A major "aha moment" is the quantitative comparison between the two methods. The Indirect method is significantly more efficient, requiring only $O(1)$ new samples per iteration because it reuses past data via RLS. In contrast, the Direct method requires $O(i^2)$ samples per iteration to maintain the necessary bias/variance balance for convergence.
- Last-Iterate Convergence: Unlike many previous works that rely on "experience replay" or "mini-batching" to stay in a stable region, this framework proves that the current policy iterate converges to the optimum, which is crucial for online deployment.
- Quasi-smoothness Matters: LQR costs aren't globally Lipschitz smooth (the gradient can explode near the boundary of stability). By using "quasi-smoothness," the authors provide a more mathematically rigorous treatment of the LQR geometry.
Key Results
- Asymptotic Convergence: Theorems 3 and 4 provide the "holy grail" for these algorithms: proof that the cost $C(K_i)$ converges to the optimal $C(K^*)$ almost surely.
- Rate of Convergence: The authors show that the suboptimality gap $E[C(K_i) - C(K^*)]$ vanishes at a rate of $o(i^{-(1-\lambda)})$ for a range of step-size parameters.
- Numerical Validation: Simulations confirm that while constant step-size/fixed-parameter methods hit a "performance floor" (suboptimality), the proposed adaptive schedules (decreasing step size, increasing rollout length) successfully drive the error toward zero.
Limitations and Future Work
- Initial Stability: The indirect method requires an "initial data collection phase" to ensure the first model estimate is stabilizing. If the initial $K_0$ is poor or the initial model is too inaccurate, the system could diverge before the SGD kicks in.
- Direct Method Practicality: While the direct method is theoretically sound, the requirement for an "unbounded increase" in samples per iteration makes it difficult to scale to very long-running real-world missions.
- Constraints: The current work focuses on unconstrained LQR. Real-world engineering often involves state and input constraints (e.g., actuator limits), which the authors identify as a promising direction for future research.
- Joint Stability: Future work is needed to analyze the "interconnected" stability of the learning algorithm and the physical system simultaneously.
Summary updated