PaperlayerView exact revision on arXiv

Source-linked AI summary

Neural Policy Gradient Methods: Global Optimality and Rates of Convergence

Lingxiao Wang, Qi Cai, Zhuoran Yang, Zhaoran Wang

arXiv:1909.01150v3cs.LGmath.OCstat.ML

TL;DR

Neural policy gradient methods lack clear theoretical guarantees of convergence or global optimality despite their empirical success. This paper proves convergence guarantees in the overparameterized regime, including global convergence for neural natural policy gradient and stationary-point convergence with global-optimality conditions for vanilla policy gradient.

  • Problem

    Theoretical understanding of neural actor-critic policy gradient methods remains limited, including whether they converge and reach globally optimal policies.

  • Method

    The paper analyzes overparameterized neural natural and vanilla policy gradients through actor-critic compatibility, including shared architectures and random initializations.

  • Results

    Neural natural policy gradient converges sublinearly to a globally optimal policy, while vanilla policy gradient converges sublinearly to a stationary point whose global optimality can be established under mild conditions.

  • Takeaways & Limitations

    The analysis establishes global optimality and convergence guarantees for neural policy gradient methods in the overparameterized regime.

  • Takeaways & Limitations

    Actor-critic policy-gradient convergence to even first- or second-order stationary points remains open when policy-evaluation errors are present.

Abstract

from arXiv · show

Policy gradient methods with actor-critic schemes demonstrate tremendous empirical successes, especially when the actors and critics are parameterized by neural networks. However, it remains less clear whether such "neural" policy gradient methods converge to globally optimal policies and whether they even converge at all. We answer both the questions affirmatively in the overparameterized regime. In detail, we prove that neural natural policy gradient converges to a globally optimal policy at a sublinear rate. Also, we show that neural vanilla policy gradient converges sublinearly to a stationary point. Meanwhile, by relating the suboptimality of the stationary points to the representation power of neural actor and critic classes, we prove the global optimality of all stationary points under mild regularity conditions. Particularly, we show that a key to the global optimality and convergence is the "compatibility" between the actor and critic, which is ensured by sharing neural architectures and random initializations across the actor and critic. To the best of our knowledge, our analysis establishes the first global optimality and convergence guarantees for neural policy gradient methods.

1 Introduction

The paper analyzes overparameterized neural actor-critic policy gradients and establishes convergence and global-optimality guarantees, addressing theoretical gaps caused by nonlinear policy evaluation and nonconvex optimization. Its results rely on actor-critic compatibility through shared neural architectures and random initializations.

  • Contributions: Neural vanilla policy gradient converges to a stationary point of the expected total reward, and every stationary point is globally optimal under mild regularity conditions.The global-optimality result relates stationary-point suboptimality to the representation power of the neural actor and critic.
  • Contributions: Neural natural policy gradient converges to a globally optimal policy through an analysis based on Kullback-Leibler divergence regularization.The supplied passage states a 1/T-rate, but the displayed rate is split across passages and is not reproduced here.
  • Contributions: Actor-critic compatibility connects policy-evaluation accuracy with policy-improvement efficacy and is ensured by sharing neural architectures and random initializations.This practice is described as a practical heuristic.
  • Contributions: The analysis provides the first global-optimality and convergence guarantees for neural policy gradient methods, contrasting with prior results limited to stationary points, linear functions, convex policy classes, or LQR and tabular settings.Actor-critic evaluation with nonlinear action-value approximators can otherwise converge to undesirable stationary points or diverge, biasing policy gradients.

2 Background

This section defines discounted reinforcement learning and its value, advantage, visitation, and reward objectives, then introduces vanilla and natural policy-gradient optimization. It also notes that practical methods must estimate both value functions and Fisher information, producing approximate policy updates.

  • Reinforcement Learning: A discounted MDP specifies state and action spaces, transitions, rewards, an initial-state distribution, and discount factor γ, while a policy defines action probabilities.The policy induces value functions, state and state-action visitation measures, and stationary distributions.
  • Reinforcement Learning: Reinforcement learning seeks the policy π∗ maximizing expected total reward J(π), often optimized over parameterized policies through maxθ∈B J(πθ).The advantage function is defined as Aπ(s, a) = Qπ(s, a) − Vπ(s).
  • Policy Gradient Methods: Vanilla policy gradient maximizes J(πθ) by gradient ascent using ∇θJ(πθ), whereas natural policy gradient uses Fisher-preconditioned ascent invariant to policy parameterization.Natural policy gradient updates use the inverse Fisher information matrix F(θi)^−1 and learning rate η.
  • Policy Gradient Methods: In practice, estimating Qπθ and F(θ) yields approximations of the vanilla and natural policy-improvement steps.The Fisher information matrix corresponds to policy πθ.

3 Neural Policy Gradient Methods

This section develops policy and action-value critics with two-layer neural networks and presents neural policy-gradient and natural-policy-gradient updates. Shared architectures and initialization yield approximate actor–critic compatibility, while artificial-MDP sampling targets visitation measures and natural-gradient estimation avoids direct Fisher inversion.

  • Neural Policy Parameterization: Policies and critics are represented by two-layer neural networks within an actor–critic scheme for estimating policy and natural-policy gradients.The policy uses an energy-based neural parameterization, while the critic represents the action-value function.
  • Shared Initialization and Compatible Function Approximation: Shared neural architectures and the same random initialization make the critic approximately compatible with the actor in the overparameterized regime.Compatible approximations support unbiased policy-gradient estimators needed for policy-gradient optimality and convergence.
  • Neural Policy-Gradient Algorithms: The algorithms iteratively update policy parameters in a constrained parameter ball, using the identity matrix for policy gradient and the inverse Fisher matrix for natural policy gradient.Updates use learning rate η, batch samples from the current policy’s visitation measure, and a critic-produced gradient estimator.
  • Sampling From Visitation Measure: The artificial MDP restarts from the initial-state distribution with probability 1 −γ, making its stationary state distribution exactly the policy’s visitation measure.Consequently, trajectories generated in the artificial MDP provide samples whose marginal distribution converges to the state-action visitation measure.
  • Inverting Fisher Information Matrix: Because direct inversion of a high-dimensional Fisher estimator may be infeasible or impossible, natural policy gradient estimates the update through an alternative optimization formulation.The Fisher estimator is unbiased and constructed from samples drawn from the current policy’s visitation measure.

4 Main Results

Section 4 establishes global optimality and convergence guarantees for neural policy gradient methods in the overparameterized regime. Neural policy gradient converges to globally optimal stationary points, while neural natural policy gradient converges directly to the global optimum at a sublinear rate.

  • 4.1 Neural Policy Gradient: Neural policy gradient converges to a stationary point of J(πθ) at a sublinear rate.The result is stated in §4.1 for the neural policy gradient update.
  • 4.1 Neural Policy Gradient: Every stationary point is globally optimal when the relevant action-value function is sufficiently well represented by the neural network class.The results also provide near-global optimality under broader representation conditions and global optimality as width m grows.
  • 4.2 Neural Natural Policy Gradient: Neural natural policy gradient converges to the global optimum of J(πθ) at a sublinear rate.Theorem 4.13 bounds the optimality gap using terms that decrease with iterations, width, and batch size.
  • 4.1 Neural Policy Gradient: For sufficiently large m and B, neural policy gradient reaches the global optimum at a 1/T^1/4-rate.The same convergence rate holds for the projection-free version.
  • 4.2 Neural Natural Policy Gradient: When m, B, and TTD are sufficiently large, neural natural policy gradient achieves global optimality and convergence.Corollary 4.14 gives explicit sufficient scaling conditions on network width and batch size.

5 Proof of Main Results

This section proves Theorems 4.7, 4.8, and 4.13 using a performance-difference lemma and bounds that separate gradient-estimation, variance, critic, and update-remainder errors. The resulting arguments establish the stated convergence and stationarity guarantees through telescoping and representation-based bounds.

  • Proof framework: The proofs begin with Lemma 5.1, which establishes one-point convexity of J(π) at the globally optimal policy π∗ via the performance difference identity.The lemma is adapted from Kakade and Langford (2002) and uses the optimal policy’s state visitation measure ν∗.
  • Theorem 4.7: The proof of Theorem 4.7 lower-bounds each actor-update reward improvement by controlling gradient-estimation error, estimator variance, and the update increment.The analysis uses Lipschitz continuity, Lemma 5.2, projection bounds, and a characterization of the update deviation ρi−δi.
  • Theorem 4.7: εQ(T) = κ · O(R5/2 · m−1/4 · T 1/2 + R9/4 · m−1/8 · T 1/2).This bound is obtained after combining the intermediate inequalities and completes the proof of Theorem 4.7.
  • Theorem 4.8: For Theorem 4.8, stationarity is combined with Proposition 3.1 and Lemma 5.1 to bound suboptimality using policy representation error and visitation-measure comparisons.The proof applies Radon-Nikodym derivatives, the Cauchy-Schwarz inequality, and the bound |Aπbθ(s, a)| ≤2Qmax.
  • Theorem 4.13: Theorem 4.13 is proved by telescoping a performance-difference bound whose three error components represent natural-gradient estimation, critic estimation, and a remainder term.Lemma 5.5 bounds these components under Assumptions 4.2 and 4.12, with concentrability coefficients and critic error εQ,i entering the result.

A Linearization Error · B Neural TD

The section establishes that wide two-layer neural networks are well approximated by their initialization-based linearizations, with the approximation error vanishing as width grows. It then presents neural TD’s optimization procedure and cites a convergence theorem under the stated assumption.

  • A Linearization Error: The linearized function class is linear in parameters but remains nonlinear in state-action inputs.Its feature mapping is evaluated at the random initialization Winit.
  • A Linearization Error: For fixed parameter radius R, the linearization error decays to zero as network width m →∞.This yields a close approximation of the neural network when parameters remain near Winit.
  • A Linearization Error: Corollary A.3 extends the vanishing-width-error result to centered feature mappings under Assumption 4.2.The result applies uniformly to parameters within the radius-R ball around Winit.
  • A Linearization Error: When width m is sufficiently large, φbθ(·, ·)⊤θ is well approximated by f((·, ·); θ) in L2(σ)-norm.Here σ is the state-action distribution induced by π and ν under Assumption 4.2.
  • B Neural TD: Neural TD solves the critic optimization problem through TD iterations summarized in Algorithm 2.The method samples transitions, computes a Bellman residue, performs a gradient TD update, and averages iterates.
  • B Neural TD: Algorithm 2 initializes neural TD with random output signs and Gaussian weights, then operates within a parameter ball.Its inputs include policy π, TD iteration count TTD, and learning rate ηTD.
  • B Neural TD: Theorem B.1 characterizes neural TD’s convergence rate under Assumption 4.2 using projection onto eFR,m and the stationary distribution ςπ.The theorem sets ηTD according to the prescribed expression and attributes the result to Cai et al. (2019).

B.1 Proof of Proposition 4.3 · C Projection-Free Neural Policy Gradient

The proof bounds neural TD’s projection error through a random-feature approximation lemma and combines it with the TD convergence theorem to establish Proposition 4.3. The projection-free method then updates the actor without projection, using an estimated policy gradient and a modified critic trained by Algorithm 2.

  • B.1 Proof of Proposition 4.3: The proof reduces neural TD convergence to characterizing the random-initialization projection error for approximating Qπ.This reduction is stated before introducing the new function class and projection-error lemma.
  • B.1 Proof of Proposition 4.3: Lemma B.2 characterizes the projection error for FR,∞ with probability at least 1 −δ for any δ > 0.The distribution involved is over S × A.
  • B.1 Proof of Proposition 4.3: Because Assumption 4.1 places Qπ in FR,∞, Lemma B.2 yields the needed approximation bound after setting f = Qπ.The expectation in the resulting bound is taken over the random initialization.
  • B.1 Proof of Proposition 4.3: Combining the projection-error bound with Theorem B.1 at ηTD = min{(1 −γ)/8, 1/√ establishes Proposition 4.3.The critic Qωi is produced by Algorithm 2 using πθi as input.
  • C Projection-Free Neural Policy Gradient: Projection-free neural policy gradient removes projection from the actor update and uses an estimator e∇θJ(πθi) of the policy gradient.The estimator is formed from samples drawn from the current policy’s state-action visitation measure, with batch size B > 0.
  • C Projection-Free Neural Policy Gradient: The method uses a modified critic eQωi defined from Qωi, where Qωi is obtained by Algorithm 2 with πθi as input, and is summarized in Algorithm 3.Algorithm 3 specifies initialization with random signs and Gaussian weights, critic training through TD iterations, and gradient estimation from visitation samples.
  • C Projection-Free Neural Policy Gradient: Algorithm 3 updates the critic using Algorithm 2 with TTD iterations and ηTD, then samples from σi to estimate e∇θJ(πθ) using (C.1).The critic is initialized with Winit and the random signs {br}r∈[m].

C.1 Convergence of Projection-Free Neural Policy Gradient

Projection-free neural policy gradient converges to a stationary point at a sublinear rate under stated regularity and sufficiently large width and batch size. Achieving the 1/√T convergence rate requires m = Ω(R^10 · T^12), with larger width than projection-based updates.

  • Convergence guarantee: Projection-free neural policy gradient converges to a stationary point bθ satisfying ∇θJ(π_bθ) = 0 at a sublinear rate.The result concerns the sequence generated by Algorithm 3.
  • Convergence rate: εPG = O(T^-1/2 + R^3/2 · m^-1/4 · T + R^5/4 · m^-1/8 · T).The bound holds for T ≥ 4L^2 and B = Ω(σ^2) under Proposition 4.3 and Assumptions 4.5, 4.6, and C.1.
  • Width requirement: m = Ω(R^10 · T^12) yields the 1/√T convergence rate when the neural-network width and batch size are sufficiently large.This width requirement applies to the two-layer neural network.
  • Comparison with projection: Projection-free actor updates require larger width than neural policy gradient with projection to achieve the 1/√T convergence rate.The stronger width requirement is identified as the extra price of using the projection-free actor update.

C.2 Global Optimality of Projection-Free Neural Policy Gradient · D Proof of Auxiliary Results

This section establishes global-optimality guarantees for projection-free neural policy gradient, showing that expected total reward converges to the global optimum at a T^-1/4 rate for sufficiently large width and batch size. It then introduces the proof of the paper’s auxiliary results.

  • C.2 Global Optimality of Projection-Free Neural Policy Gradient: The section characterizes when projection-free neural policy gradient achieves global optimality.
  • C.2 Global Optimality of Projection-Free Neural Policy Gradient: The analysis bounds parameter-sequence suboptimality using gradient magnitude and neural-network approximation error, linking performance to representation power.
  • C.2 Global Optimality of Projection-Free Neural Policy Gradient: Theorem C.3 provides a sufficient condition for the output of projection-free neural policy gradient to be globally optimal.
  • C.2 Global Optimality of Projection-Free Neural Policy Gradient: For T ≥4L2, B = Ω(T 1/2), and m = Ω(R10 · T 12), the theorem yields a global-optimality guarantee.
  • C.2 Global Optimality of Projection-Free Neural Policy Gradient: The proof derives the guarantee by upper-bounding the expected right-hand side of the central optimality inequality over all randomness.
  • C.2 Global Optimality of Projection-Free Neural Policy Gradient: 1/T 1/4-rate: for sufficiently large width m and batch size B, expected total reward J(πθi) converges to the global optimum J(π∗).
  • D Proof of Auxiliary Results: The auxiliary-results section lays out the proofs of supporting results used elsewhere in the paper.

D.1 Proof of Proposition 3.1

The proof derives the policy’s log-gradient from its definition and feature mapping, then substitutes this expression into the policy gradient theorem and Fisher information matrix to establish Proposition 3.1.

  • D.1 Proof of Proposition 3.1: The proof starts from the policy gradient theorem and Fisher information matrix, reducing the argument to calculating ∇θ log πθ(· | ·).These are identified as the main ingredients before the policy-specific gradient calculation.
  • D.1 Proof of Proposition 3.1: Using the policy definition and feature mapping φθ, the proof obtains the log-policy gradient as a feature term minus its πθ-expectation.The feature mapping satisfies ∇θf((·, ·); θ) = φθ(·, ·), and the expectation is taken over actions sampled from πθ(· | s).

D.2 Proof of Theorem 4.9 … D.7 Proof of Lemma 5.4

The appendix proves Theorem 4.9, Inequality (4.5), Corollary 4.14, and Lemmas 5.2–5.4 by combining approximation bounds, projection arguments, neural feature estimates, and KL-divergence expansions. The derivations rely on random initialization, bounded parameter regions, feature-norm control, and Assumption 4.5 where indicated.

  • D.2 Proof of Theorem 4.9: Theorem 4.9 is established by bounding the target’s approximation error using the initial and current neural feature mappings within parameter ball B.The proof applies triangle- and Jensen-type bounds, expectations over random initialization, and separately treats the case without the assumption ubθ ∈ FR,∞.
  • D.3 Proof of Inequality (4.5): Inequality (4.5) follows from projection properties, Cauchy-Schwarz and Jensen inequalities, and the bound ∥θ − θi∥2 ≤ 2R for θ, θi ∈ B.The proof also uses τi = 1 and Proposition 3.1 before substituting the resulting estimate into the target inequality.
  • D.4 Proof of Corollary 4.14: Corollary 4.14 is derived by evaluating ϵi(T), combining bounds including B = Ω(R2 · T 2 · σ2), and applying Theorem 4.13.The displayed bound includes terms proportional to (1 + τi+1 · T 1/2) · R3/2 · m−1/4 and R5/4 · m−1/8.
  • D.6 Proof of Lemma 5.3: Lemma 5.3 is proved by decomposing the relevant squared quantity, applying Proposition 3.1, and using ∥φθi(s, a)∥2 ≤ 2 with κ from Assumption 4.5.The proof invokes Jensen and Cauchy-Schwarz inequalities and takes expectations over all randomness.
  • D.7 Proof of Lemma 5.4: Lemma 5.4 follows by expanding the KL divergence and the difference involving Li, then applying Lemma 5.1 and averaging over s ∼ ν∗(·).The resulting expression is identified with Hi from (5.21), after which (D.20) is substituted to conclude the lemma.

D.8 Proof of Lemma 5.5 · E Proof of Supporting Lemmas · E.1 Proof of Lemma D.1

The paper proves Lemma 5.5 by bounding its three right-hand-side terms through Lemmas D.1–D.3, with Lemma D.1 established using Jensen’s and Cauchy–Schwarz inequalities. Section E supplies supporting proofs, including definitions based on critic error and concentrability coefficients.

  • D.8 Proof of Lemma 5.5: Lemma 5.5 is reduced to upper bounds for three right-hand-side terms, supplied by Lemmas D.1, D.2, and D.3.The proof applies these three lemmas to equation (D.24) to complete the argument.
  • D.8 Proof of Lemma 5.5: Lemma D.1 states a bound involving concentrability coefficients from Assumption 4.11, with expectations taken over all randomness.Its detailed proof is deferred to Section E.1.
  • D.8 Proof of Lemma 5.5: Lemma D.2 provides another bound under Assumptions 4.2 and 4.12, involving the absolute constant M from Assumption 4.12.The expectations are over all randomness, and the detailed proof appears in Section E.2.
  • D.8 Proof of Lemma 5.5: Lemma D.3 gives a bound under Assumption 4.2 involving ϕ_i, ψ_i, η, R, τ_i, n, and neural-width terms m^-1/4 and m^-1/8.The coefficients ϕ_i and ψ_i come from Assumption 4.11, while ξ_i(δ_i) and ξ_i(ω_i) come from Assumption 4.10.
  • E Proof of Supporting Lemmas: Section E introduces the proofs of the supporting lemmas in Section D.It serves as the transition from the statement of the supporting results to their detailed derivations.
  • E.1 Proof of Lemma D.1: The proof of Lemma D.1 defines the critic error as ∆Q,i(s, a) = Qωi(s, a) − Qπi(s, a) for every state-action pair.This error is then used in the subsequent inequalities.
  • E.1 Proof of Lemma D.1: The Lemma D.1 derivation uses Jensen’s inequality, then applies Cauchy–Schwarz after rewriting quantities through eσ, ς_i, and σ*.The resulting bound uses Radon–Nikodym derivatives and the concentrability coefficients defined in Assumption 4.11.
  • E.1 Proof of Lemma D.1: The proof concludes by taking expectations over all randomness and thereby establishing Lemma D.1.This completes the detailed argument referenced in the proof of Lemma 5.5.

E.2 Proof of Lemma D.2

The proof establishes uniform parameter and feature bounds, controls the change in policy logits between iterations, and combines separate bounds on the two terms in (E.8) to conclude the lemma under the stated assumptions.

  • Parameter and feature bounds: The iterates remain in B, so the parameter difference satisfies ∥δ_i−θ_i∥2 ≤ 2R for every i ∈ [T].This follows recursively from θ_1 = W_init ∈ B and δ_i ∈ B.
  • Parameter and feature bounds: Because ∥φ_i(s,a)∥2 ≤ 1, the product ∥φ_i(s,a)∥2 · ∥δ_i−θ_i∥2 is at most 2R for all (s,a) ∈ S × A.The feature norm bound holds for every θ and state-action pair.
  • Bounding term (i): The logit update is bounded by η · (M_0 + 3R), uniformly over state-action pairs.The proof derives this by combining the feature and parameter bounds with the neural-network representation and the definition of M_0.
  • Bounding term (i): The proof uses Pinsker’s inequality and completion of squares to convert the logit bound into a bound involving the policy differences’ ℓ1- and ℓ2-norms.This controls the right-hand side of (E.15) uniformly over states.
  • Bounding term (ii): The second term in (E.8) is bounded using distribution-weighted Lp norms, Assumption 4.2, Lemma A.2, Cauchy-Schwarz, and expectations over all randomness.Combining the resulting estimates with the bound for term (i) completes the proof under Assumptions 4.2 and 4.12.

E.3 Proof of Lemma D.3 · F Auxilliary Lemma

The proof of Lemma D.3 decomposes the error into terms and bounds their expectations using norm constraints, concentration quantities, and standard inequalities. The auxiliary section states the performance-difference lemma and identifies the associated state-visitation measure.

  • E.3 Proof of Lemma D.3: The proof rewrites the key expression using centered actor and critic feature mappings and the policy difference π∗(· | s) − πi(· | s).The decomposition introduces δi and separates terms labeled (iii) and (iv).
  • E.3 Proof of Lemma D.3: Terms (iii) and (iv) are upper-bounded in expectation over all randomness, with Cauchy-Schwarz and Jensen’s inequalities used repeatedly.The proof treats (iii), then its components (iii.a) and (iii.b), before analyzing (iv).
  • E.3 Proof of Lemma D.3: The bounds for (iii) use Radon-Nikodym derivatives and the quantities ϕi and ψi from Assumption 4.11.The proof separately introduces dσ∗/dσi and dν∗/dνi before combining the resulting inequalities.
  • E.3 Proof of Lemma D.3: For (iii.a), the proof constrains ωi and δi to B = {α ∈ Rmd : ∥α − Winit∥2 ≤ R} and bounds the gradient-related discrepancy involving bF(θi)·δi.The analysis defines gi = Eσi[b∇J(πθi)] and applies Cauchy-Schwarz together with Assumption 4.2 and Corollary A.3.
  • E.3 Proof of Lemma D.3: For (iii.b), the proof uses ∥φ0(s, a)∥2 ≤ 2 and derives φ0(s, a)∥2 · ∥δi − ωi∥2 ≤ 4R for all (s, a) ∈ S × A.The latter inequality follows from δi, ωi ∈ B.
  • E.3 Proof of Lemma D.3: The final Lemma D.3 bound combines contributions involving ϕi, ψi, ξi(δi), and ξi(ωi), including terms proportional to η · R1/2 · τi−1 · n and m−1/4 or m−1/8.The displayed final terms include (τi+1 + 1) · R3/2 · m−1/4 and η · R5/4 · m−1/8.
  • F Auxilliary Lemma: Lemma F.1 states the Performance Difference result of Kakade and Langford (2002) for any policy π.Its proof is deferred to Kakade and Langford (2002).
  • F Auxilliary Lemma: The auxiliary lemma uses νeπ as the state visitation measure corresponding to eπ, defined in (2.3).This measure is the notation used in the performance-difference statement.
Loading 1909.01150v3…