PaperlayerView exact revision on arXiv

Source-linked AI summary

An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods

Yanli Liu, Kaiqing Zhang, Tamer Başar, Wotao Yin

arXiv:2211.07937v2cs.LG

TL;DR

Variance-reduced PG methods had been analyzed for stationary-point convergence, while global convergence guarantees were a desired target. The paper combines PG and NPG analyses under a positive-definite Fisher assumption, establishing global convergence results, improving NPG’s sample complexity, and introducing SRVR-NPG. It also identifies a current sample-complexity trade-off for SRVR-NPG because solving its subproblems offsets the variance-reduction advantage.

  • Problem

    Variance-reduced PG methods had not been shown to have global convergence guarantees, despite interest in guarantees beyond stationary-point convergence.

    Source: §1 · pp. 1–2

  • Method

    The paper integrates analyses of PG and NPG under a positive-definite Fisher information matrix assumption and proposes SRVR-NPG to add variance reduction to NPG.

    Source: §1 · p. 2, §2.2 · p. 5, §6 · p. 9

  • Results

    The paper establishes global convergence for SRVR-PG up to policy-approximation error, improves NPG’s sample complexity, and reports global convergence with efficient sample complexity for SRVR-NPG.

    Source: §1 · p. 2, §6 · p. 9

  • Takeaways & Limitations

    The integrated analysis may be useful for designing faster variance-reduced NPG methods in the future.

    Source: §6 · p. 9

    SRVR-NPG’s current sample complexity is not better than the improved NPG result because solving its subproblems offsets the advantage of variance reduction.

    Source: §4.2 · p. 9

Abstract

from arXiv · show

In this paper, we revisit and improve the convergence of policy gradient (PG), natural PG (NPG) methods, and their variance-reduced variants, under general smooth policy parametrizations. More specifically, with the Fisher information matrix of the policy being positive definite: i) we show that a state-of-the-art variance-reduced PG method, which has only been shown to converge to stationary points, converges to the globally optimal value up to some inherent function approximation error due to policy parametrization; ii) we show that NPG enjoys a lower sample complexity; iii) we propose SRVR-NPG, which incorporates variance-reduction into the NPG update. Our improvements follow from an observation that the convergence of (variance-reduced) PG and NPG methods can improve each other: the stationary convergence analysis of PG can be applied to NPG as well, and the global convergence analysis of NPG can help to establish the global convergence of (variance-reduced) PG methods. Our analysis carefully integrates the advantages of these two lines of works. Thanks to this improvement, we have also made variance-reduction for NPG possible, with both global convergence and an efficient finite-sample complexity.

1 Introduction

The paper addresses the gap between variance-reduced policy-gradient methods’ stationary-point guarantees and the desired global guarantees. It combines analyses of PG and NPG to establish global convergence results and introduce variance reduction for NPG.

Motivation

  • Stochastic PG methods can have high variance that destabilizes and slows convergence; baselines, actor-critic methods, and variance reduction are approaches used to address it.Prior variance-reduced PG methods were reported as faster, but their cited sample-complexity results concerned stationary-point convergence.Source: §1 · pp. 1–2
  • Prior variance-reduced PG methods had not been shown to converge globally, while stationary-point convergence can yield arbitrarily poor performance.The paper seeks guarantees of global optimality up to compatible policy-approximation error.Source: §1 · pp. 2–3

Contributions

  • The paper establishes global convergence for SRVR-PG up to policy-approximation error, improves NPG’s sample complexity, and introduces globally convergent SRVR-NPG.The analysis assumes the policy’s Fisher information matrix is positive definite.Source: §1 · p. 2
  • The analysis integrates advantages of previous PG and NPG analyses, relying on a positive-definite Fisher information matrix.The paper lays out comparisons of previous results and its improvements in Table 1.Source: §1 · p. 2

2 Preliminaries

The preliminaries formulate policy learning as return maximization in a discounted MDP, with policies parameterized to handle large state and action spaces. They distinguish stationary-point convergence from near-optimality and introduce PG and NPG updates, including the Fisher-matrix assumption used in the analysis.

2.1 Markov Decision Processes

  • A discounted MDP specifies state and action spaces, transition probabilities, bounded rewards, and a discount factor; the objective is maximizing expected discounted return.The policy’s value and advantage functions are defined from its action-value function.Source: §2.1 · p. 3
  • Policy parametrization makes return maximization a generally nonconvex problem, and a small gradient alone need not imply high return.The target is optimal value up to an error reflecting the policy parametrization’s limited expressive power.Source: §2.1 · p. 3

2.2 (Natural) Policy Gradient Methods

  • PG uses sampled trajectories for stochastic ascent, while truncating GPOMDP’s infinite sum yields a biased gradient estimate whose bias is negligible for sufficiently large horizons.The estimate is based on a truncated trajectory of length H.Source: §2.2 · p. 4
  • NPG preconditions the PG direction with the Fisher information matrix; under the stated positive-definiteness assumption, its global sample complexity improves to O(ε^-3) from O(ε^-4).The paper also states that PG and SRVR-PG enjoy global convergence under this assumption, although the Fisher matrix is not explicit in their updates.Source: §2.2 · pp. 4–5

3 Variance-Reduced Policy Gradient Methods

This section presents SRVR-PG’s global guarantee and introduces SRVR-NPG as a variance-reduced natural policy-gradient method. The supplied description gives SRVR-NPG a global-convergence sample complexity comparable to the paper’s improved NPG result.

SRVR-PG

  • SRVR-PG applies variance reduction to PG and previously had a reported O(ε^-1.5) sample complexity for finding an ε-stationary point.The cited earlier result did not establish global convergence.Source: §3 · p. 5
  • SRVR-PG is shown to require O(ε^-3) samples to reach an ε-optimal policy, up to compatible function-approximation error.This supplies the global-convergence result missing from the earlier stationary-point guarantee.Source: §3 · p. 5

SRVR-NPG

  • SRVR-NPG incorporates variance reduction into NPG and is analyzed for global convergence with sample complexity comparable to the improved NPG result.The algorithm description specifies epochs, minibatches, a truncation horizon, and an initial parameter.Source: §3 · pp. 5–6

4 Theoretical Results

The analysis links global convergence to stationary convergence and the accuracy of each method’s update direction relative to exact NPG. Applying this framework yields global-convergence results for PG, NPG, SRVR-PG, and SRVR-NPG, with function-approximation error due to policy parametrization qualifying the guarantees.

4 Theoretical Results

  • The policy-parametrization error reflects the capacity to approximate the advantage function; it is zero for softmax policies and can be small for rich neural parametrizations.Restricted parametrizations may have positive approximation error because they need not represent all stochastic policies.Source: §4 · pp. 6–7

4.1 A General Framework for Global Convergence

  • The framework relates global convergence rates to stationary convergence and the difference between an algorithm’s update direction and exact NPG.Its bound also includes function-approximation error from the policy parametrization and a term of order O(1/K).Source: §4.1 · p. 7
  • When H and N are large enough, the update estimator has low variance and the truncated gradient is close to the full gradient, supporting the framework’s convergence argument.The analysis also shows the residual terms vanish as the iterates approach stationarity for NPG and SRVR-NPG.Source: §4.1 · pp. 7–8

4.2 Global Convergence Results

  • The results apply the framework to PG, NPG, SRVR-PG, and SRVR-NPG; the PG guarantee improves prior work from full gradients to sample-based stochastic gradients [1, Thm. 6.11].The stochastic PG analysis uses the truncated GPOMDP estimator.Source: §4.2 · p. 8
  • Theorem 4.11 establishes global convergence of SRVR-PG, while Theorem 4.9 improves NPG sample complexity over [1, Coro. 6.10] by O(ε^-1), allowing constant stepsize η.Source: §4.2 · p. 8
  • SRVR-NPG has better dependence on W and σ² than SRVR-PG, but its sample complexity is not better than the improved NPG result in this analysis.The analysis attributes the offset to the cost of solving SRVR-NPG’s subproblems.Source: §4.2 · pp. 8–9

5 Numerical Experiments

The experiments compare stochastic PG, NPG, SRVR-PG, and SRVR-NPG on Cartpole and Mountain Car. On Cartpole, SRVR-NPG has the best reported performance.

5 Numerical Experiments

  • The experiments compare stochastic PG, NPG, SRVR-PG, and SRVR-NPG on Cartpole and Mountain Car.Cartpole uses a 32 × 1 neural network, horizon H = 100, and 5,000 trajectories per algorithm; Mountain Car uses a 64 × 1 network, horizon H = 1000, and 3,000 trajectories per algorithm.Source: §5 · p. 9
  • Both tasks use Gaussian policies whose mean is modeled by a neural network with Tanh activation.Source: §5 · p. 9
  • SRVR-NPG has the best overall performance on Cartpole.The figure reports undiscounted average return for PG, SRVR-PG, and SRVR-NPG over 10 runs, and averaged return for NPG over 40 runs.Source: Figure 1 · p. 9

6 Concluding Remarks

The paper presents a framework for global convergence analysis of PG, NPG, and their variance-reduced variants under a positive-definite Fisher information matrix. It also introduces SRVR-NPG; on Mountain Car, NPG has the best reported performance.

6 Concluding Remarks

  • NPG has the best overall performance on Mountain Car.The figure reports undiscounted average return for PG, SRVR-PG, and SRVR-NPG over 10 runs, and averaged return for NPG over 40 runs.Source: Figure 2 · p. 9
  • The paper establishes global-convergence sample complexities for stochastic PG and SRVR-PG and improves the sample complexity of NPG.Source: §6 · p. 9
  • SRVR-NPG combines variance reduction with NPG and has a global-convergence guarantee with an efficient sample complexity.Source: §6 · p. 9

Broader Impact

The paper states that its results may benefit research communities including machine learning and robotics, and that the authors do not believe the work will cause ethical issues or societal disadvantage.

Broader Impact

  • The authors state that the work may benefit machine learning and robotics research communities.Source: Broader Impact · p. 10
  • The authors do not believe the results will cause ethical issues or put anyone at a societal disadvantage.Source: Broader Impact · p. 10

Supplementary Materials for “An Improved Analysis of (Variance-

The supplementary material derives prior complexity bounds, gives estimator and Fisher-matrix properties, describes sampling and subproblem procedures, and presents stationary-convergence results and proof material.

B Helper Lemmas

B.1 Properties of PG Estimator

  • The PG estimators are unbiased for their corresponding full or truncated-horizon policy gradients, and the return functions are smooth.Source: §B.1 · p. 14

B.2 On the Positive Definiteness of Fρ(θ)

  • The positive-definite Fisher-matrix assumption holds for some Gaussian and full-rank exponential-family policies under stated feature-rank conditions.For nonlinear mean parametrizations, the passage gives a corresponding condition on the Jacobian.Source: §B.2 · p. 15

C.1 SGD for Solving the Subproblems of NPG and SRVR-NPG

  • The NPG and SRVR-NPG subproblem procedures use stochastic gradients described as unbiased estimates of their objectives’ gradients.Source: §C.1 · pp. 15–16

C.2 Sampling Procedures

  • The sampling procedure draws state-action pairs from νπθk and uses an unbiased estimate of the advantage; the described procedure needs 1/(1−γ) state-action pairs in expectation.Source: §C.1 · p. 16, §C.2 · p. 17

D SRVR-PG Algorithm

E Stationary Convergence

  • Stationary-convergence results are established for JH(θ) or J(θ), with intermediate results supporting global convergence on J(θ), up to policy-parametrization function-approximation errors.NPG (SRVR-NPG) has similar iteration complexity to PG (SRVR-PG), although each iteration requires solving a subproblem to obtain an approximate preconditioned update direction.Source: E Stationary Convergence · p. 17

G Proof of Theorem E.2

These appendices prove convergence and sample-complexity results for NPG, SRVR-PG, and SRVR-NPG by analyzing the stochastic-gradient subproblems used in their updates.

G Proof of Theorem E.2

  • The NPG proof uses SGD to obtain an approximate update direction and derives the trajectory requirements for the resulting method.The subproblem objective is built from an advantage-function target and policy score features.Source: G Proof of Theorem E.2 · pp. 19, 21

H Proof of Theorem E.3

  • The SRVR-PG proof invokes its prior convergence result and derives the number of trajectories required by the method.Source: H Proof of Theorem E.3 · p. 22

I Proof of Theorem E.4

  • The SRVR-NPG proof uses SGD to solve its subproblems and derives the trajectory requirement for reaching ε-stationarity.Its analysis adapts a variance-bound lemma used for SRVR-PG to SRVR-NPG.Source: I Proof of Theorem E.4 · pp. 22, 29

J Proof of Proposition 4.5

The proof bounds global convergence for policy updates using KL divergence and relates the rate to update accuracy and stationary convergence. It then applies the framework to PG.

J Proof of Proposition 4.5

  • The global-convergence bound contains a function-approximation error from policy parametrization, while its other term vanishes as K grows.The rate also depends on the gap between the chosen update and exact NPG, and on stationary convergence.Source: J Proof of Proposition 4.5 · p. 30

K Proof of Theorem 4.6

L Proof of Theorem 4.9

These proofs apply the general convergence framework to NPG and SRVR-PG, deriving update requirements and sample-complexity bounds for each method.

L Proof of Theorem 4.9

  • The NPG proof applies Proposition 4.5 using the NPG update direction and derives the method’s trajectory requirement.It also uses an SGD sample requirement for obtaining the update direction.Source: L Proof of Theorem 4.9 · pp. 32–33

M Proof of Theorem 4.11

N Proof of Theorem 4.13

The SRVR-NPG proof establishes convergence and sample requirements, while the implementation appendix documents practical choices and difficulties in the experiments.

N Proof of Theorem 4.13

  • The SRVR-NPG proof combines its bounds with the general convergence result and derives the trajectory requirement for the method.The proof states that its assumptions are satisfied when ε is small enough.Source: N Proof of Theorem 4.13 · pp. 37, 41

O Implementation Details

  • In experiments, PG and SRVR-PG use Adagrad averaging, while SRVR-NPG uses Adam averaging as an approximation to the Fisher matrix.The authors leave better Fisher-matrix approximation for future work.Source: O Implementation Details · p. 41
  • The naive PG and SRVR-PG implementations often performed poorly on mountain car, with average reward around −90 despite the authors’ efforts.Source: O Implementation Details · p. 41
Loading 2211.07937v2…