PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Alekh Agarwal, Sham M. Kakade, Jason D. Lee, Gaurav Mahajan

arXiv:1908.00261v5cs.LGstat.ML

TL;DR

Policy-gradient methods lacked detailed guarantees for global convergence, restricted-policy approximation, and finite-sample behavior. This paper analyzes tabular and parametric policy classes in discounted MDPs, connecting approximation under distribution shift with estimation and exploration. It establishes global and dimension-free convergence results in key tabular settings while identifying conditioning and exploration as important constraints.

  • Problem

    Existing theory largely guarantees convergence only to stationary points and leaves global optimality, restricted-policy approximation, and finite-sample behavior insufficiently characterized.

  • Method

    The paper studies first-order and natural policy-gradient methods for tabular and restricted parametric policies, using approximation and estimation decompositions under distribution shift.

  • Results

    The analysis establishes global convergence for tabular policy-gradient methods, fast dimension-free convergence for tabular NPG with exact gradients, and performance bounds governed by estimation, approximation, and conditioning quantities.

  • Takeaways & Limitations

    The results indicate that policy-optimization non-convexity is not the fundamental obstacle, whereas insufficient exploration creates conditioning effects that can produce sub-optimal convergence.

  • Takeaways & Limitations

    Polynomial convergence with the more common entropy regularizer remains an open question because the analyzed KL regularizer more aggressively prevents small probabilities.

Abstract

from arXiv · show

Policy gradient methods are among the most effective methods in challenging reinforcement learning problems with large state and/or action spaces. However, little is known about even their most basic theoretical convergence properties, including: if and how fast they converge to a globally optimal solution or how they cope with approximation error due to using a restricted class of parametric policies. This work provides provable characterizations of the computational, approximation, and sample size properties of policy gradient methods in the context of discounted Markov Decision Processes (MDPs). We focus on both: "tabular" policy parameterizations, where the optimal policy is contained in the class and where we show global convergence to the optimal policy; and parametric policy classes (considering both log-linear and neural policy classes), which may not contain the optimal policy and where we provide agnostic learning results. One central contribution of this work is in providing approximation guarantees that are average case -- which avoid explicit worst-case dependencies on the size of state space -- by making a formal connection to supervised learning under distribution shift. This characterization shows an important interplay between estimation error, approximation error, and exploration (as characterized through a precisely defined condition number).

1 Introduction

The paper develops global convergence guarantees for tabular policy-gradient methods and analyzes restricted policy classes through approximation, estimation, and exploration. Its results identify conditioning and distribution coverage as central factors in convergence and performance.

  • 1 Introduction: Policy-gradient methods are studied for global optimality, restricted-policy approximation error, and finite-sample behavior beyond stationary-point guarantees.The analysis covers discounted MDPs, tabular parameterizations, and function approximation.
  • 1 Introduction: The results suggest that insufficient exploration, rather than non-convexity itself, can drive convergence toward sub-optimal policies.The paper connects this issue to conditioning and notes related incremental algorithms as a direction for sharper analysis.
  • 1 Introduction: Gradient domination shows that first-order stationary points are approximately optimal under regularity assumptions, enabling global convergence analysis for projected gradient ascent.The method performs gradient ascent on the policy simplex and projects updates back when needed.
  • 1 Introduction: Softmax policy gradients receive global first-order convergence guarantees, although attaining deterministic optimal policies requires parameters to diverge.The exponential parameterization enforces the simplex constraint without projections.
  • 1 Introduction: At most 2/((1−γ)^2ǫ) iterations suffice for NPG to reach an ǫ-optimal policy, without dependence on state count, action count, or D∞.The proof uses a mirror-descent-style analysis and handles the non-concavity of policy optimization.
  • 1 Introduction: For restricted policy classes, performance bounds decompose estimation and approximation error while incorporating exploration through condition numbers and distribution mismatch.Average-case guarantees support supervised-learning approaches to the underlying approximation problem.

2 Related Work

Related work establishes average-case guarantees for approximate dynamic programming and connects natural policy gradient methods to actor-critic and incremental policy-improvement algorithms. This paper extends the theoretical analysis toward broader policy classes and sharper distribution-mismatch dependence.

  • Incremental algorithms: The analysis suggests incremental policy-improvement algorithms may avoid worst-case density-ratio dependence through an approximation–estimation decomposition.Examples include CPI, PSDP, and MD-MPI, while the paper identifies this extension as future work.
  • Approximate dynamic programming: Approximate dynamic programming obtains average-case error and sample guarantees when concentrability coefficients are bounded, avoiding uniformly bounded approximation errors.The paper relates its distribution mismatch coefficient D∞ to the concentrability coefficient C∞, with D∞ ≤ C∞.
  • Natural policy gradient: Natural policy gradient updates resemble natural actor-critic methods, but this work uses stochastic optimization with Monte Carlo value estimates and supports broadly differentiable policy classes.The contrast includes least-squares temporal-difference methods and linear value-function approximations used in earlier natural actor-critic analyses.
  • Global convergence: Prior global-convergence results apply to projected gradient ascent but not to softmax policy gradients, while this work analyzes the latter parameterization.The cited concurrent work also does not cover infinite-state-space function approximation.

3 Setting

The paper studies policy optimization in discounted finite MDPs using complete tabular parameterizations and restricted policy classes. It formalizes policy gradients, distribution mismatch, and non-concavity, then motivates convergence analyses for direct, softmax, and approximate policies.

  • MDP setting: The environment is a finite discounted MDP with states, actions, transitions, bounded rewards, discount factor γ, and starting distribution ρ.Rewards lie in [0,1], and the value is the expected discounted sum of future rewards.
  • Objective: The optimization objective is to find a policy maximizing expected value from the initial-state distribution, with an optimal policy simultaneously maximizing value from every state.The paper denotes the optimal policy and corresponding value and action-value functions by π⋆, V⋆, and Q⋆.
  • Policy classes: The paper considers direct and softmax policy parameterizations, both complete, alongside restricted log-linear and neural policy classes that may exclude the optimal policy.For restricted classes, the target is an agnostic guarantee relative to the best policy in the class.
  • Non-concavity: Value functions are non-concave in parameters for both direct and softmax parameterizations, so standard convex-optimization tools do not apply.Lemma 3.1 gives an MDP exhibiting this non-concavity.
  • Policy gradients: Policy gradients are expressed using discounted state visitation distributions, while the gradient expression for simplex-constrained policies does not apply to the direct parameterization.The distinction arises because direct parameterization does not explicitly maintain the zero-sum constraint on action-probability gradients.
  • Analysis tools: The performance difference lemma and distribution mismatch coefficient provide tools for relating policy values across policies and characterizing exploration difficulty.The coefficient compares visitation distributions associated with the optimization and evaluation measures, often using the optimal policy as the reference.

4 Warmup: Constrained Tabular Parameterization

The constrained tabular analysis establishes when policy-gradient stationarity implies near-optimality, while showing that inadequate exploration can produce vanishing gradients at highly suboptimal policies.

  • Constrained tabular parameterization: Projected gradient ascent on the policy simplex satisfies gradient domination, so feasible first-order stationary points yield approximately optimal policies under regularity assumptions.The result supports a global convergence analysis for direct policy parameterization.
  • Constrained tabular parameterization: The gradient may be evaluated under an optimization distribution µ while the guarantee applies to any performance distribution ρ, provided µ adequately covers an optimal policy’s state distribution.The resulting distribution mismatch coefficient captures the exploration difficulty.
  • Constrained tabular parameterization: Projected gradient ascent updates stochastic policies by taking a gradient step on V^π(µ) and projecting back onto the policy simplex.The projection is Euclidean, and the analysis provides an iteration-complexity bound for this update.
  • Constrained tabular parameterization: The convergence guarantee selects the best policy among T iterations using the average gradient norm, requiring policy evaluation across O(T) policies for the stated rates.Evaluation need not occur every iteration, but the best-policy guarantee is not obtained by averaging policies.
  • Constrained tabular parameterization: In a chain MDP, gradients and higher-order derivatives can be exponentially small in H even when the policy remains highly suboptimal, undermining saddle-point-escape arguments.Under random exploration, sample-based gradient estimates can be zero because reaching the goal has exponentially small probability in H.
  • Constrained tabular parameterization: The lower bound targets policy-gradient-like searches for small gradients rather than all algorithms, and it does not contradict the upper bound when the distribution mismatch coefficient is infinite.The chain MDP concentrates the start-state distribution on one state, allowing the mismatch coefficient to become infinite.

5 The Softmax Tabular Parameterization

The softmax parameterization avoids simplex projections but creates optimization difficulties because policies can become nearly deterministic and gradients can vanish. The paper establishes asymptotic global convergence, polynomial convergence with log-barrier regularization, and dimension-free convergence for natural policy gradient under stated conditions.

  • Softmax parameterization: The softmax parameterization enforces the simplex constraint through unconstrained exponential parameters, but the resulting optimization problem remains generally non-concave.Its practical advantage is that standard unconstrained optimization algorithms can be used.
  • Asymptotic convergence: Near-deterministic softmax policies can have gradients close to 0 because probabilities scale exponentially with the parameters.The analysis must therefore handle parameter magnitudes diverging as some action probabilities approach zero.
  • Asymptotic convergence: Under strictly positive µ and η ≤ (1−γ)^3/8, gradient ascent satisfies V^(t)(s) → V⋆(s) for every state as t →∞.The proof uses pointwise monotonicity of values, limiting value and action-value quantities, and a contradiction argument for suboptimal actions.
  • Polynomial convergence with log-barrier regularization: Log-barrier regularization keeps action probabilities from becoming too small and converts approximate first-order stationarity into approximate global optimality when λ is sufficiently small.The resulting polynomial guarantee depends on balancing λ with the desired accuracy and on the initial distribution µ.
  • Polynomial convergence with log-barrier regularization: The polynomial convergence rate is specific to the aggressive probability control of the log-barrier or relative-entropy regularizer; whether common entropy regularization achieves such a rate remains open.Entropy is bounded between 0 and log |A|, whereas relative entropy diverges as action probabilities approach zero.
  • Dimension-free convergence of natural policy gradient ascent: Natural policy gradient updates become multiplicative-weights updates over actions, with the Fisher pseudoinverse canceling the state-distribution dependence.This yields a convergence rate with no dependence on the number of states, number of actions, or distribution mismatch coefficient D∞.

6 Function Approximation and Distribution Shift

The paper analyzes policy-gradient methods with restricted policy classes, showing how approximation, estimation, transfer error, and conditioning determine performance under distribution shift.

  • Parametric policy classes may exclude optimal policies, motivating function-approximation analysis for log-linear and neural policies.
  • NPG and Q-NPG admit approximate, sample-based updates whose performance reflects both statistical estimation error and function-class approximation error.
  • Transfer error is measured relative to a comparator policy’s fixed state-action distribution, rather than requiring worst-case state-space dependencies.
  • Q-NPG: Q-NPG bounds disentangle estimation error from approximation error but additionally depend on distribution mismatch through a condition number.
  • Q-NPG: A suitable state-action distribution can achieve κ ≤ d using support on at most d^2 state-action pairs, based only on feature knowledge.
  • NPG: NPG avoids polynomial dependence on |A| in its rate, unlike Q-NPG, because Q-NPG must also control advantage-estimation error.

7 Discussion

The discussion concludes that policy-gradient optimization can globally converge, while approximation and finite-sample performance remain governed by exploration-related conditioning and distribution shift.

  • Global convergence results indicate that non-convexity is not the fundamental challenge for typical policy-gradient variants.
  • Insufficient exploration can cause convergence to sub-optimal policies, an effect characterized technically through conditioning.
  • In tabular settings with exact gradients, standard policy gradients can be slow under distribution mismatch, whereas natural policy gradient has fast dimension-free convergence.
  • Function approximation guarantees permit average-case errors without explicit worst-case state-space dependence by using distribution-shifted approximation error.
  • Accurate policy optimization is possible with stochastic projected gradient ascent, but variance reduction and data reuse remain open sample-efficiency questions.
  • Future work includes removing density-ratio guarantees, understanding representations robust to distribution shift, and combining policy optimization with exploration.

A Proofs for Section 3

The appendix proves non-concavity for a softmax policy example by comparing values at two endpoint parameterizations with their midpoint.

  • The proof restricts attention to actions in states s1 and s2 because terminal-state actions do not change expected reward.
  • For the softmax parameterization, the policy parameters are represented as a tuple indexed by action and state.
  • The inequality V^(1)(s1) + V^(2)(s1) > 2V^(mid)(s1) establishes that V^π is non-concave.
  • A telescoping trajectory argument rewrites the value difference using trajectory probabilities and the state-visitation distribution d^π.

B.1 Proofs for Section 4.2

The appendix defines first-order stationarity on the policy simplex and connects projected-gradient mappings to approximate stationarity through smoothness.

  • Definitions: First-order stationarity is defined by bounding the largest feasible directional improvement over perturbations in the policy simplex.
  • Definitions: When ε = 0, stationarity means the gradient has nonpositive inner product with every feasible direction.
  • Projected-gradient analysis: The projected-gradient update uses a gradient mapping, and a small mapping norm implies approximate first-order stationarity after accounting for smoothness.
  • Projected-gradient analysis: For the value function, β-smoothness enables standard gradient-mapping bounds with a step size selected using ηβ = 1.
  • Projected-gradient analysis: The resulting analysis bounds the best stationarity measure over the iterates through a minimum over t = 0,1,...,T.

B.2 Proofs for Section 4.3

The proof analyzes a direct policy parameterization on a chain-like MDP, derives bounds on discounted transition probabilities and their derivatives, and uses them to establish a suboptimality lower bound.

  • Setup: The direct parameterization assigns action probabilities to states s1 through sH, with the remaining action probability determined by normalization.States s0 and sH+1 have only one action, so their parameters are omitted.
  • Setup: The transition matrix moves between neighboring states according to the policy probabilities, with deterministic transitions from s0 and sH+1.The matrix entries depend on θs,a1 and 1 − θs,a1 for intermediate states.
  • Gradient control: The value function at s0 depends only on the state parameters θs,a1, allowing the transition and derivative bounds to control its gradient tensor.The argument assumes all policy parameters are strictly positive so infinitesimal changes preserve the relevant parameterization behavior.
  • Result: V⋆(s0) − V^πθ(s0) ≥ (H + 1)/8 − (H + 1)2/3H for the specified policy and MDP.This establishes the claimed suboptimality lower bound relative to the optimal policy parameters θ⋆.
  • Transition bounds: The proof bounds normalized discounted reachability probabilities recursively across all time steps and state pairs.These bounds apply to the limiting matrix Mθ as well.
  • Derivative bounds: Higher-order derivatives of Mθ are expanded into monomials whose coefficients and counts are controlled inductively.Each differentiation produces two monomials, while coefficients acquire factors of γ.

C.1 Proofs for Section 5.1

The proof studies softmax policy-gradient updates by showing monotonic value improvement, convergence of value and action-value iterates, and elimination of suboptimal actions, yielding convergence to an optimal policy.

  • Optimality: The proof therefore establishes that policy gradient converges to an optimal policy for the softmax parameterization.This is the theorem-level conclusion for the updates under the stated assumptions.
  • Monotonic improvement: For learning rate η ≤ (1 − γ)^2, the updates monotonically improve V^(t)(s) for every state.The argument uses smoothness of the relevant objective and gradient ascent with an appropriately bounded step size.
  • Limit behavior: The iterates V^(t)(s) and Q^(t)(s,a) converge to limiting values V^(∞)(s) and Q^(∞)(s).Monotonicity and boundedness support the convergence argument.
  • Suboptimal actions: Actions separated from the limiting value by a positive advantage gap eventually receive vanishing softmax probability.After a finite threshold, their advantages are negative and their probabilities decrease toward zero.
  • Action dominance: The proof tracks relative probabilities and parameter differences among actions to show that favorable actions dominate persistently over time.Monotonic comparisons and bounded parameter behavior are used to analyze action groups.
  • Optimality: The set of actions with strictly positive limiting advantage must be empty, so V^(t)(s0) converges to V⋆(s0).Assuming such an action exists leads to a contradiction with the gradient and update bounds.

C.2 Proofs for Section 5.2

The proof derives an iteration bound for obtaining a sufficiently small regularized objective gradient, then converts that condition into the desired optimality gap.

  • Stationarity condition: The target optimality gap follows when the regularized gradient norm satisfies ∥∇θLλ(θ)∥2 ≤ λ/(2|S||A|).The proof uses Theorem 5.2 to connect this stationarity condition to the desired gap.
  • Iteration complexity: Gradient ascent with stepsize 1/βλ provides the iteration-complexity bound for reducing the gradient of the smooth objective Lλ.Here βλ is an upper bound on the smoothness of Lλ.
  • Iteration complexity: The proof completes the result by selecting βλ using the smoothness bound from Lemma D.4 and applying the condition λ < 1.This choice ensures the required gradient inequality after the stated number of iterations.

C.3 Proofs for Section 5.3

The proof connects compatible function approximation to the natural policy-gradient direction and shows that state-dependent offsets in the least-squares solution do not affect the resulting softmax policy update.

  • Compatible approximation: Compatible function approximation defines a least-squares error for approximating the policy advantage function.The construction follows the compatible-function-approximation framework invoked in prior policy-gradient analyses.
  • Natural policy gradient: The minimum-norm approximation solution is proportional to the natural policy-gradient update direction.The relationship is expressed through the discounted Fisher matrix pseudoinverse and the gradient of the value function.
  • Compatible approximation: For softmax policies, the advantage function achieves zero approximation loss because action-probability-weighted advantages sum to zero at each state.The minimum-norm issue is handled by characterizing the remaining solution ambiguity.
  • Update invariance: The least-squares minimizer is defined only up to a state-dependent action-independent offset.Such offsets can be represented by constants cs for each state.
  • Update invariance: The normalization factor cancels these offsets, making the resulting softmax policy update invariant to the particular offset choice.The proof therefore sets cs ≡ 0 without changing the policy update.

D Smoothness Proofs

This section develops smoothness results needed for convergence analysis across direct and softmax policy parameterizations. It uses a general perturbation lemma, transition-matrix expansions, and derivative bounds to establish smoothness of value functions and regularized objectives.

  • Overview: The analysis first collects smoothness results for policies and value functions required by the convergence guarantees.These results apply to multiple policy parameterizations and support the later optimization analysis.
  • Parameterization-specific results: The softmax analysis also bounds the smoothness of the regularizer using Hadamard products and diagonal-matrix notation.These algebraic identities support the smoothness proof for the log-barrier-regularized objective.
  • General perturbation lemma: A general perturbation lemma analyzes how a policy and its value change along π_α = π_{θ+αu}.The proof studies the induced state-action transition matrix, its inverse representation, and derivatives with respect to α.
  • General perturbation lemma: The transition-matrix inverse is controlled through a power-series expansion whose rows are positive and sum to 1/(1 − γ).This property supplies bounds used to complete the perturbation argument.
  • Parameterization-specific results: The section applies the lemma to establish smoothness for direct-policy value functions and the log-barrier-regularized softmax objective.The direct-parameterization and softmax results are stated as separate lemmas.
  • Parameterization-specific results: For softmax policies, the proof bounds value-function derivatives using state-specific parameters, action-probability derivatives, and constants C1 = 2 and C2 = 6.The resulting bound is extended from individual starting states to arbitrary starting-state distributions.

E Standard Optimization Results

This section reviews optimization results used in the paper’s proofs for constrained smooth optimization and stochastic projected gradient descent. It introduces the gradient mapping and records monotonicity and update results under convexity and smoothness assumptions.

  • Problem setup: The section formulates a constrained optimization problem and identifies the unit ℓ2 ball and normal cone used in its analysis.The feasible set is represented by a nonempty closed convex set C.
  • Assumptions: The main assumptions require f to be proper and closed, have a convex domain, and be β-smooth over the interior of its domain.These conditions underpin the deterministic and stochastic optimization results.
  • Gradient mapping: The gradient mapping G_η(x) is defined using projection onto the feasible set C.The projection operator P_C maps the update back to the constraint set.
  • Deterministic guarantees: With stepsize η = 1/β, gradient descent generates a non-increasing sequence of objective values F(x_t).This monotonicity result is cited from the standard smooth constrained optimization literature.
  • Gradient-step analysis: A separate result analyzes one projected gradient step x+ = x − ηG_η(x) under the same smoothness assumption.This one-step inequality is used as a standard ingredient in convergence proofs.
  • Stochastic projected gradient descent: The stochastic projected gradient descent algorithm updates each iterate using a sampled stochastic vector.The section subsequently states conditions controlling these stochastic updates.
Loading 1908.00261v5…