Sample Complexity of Policy Gradient for Log-Growth Control
On the map: Deep reinforcement learning methods → RL theory and sample complexity
Abstract (arXiv)
We study the sample complexity of policy gradient for log-growth control -- the problem of learning, from observed state transitions, a feedback gain that optimally stabilizes a scalar linear system driven through a multiplicative-noise actuation channel. The objective J(K) = mathbbE[log|1+BK|] is the top Lyapunov exponent of the closed loop. This problem carries a structural difficulty we call the cusp obstruction: the optimal gain K^* always places the noise singularity brm sing(K) = -1/K in the interior of the support. At this singular optimum the policy gradient exists only as a Cauchy principal value, not as a Lebesgue integral, and the natural single-sample gradient estimator has infinite variance. Standard first-order stochastic-optimization analysis is thus inapplicable at the optimum, and merely smoothing the objective does not resolve the difficulty. The obstruction, however, has an exploitable symmetry: the Cauchy kernel is an odd function of the displacement from the moving pole, so pairing each observation with its reflection through the pole cancels the divergent part. This one cancellation simultaneously controls the population curvature, the gradient-estimator variance, and the bias incurred when the noise density is estimated. Combining these bounds with a closed-form single-transition gradient oracle, we prove that projected mini-batch policy gradient, initialized in any compact subset of the stabilizing region, attains total sample complexity tildeO(1/η) when the noise density is known and tildeO(η-(2s+1)/(2s)) when it must be estimated, for Cs noise densities with s ≥ 2.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 13 of its 36 references that are in the map. First posted on arXiv 26 May 2026.
Builds on
13 of 36 references.
References · 13
- 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
- 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
- 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 250
- 2018Stochastic model-based minimization of weakly convex functionscited by 159
- 2019Conservative set valued fields, automatic differentiation, stochastic gradient method and deep learningcited by 72
- 2018Derivative-Free Methods for Policy Optimization: Guarantees for Linear Quadratic Systemscited by 67
- 2020Policy Gradient Methods for the Noisy Linear Quadratic Regulator over a Finite Horizoncited by 50
- 2019Convergence and sample complexity of gradient methods for the model-free linear quadratic regulator problemcited by 46
- 2018The Gap Between Model-Based and Model-Free Methods on the Linear Quadratic Regulator: An Asymptotic Viewpointcited by 40
- 2019LQR through the Lens of First Order Methods: Discrete-time Casecited by 40
- 2022Convergence of policy gradient methods for finite-horizon exploratory linear-quadratic control problemscited by 25
- 2015A variational formula for risk-sensitive rewardcited by 3
1 more
- 2017Control Capacitycited by 1
Built on by
Not cited yet.
Similar, not cited
Close in wording, no citation either way
- 2025Logit Dynamics in Softmax Policy Gradient Methods
- 2024Towards Provable Log Density Policy Gradient
- 2025Equivalence of stochastic and deterministic policy gradients
- 2026Learning and Control Beyond Linearity: Towards a Non-asymptotic Theory for Bilinear Systems
- 2026How Log-Barrier Helps Exploration in Policy Optimization
- 2026Achieving ε-2 Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions
- 2025Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learning
- 2026Variance-Reduced Policy Gradient is Nearly Minimax-Optimal