Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies

Ilyas FatkhullinAnas BarakatAnastasia KireevaNiao He

article2023ICML66 citations

Establishes improved global sample complexities of $\tilde{\mathcal{O}}(\varepsilon^{-2.5})$ and $\tilde{\mathcal{O}}(\varepsilon^{-2})$ for Fisher-non-degenerate parameterized policies through computationally efficient, single-loop stochastic policy gradient algorithms that bypass the need for importance sampling weights.

Listen

Policy gradient methods have achieved widespread empirical success in complex reinforcement learning tasks, such as robotics and continuous control. However, their theoretical foundations remain incomplete. Because the policy optimization objective is generally non-concave, finding a globally optimal policy using only stochastic trajectory simulations usually demands massive amounts of sample data. Existing approaches often rely on importance sampling, which requires strong and unverifiable mathematical assumptions, or on computationally expensive second-order subroutines. Developing efficient, lightweight algorithms that guarantee global convergence with improved sample efficiency is essential for reducing data collection costs and compute requirements.

The article establishes improved theoretical sample complexity guarantees for finding globally optimal policies within the broad class of Fisher-non-degenerate parameterized policies, which includes standard continuous Gaussian policies. It evaluates whether simple, single-loop policy gradient algorithms can surpass established sample complexity thresholds without resorting to large batch sizes, importance sampling mechanisms, or costly computational subroutines.

To address this challenge, the authors design and analyze two algorithmic frameworks. The first, Normalized Policy Gradient with Implicit Gradient Transport, uses momentum and an extrapolative look-ahead update step to leverage the objective's curvature without explicitly calculating second-order derivatives. The second, Hessian-Aided Recursive Policy Gradient—evaluated in both normalized and unnormalized forms—uses efficient Hessian-vector products to correct distribution shifts between consecutive iterations. The authors mathematically prove global convergence rates by exploiting a relaxed weak gradient dominance condition and evaluate the methods empirically across standard continuous-control benchmark environments against traditional policy gradient methods.

The theoretical analysis demonstrates that Normalized Policy Gradient with Implicit Gradient Transport achieves a sample complexity of order eps^(-2.5) for finding a globally eps-optimal policy, improving over the classical baseline of eps^(-3) while sampling only one trajectory per iteration. The Hessian-Aided Recursive Policy Gradient methods further improve sample complexity to order eps^(-2) using at most two trajectory samples per iteration and maintaining linear per-iteration compute and memory costs. Empirically, Normalized Policy Gradient with Implicit Gradient Transport significantly outperformed other methods on benchmark environments like Humanoid and Walker2d, showing superior reward progression and robustness across a wide range of learning rates. In contrast, while Hessian-aided methods performed well at very small learning rates, they underperformed baselines when learning rates were tuned, primarily due to the high empirical variance of stochastic Hessian estimates.

These findings prove that policy gradient algorithms can achieve near-optimal sample efficiency without sacrificing computational simplicity or relying on problematic importance sampling assumptions. In practice, Normalized Policy Gradient with Implicit Gradient Transport offers a compelling balance: it accelerates convergence, simplifies hyperparameter tuning, and lowers execution overhead by eliminating large batch requirements and matrix inversions.

For practitioners and engineering teams, the article supports adopting Normalized Policy Gradient with Implicit Gradient Transport as an efficient, robust alternative to standard policy gradient methods in continuous action settings. For teams considering Hessian-aided methods, careful attention should be paid to the trade-off between theoretical efficiency and the variance of Hessian estimates, which currently limits their practical utility when learning rates are aggressively tuned. Further research should focus on variance-reduction techniques for stochastic Hessian estimates and testing these methods on broader policy parameterizations and complex industrial environments.

The theoretical guarantees are derived under specific structural conditions, including Fisher-non-degeneracy and bounded approximation transfer errors, which generally hold for Gaussian policies but may fail for near-deterministic softmax policies. While theoretical confidence in the convergence proofs is high, practitioners should exercise caution regarding the empirical performance of Hessian-assisted variants until variance-related sensitivities in high-dimensional tasks are fully resolved.

Amazon ETH Zurich Purdue University computational efficiency deterministic gaussians stochastic policy gradient methods sample complexity Fisher information

arXiv: 2302.01734 aabkn/Stochastic-Policy-Gradient-Methods

Paper: Policy Gradient Methods for Reinforcement Learning with Function Approximation, Richard S. Sutton et al. (1999). The source’s trajectory-based policy-gradient analysis builds on the Policy Gradient Theorem’s connection between expected-return derivatives and action-value-weighted policy changes.
Paper: A Natural Policy Gradient, Sham M. Kakade (2001). Kakade’s Fisher-metric natural gradient provides the geometric policy-optimization foundation for understanding the source’s Fisher-non-degeneracy and normalized updates.
Paper: Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming, Saeed Ghadimi et al. (2013). Its stochastic nonconvex convergence and sample-complexity framework supplies useful context for the source’s improved guarantees over conventional stochastic-gradient rates.

No sufficiently relevant recommendations were found.

Cover for Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies

1. Introduction
1.1. Summary of contributions
1.2. Related work
2. Preliminaries
2.1. Problem formulation
2.2. First order stationarity and global optimality
2.3. Policy gradient and Hessian
3. Normalized Momentum-Based Policy Gradient Algorithms
3.1. Normalized PG with Implicit Gradient Transport
3.2. Hessian-Aided Recursive Policy Gradient
4. Global Convergence Analysis
4.1. Assumptions
4.2. Convergence analysis of N-PG-IGT
4.3. Convergence analysis of (N)-HARPG
5. Experiments
5.1. Comparison with tuned initial step-sizes
5.2. Robustness to initial step-sizes
6. Concluding Remarks
Acknowledgements
References
Appendix
A. Additional Experiments and Implementation Details
A.1. Experiment 1: Comparison with tuned initial step-sizes
A.2. Experiment 2: Robustness to initial step-sizes
A.3. Experiment 3: Comparison of Vanilla-PG and HARPG with small untuned step-sizes
A.4. Experiment 4: Additional comparison to other methods with tuned step-sizes
A.5. Experiment 5: Performance under the soft-max parameterization for discrete state-action space
B. Further Discussion of Assumptions from Section 4.1
B.1. Gaussian policy
B.2. Cauchy policy
C. Proof Sketch of the Main Results
D. Further Related Work
D.1. First-order stationarity for variance-reduced PG methods
D.2. Global optimality of exact PG methods
D.3. Further discussion about stochastic policy optimization
D.4. Comparison to prior work in stochastic optimization
E. Notation and Useful Lemma
F. Proof of Theorem 1 ( N-PG-IGT )
F.1. Global convergence
F.2. Convergence to first order stationary point
G. Proof of Theorem 2 ( HARPG )
H. Proof of Theorem 3 ( N-HARPG )
I. Convergence Analysis of Normalized-Momentum Policy Gradient Method ( N-MPG )
J. Technical Lemma
J.1. Lemma for solving recursions
J.2. Lemma for decreasing step-sizes estimates

Knowls

Knowl 1 — Fisher non-degeneracy and policy approximation assumptions
assumption
Consider a discounted Markov decision process with discount factor $\gamma\in(0,1)$ and a differentiable policy $\pi_\theta$ , parameterized by $\theta\in\mathbb{R}^d$ . Let $d_\rho^{\pi_\theta}$ denote its normalized discounted state-visitation distribution, and define the Fisher information matrix
$F_\rho(\theta)=\mathbb{E}_{s\sim d_\rho^{\pi_\theta},\,a\sim\pi_\theta(\cdot\mid s)}[\nabla_\theta\log\pi_\theta(a\mid s)\nabla_\theta\log\pi_\theta(a\mid s)^\top].$
The Fisher-non-degeneracy condition requires a constant $\mu_F>0$ such that $F_\rho(\theta)\succeq\mu_F I_d$ for every $\theta$ . The policy family is also assumed to approximate advantages through its score functions: for an optimal policy $\pi^*$ , its advantage function $A^{\pi_\theta}$ , and $w^*(\theta)=F_\rho(\theta)^\dagger\nabla J(\theta)$ , require
$\mathbb{E}_{s\sim d_\rho^{\pi^*},\,a\sim\pi^*(\cdot\mid s)}\left[(A^{\pi_\theta}(s,a)-(1-\gamma)w^*(\theta)^\top\nabla_\theta\log\pi_\theta(a\mid s))^2\right]\leq\varepsilon_{\rm bias}$
for every $\theta$ . Here $J(\theta)$ is the expected discounted return and $F_\rho(\theta)^\dagger$ is the pseudoinverse. The term $\varepsilon_{\rm bias}$ measures the policy class's compatible-function-approximation error; it need not be zero. Gaussian policies with suitable full-rank mean Jacobians are examples discussed by the paper, while softmax policies can fail the Fisher lower bound near deterministic policies.
Knowl 2 — Relaxed gradient dominance for Fisher-non-degenerate policies
theoretical result
For a discounted policy-optimization problem, suppose rewards are bounded by $r_{\max}$ , the policy score satisfies $\|\nabla_\theta\log\pi_\theta(a\mid s)\|\leq M_g$ , and the Fisher and compatible-approximation conditions hold with constants $\mu_F$ and $\varepsilon_{\rm bias}$ as defined here: $F_\rho(\theta)\succeq\mu_F I_d$ for every parameter, and the squared error in approximating $A^{\pi_\theta}$ by $(1-\gamma)w^*(\theta)^\top\nabla_\theta\log\pi_\theta$ under $s\sim d_\rho^{\pi^*},a\sim\pi^*(\cdot\mid s)$ is at most $\varepsilon_{\rm bias}$ , where $w^*(\theta)=F_\rho(\theta)^\dagger\nabla J(\theta)$ . Then the expected return obeys the relaxed weak gradient-dominance inequality
$\varepsilon' + \|\nabla J(\theta)\|\geq\sqrt{2\mu\,(J^*-J(\theta))},\qquad \varepsilon'=\frac{\mu_F\sqrt{\varepsilon_{\rm bias}}}{M_g(1-\gamma)},\quad \mu=\frac{\mu_F^2}{2M_g^2}.$
Here $J^*=\max_\theta J(\theta)$ , and $\theta\in\mathbb{R}^d$ . This structure links return suboptimality to the gradient norm, up to a floor caused by policy approximation; it is the key property used to turn the algorithms' stochastic-gradient error bounds into global-return guarantees.
Knowl 3 — Normalized policy gradient with implicit gradient transport
algorithm
N-PG-IGT maximizes the expected discounted return using a normalized momentum estimate evaluated at a look-ahead parameter. Let $\theta_t\in\mathbb{R}^d$ be the policy parameter, $d_t\in\mathbb{R}^d$ the momentum direction, $\eta_t\in(0,1]$ the momentum weight, and $\alpha_t>0$ the step size. For a length- $H$ trajectory $\tau=(s_0,a_0,\ldots,s_{H-1},a_{H-1})$ , define the truncated policy-gradient estimator
$g(\tau,\theta)=\sum_{t=0}^{H-1}\left(\sum_{h=t}^{H-1}\gamma^h r(s_h,a_h)\right)\nabla_\theta\log\pi_\theta(a_t\mid s_t),$
where $r$ is the reward and $\gamma$ is the MDP discount factor. Initialize $\theta_0,\theta_1,d_0$ and, for $t=1,\ldots,T-1$ , perform:
Input: $\theta_0$ , $\theta_1$ , $d_0$ , iteration count $T$ , step sizes $\{\alpha_t\}$ , momentum weights $\{\eta_t\}$ , trajectory horizon $H$
for $t=1,\ldots,T-1$
    Set $\widetilde{\theta}_t=\theta_t+\frac{1-\eta_t}{\eta_t}(\theta_t-\theta_{t-1})$
    Sample one length- $H$ trajectory $\widetilde{\tau}_t$ using policy $\pi_{\widetilde{\theta}_t}$
    Set $d_t=(1-\eta_t)d_{t-1}+\eta_t g(\widetilde{\tau}_t,\widetilde{\theta}_t)$
    If $d_t\neq 0$ , set $\theta_{t+1}=\theta_t+\alpha_t d_t/\|d_t\|$ ; otherwise set $\theta_{t+1}=\theta_t$
end for
return $\theta_T$
The look-ahead parameter is chosen so that $\theta_t=\eta_t\widetilde{\theta}_t+(1-\eta_t)\theta_{t-1}$ . The convergence analysis uses $\alpha_t=6M_g/[\mu_F(t+2)]$ , $\eta_t=(2/(t+2))^{4/5}$ , and $H=(1-\gamma)^{-1}\log(T+1)$ . The method uses one trajectory per iteration, does not use importance sampling, and does not require Hessian estimates.
Knowl 4 — Hessian-aided recursive policy gradient
algorithm
HARPG and its normalized variant N-HARPG maintain a recursive policy-gradient estimate and correct its drift with a Hessian-vector product. Let $g(\tau,\theta)$ be the length- $H$ truncated policy-gradient estimator defined by the reward-to-go times the policy score. For a trajectory $\tau$ , define the sample Hessian estimator $B(\tau,\theta)=\nabla_\theta\Phi(\tau,\theta)\nabla_\theta\log p(\tau\mid\pi_\theta)^\top+\nabla_\theta^2\Phi(\tau,\theta)$ , where $p(\tau\mid\pi_\theta)$ is the trajectory density and $\Phi(\tau,\theta)=\sum_{t=0}^{H-1}(\sum_{h=t}^{H-1}\gamma^h r(s_h,a_h))\log\pi_\theta(a_t\mid s_t)$ . Initialize $\theta_0,\theta_1,d_0$ . At iteration $t=1,\ldots,T-1$ , draw $q_t$ uniformly from $[0,1]$ , set $\widehat\theta_t=q_t\theta_t+(1-q_t)\theta_{t-1}$ , and sample independent length- $H$ trajectories $\tau_t\sim p(\cdot\mid\pi_{\theta_t})$ and $\widehat\tau_t\sim p(\cdot\mid\pi_{\widehat\theta_t})$ . Then compute
$v_t=B(\widehat\tau_t,\widehat\theta_t)(\theta_t-\theta_{t-1}),\qquad d_t=(1-\eta_t)(d_{t-1}+v_t)+\eta_tg(\tau_t,\theta_t).$
For HARPG use $\theta_{t+1}=\theta_t+\alpha_t d_t$ ; for N-HARPG use $\theta_{t+1}=\theta_t+\alpha_t d_t/\|d_t\|$ when $d_t\ne0$ (leave $\theta_t$ unchanged if it is zero). The uniform interpolation makes the Hessian correction an unbiased estimate of the gradient change along the segment between consecutive parameters. Each iteration uses two trajectories, without importance sampling. The convergence analysis uses decreasing momentum weights; N-HARPG uses $\eta_t=2/(t+2)$ and $\alpha_t=6M_g/[\mu_F(t+2)]$ .
Knowl 5 — Global sample complexity of N-PG-IGT
theoretical result
Consider a discounted MDP with $|r(s,a)|\leq r_{\max}$ and discount $\gamma\in(0,1)$ . Assume the positive policy density is twice continuously differentiable, its score norm is bounded by $M_g$ , its log-policy Hessian is bounded by $M_h$ , and that Hessian is Lipschitz in the parameter. Also assume Fisher non-degeneracy $F_\rho(\theta)\succeq\mu_F I_d$ and compatible-advantage approximation error at most $\varepsilon_{\rm bias}$ , with the Fisher matrix and error defined by the policy's discounted state distribution and optimal-policy transfer distribution. For N-PG-IGT, take $\alpha_t=6M_g/[\mu_F(t+2)]$ , $\eta_t=(2/(t+2))^{4/5}$ , and trajectory horizon $H=(1-\gamma)^{-1}\log(T+1)$ . The expected return gap of its final iterate satisfies
$J^*-\mathbb{E}[J(\theta_T)]\leq\mathcal{O}\!\left(\frac{\sigma_g+L_h}{(T+1)^{2/5}}\right)+\frac{\sqrt{\varepsilon_{\rm bias}}}{1-\gamma},$
where $\sigma_g^2=r_{\max}^2M_g^2/(1-\gamma)^3$ bounds the variance of the truncated stochastic gradient and $L_h$ is a Lipschitz constant for the Hessian of $J$ . Thus, to obtain expected suboptimality at most $\varepsilon+\sqrt{\varepsilon_{\rm bias}}/(1-\gamma)$ requires $\widetilde{\mathcal{O}}(\varepsilon^{-5/2})$ trajectory samples. The Lipschitz-Hessian regularity is needed for this guarantee, even though the algorithm itself does not compute Hessians.
Knowl 6 — Global sample complexity of HARPG
theoretical result
Consider a discounted MDP with bounded rewards $|r(s,a)|\leq r_{\max}$ and discount $\gamma\in(0,1)$ . Suppose the policy is positive and twice continuously differentiable, with $\|\nabla_\theta\log\pi_\theta(a\mid s)\|\leq M_g$ and $\|\nabla_\theta^2\log\pi_\theta(a\mid s)\|\leq M_h$ . Assume also $F_\rho(\theta)\succeq\mu_F I_d$ and compatible-advantage approximation error at most $\varepsilon_{\rm bias}$ under the optimal-policy transfer distribution. No Lipschitz-Hessian assumption on $J$ is required. With a decreasing momentum weight and step sizes of the form $\alpha_t=\alpha_0\sqrt{\eta_t}$ , where $\alpha_0$ is chosen sufficiently small according to the smoothness, stochastic-gradient and Hessian-estimator variance bounds, HARPG's final iterate obeys
$J^*-\mathbb{E}[J(\theta_T)]\leq\mathcal{O}\!\left(\frac{\sigma_g+L_g+\sigma_h}{\sqrt{T+1}}\right)+\frac{2\sqrt{\varepsilon_{\rm bias}}}{1-\gamma}.$
Here $L_g=r_{\max}(M_g^2+M_h)/(1-\gamma)^2$ , $\sigma_g^2=r_{\max}^2M_g^2/(1-\gamma)^3$ , and $\sigma_h$ bounds the stochastic Hessian-estimator deviation; for horizon $H$ , the paper gives $\sigma_h^2=r_{\max}^2(H^2M_g^4+M_h^2)/(1-\gamma)^4$ . Choosing $H$ logarithmic in $T$ yields a global sample complexity of $\widetilde{\mathcal{O}}(\varepsilon^{-2})$ to reach return gap at most $\varepsilon+2\sqrt{\varepsilon_{\rm bias}}/(1-\gamma)$ . HARPG uses unnormalized updates and does not require importance sampling.
Knowl 7 — Global sample complexity of N-HARPG
theoretical result
For a discounted MDP with bounded rewards and discount $\gamma\in(0,1)$ , assume a positive twice continuously differentiable policy with bounded score and bounded log-policy Hessian, Fisher non-degeneracy $F_\rho(\theta)\succeq\mu_F I_d$ , and compatible-advantage approximation error at most $\varepsilon_{\rm bias}$ . N-HARPG needs no Lipschitz-Hessian condition. Set $\eta_t=2/(t+2)$ , $\alpha_t=6M_g/[\mu_F(t+2)]$ , and $H=(1-\gamma)^{-1}\log(T+1)$ . Its normalized final iterate satisfies
$J^*-\mathbb{E}[J(\theta_T)]\leq\mathcal{O}\!\left(\frac{\sigma_g+L_g+\sigma_h}{\sqrt{T+1}}\right)+\frac{\sqrt{\varepsilon_{\rm bias}}}{1-\gamma},$
where $M_g$ bounds the score norm, $M_h$ bounds the log-policy Hessian, $L_g=r_{\max}(M_g^2+M_h)/(1-\gamma)^2$ , $\sigma_g^2=r_{\max}^2M_g^2/(1-\gamma)^3$ , and $\sigma_h^2=r_{\max}^2(H^2M_g^4+M_h^2)/(1-\gamma)^4$ bounds the Hessian-estimator variance. Consequently, the sample complexity is $\widetilde{\mathcal{O}}(\varepsilon^{-2})$ for return gap at most $\varepsilon+\sqrt{\varepsilon_{\rm bias}}/(1-\gamma)$ . This normalized variant uses two trajectories per iteration and no importance sampling.
Knowl 8 — Hessian correction can be implemented with Hessian-vector products
model/method
The HARPG correction does not require forming or storing a full trajectory Hessian matrix. For the sample Hessian estimator $B(\tau,\theta)$ , a parameter vector $u\in\mathbb{R}^d$ , trajectory density $p(\tau\mid\pi_\theta)$ , and sample-gradient quantity $g(\tau,\theta)$ , the required product is
$B(\tau,\theta)u=\langle\nabla_\theta\log p(\tau\mid\pi_\theta),u\rangle g(\tau,\theta)+\nabla_\theta\langle g(\tau,\theta),u\rangle.$
The second term can be computed by automatic differentiation of the scalar inner product, rather than finite-differencing gradients. The paper states that this implementation costs $\mathcal{O}(Hd)$ arithmetic operations for trajectory horizon $H$ and parameter dimension $d$ ; it avoids storing the $d\times d$ Hessian and supports memory linear in the parameter dimension.
Knowl 9 — Continuous-control experimental protocol
experimental setup
The empirical evaluation used continuous-state, continuous-action MuJoCo tasks with diagonal Gaussian policies, $a=\mu_\theta(s)+\sigma_\theta(s)\odot z$ for $z\sim\mathcal{N}(0,I)$ . The mean and standard deviation were parameterized by fully connected networks with two hidden layers of 64 units and tanh activations, using the garage REINFORCE implementation as a base. The main comparisons covered Humanoid and Reacher; additional tasks included Walker2d, Hopper, Halfcheetah, and Cartpole. Training used batches of 20 trajectories per iteration in the main comparison, each capped at horizon 500; for HARPG variants, half the batch estimated the gradient and half the Hessian-vector correction to match per-iteration sampling cost. Results were summarized over five independent runs. In the tuned-step-size experiments, 13 initial step sizes from $10^{-3}$ to $4$ were tested, with the choice selected by average reward after $2\times10^7$ system probes.
Knowl 10 — N-PG-IGT performance and Hessian-estimator variance in experiments
empirical result
In the tuned-step-size Humanoid runs, N-PG-IGT raised average reward above 450 quickly and stabilized around 500, outperforming Vanilla-PG and both HARPG variants in the reported comparison. On Reacher, where the robustness experiment measured probes needed to exceed average reward $-11$ , HARPG could reach the target faster than Vanilla-PG for small initial step sizes, whereas N-PG-IGT tolerated larger initial step sizes and was more robust to that choice. Additional Walker2d results showed the same reported advantage for N-PG-IGT over the comparison methods. The authors suggest that the weaker practical performance of HARPG and N-HARPG under tuned step sizes may be caused by high variance in their sampled Hessian-vector corrections; this is offered as an explanation rather than established as a separate experimental finding.

Coverage note — The appendix-only first-order-stationarity guarantee for N-PG-IGT, the analysis of the simpler N-MPG baseline, and additional task-by-task plots are omitted because they are secondary to the paper's main global-optimality algorithms and results.

References

1.Alekh Agarwal, Sham M. Kakade, Jason D. Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1–76, 2021.
2.Carlo Alfano and Patrick Rebeschini. Linear convergence for natural policy gradient with log-linear policy parametrization. arXiv preprint arXiv:2209.15382, 2022.
3.Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Ayush Sekhari, and Karthik Sridharan. Second-order information in non-convex stochastic optimization: Power and limitations. In Conference on Learning Theory, pages 242–299. PMLR, 2020.
4.Sebastien Arnold, Pierre-Antoine Manzagol, Reza Babanezhad Harikandeh, Ioannis Mitliagkas, and Nicolas Le Roux. Reducing the variance in online optimization by transporting past gradients. Advances in Neural Information Processing Systems, 32, 2019.
5.Hedy Attouch and Jérôme Bolte. On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Mathematical Programming, 116(1):5–16, 2009.
6.Amrit Singh Bedi, Anjaly Parayil, Junyu Zhang, Mengdi Wang, and Alec Koppel. On the sample complexity and metastability of heavy-tailed policy search in continuous control. arXiv preprint arXiv:2106.08414, 2021.
7.Amrit Singh Bedi, Souradip Chakraborty, Anjaly Parayil, Brian M Sadler, Pratap Tokekar, and Alec Koppel. On the hidden biases of policy mirror ascent in continuous action spaces. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 1716–1731. PMLR, 17–23 Jul 2022.
8.Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods. arXiv preprint arXiv:1906.01786, 2019.
9.Jalaj Bhandari and Daniel Russo. On the linear convergence of policy gradient methods for finite mdps. In International Conference on Artificial Intelligence and Statistics, pages 2386–2394. PMLR, 2021.
10.Zaiwei Chen and Siva Theja Maguluri. Sample complexity of policy-based methods under off-policy sampling and linear function approximation. In International Conference on Artificial Intelligence and Statistics, pages 11195–11214. PMLR, 2022.
11.Zaiwei Chen, Sajad Khodadadian, and Siva Theja Maguluri. Finite-sample analysis of off-policy natural actor–critic with linear function approximation. IEEE Control Systems Letters, 6:2611–2616, 2022.
12.Ashok Cutkosky and Harsh Mehta. Momentum improves normalized SGD. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 2260–2268. PMLR, 2020.
13.Ashok Cutkosky and Francesco Orabona. Momentum-based variance reduction in non-convex sgd. Advances in neural information processing systems, 32, 2019.
14.Anirban DasGupta and Anirban DasGupta. The exponential family and statistical applications. Probability for Statistics and Machine Learning: Fundamentals and Advanced Topics, pages 583–612, 2011.
15.Yuhao Ding, Junzi Zhang, and Javad Lavaei. Beyond exact gradients: Convergence of stochastic soft-max policy gradient methods with entropy regularization. arXiv preprint arXiv:2110.10117, 2021.
16.Yuhao Ding, Junzi Zhang, and Javad Lavaei. On the global optimum convergence of momentum-based policy gradient. In International Conference on Artificial Intelligence and Statistics, pages 1910–1934. PMLR, 2022.
17.Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. In Advances in Neural Information Processing Systems, volume 31, 2018.
18.Ilyas Fatkhullin and Boris Polyak. Optimizing Static Linear Feedback: Gradient Method. SIAM Journal on Control and Optimization, 59(5):3887–3911, 2021.
19.Ilyas Fatkhullin, Jalal Etesami, Niao He, and Negar Kiyavash. Sharp analysis of stochastic optimization under global Kurdyka-łojasiewicz inequality. Advances in Neural Information Processing Systems, 2022.
20.Maryam Fazel, Rong Ge, Sham Kakade, and Mehran Mesbahi. Global convergence of policy gradient methods for the linear quadratic regulator. In International Conference on Machine Learning, pages 1467–1476. PMLR, 2018.
21.Xavier Fontaine, Valentin De Bortoli, and Alain Durmus. Convergence rates and approximation results for sgd and its continuous-time counterpart. In Conference on Learning Theory, pages 1965–2058. PMLR, 2021.
22.Sebastien Gadat, Fabien Panloup, and Sofiane Saadane. Stochastic Heavy ball. Electronic Journal of Statistics, 12(1):461–529, 2018.
23.The garage contributors. Garage: A toolkit for reproducible reinforcement learning research. https://github.com/rlworkgroup/garage, 2019.
24.Matilde Gargiani, Andrea Zanelli, Andrea Martinelli, Tyler Summers, and John Lygeros. PAGE-PG: A simple and loopless variance-reduced policy gradient method with probabilistic gradient estimation. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 7223–7240. PMLR, 2022.
25.Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341–2368, 2013.
26.Elad Hazan, Kfir Y. Levy, and Shai Shalev-Shwartz. Beyond Convexity: Stochastic Quasi-Convex Optimization. arXiv preprint arXiv:1507.02030, 2015.
27.Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic. To appear in SIAM Journal on Optimization 2022, arXiv preprint arXiv:2007.05170, 2020.
28.Feihu Huang, Shangqian Gao, Jian Pei, and Heng Huang. Momentum-based policy gradient methods. In International conference on machine learning, pages 4422–4433. PMLR, 2020.
29.Sajad Khodadadian, Thinh T Doan, Justin Romberg, and Siva Theja Maguluri. Finite sample analysis of two-time-scale natural actor-critic algorithm. IEEE Transactions on Automatic Control, 2022a.
30.Sajad Khodadadian, Prakirt Raj Jhunjhunwala, Sushil Mahavir Varma, and Siva Theja Maguluri. On linear and super-linear convergence of natural policy gradient algorithm. Systems & Control Letters, 164:105214, 2022b. ISSN 0167-6911.
31.Solomon Kullback. Information theory and statistics. Courier Corporation, 1997.
32.Krzysztof Kurdyka. On gradients of functions definable in o-minimal structures. In Annales de l’institut Fourier, volume 48, pages 769–783, 1998.
33.Guanghui Lan. Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. Mathematical programming, pages 1–48, 2022.
34.Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtarik. Page: A simple and optimal probabilistic gradient estimator for nonconvex optimization. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 6286–6295. PMLR, 2021.
35.Yanli Liu, Kaiqing Zhang, Tamer Basar, and Wotao Yin. An improved analysis of (variance-reduced) policy gradient and natural policy gradient methods. Advances in Neural Information Processing Systems, 33:7624–7636, 2020.
36.Stanislaw Lojasiewicz. Une propriete topologique des sous-ensembles analytiques reels. Les equations aux derivees partielles, 117:87–89, 1963.
37.Saeed Masiha, Saber Salehkaleybar, Niao He, Negar Kiyavash, and Patrick Thiran. Stochastic second-order methods provably beat sgd for gradient-dominated functions. To appear in Advances in Neural Information Processing Systems, arXiv preprint arXiv:2205.12856v1, 2022.
38.Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 6820–6829. PMLR, 2020.
39.Jincheng Mei, Bo Dai, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. Understanding the effect of stochasticity in policy optimization. Advances in Neural Information Processing Systems, 34:19339–19351, 2021a.
40.Jincheng Mei, Yue Gao, Bo Dai, Csaba Szepesvari, and Dale Schuurmans. Leveraging non-uniformity in first-order non-convex optimization. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 7555–7564. PMLR, 2021b.
41.Francisco S Melo, Sean P Meyn, and M Isabel Ribeiro. An analysis of reinforcement learning with function approximation. In Proceedings of the 25th international conference on machine learning, pages 664–671, 2008.
42.Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Sarah: A novel method for machine learning problems using stochastic recursive gradient. In International Conference on Machine Learning, pages 2613–2621. PMLR, 2017.
43.Matteo Papini, Damiano Binaghi, Giuseppe Canonaco, Matteo Pirotta, and Marcello Restelli. Stochastic variance-reduced policy gradient. In International conference on machine learning, pages 4026–4035. PMLR, 2018.
44.Nhan Pham, Lam Nguyen, Dzung Phan, Phuong Ha Nguyen, Marten Dijk, and Quoc Tran-Dinh. A hybrid stochastic policy gradient algorithm for reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 374–385. PMLR, 2020.
45.Boris Teodorovich Polyak. Gradient methods for minimizing functionals. Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, 3(4):643–653, 1963.
46.Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
47.Shuang Qiu, Zhuoran Yang, Jieping Ye, and Zhaoran Wang. On finite-time convergence of actor-critic algorithm. IEEE Journal on Selected Areas in Information Theory, 2(2):652–664, 2021.
48.Saber Salehkaleybar, Sadegh Khorasani, Negar Kiyavash, Niao He, and Patrick Thiran. Adaptive momentum-based policy gradient with second-order information. arXiv preprint arXiv:2205.08253, 2022.
49.Kevin Scaman, Cedric Malherbe, and Ludovic Dos Santos. Convergence Rates of Non-Convex Stochastic Gradient Descent Under a Generic Lojasiewicz Condition and Local Smoothness. In Proceedings of the 39th International Conference on Machine Learning, pages 19310–19327. PMLR, June 2022.
50.John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pages 1889–1897. PMLR, 2015.
51.John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
52.Zebang Shen, Alejandro Ribeiro, Hamed Hassani, Hui Qian, and Chao Mi. Hessian aided policy gradient. In International conference on machine learning, pages 5729–5738. PMLR, 2019.
53.David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In International conference on machine learning, pages 387–395. PMLR, 2014.
54.Sebastian U. Stich. Unified optimal analysis of the (stochastic) gradient method. arXiv preprint arXiv:1907.04232v2, 2019.
55.Richard S. Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems, volume 12. MIT Press, 1999.
56.Hoang Tran and Ashok Cutkosky. Better SGD using Second-order Momentum. arXiv preprint arXiv:2103.03265, 2021.
57.J.N. Tsitsiklis and B. Van Roy. An analysis of temporal-difference learning with function approximation. IEEE Transactions on Automatic Control, 42(5):674–690, 1997. doi: 10.1109/9.580874.
58.Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence. In International Conference on Learning Representations, 2020.
59.Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning, 8:229–256, 1992.
60.Yue Frank Wu, Weitong Zhang, Pan Xu, and Quanquan Gu. A finite-time analysis of two time-scale actor-critic methods. Advances in Neural Information Processing Systems, 33:17617–17628, 2020.
61.Lin Xiao. On the convergence rates of policy gradient methods. Journal of Machine Learning Research, 23 (282):1–36, 2022.
62.Pan Xu, Felicia Gao, and Quanquan Gu. Sample efficient policy gradient methods with recursive variance reduction. In International Conference on Learning Representations, 2020a.
63.Pan Xu, Felicia Gao, and Quanquan Gu. An improved convergence analysis of stochastic variance-reduced policy gradient. In Uncertainty in Artificial Intelligence, pages 541–551. PMLR, 2020b.
64.Tengyu Xu, Zhe Wang, and Yingbin Liang. Improving sample complexity bounds for (natural) actor-critic algorithms. In Advances in Neural Information Processing Systems, volume 33, pages 4358–4369, 2020c.
65.Long Yang, Qian Zheng, and Gang Pan. Sample complexity of policy gradient finding second-order stationary points. Proceedings of the AAAI Conference on Artificial Intelligence, 35(12):10630–10638, 2021.
66.Huizhuo Yuan, Xiangru Lian, Ji Liu, and Yuren Zhou. Stochastic Recursive Momentum for Policy Gradient Methods, 2020.
67.Rui Yuan, Simon S Du, Robert M Gower, Alessandro Lazaric, and Lin Xiao. Linear convergence of natural policy gradient methods with log-linear policies. arXiv preprint arXiv:2210.01400, 2022a.
68.Rui Yuan, Robert M. Gower, and Alessandro Lazaric. A general sample complexity analysis of vanilla policy gradient. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 3332–3380. PMLR, 2022b.
69.Junyu Zhang, Alec Koppel, Amrit Singh Bedi, Csaba Szepesvari, and Mengdi Wang. Variational policy gradient method for reinforcement learning with general utilities. Advances in Neural Information Processing Systems, 33:4572–4583, 2020a.
70.Junyu Zhang, Chengzhuo Ni, Csaba Szepesvari, Mengdi Wang, et al. On the convergence and sample efficiency of variance-reduced policy gradient method. Advances in Neural Information Processing Systems, 34:2228–2240, 2021a.
71.Junzi Zhang, Jongho Kim, Brendan O’Donoghue, and Stephen Boyd. Sample efficient reinforcement learning with reinforce. Proceedings of the AAAI Conference on Artificial Intelligence, 35(12):10887–10895, 2021b.
72.Kaiqing Zhang, Alec Koppel, Hao Zhu, and Tamer Basar. Global convergence of policy gradient methods to (almost) locally optimal policies. SIAM Journal on Control and Optimization, 58(6):3586–3612, 2020b.
73.Matthew S Zhang, Murat A Erdogdu, and Animesh Garg. Convergence and optimality of policy gradient methods in weakly smooth settings. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 9066–9073, 2022.

Citation

MLA

Fatkhullin, I., et al. “Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies”. International Conference on Machine Learning, vol. 202, 2023, pp. 9827–69, https://proceedings.mlr.press/v202/fatkhullin23a.html.

APA

Fatkhullin, I., Barakat, A., Kireeva, A., & He, N. (2023). Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies. International Conference on Machine Learning, 202, 9827–9869. https://proceedings.mlr.press/v202/fatkhullin23a.html

Chicago

Fatkhullin, I., A. Barakat, A. Kireeva, and N. He. 2023. “Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies”. International Conference on Machine Learning 202: 9827–69. https://proceedings.mlr.press/v202/fatkhullin23a.html.

Harvard

Fatkhullin, I. et al. (2023) “Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies”, International Conference on Machine Learning. PMLR, pp. 9827–9869. Available at: https://proceedings.mlr.press/v202/fatkhullin23a.html.

Vancouver

1. Fatkhullin I, Barakat A, Kireeva A, He N (2023) Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies. In: International Conference on Machine Learning. PMLR, pp 9827–9869

BibTeX

@InProceedings{pmlr-v202-fatkhullin23a,
  title = 	 {Stochastic Policy Gradient Methods: Improved Sample Complexity for {F}isher-non-degenerate Policies},
  author =       {Fatkhullin, Ilyas and Barakat, Anas and Kireeva, Anastasia and He, Niao},
  booktitle = 	 {Proceedings of the 40th International Conference on Machine Learning},
  pages = 	 {9827--9869},
  year = 	 {2023},
  editor = 	 {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan},
  volume = 	 {202},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {23--29 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v202/fatkhullin23a/fatkhullin23a.pdf},
  url = 	 {https://proceedings.mlr.press/v202/fatkhullin23a.html},
  abstract = 	 {Recently, the impressive empirical success of policy gradient (PG) methods has catalyzed the development of their theoretical foundations. Despite the huge efforts directed at the design of efficient stochastic PG-type algorithms, the understanding of their convergence to a globally optimal policy is still limited. In this work, we develop improved global convergence guarantees for a general class of Fisher-non-degenerate parameterized policies which allows to address the case of continuous state action spaces. First, we propose a Normalized Policy Gradient method with Implicit Gradient Transport (N-PG-IGT) and derive a $\tilde{\mathcal{O}}(\varepsilon^{-2.5})$ sample complexity of this method for finding a global $\varepsilon$-optimal policy. Improving over the previously known $\tilde{\mathcal{O}}(\varepsilon^{-3})$ complexity, this algorithm does not require the use of importance sampling or second-order information and samples only one trajectory per iteration. Second, we further improve this complexity to $\tilde{ \mathcal{\mathcal{O}} }(\varepsilon^{-2})$ by considering a Hessian-Aided Recursive Policy Gradient ((N)-HARPG) algorithm enhanced with a correction based on a Hessian-vector product. Interestingly, both algorithms are $(i)$ simple and easy to implement: single-loop, do not require large batches of trajectories and sample at most two trajectories per iteration; $(ii)$ computationally and memory efficient: they do not require expensive subroutines at each iteration and can be implemented with memory linear in the dimension of parameters.}
}

Metadata:DOI registry

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Fisher non-degeneracy and policy approximation assumptions

Knowl 2 — Relaxed gradient dominance for Fisher-non-degenerate policies

Knowl 3 — Normalized policy gradient with implicit gradient transport

Knowl 4 — Hessian-aided recursive policy gradient

Knowl 5 — Global sample complexity of N-PG-IGT

Knowl 6 — Global sample complexity of HARPG

Knowl 7 — Global sample complexity of N-HARPG

Knowl 8 — Hessian correction can be implemented with Hessian-vector products

Knowl 9 — Continuous-control experimental protocol

Knowl 10 — N-PG-IGT performance and Hessian-estimator variance in experiments

References

Citation

BibTeX

Source Code

Access the Paper