PaperlayerView exact revision on arXiv

Source-linked AI summary

Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies

Kaiqing Zhang, Alec Koppel, Hao Zhu, Tamer Başar

arXiv:1906.08383v3math.OCcs.LGeess.SYmath.ST

TL;DR

Policy gradient methods lack a rigorous global-convergence theory for infinite-horizon discounted reinforcement learning, where finite rollouts bias gradient estimates and the objective is nonconvex. The paper uses random rollout horizons to obtain unbiased policy gradients, then adds periodically enlarged stepsizes to escape saddle points. Under stated reward, parameterization, and strict-saddle assumptions, the resulting methods converge to essentially locally optimal policies, with reward reshaping supported analytically and empirically.

  • Problem

    Global convergence of policy gradient methods is not well understood in infinite-horizon discounted reinforcement learning because unbiased gradient estimation is difficult and the objective is generally nonconvex.

  • Method

    The paper introduces random-horizon policy gradients and periodically enlarged stepsizes, using nonconvex-optimization tools to analyze their convergence and saddle-point escape.

  • Results

    Under mild reward and policy-parameterization conditions, Modified RPG escapes saddle points; under a strict saddle-points assumption, it converges to actual locally optimal policies.

  • Takeaways & Limitations

    Reward reshaping can satisfy the method's reward condition and is justified as beneficial from a nonconvex-optimization perspective.

  • Takeaways & Limitations

    Non-asymptotic convergence of actor-critic variants with biased, correlated policy-gradient noise remains open.

Abstract

from arXiv · show

Policy gradient (PG) methods are a widely used reinforcement learning methodology in many applications such as video games, autonomous driving, and robotics. In spite of its empirical success, a rigorous understanding of the global convergence of PG methods is lacking in the literature. In this work, we close the gap by viewing PG methods from a nonconvex optimization perspective. In particular, we propose a new variant of PG methods for infinite-horizon problems that uses a random rollout horizon for the Monte-Carlo estimation of the policy gradient. This method then yields an unbiased estimate of the policy gradient with bounded variance, which enables the tools from nonconvex optimization to be applied to establish global convergence. Employing this perspective, we first recover the convergence results with rates to the stationary-point policies in the literature. More interestingly, motivated by advances in nonconvex optimization, we modify the proposed PG method by introducing periodically enlarged stepsizes. The modified algorithm is shown to escape saddle points under mild assumptions on the reward and the policy parameterization. Under a further strict saddle points assumption, this result establishes convergence to essentially locally-optimal policies of the underlying problem, and thus bridges the gap in existing literature on the convergence of PG methods. Results from experiments on the inverted pendulum are then provided to corroborate our theory, namely, by slightly reshaping the reward function to satisfy our assumption, unfavorable saddle points can be avoided and better limit points can be attained. Intriguingly, this empirical finding justifies the benefit of reward-reshaping from a nonconvex optimization perspective.

1 Introduction

The paper studies the poorly understood global convergence of policy gradient methods in infinite-horizon discounted reinforcement learning. It introduces random-horizon estimation and periodically enlarged stepsizes to connect policy gradients with nonconvex optimization and avoid undesirable limit points.

  • Global convergence of policy gradient methods remains poorly understood in infinite-horizon discounted reinforcement learning.
  • Finite-horizon Monte-Carlo rollouts bias infinite-horizon value estimates, while random geometric horizons provide unbiased Q-function and discounted occupancy estimates.These two estimates yield an unbiased policy-gradient estimate.
  • Periodically enlarged stepsizes enable Modified RPG to escape saddle points and converge to approximate second-order stationary points under bounded, strictly signed rewards and regular policy parameterization.
  • The random-horizon policy gradient methods support convergence analyses for both limiting and finite-iteration behavior.The paper frames these methods using tools from nonconvex optimization.
  • Under a strict saddle-points assumption, the modified methods are guaranteed to converge to actual locally optimal policies.
  • The paper connects the reward condition to reward reshaping, providing an analytical and empirical nonconvex-optimization justification for its benefit.

2 Problem Formulation

The problem is to maximize the long-term discounted return of a parameterized policy in an MDP when the transition model and rewards are unknown. Because the resulting objective is generally nonconvex, gradient methods may converge to undesirable saddle points rather than locally optimal policies.

  • An MDP models state-action transitions with a Markov kernel, rewards, and discount factor γ, while a policy maps states to action distributions.
  • The action-value Q-function measures discounted long-term reward conditional on an initial state-action pair, and the advantage is Aπ(s,a) = Qπ(s,a) − Vπ(s).
  • Policy search parameterizes π as πθ with θ ∈ R^d, reducing optimization over a potentially complicated policy class to optimization over Euclidean space.The objective is defined as J(θ) := Vπθ(s0).
  • The value function is generally nonconvex in θ, and globally optimizing it is NP-hard except in certain special reinforcement-learning settings.
  • First-order methods may converge to stationary points that are saddle points or local optima, while saddle points can stall training.
  • The paper develops stochastic gradient methods to study how algorithmic updates, reward functions, and policy parameterization affect escape from undesirable limit points.

3 Policy Gradient Methods

The paper formulates policy gradient as stochastic optimization under regularity assumptions and introduces random-horizon sampling to obtain unbiased, bounded stochastic gradients for infinite-horizon problems.

  • Problem formulation: Policy gradient methods are analyzed as stochastic gradient methods for the nonconvex objective J(θ), using differentiable parameterized policies and bounded score functions.The analysis assumes regularity of the MDP, bounded rewards, and Lipschitz, bounded policy score functions.
  • Policy gradient formulation: The discounted state-action occupancy measure ρθ(s,a) combines the discounted state occupancy ρπθ(s) with the policy action distribution πθ(a|s).This measure is used to express the policy gradient and to identify the state-action pair that must be sampled.
  • Policy gradient sampling: Unbiased policy-gradient sampling requires drawing (s,a) from ρθ and obtaining an unbiased estimate of Qπθ(s,a) or Aπθ(s,a).A baseline such as Vπθ(s) can yield an advantage-based policy-gradient representation.
  • Random-horizon estimation: Random geometric horizons produce the required discounted occupancy sample and unbiased finite-rollout estimates of the infinite-horizon Q-function.The last state-action pair of a trajectory with T ∼ Geom(1−γ) has distribution ρθ, while the inner rollout uses a geometric horizon with γ^1/2 discounting.
  • Random-horizon estimation: The resulting stochastic policy gradients are unbiased and almost surely bounded, as are the true policy gradient and the alternative gradient estimators.The γ^1/2-discount factor makes the Q estimate almost surely bounded, supporting convergence analysis for approximate second-order stationary points.
  • Limitations: Monte-Carlo Q-function estimation is not sample-efficient, while actor-critic alternatives introduce bias and correlated gradient noise whose non-asymptotic analysis remains open.Bootstrapping-based online policy evaluation can bias both the Q-function and policy-gradient estimates.

4 Convergence to Stationary Points

The random-horizon policy gradient algorithm converges to stationary points under standard diminishing-stepsize conditions and achieves nonconvex stochastic-optimization convergence rates for diminishing or constant stepsizes.

  • Asymptotic convergence: Under Assumptions 3.1 and 4.1, Algorithm 3 converges almost surely to the set of stationary points of J(θ).The proof uses an optimization perspective based on a supermartingale convergence theorem and the unbiased stochastic policy gradients.
  • Rate metric: The analysis measures nonstationarity through the gradient norm because J(θ) is generally nonconvex.The paper presents separate rate results for diminishing and constant stepsizes.
  • Finite-iteration rates: Diminishing stepsizes αk = k^-a with a ∈ (0,1) yield Kϵ ≤ O(ϵ^-1/p), where p = min{1−a,a}.Optimizing the bound gives Kϵ ≤ O(ϵ^-2) when a = 1/2.
  • Constant stepsizes: With constant stepsize α > 0, the average gradient norm square converges to a neighborhood around zero whose size is controlled by α.A smaller constant stepsize reduces the neighborhood size at the expense of convergence speed.
  • Finite-iteration rates: The expected gradient norm square converges at a 1/k rate under diminishing stepsizes.This recovers the standard convergence behavior of stochastic gradient descent for nonconvex optimization.

5 Convergence to Second-Order Stationary Points

The modified RPG algorithm periodically enlarges its stepsize to escape saddle points and converge to approximate second-order stationary points under reward and policy assumptions. With strict saddle points, these points correspond to local maxima, while reward shifting preserves optimal policies and can improve convergence behavior.

  • Algorithm: MRPG uses random-horizon policy gradients with Q-function, baseline, or temporal-difference advantage estimates.The baseline and TD-based variants are designed to reduce the variance of the RPG update.
  • Algorithm: Periodic stepsize enlargement amplifies variance along the Hessian’s largest-eigenvalue direction, helping updates escape saddle points.The method uses constant stepsizes β > α > 0 and applies the larger step once every k_thre steps.
  • Assumptions: The method assumes bounded rewards of one sign, regular score-function derivatives, and a uniformly positive-definite Fisher information matrix.The reward condition requires either positive or negative rewards, while the policy conditions support Hessian regularity and curvature analysis.
  • Reward reshaping: Adding a constant offset to rewards preserves the set of optimal policies and can satisfy the strict-positivity or strict-negativity assumption.The sign condition also lower-bounds the absolute Q-function, which benefits MRPG convergence; baseline gradients help offset the resulting variance increase.
  • Convergence: Under the stated assumptions, Algorithm 5 returns an (ϵ,√ρϵ)-approximate second-order stationary policy with high probability in polynomially many iterations.If all saddle points are strict, convergence to second-order stationary points is equivalent to convergence to approximate local maxima.

6 Simulations

Experiments in the discounted infinite-horizon Pendulum environment compare RPG and its modified variants with REINFORCE. Random-horizon RPG is slightly better in return but more variable, while MRPG variants improve return over REINFORCE and reward reshaping supports avoidance of unfavorable stationary points.

  • Setup: In Pendulum, the experiments use a discounted factor γ = 0.97 and a truncated Gaussian policy with a two-hidden-layer neural-network mean.The reward is shifted by −0.5 so that it is negative, satisfying the convergence assumption with LR = 0.5.
  • RPG versus REINFORCE: RPG’s rollout horizon is geometrically randomized, while REINFORCE uses the matching expected horizon T = 66 for a fair comparison.The comparison evaluates both diminishing and constant RPG stepsizes against REINFORCE.
  • RPG versus REINFORCE: RPG achieves slightly higher discounted return than REINFORCE but exhibits higher variance across the 30 simulations.The higher variance is attributed to the additional randomness of RPG’s rollout horizon.
  • RPG convergence: With diminishing stepsizes, the expected gradient-norm square decreases toward zero, whereas constant stepsizes leave a nonzero error neighborhood that shrinks with smaller stepsizes.These observations match the reported convergence behavior for the two stepsize regimes.
  • Reward structure: Mixed-reward experiments produce lower discounted return and greater variance across trajectories, consistent with convergence to stationary points of differing quality.The mixed-reward environment is created by adding 10.0 to the original reward, removing the strict-negative structure.
  • MRPG comparisons: All MRPG variants outperform REINFORCE in discounted return, while MRPG1 and MRPG2 also outperform it in variance.The baseline variant outperforms MRPG1 in this experiment, whereas the TD-error advantage variant performs worse.

7 Conclusions

The paper develops random-horizon policy-gradient algorithms for infinite-horizon settings, recovering stationary-point convergence and using periodically enlarged stepsizes to escape saddles and reach local optima under assumptions.

  • Contributions: Random-horizon policy-gradient algorithms generate unbiased policy-gradient estimates for infinite-horizon reinforcement-learning problems.The paper uses these estimates to analyze policy-gradient methods through nonconvex optimization.
  • Contributions: The algorithms recover convergence to stationary-point policies for first-order optimization methods under standard reinforcement-learning assumptions.
  • Saddle-point escape: Periodically enlarged stepsizes enable modified RPG algorithms to escape saddle points under mild conditions on rewards and policy parameterization.
  • Saddle-point escape: Under a strict saddle-points assumption, the modified algorithms converge to actual local optimal policies.

A Detailed Proofs

The appendix provides proofs for results stated in the paper's main body.

  • Appendix scope: The appendix collects proofs supporting results presented in the main body of the paper.

A.1 Proof of Lemma 3.2

The proof establishes Lipschitz continuity of the policy gradient by decomposing gradient differences into score-function and trajectory-distribution terms, then bounding both by parameter distance.

  • Gradient regularity: The proof bounds ∥∇J(θ1) − ∇J(θ2)∥ by multiples of ∥θ1 − θ2∥ to establish gradient regularity.
  • Trajectory representation: The trajectory density is represented using the Markov property, allowing gradient differences to be analyzed through the trajectory distribution.
  • Gradient decomposition: The gradient difference is decomposed into I1, involving score-function differences, and I2, involving differences between policy-induced distributions.
  • Bounding policy terms: Taylor expansion and interpolation between θ1 and θ2 are used to control policy-dependent terms in the bound.
  • Final bound: The proof combines bounds on I1 and I2 with a geometric-series calculation to define a Lipschitz constant L.

A.2 Proof of Theorem 3.4

The proof shows that random-horizon value and policy-gradient estimators are unbiased, while bounded rewards and score functions provide bounded stochastic gradients.

  • Value-estimator unbiasedness: The random-horizon Q-estimate is established as an unbiased estimate of Qπθ(s,a).
  • Value-estimator unbiasedness: The random-horizon V-estimate is also unbiased, using independence of the random horizon and system evolution.
  • Advantage estimation: The estimators Q̂πθ(s,a) − V̂πθ(s) and R(s,a) + γV̂πθ(s′) − V̂πθ(s) are unbiased advantage estimates.
  • Policy-gradient unbiasedness: The stochastic policy-gradient estimators coincide in expectation with the policy gradient, proving their unbiasedness.
  • Gradient boundedness: Bounded rewards and score-function gradients yield almost sure bounds for the stochastic policy gradients.

A.3 Proof of Theorem 4.2

The proof establishes almost-sure convergence of the policy-gradient iterates to stationary-point policies. It combines bounded stochastic-ascent analysis with a contradiction argument based on finite total movement.

  • Stochastic ascent: The auxiliary sequence W_k is bounded and forms a submartingale under the algorithm’s stochastic ascent property.The construction uses boundedness of J(θ) and square-summable stepsizes.
  • Stochastic ascent: The stochastic policy-gradient estimator has bounded second moment, enabling conditional-expectation bounds on objective increments.The proof substitutes the update θ_k+1 − θ_k = α_k ˆ∇J(θ_k) and uses E[∥ˆ∇J(θ_k)∥^2] ≤ ˆℓ^2.
  • Gradient convergence: Because the stepsizes are non-summable, the convergence relation forces the gradient norm toward zero rather than remaining bounded away from zero.Assumption 4.1 supplies the non-summability condition used in this step.
  • Gradient convergence: A contradiction argument partitions iterates into separated regions with large and small gradient norms, then shows their required crossings have finite total movement.The finite-movement conclusion contradicts the positive distance between the two closed sets.
  • Conclusion: Almost surely, lim_k→∞ ∥∇J(θ_k)∥ = 0.The conclusion follows after ruling out a positive limsup of the gradient norm.

A.4 Proofs of Theorem 4.3 and Corollary 4.4

The proofs derive finite-iteration convergence rates for the policy-gradient method by telescoping expected suboptimality bounds. They obtain an O(ϵ^-1/p) iteration requirement and optimize the stepsize exponent to reach the best stated rate.

  • Finite-sample convergence: The value suboptimality U(θ) = J* − J(θ) is bounded by 2U_R/(1 − γ), providing the bounded objective terms needed for the rate analysis.This bound follows from |J(θ)| ≤ U_R/(1 − γ).
  • Finite-sample convergence: Telescoping the stochastic-ascent inequality over iterations converts the expected suboptimality relation into an average-gradient bound.The proof uses non-increasing stepsizes and then chooses N = k − 1.
  • Finite-sample convergence: K_ϵ ≤ O(ϵ^-1/p), and maximizing p(a) over a ∈ (0,1) gives p = 1/2 at a = 1/2.This choice yields the best rate established by the theorem’s stepsize analysis.
  • Corollary: The proof of Corollary 4.4 follows by combining the finite-iteration inequality with the boundedness of the auxiliary value terms.The final step sets N = k − 1, divides by k, and applies the preceding bounds.

A.5 Proof of Lemma 5.3

The proof shows that adding a constant to every reward shifts the policy’s Q-function by a corresponding discounted constant. The Bellman equation is therefore preserved under this reward transformation.

  • Bellman characterization: An optimal policy is characterized by its Q-function satisfying the Bellman equation for every state-action pair.This criterion is used as the starting point for the transformation argument.
  • Reward transformation: Adding C/(1 − γ) to both sides of the Bellman equation corresponds to replacing R(s,a) with the shifted reward R(s,a) + C.The transformed Q-function is ˜Q^π(s,a) = Q^π(s,a) + C/(1 − γ).
  • Reward transformation: Because C can be any real value, the transformed Q-function satisfies the Bellman equation under the shifted reward for the same policy.This establishes the reverse direction of the lemma’s equivalence.

A.6 Proof of Lemma 5.4

The proof establishes regularity properties of the policy-gradient objective and its components, then uses them to analyze periodic enlarged stepsizes and escape from non-second-order stationary points.

  • Hessian and regularity: The Hessian decomposition separates policy curvature, log-likelihood curvature, and score–Q-gradient interaction terms under the discounted occupancy measure.H1 is the scaled Fisher-information term, H2 the scaled log-likelihood Hessian, and H12 the score and action-value-gradient interaction.
  • Hessian and regularity: Q^πθ and ∇Q^πθ are uniformly bounded and Lipschitz continuous under the stated reward and policy-parameterization bounds.The proof derives explicit constants from bounded rewards, score-function derivatives, and the discount factor.
  • Hessian and regularity: A geometric random horizon yields the moment identity needed to establish uniform Lipschitz continuity of ∇Q^πθ.The proof uses the geometric distribution of T and its second moment.
  • Saddle-point escape: The analysis divides convergence into regimes determined by gradient magnitude and Hessian curvature, without assuming isotropic policy-gradient noise.It avoids artificial perturbations because trajectory noise need not be isotropic and may already be large.
  • Saddle-point escape: After k_thre steps, the expected return increases by at least J_thre whenever the iterate violates the (ϵ, √ρϵ)-approximate second-order stationarity condition.When the condition is satisfied, the proof separately controls possible return decrease.
Loading 1906.08383v3…