Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds

arXiv:2610.03165v1 Announce Type: new Abstract: Several variance-reduced versions of REINFORCE based on importance sampling achieve an improved O(epsilon^{-3}) sample complexity to find an epsilon-stationary point, under an unrealistic assumption on the variance of the importance weights. In this paper, we propose the algo (Defensive Policy Gradient) algorithm, based on defensive importance sampling, which achieves the same rate without any assumption on the variance of ordinary importance weights. We also establish lower bounds in a generalized black-box policy-optimization model that hides states and actions and permits parameter-dependent rewards. In this model, the optimal rates are Theta(epsilon^{-4}) with bounded-variance one-policy feedback and Theta(epsilon^{-3}) with mean-square-smooth coupled two-policy feedback. Under standard policy-regularity conditions, REINFORCE and algo realize the corresponding oracle conditions and attain the O(epsilon^{-4}) and O(epsilon^{-3}) upper bounds, respectively. Although the lower bounds do not apply directly to the classical MDP interaction model in which these algorithms operate, this correspondence provides oracle-level evidence that the faster rate of algo is optimal and genuinely separated from that of vanilla policy gradient.

Related

• Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL
• Constrained Policy Optimization via Sampling-Based Weight-Space Projection
• LoRA Scaffolded Policy Optimization (LSPO): A Sampling-Time Low-Rank Scaffold for Recovering Reinforcement-Learning Gradient on Zero-Reward Cliff Prompts
• Rennala MVR: Improved Time Complexity for Parallel Stochastic Optimization via Momentum-Based Variance Reduction
• Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization

Source: arXiv cs.LG | 2026-10-05