Biased Stochastic Gradient Descent under Local Geometry, with Application to Data-Driven LQR
summary
The gist
In this work, we propose a stochastic gradient descent (SGD) framework to design data-driven policy gradient descent algorithms for the linear quadratic regulator problem Problem Formulation and Cost…
In short
This work proposes a Stochastic Gradient Descent (SGD) framework to design data-driven policy gradient algorithms for the Linear Quadratic Regulator (LQR) problem under stochastic noise. It analyzes two gradient estimation methods—indirect and direct—showing how to ensure convergence by satisfying specific conditions on step size and oracle properties, ultimately proving that both approaches can find the optimal policy.
Key concepts
- Gradient Domination
- This property means the cost function's difference between a current point and the optimum is bounded by a multiple of the squared norm of its gradient. This mathematical relationship is crucial because it allows researchers to analyze how quickly SGD approaches the minimum, providing a fundamental guarantee for convergence analysis.
- Gradient Oracle
- A gradient oracle formalizes how we estimate the true gradient using data from stochastic trajectories. The paper characterizes these oracles by their first and second moments, which are statistical measures of the estimator's bias and variance. These characterizations are used to prove that SGD converges correctly.
- Indirect Method
- This estimation technique uses recursive least squares to estimate the system matrices from data collected during operation. Once these matrices are estimated, a model-based gradient is computed. This method requires local persistency of data for convergence and has a low per-iteration sample complexity of O(1).
- Direct Method
- This zeroth-order approach approximates the gradient directly from empirical cost evaluations without explicitly estimating system matrices. It relies on finite-horizon rollouts and can only be used in an on-policy setting. The paper shows that an adaptive strategy, like decreasing exploration radius, improves its performance.
Terminology used across episodes
This episode discusses
- Biased Stochastic Gradient Descent under Local Geometry, with Application to Data-Driven LQR · Paper Radio
- Efficient Model-Based Reinforcement Learning for Robot Control via Online Optimization
- Perturbed Gradient Descent Algorithms are Small-Disturbance Input-to-State Stable · Paper Radio
- Policy Gradient Adaptive Control for the LQR: Indirect and Direct Approaches
- Finite-Sample Analysis of Model-free Policy Gradient Methods for LQR with Stochastic Data · Paper Radio
- Handbook of Convergence Theorems for (Stochastic) Gradient Methods
- On the Robustness of Derivative-free Methods for Linear Quadratic Regulator
- Optimal Local Convergence Rates of Stochastic First-Order Methods under Local alpha-PL
- Better Theory for SGD in the Nonconvex World
The paper
Biased Stochastic Gradient Descent under Local Geometry, with Application to Data-Driven LQR · Read on arXiv
International Max Planck Research School for Intelligent Systems Institute for Systems Theory and Automatic Control University of Stuttgart Institute for Mathematics University of Mannheim
Transcript
Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.
Rosa: I'm Rosa.
Dev: And I'm Dev, here with Taro.
Rosa: We're looking at the paper: "Biased Stochastic Gradient Descent under Local Geometry, with Application to Data-Driven LQR".
Dev: Here's the gist of the paper. In this work, we propose a stochastic gradient descent (SGD) framework to design data-driven policy gradient descent algorithms for the linear quadratic regulator problem Problem Formulation and Cost Function Analysis The paper considers an averaged infinite horizon optimal control problem where the plant is subject to additive stochastic noise.
Rosa: The objective is to minimize the infinite-horizon average cost under a linear policy ut = Kxt with K ∈ S.
Dev: The gradient of this cost function C(K) is given by ∇C(K) = 2EKΣK.
Rosa: Key properties of the cost function include gradient domination, where C(K) − C(K∗) ≤ µ∥∇C(K)∥2F, and quasi-smoothness, which is quantified by Lemma 4.
Title and authors: Rosa: The paper we are discussing today is called "Biased Stochastic Gradient Descent under Local Geometry, with Application to Data-Driven LQR". This study focuses on designing policy gradient descent algorithms for the linear quadratic regulator problem.
Dev: It's authored by Bowen Song, Simon Weissmann, Mathias Staudigl, and Andrea Iannelli. They are looking at how to use stochastic gradient descent in a data-driven way for this control problem.
Taro: The title hints that they are dealing with some geometric constraints or local geometry in the analysis of these gradient estimates > Page one <ref:2602.18933#pg1> <ref:2602.18933#pg1>
Rosa: Right, it means they are accounting for the specific structure of the cost function when estimating those gradients from noisy data > Page one <ref:2602.18933#pg1> <ref:2602.18933#pg1>
Dev: They propose two schemes: an indirect approach based on online identification and a direct zeroth-order approach using empirical cost evaluations > Page one <ref:2602.18933#pg1> <ref:2602.18933#pg1,a direct zeroth-order approach>
Taro: These two approaches are what they are comparing to see which one is better for actual use in policy gradient methods > Page two <ref:2602.18933#pg2> <ref:2602.18933#pg2>
Rosa: The authors are showing how these gradient estimates, because of the way they are computed, are inherently random due to the stochasticity in the data itself > Page one <ref:2602.18933#pg1> <ref:2602.18933#pg1,because of the way they are computed, are inherently>
Dev: And that randomness is what allows them to use SGD theory to analyze the convergence of those policy gradient methods > Page two <ref:2602.18933#pg2> <ref:2602.18933#pg2>
Taro: So, they are treating these estimates as stochastic gradient oracles, which is a key technical step in their analysis > Page one <ref:2602.18933#pg1> <ref:2602.18933#pg1>
Rosa: That modeling step is what lets them use the SGD framework to derive sufficient conditions for convergence > Page one <ref:2602.18933#pg1> <ref:2602.18933#pg1>
The paper's summary: Dev: So, to summarize the main point of this paper, they are developing a stochastic gradient descent framework specifically for designing policy gradient descent algorithms for the linear quadratic regulator problem under stochastic noise.
Taro: They are tackling the core problem of how to design these data-driven algorithms when you have additive stochastic noise in a continuous state and action space > Page one <ref:2602.18933#pg1> <ref:2602.18933#pg1>
Rosa: The paper proposes two alternative schemes for estimating the policy gradient from stochastic trajectory data: an indirect online identification-based approach, which estimates system matrices first, and a direct zeroth-order approach that approximates the gradient directly from empirical cost evaluations > Page one <ref:2602.18933#pg1> <ref:2602.18933#pg1,the policy gradient from stochastic trajectory data>
Dev: They are also making sure to characterize these as gradient oracles with analytical characterizations of their first and second moments > Page two <ref:2602.18933#pg2> <ref:2602.18933#pg2>
Taro: The analysis relies on Lemma seven and Lemma eight to characterize the first and second moments of both the indirect and direct estimators > Page two <ref:2602.18933#pg2> <ref:2602.18933#pg3>
Rosa: This is where they establish the core mathematical machinery for analyzing convergence under gradient-dominated and quasi-smooth function assumptions > Page one <ref:2602.18933#pg1> <ref:2602.18933#pg1>
Dev: They then use this machinery to show that under these assumptions, SGD with a biased gradient oracle converges asymptotically to the optimal policy > Page two <ref:2602.18933#pg2> <ref:2602.18933#pg2>
Taro: The result is that Theorem two establishes sufficient conditions on step size choices to ensure convergence both in expectation and almost surely > Page one <ref:2602.18933#pg1> <ref:2602.18933#pg3>
The paper's improvements: Rosa: They suggest two major improvements by comparing the indirect and direct policy gradient methods based on their sample complexity, excitation policy requirements, and data collection strategies > Page two <ref:2602.18933#pg2> <ref:2602.18933#pg2>
Dev: For the indirect method, they show that it requires local persistency of the data sequence to ensure convergence > Page two <ref:2602.18933#pg2> <ref:2602.18933#pg2>
Taro: The direct method relies on finite-horizon rollouts and can only be implemented in an on-policy setting > Page one <ref:2602.18933#pg1> <ref:2602.18933#pg1>
Rosa: In terms of per-iteration sample complexity, the indirect method is shown to have O(one) new samples, but the direct method needs O(i squared) data per iteration > Page two <ref:2602.18933#pg2> <ref:2602.18933#pg3>
Dev: That difference in data requirement is a big factor when you're thinking about how much data you need to collect for these methods > Page two <ref:2602.18933#pg2> <ref:2602.18933#pg2>
Taro: The paper also points out that the indirect method is shown to have a per-iteration sample complexity of O(one) new samples, while the direct method requires O(i squared) data per iteration > Page two <ref:2602.18933#pg2> <ref:2602.18933#pg3>
Rosa: Plus, they show that increasing amounts of data lead to different gradient estimates at different iterations for both methods, which means we need a decreasing step-size schedule to keep things converging > Page one <ref:2602.18933#pg1> <ref:2602.18933#pg1>
Dev: And in the direct method, an adaptive strategy improves performance by gradually decreasing parameters like exploration radius v and rollout length l i, which helps reduce the bias term while maintaining a uniformly bounded second moment > Page three <ref:2602.18933#pg3> <ref:2602.18933#pg3>
Taro: That adaptive strategy in the direct method is what makes it better than prior zeroth-order frameworks because it leads to better convergence behavior > Page three <ref:2602.18933#pg3> <ref:2602.18933#pg3>
Conclusion: Rosa: So, wrapping up, the main implication of this work is that both indirect and direct methods can achieve convergence to the optimal policy under appropriate parameter tuning > Page one <ref:2602.18933#pg1> <ref:2602.18933#pg1>
Dev: They establish explicit conditions on step size choices and gradient accuracy under which SGD converges to the optimal cost > Page two <ref:2602.18933#pg2> <ref:2602.18933#pg2>
Taro: The adaptive strategy in the direct method in the direct method is what makes it better than prior zeroth-order frameworks because it leads to better convergence behavior > Page three <ref:2602.18933#pg3> <ref:2602.18933#pg3>
Rosa: So, to summarize, this paper "Biased Stochastic Gradient Descent under Local Geometry, with Application to Data-Driven LQR" provides a framework for designing data-driven policy gradient algorithms for the LQR problem under stochastic disturbances > Page one <ref:2602.18933#pg1> <ref:2602.18933#pg1>
More episodes
- 2608.13438-ContactGuard: Pre-Contact Execution Monitoring with Action-Conditioned Latent World Models
- 2610.34593-Future Prediction as Training-Only Video Supervision for Pretrained VLA Policies
- 2610.35385-EmbodiedLab: Beyond Manipulation, Benchmarking Embodied Agents That Act to Know
- 2610.36378-Data-Driven Hamiltonian for Neural Optimal Control
- 2610.37275-A Heuristic for Scheduling Autonomous Vehicles at Intersections
- 2610.37288-Dynamic Coordination of Autonomous Vehicles at Intersections
- 2610.37632-Real-Time Coordination of Autonomous Vehicles at Intersections
- 2611.13779-Softness is something you also need! Why compliance helps control: information metrics of a passive walker with compliant ankle
- 2611.13411-Residual-Corrected Physics-Informed Neural Network KKL Observers with Input-to-State Stability Guarantees
- 2611.14488-Is Your Robot's Memory Just a Clock? Temporal Shortcuts in Memory-Augmented VLA Policies