On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift

1 Introduction

• The paper provides global theoretical footing for policy gradient methods, beyond guarantees that only establish convergence to stationary points under smoothness and gradient-estimation assumptions.It targets global optimality, approximation error from restricted policy classes, and finite-sample behavior.Source: §1 · p. 2

1.1 Our Contributions

• The analysis covers tabular policies containing the optimum and restricted differentiable stochastic policy classes that may not, characterizing computational, approximation, and sample-size properties in discounted MDPs.The function-approximation results include log-linear and broader parametric policy classes.Source: §1.1 · pp. 2, 4
• Projected gradient ascent is globally convergent because gradient domination makes every first-order stationary point approximately optimal under regularity assumptions.For softmax policies, a log-barrier regularizer prevents vanishing gradients near suboptimal deterministic policies and yields a polynomial finite-time convergence bound.Source: §1.1 · pp. 2–3
• Natural policy gradient reaches an ǫ-optimal policy in at most 2 (1−γ)2ǫ iterations, with no dependence on state or action counts or the distribution-mismatch coefficient D∞.This dimension-free rate improves related results and follows from a mirror-descent-style analysis handling policy-optimization non-concavity.Source: §1.1 · p. 4
• For restricted policy classes, the paper decomposes natural-policy-gradient error into estimation, approximation, transfer, and exploration terms, sometimes weakening dependence on worst-case density ratios.The special-case rates depend on ǫstat, ǫapprox, κ, and D∞, with κ measuring a relative feature-covariance condition.Source: §1.1 · pp. 5–6, Table 2 · p. 6
• In realizable settings, ǫapprox = 0 and a suitable universal initial distribution can make κ polynomial in feature dimension d rather than state-space size, enabling fully polynomial sample-efficient convergence.This avoids guarantees requiring dynamics-dependent C∞ or an initial distribution constructed using knowledge of the optimal policy.Source: §1.1 · p. 5

• The tabular direct-policy analysis uses Polyak-like gradient domination, extending related CPI and boosting perspectives while enabling non-convex optimization tools.This property makes stationary policies approximately optimal up to a distribution mismatch coefficient and parallels analyses for linear-quadratic regulators.Source: §2 · p. 7
• For tabular natural policy gradients, the softmax update is equivalent to MDP Experts and entropy-based mirror-descent policy iteration, but this analysis yields sharper guarantees.Related dynamic policy programming has a similar rate but an additional 1/(1 −γ) factor, while prior mirror-descent bounds also depend logarithmically on |A|.Source: §2 · p. 7
• Incremental function-approximation methods include CPI and PSDP, with PSDP enjoying improved iteration complexity; NPG and projected gradient ascent are also incremental algorithms.CPI belongs to a broader boosting-style family, while the policy-gradient methods update policies incrementally rather than making unrestricted policy changes.Source: §2 · p. 7
• Approximate dynamic programming obtains average-case error and sample guarantees under bounded concentrability, but concentrability can restrict MDP dynamics unlike the distribution-mismatch coefficient D∞.The related bounds cover fitted value and policy iteration, generalized policy iteration, and MD-MPI, whose actor-critic guarantees inherit concentrability dependencies from approximate critic updates.Source: §2 · p. 8
• For function approximation, this work uses stochastic approximation for computational and statistical analysis, including a linear-time critic-estimation method based on stochastic projected gradient ascent.Its natural actor-critic updates minimize compatible-function-approximation error through streaming Monte Carlo stochastic optimization rather than least-squares temporal-difference methods.Source: §2 · p. 8
• Unlike natural actor-critic methods that linearly approximate value functions, this approach accommodates a wide family of smoothly differentiable policy classes, including neural policies.Concurrent work studies related global-convergence, TRPO, and average-reward natural-policy-gradient settings, but differs in policy parameterization, approximation scope, or discounted formulation.Source: §2 · p. 9

MDP setting

• A finite discounted MDP consists of finite states and actions, transition probabilities, rewards in [0, 1], discount factor γ, and initial distribution ρ.Policies may be deterministic or stochastic, and V^π(ρ) is the expected discounted return from ρ, with 0 ≤ V^π(s) ≤ 1/(1−γ).Source: §3 · pp. 9–10

Objective

• The optimization goal is maximizing V^π(ρ), and a policy π⋆ exists that simultaneously maximizes value from every state.The framework also defines Q-values and advantages for policy evaluation and comparison.Source: §3 · p. 10

Policy Parameterizations

• The paper analyzes complete direct and softmax parameterizations alongside restricted log-linear and neural classes, where only agnostic performance relative to the best in-class policy may be possible.For restricted classes, the optimal policy need not be representable.Source: §3 · pp. 10–11
• Even complete direct and softmax parameterizations can produce non-concave V^{πθ}, so standard convex-optimization tools do not apply.Lemma 3.1 establishes non-concavity for both parameterizations.Source: §3 · p. 11, Figure 1 · p. 11

Policy gradients

• Policy gradients are expressed using discounted state-visitation distributions and advantage functions, but the simplex-constrained gradient identity does not hold for direct parameterization.The performance difference lemma supports comparisons between policies, while the distribution mismatch coefficient quantifies exploration difficulty between optimization and evaluation distributions.Source: §3 · pp. 11–12

4 Warmup: Constrained Tabular Parameterization

• Direct projected gradient ascent on state-action probabilities provides a simple non-convex tabular setting where gradient domination supports convergence analysis.The policy parameters are θ_s,a = π_θ(a|s), with updates projected back onto the policy simplex.Source: §4 · p. 13

4.1 Gradient Domination

• Gradient domination converts small feasible-direction gradients under an optimization distribution µ into near-optimality under any evaluation distribution ρ, subject to distribution coverage.The relevant exploration difficulty is captured by the distribution mismatch coefficient; choosing µ appropriately can circumvent strategic exploration issues.Source: §4.1 · pp. 14–15

4.2 Convergence Rates for Projected Gradient Ascent

• Projected gradient ascent achieves a best-iterate convergence guarantee by driving feasible-direction gradients toward stationarity, using the gradient-domination lemma to obtain policy-value control.The guarantee concerns the best policy among T iterates and may require evaluating O(T) policies, though evaluation need not occur at every iteration.Source: §4.2 · pp. 15–16

4.3 A Lower Bound: Vanishing Gradients and Saddle Points

• In a chain MDP, policies can have exponentially small gradients despite being substantially suboptimal, and derivatives through order O(H/log H) can also be exponentially small.The stated value gap is V⋆(s0) − V^πθ(s0) ≥ (H + 1)/8 − (H + 1)^2/3^H.Source: §4.3 · p. 16
• The lower bound shows that poor exploration can make policy-gradient methods mistake low visitation for near-optimality, while saddle-point escape results do not directly ensure global convergence.The example can yield zero sample-based gradients under random exploration, and its distribution mismatch coefficient may be infinite; the hardness targets gradient-search methods rather than all algorithms.Source: §4.3 · p. 17

5 The Softmax Tabular Parameterization

• Softmax policies are unconstrained for optimization, but deterministic optima occur only as parameters tend to infinity, causing near-deterministic policies, vanishing gradients, and slow convergence.The section therefore studies direct gradient ascent, log-barrier regularization for exploration, and natural policy gradient as three responses to these challenges.Source: §5 · pp. 17–18, §5.1 · p. 18, §5.2 · p. 19

5.1 Asymptotic Convergence, without Regularization

• With strictly positive optimization distribution µ and sufficiently small stepsize, unregularized gradient ascent converges asymptotically to the global optimum at every state.The proof handles near-deterministic policies whose gradients approach zero and relies on pointwise monotonicity of value iterates; the convergence rate remains open and may be exponentially slow.Source: §5.1 · pp. 18–19

5.2 Polynomial Convergence with Log Barrier Regularization

• Log-barrier regularization makes approximate first-order stationary points approximately globally optimal and yields polynomial convergence when regularization, accuracy, and the initial distribution are appropriately balanced.Unlike ordinary entropy, the relative-entropy barrier diverges as action probabilities approach zero, which is crucial for preventing small probabilities; polynomial convergence for entropy remains open.Source: §5.2 · pp. 20–21

5.3 Dimension-free Convergence of Natural Policy Gradient Ascent

• Natural policy gradient achieves global convergence with an iteration bound independent of the numbers of states and actions, despite the underlying non-concavity.Its softmax update is equivalent to multiplicative-weights updating, and the Fisher pseudoinverse removes dependence on the state distribution.Source: §5.3 · pp. 22–23

6 Function Approximation and Distribution Shift

• The framework treats policy optimization with restricted classes as compatible function approximation, using regression of advantages or Q-values on policy-gradient features to form approximate NPG updates.This yields a decomposition involving statistical estimation error and approximation error, with guarantees that avoid explicit worst-case dependence on the state-space size.Source: §6 · p. 25

6.1.1 Log-linear Policy Classes and Soft Policy Iteration

• For log-linear policies, NPG and Q-NPG become incremental soft-policy-iteration updates, and they are equivalent when the compatible function-approximation error is zero.The approximation error measures how well linear functions of the policy features capture the advantage function.Source: §6.1.1 · pp. 26–27

6.1.2 Neural Policy Classes

• The same NPG and Q-NPG construction extends to neural policy classes by using centered gradients of the network score function as regression features.The neural-policy updates retain the compatible-function-approximation structure while replacing linear features with gradients of fθ.Source: §6.1.2 · p. 27

6.2 Q-NPG: Performance Bounds for Log-Linear Policies

• The transfer error is evaluated under a fixed comparator-induced measure, while choosing a starting state-action distribution ν can control conditioning; a universal ν can ensure κ ≤d.For compact feature sets, such a ν can be supported on at most d^2 state-action pairs and constructed without knowing the MDP or comparator.Source: §6.2 · pp. 29–31
• Q-NPG achieves agnostic performance guarantees against an arbitrary comparator policy, with final performance governed by approximation error, excess risk, and a relative condition number.When transfer error is zero, the convergence rate is O(1/T) plus an excess-risk term; exact tabular gradients recover the corresponding tabular behavior, while faster rates require stronger approximation control.Source: §6.2 · p. 29
• Q-NPG permits zero approximation bias for correctly specified linear MDP features while also supporting misspecification with non-worst-case approximation error.The guarantees apply when ϵbias = 0 for suitable linear-MDP features and allow ϵbias ≠ 0 under model misspecification.Source: §6.2 · p. 31

6.2.1 Q-NPG Sample Complexity

• With an episodic sampling oracle, Sample Based Q-NPG run for T iterations with N gradient steps per iteration uses 2NT/(1 −γ) samples, obtaining unbiased Qπ or Aπ samples under dπ.Source: §6.2.1 · pp. 31–32

6.3 NPG: Performance Bounds for Smooth Policy Classes

• NPG extends the analysis beyond log-linear policies by assuming β-smooth log πθ(a|s) and decomposing performance into statistical error, transfer error, and relative conditioning.The main theorem allows an arbitrary comparator policy and uses a path-dependent relative condition-number assumption; direct advantage fitting avoids polynomial dependence on |A|.Source: §6.3 · pp. 33–35

6.3.1 NPG Sample Complexity

• Sample-based NPG uses stochastic projected gradient ascent with unbiased advantage estimates and requires expected total samples 2NT/(1 −γ) under the episodic sampling oracle.The guarantee assumes bounded score-function gradients, ∥∇θ log π(t)(a|s)∥2 ≤B.Source: §6.3.1 · pp. 35–36

6.4 Analysis

• The analysis first treats NPG as an update rule for arbitrary bounded weight sequences, then specializes the resulting guarantees to the main theorems.The sample-based algorithm updates policy parameters using averaged projected-gradient estimates of advantages.Source: §6.4 · pp. 36–37

6.4.1 The NPG “Regret Lemma”

• The NPG regret lemma applies to β-smooth policies initialized uniformly and bounds performance relative to a comparison policy for any bounded weight sequence.Its proof uses smoothness, the performance difference lemma, and a mirror-descent analysis inspired by Even-Dar et al. [2009].Source: §6.4.1 · pp. 37–38

6.4.2 Proofs of Theorem 6.1 and 6.2

• The proofs of Theorems 6.1 and 6.2 decompose the regret-lemma error and control its terms using log-linear score identities and relative-condition-number arguments.The derivation links the policy-gradient representation to the distribution-shift quantities appearing in the performance bounds.Source: §6.4.2 · p. 39
• The proofs bound the relevant error by decomposing it into terms controlled through first-order optimality, feasibility of w(t), and approximation to Q^(t)(s,a).Algorithm 4 keeps w(t) in W, while the proof compares w·φ(s,a) with w⋆·φ(s,a) and Q^(t)(s,a).Source: §6.4.2 · pp. 40–41
• Theorem 6.1’s proof combines bounds on the decomposed error terms using concavity of the square-root function, then substitutes the assumptions on ǫstat and ǫbias.The argument explicitly invokes the bounds from equations (25) and (26) before completing the substitution.Source: §6.4.2 · p. 40
• Both proof chains finish by substitution, with the NPG argument also using concavity of the square-root function.The final steps state that the remaining bounds follow from the stated assumptions and square-root concavity.Source: §6.4.2 · pp. 40–41
• Theorem 6.2 applies the NPG regret lemma with the chosen η, takes expectation over the iterate sequence, and uses the relative condition number together with κ and ǫstat assumptions.The NPG proof repeats the error decomposition and relies on w⋆ minimizing LA over W and w(t) remaining feasible.Source: §6.4.2 · pp. 40–41

Overall implications

• Global convergence results suggest that non-convexity is not the fundamental challenge, whereas insufficient exploration can cause convergence to sub-optimal policies through poor conditioning.Typical policy-gradient algorithms can find the best policy among those whose state-visitation distributions align adequately with the discovered policies when distribution-shifted approximation error is small.Source: §7 · p. 41

Tabular and finite-sample behavior

• In tabular settings, standard direct and softmax policy gradients can converge slowly under distribution mismatch, while exact-gradient natural policy gradient converges quickly without dimension dependence.With function approximation or finite samples, all algorithms remain affected to some degree by the exploration-related conditioning issue.Source: §7 · pp. 41–42

Function approximation

• The function-approximation guarantees are the first to allow average-case approximation errors without explicit worst-case state-space dependence.Their error decomposition makes success depend on good conditioning and low distribution-shifted approximation error, identifying this shifted error as a relevant measure of natural-policy-gradient expressivity.Source: §7 · p. 42

Sample size

• Stochastic projected gradient ascent suffices for accurate policy optimization, but variance reduction and data reuse remain important questions for improving sample efficiency and polynomial dependencies.Source: §7 · p. 42

Future directions

• Future work should remove density-ratio guarantees, develop representations robust to distribution shift, and combine policy optimization with exploration while preserving agnostic guarantees.Incremental approaches such as CPI, PSDP, and MD-MPI Geist et al. [2019] may enable improved analyses.Source: §7 · p. 42

A Proofs for Section 3

• The proof of Lemma 3.1 reduces attention to actions in states s1 and s2 because terminal-state actions do not change expected reward.States s3, s4, and s5 are terminal in the referenced MDP.Source: A Proofs for Section 3 · p. 48
• The policy parameters are represented as θ=(θa1,s1, θa2,s1, θa1,s2, θa2,s2) under the softmax parameterization.Source: A Proofs for Section 3 · p. 48
• V^(1)(s1)+V^(2)(s1)>2V^(mid)(s1), showing that V^π is non-concave.Source: A Proofs for Section 3 · p. 48
• The proof of Lemma 3.2 defines Pr^π(τ|s0=s) as the probability of observing trajectory τ from state s under policy π.Source: A Proofs for Section 3 · p. 48
• A telescoping argument rearranges the summation and cancels the V^π′(s0) term with the external −V^π′(s) term.Source: A Proofs for Section 3 · p. 48
• The remaining equality uses the tower property of conditional expectations and the definition of d^π.Source: A Proofs for Section 3 · p. 48

• First-order stationarity is measured by the largest feasible directional derivative over unit-radius perturbations of the policy simplex.A policy is ε-stationary when this maximum is at most ε.Source: §B.1 · p. 49
• When ε = 0, stationarity means the policy gradient has nonpositive inner product with every feasible movement direction in the convex probability simplex.Source: §B.1 · p. 49
• For β-smooth policy values, a projected-gradient step with small gradient mapping yields a subsequent gradient whose feasible directional derivatives are bounded by ε(ηβ + 1).The argument uses the normal and tangent cones of the product simplex.Source: §B.1 · p. 49
• Theorem 4.1’s proof establishes smoothness with β = 2γ|A|/(1−γ)^3, applies a standard projected-gradient result with η = 1/β, and then invokes Proposition B.1.The iteration count T is chosen to obtain the required ε bound.Source: §B.1 · pp. 49–50

B.2 Proofs for Section 4.3

• The Section 4.3 proof analyzes a discounted chain MDP under direct parameters, with γ = H/(H + 1) and transitions controlled by θ_s,a1.States s0 and sH+1 have only one action, so the proof focuses on parameters for states s1 through sH.Source: §B.2 · p. 50
• Strictly positive simplex-feasible parameters let the proof reduce notation to θ_s = θ_s,a1, because infinitesimal changes to other action parameters do not change policy value.The value depends only on the a1 probabilities, while derivatives must still respect the simplex constraints.Source: §B.2 · p. 51
• The proof bounds discounted transition quantities recursively and transfers those bounds to the limiting matrix M_θ, completing the key matrix lemma.The argument uses the transition recursion and conditions including p̄ ≤ 1/4.Source: §B.2 · pp. 51, 53
• For p̄ ≤ 1/4, the first part has bound 40 log(2H) −1, while the second part establishes V⋆(s0) − Vπθ(s0) ≥ (H + 1)/8 − (H + 1)2/3H.The cited proof also states that the optimal policy always chooses a1.Source: §B.2 · pp. 51, 58, 59
• Higher-order derivatives of M_θ expand into signed monomials of transition-matrix entries, with coefficients of magnitude γ^k and at most 2^k k! monomials.The induction follows from differentiating matrix entries through the chain rule, where each derivative creates two monomials.Source: §B.2 · pp. 54–55

C Proofs for Section 5

• For softmax policies, Section 5 defines trajectory probabilities from an initial state and their mixture under a state distribution μ, then states a policy-gradient structural lemma.The lemma uses trajectory indicators and is combined with the policy-gradient expression (6).Source: C Proofs for Section 5 · p. 59
• The softmax-gradient derivation substitutes the trajectory-probability identity into expression (6), with the final simplification relying on a property valid for any policy.The supplied proof passage identifies the penultimate step as the point where this general policy property is used.Source: C Proofs for Section 5 · pp. 59–60

• Policy gradient converges to the optimal policy under the softmax parameterization.This is Theorem 5.1’s stated conclusion.Source: §C.1 · p. 60
• With learning rate η ≤ (1−γ)^2, V^(t)(s) increases monotonically for every state through smooth-objective improvement.Lemma C.2 provides the monotonic-improvement property used throughout the proof.Source: §C.1 · p. 60
• The iterates V^(t)(s) and Q^(t)(s,a) converge, yielding limiting advantages that separate actions by their asymptotic value gaps.Lemma C.3 establishes existence of V^(∞)(s) and Q^(∞)(s,a), while later arguments use these limits to classify actions.Source: §C.1 · p. 61
• Suboptimal actions eventually receive vanishing probability, while the proof’s final contradiction forces the set of strictly better limiting actions to be empty.This implies V^(t)(s0) → V⋆(s0) as t → ∞ and completes the optimality proof.Source: §C.1 · pp. 62, 63, 67, 68

• Corollary 5.1 follows from Theorem 5.2 when the regularization parameter is set appropriately and ||∇θLλ(θ)||2 ≤ λ/(2|S||A|).This reduces the proof to establishing a sufficiently small gradient and bounding the iteration complexity required to reach it.Source: §C.2 · pp. 68–69
• After T iterations of unconstrained deterministic gradient ascent with stepsize 1/βλ, standard smoothness results bound the resulting optimization error.Here βλ is an upper bound on the smoothness of Lλ(θ).Source: §C.2 · p. 69
• The proof verifies that the target term (1−γ)λ2 satisfies the smoothness-based inequality, using Lemma D.4 to select βλ and λ < 1 to complete the argument.The final substitution establishes the required iteration bound and completes the proof.Source: §C.2 · p. 69

C.3 Proofs for Section 5.3

• Compatible function approximation and the Moore–Penrose pseudoinverse identify the smallest-norm least-squares solution used in Lemma 5.1.The construction follows Sutton et al. [1999] and Kakade [2001].Source: §C.3 · p. 69
• Equation (50) equates the policy-gradient expectation with (1 −γ)Fρ(θ)†∇θV^πθ(ρ), making the compatible-approximation solution proportional to the NPG update direction.Source: §C.3 · p. 69
• For softmax policies, the least-squares minimizer is determined only up to a state-dependent action-independent offset because the advantage has zero policy-weighted mean.Positivity of action probabilities ensures the relevant zero-derivative conditions apply at every state reachable under ρ.Source: §C.3 · p. 70
• Normalization cancels the state-dependent offset c_s in the softmax update, so the resulting policy is invariant to its choice and the lemma follows by setting c_s = 0.The corresponding update uses π^(t+1)(a|s) = π^t(a|s)exp(ηA^(t)(s, a)/(1 −γ) + ηc_s).Source: §C.3 · p. 70

• The section assembles smoothness guarantees for policies and value functions across the parameterizations used in the convergence analysis.These results support the paper’s treatment of smooth, non-convex optimization.Source: D Smoothness Proofs · p. 70
• For the softmax parameterization, the section derives the Hessian structure of a policy-weighted quantity using diagonal and Hadamard-product identities.The resulting expression combines derivatives of the softmax probabilities with the weighted action values.Source: D Smoothness Proofs · pp. 70–71
• A general perturbation lemma bounds how a fixed-state value changes along πα = πθ+αu by analyzing transition-matrix resolvents and their derivatives.The proof uses M(α) = (I − γeP(α))^-1, its power-series expansion, and row-sum properties of the resolvent.Source: D Smoothness Proofs · pp. 71, 73
• The established bounds yield smoothness results for value functions under the direct policy parameterization and for the log-barrier-regularized softmax objective.For the softmax value-function argument, the proof applies the general lemma with C1 = 2 and C2 = 6.Source: D Smoothness Proofs · pp. 74–76

Assumptions

• The analysis assumes a nonempty closed convex feasible set C and a proper, closed, convex-domain function f that is β-smooth on its interior.The optimal value is denoted f(x∗).Source: E Standard Optimization Results · pp. 76–77

Gradient mapping

• The gradient mapping Gη(x) is defined using the projection PC onto the feasible set C.This mapping supports the constrained gradient-descent analysis.Source: E Standard Optimization Results · p. 77

Deterministic optimization

• Under Assumption E.1, the gradient descent sequence for problem (54), using stepsize η = 1/β, has objective values F(x_t) that are non-increasing (Beck [2017]).Source: E Standard Optimization Results · p. 77
• A projected-gradient step is represented as x+ = x −ηGη(x), with the analysis involving the unit ℓ2 ball B2 and the normal cone NC.These geometric objects characterize constrained first-order behavior.Source: E Standard Optimization Results · p. 77

Stochastic optimization

• The stochastic projected-gradient method updates x_t by sampling a random v_t, with guarantees stated for convex f over a radius-B ball and bounded gradients ∥v_t∥≤ρ (Shalev-Shwartz and Ben-David [2014]).The theorem assumes x∗ minimizes f over the feasible ball and runs the method for N iterations.Source: E Standard Optimization Results · p. 77