PaperlayerView exact revision on arXiv

Source-linked AI summary

Global Optimality Guarantees For Policy Gradient Methods

Jalaj Bhandari, Daniel Russo

arXiv:1906.01786v3cs.LGstat.ML

TL;DR

Policy gradient methods optimize non-convex control objectives, yet their stationary points may be poor. This paper links policy-gradient optimization to policy iteration, establishing global-optimality guarantees and convergence-rate results under structural conditions, while identifying important scope limits.

  • Problem

    Policy gradient methods are widely understood to converge only to stationary points, with little guarantee about their quality even for simple control problems.

  • Method

    The paper connects policy-gradient objectives to structural properties of single-period policy-iteration problems and studies exact-gradient updates over parameterized policy classes.

  • Results

    The framework guarantees globally optimal stationary points for several classic control problems and yields convergence rates or optimality-gap bounds under strengthened or relaxed conditions.

  • Takeaways & Limitations

    Non-convex policy-gradient objectives can inherit favorable optimization structure from policy iteration, including global convergence guarantees and fast rates.

  • Takeaways & Limitations

    The analysis focuses on optimization landscapes and does not address exploration, policy-parameterization issues, or stochastic gradient estimators; it assumes exact gradients.

Abstract

from arXiv · show

Policy gradients methods apply to complex, poorly understood, control problems by performing stochastic gradient descent over a parameterized class of polices. Unfortunately, even for simple control problems solvable by standard dynamic programming techniques, policy gradient algorithms face non-convex optimization problems and are widely understood to converge only to a stationary point. This work identifies structural properties -- shared by several classic control problems -- that ensure the policy gradient objective function has no suboptimal stationary points despite being non-convex. When these conditions are strengthened, this objective satisfies a Polyak-lojasiewicz (gradient dominance) condition that yields convergence rates. We also provide bounds on the optimality gap of any stationary point when some of these conditions are relaxed.

1 Introduction

Policy gradient methods face non-convex objectives with no general guarantee that stationary points are good. This paper identifies structural conditions yielding global optimality, convergence rates, or optimality-gap bounds across classic control problems.

  • Motivation: Policy gradient methods can get stuck at bad local minima even when the policy class contains the optimal policy.This motivates analyzing the quality of stationary points rather than only asymptotic stationarity.
  • Approach: The paper analyzes policy gradients indirectly through structural conditions on the single-period problems solved by policy iteration.The framework connects first-order optimization of total cost with classical dynamic programming.
  • Applications: The framework covers finite MDPs, linear quadratic control with linear policies, optimal stopping with threshold policies, and finite-horizon inventory control with non-stationary base-stock policies.These examples use natural structured policy classes rather than unrestricted policy representations.
  • Main guarantee: Any stationary point is globally optimal when the relevant structural properties and mild regularity conditions hold.The result applies despite non-convexity of the policy gradient loss.
  • Scope of assumptions: The closure condition is stronger than merely containing an optimal policy, as illustrated by the bad local minimum example.The paper relates this stronger requirement to closure under policy improvement.
  • Extensions: A Polyak-Lojasiewicz condition inherited from the single-period objective yields fast global convergence for non-convex policy gradient objectives.The paper also studies finite-horizon settings and approximate closure under policy improvement, where stationary-point optimality gaps can be bounded.

2 Problem formulation

The paper formulates policy-gradient optimization over stationary policies in a Markov decision process, measuring discounted cost from an initial distribution. It connects this objective to cost-to-go functions, occupancy measures, and Bellman operators.

  • MDP formulation: An MDP is specified by state and action spaces, costs, transitions, a discount factor, and an initial distribution.The formulation assumes measurable spaces and uniformly bounded per-period costs.
  • Policies: A stationary policy maps each state to a feasible action, while randomized policies can be represented through probability-vector actions.The policy class consists of measurable stationary policies.
  • Occupancy measure: The discounted state-occupancy measure represents the discounted fraction of time spent in state-space regions and satisfies a balance equation.It can also be interpreted as a steady-state distribution for an equivalent resetting average-cost problem.
  • Objective: The discounted average cost is the objective minimized by first-order methods over a parameterized policy class ΠΘ.The paper writes ℓ(θ)=ℓ(πθ) and associates each policy with a cost-to-go function.
  • Optimality: The optimal cost-to-go function is J*(s), and minimizing the average cost is equivalent to matching it ρ-almost surely under the stated conditions.This links the policy-gradient objective to the dynamic-programming notion of optimality.
  • Bellman operators: Bellman policy and optimality operators have Jπ and J* as unique fixed points under bounded-cost assumptions.The optimality operator can be written as the pointwise minimum over policy-specific Bellman operators.

3 Background on smooth nonconvex optimization

Smooth nonconvex optimization typically guarantees convergence only to stationary points, but gradient dominance links stationarity to global optimality and supports finite-time convergence rates.

  • Convergence to stationary points: Projected gradient descent converges asymptotically to stationary points under Lipschitz-gradient or suitable sublevel-set smoothness conditions.The iterates decrease the objective and have stationary limit points.
  • Gradient dominance: Degree-one gradient dominance corresponds to µ = 0, while degree-two gradient dominance requires µ > 0.The definition uses constants c > 0 and µ ≥ 0.
  • Gradient dominance: Gradient dominance bounds the optimality gap by a measure of distance from stationarity, extending a key property of convex functions to some nonconvex functions.Any stationary point of a gradient-dominated function is globally optimal.
  • Convergence rates under gradient dominance: Under gradient dominance and smoothness, first-order methods converge to the global minimum with finite-time rates.The illustrative bounded-domain result gives an O(1/T) rate under degree-one dominance.
  • Convergence rates under gradient dominance: Projected gradient descent also admits geometric convergence for unconstrained degree-two gradient-dominated functions with Lipschitz-continuous gradients.The stated setting uses X = R^d and step size α = 1/L.

4 Motivation from linear quadratic control

Linear quadratic control provides a motivating example where the policy-gradient loss is nonconvex, yet policy iteration has tractable structure. Closure under policy improvement and an exactly solvable convex quadratic update yield global optimality of stationary policies.

  • Global optimality: The two structural properties—closure under policy improvement and an optimizable policy-iteration problem—imply that the LQ policy-gradient loss has no suboptimal stationary points.A descent direction is constructed toward a policy-iteration update for every suboptimal stable linear policy.
  • Linear quadratic control: The LQ policy-gradient loss is nonconvex, making global convergence of gradient descent unclear despite linear policies being optimal.Stable linear policies have finite cost, while unstable policies have infinite cost.
  • Policy improvement structure: Policy iteration maps a stable linear policy to another stable linear policy, so the class of linear policies is closed under policy improvement.The update selects the action minimizing Qπθ(s, a) and has lower cost-to-go.
  • Policy iteration objective: The weighted policy-iteration objective is a convex quadratic in policy parameters and therefore has no suboptimal stationary points.Under appropriate conditions on η, its solution is unique.
  • Scope boundary: The LQ example technically lies outside the basic formulation because its per-stage costs are unbounded.The authors state that Bellman-operator properties still support analogous results for stable policies.
  • Global optimality: For LQ control, a stable linear policy is stationary exactly when its cost-to-go equals the optimal cost-to-go.This establishes global optimality of every stationary point within the stable linear-policy class.
  • Generalization: The descent-direction argument relies on convexity of the policy class and policy-iteration cost, motivating a broader Condition 2 that relaxes these requirements.The argument is related to prior finite-MDP policy-improvement analyses.

5 General results

The paper infers global properties of the non-convex policy-gradient objective from single-period Bellman problems and policy-class structure. Under progressively weaker or stronger conditions, it establishes global optimality of stationary points, gradient dominance, and broader finite-horizon guarantees.

  • General framework: The analysis avoids studying the multi-period objective directly by relating policy-gradient updates to simpler weighted policy-iteration or Bellman objectives.Policy iteration solves the single-period problem to optimality, whereas policy gradients take a gradient step; this connection transfers structural properties to the full objective.
  • Closed policy classes: Under differentiability, closure under policy improvement, and Bellman-objective optimality conditions, every stationary point of the policy-gradient objective is globally optimal.Theorem 1 states that stationary points are exactly those achieving the optimal policy cost.
  • Convergence rates: If the weighted policy-iteration objective is gradient dominated, then the policy-gradient objective is also gradient dominated for closed policy classes.Theorem 2 provides this condition under the stronger Bellman regularity assumption, connecting gradient dominance to convergence-rate results for first-order methods.
  • Convergence rates: The effective concentrability coefficient κρ measures how cost-to-go errors become Bellman errors detectable from the exploratory initial distribution.This coefficient refines the role of the exploratory distribution in the gradient-dominance analysis.
  • Convergence rates: Convex and strongly convex single-period Bellman objectives yield degree-one and degree-two gradient dominance, respectively, for the policy-gradient objective.This is the content of Corollary 1 under Conditions 0 and 1.
  • Beyond closed policy classes: For finite-horizon non-stationary policies, containing an optimal policy is sufficient for every stationary point to be globally optimal, without closure under policy improvement.The corresponding result relies critically on non-stationarity; stationary policy classes can still have bad local minima even when they contain an optimal policy.

6 Examples

The examples show that structural properties of policy classes can eliminate suboptimal stationary points and yield gradient-dominance guarantees, including for tabular, regularized, nonlinear, and control settings.

  • Finite state-action MDPs: For tabular MDPs, the weighted policy iteration objective is linear in the policy, implying no suboptimal stationary points and degree-one gradient dominance.The policy class is closed under policy improvement, and the objective is continuously differentiable.
  • Finite state-action MDPs: Projected gradient descent receives an explicit convergence-rate guarantee for tabular MDPs under γ ≥ 1/3 and normalized per-period costs.The result uses natural parameterization and a stepsize depending on γ.
  • Regularized finite MDPs: Adding a strongly convex regularizer makes the weighted Bellman objective linear plus strongly convex, yielding degree-two gradient dominance.The regularizer is incorporated into the single-period costs and ensures strictly stochastic optimal policies.
  • Regularized finite MDPs: For small λ, optimizing the relative-entropy-regularized objective produces a policy near-optimal for the unregularized objective.The regularized objective converges to its own optimum under appropriate first-order methods.
  • Nonlinear parameterization: Under Conditions 1 and 2.A, nonlinear parameterizations have no suboptimal stationary points, but unregularized softmax policies can lack both minimizers and stationary points.The degeneracy arises because optimal deterministic policies are approached only as parameters diverge.
  • Linear quadratic control: For linear quadratic control, the framework gives degree-two gradient dominance over stable policies, although convergence-rate analysis is complicated by smoothness holding only on sublevel sets.The problem lies outside the general formulation because its single-period costs are not uniformly bounded.

7 Bounds on the concentrability coefficient

The concentrability coefficient connects Bellman-error bounds to policy optimality gaps, with bounds determined by state-distribution mismatch or contraction properties.

  • General bounds: The framework uses κρ to relate weighted cost-to-go error and Bellman error under the initial distribution ρ.This coefficient is needed because the Bellman operator may not be contractive in the weighted norm used for analysis.
  • General bounds: The optimality gap equals (1 −γ)∥Jπθ −J∗∥1,ρ, while policy-gradient analysis naturally weights Bellman errors by the state-occupancy measure.The relation ηπ ⪰ (1 −γ)ρ motivates measuring errors in the ρ-weighted norm.
  • General bounds: Theorem 4 provides general bounds on κρ, including bounds from contraction in a weighted norm.The contraction-based result suggests choosing ρ to align with the norm’s state weighting.
  • Distributional mismatch: κρ is bounded by a constant when the optimal-policy occupancy measure is dominated by the initial distribution, ηπ∗(M) ≤ Cρ(M).This is expressed through the Radon–Nikodym derivative and captures distributional mismatch.
  • Linear quadratic control: For linear quadratic control, the analysis restricts attention to stable policies because per-stage costs are unbounded.The resulting bounds depend on second-moment matrices and can worsen when the optimal system is barely stable.

8 Closure under approximate policy improvement.

When policy classes are only approximately closed under policy improvement, stationary points remain nearly optimal, with the gap controlled by inherent Bellman error.

  • Approximate closure: Theorem 5 states that any stationary point is nearly optimal when Conditions 0, 2.A, and 5 hold.The optimality gap is bounded as a function of inherent Bellman error and the concentrability coefficient.
  • Approximate closure: The inherent Bellman error is zero when the policy class contains all possible policies or an appropriate low-dimensional policy family.Thus, approximate closure recovers exact closure in these cases.
  • Scope and trade-offs: A richer policy class does not necessarily reduce inherent Bellman error monotonically because improvement must hold for more policies.Expressive classes such as neural-network, kernel, and state-aggregation policies motivate this relaxation.
  • State aggregation: For state aggregation, smooth costs and transitions motivate grouping nearby states, with approximation error determined by within-group discrepancies.The construction uses representative states and bounds differences in costs and transition distributions.
  • Approximate closure: Approximate closure permits a policy-iteration update whose weighted Bellman objective is within ϵ of an unconstrained update.The error is measured under the discounted state-occupancy distribution of the current policy.

9 Conclusion

The paper identifies structural MDP properties that make policy-gradient objectives globally optimizable despite non-convexity, and characterizes convergence rates.

  • Structural MDP properties guarantee global convergence of policy gradients despite non-convex objectives.The analysis connects policy gradients to policy iteration and its single-period optimization structure.
  • The framework characterizes convergence rates when stronger structural conditions hold.

B Discussion on concurrent work of Agarwal et al. [2020]

The discussion contrasts this paper’s algorithm-independent loss-landscape analysis with Agarwal et al.’s algorithm-specific natural-gradient theory, while highlighting complementary scope and limitations.

  • Approach: This paper studies when the loss landscape supports near-optimal policy search, whereas Agarwal et al. analyze specific natural-gradient actor-critic algorithms.The comparison is framed as algorithm-independent landscape analysis versus explicit algorithm analysis and convergence bounds.
  • Scope: The analysis covers infinite action spaces, structured costs, deterministic policies, linear-quadratic control, and optimal stopping.
  • Scope: The theory extends to finite-horizon problems with nonstationary policy classes and is instantiated for finite-horizon inventory control.
  • Rates: The concentration-coefficient approach yields tighter bounds for some examples than Agarwal et al.’s distribution-mismatch coefficient.
  • Limitation: The algorithm-agnostic focus leaves unregularized softmax optimization unresolved because optimal performance may require parameters to diverge.Entropy regularization is covered, but the unregularized case requires more specialized analysis.
  • Function approximation: The paper links accurate value-function approximation to closure of policy classes under policy improvement.Greedy policies induced by an approximating Q-function can remain within the policy class, exactly or approximately.

C On the necessity of an exploratory initial distribution

Exploratory initial-state coverage is essential: without it, chain MDPs can produce suboptimal local minima and exponentially small policy gradients.

  • The results critically rely on an exploratory initial distribution rather than treating exploration as a proof artifact.Without strong transition-kernel assumptions, policy gradients can have poor convergence properties without sophisticated exploration.
  • In the chain MDP, starting deterministically at the leftmost state makes the always-left policy a suboptimal local minimum.The policy class is closed under policy improvement, yet the initial distribution prevents useful occupancy of later states.
  • Policies favoring leftward movement may require exponentially many periods in the number of states to reach the rightmost state.An explicit bound shows that the policy gradient can be exponentially small in N.

D Omitted proofs.

The omitted proofs develop the dynamic-programming identities and measure-theoretic tools underlying the paper’s optimality and convergence results.

  • Bellman operators: Bellman operators provide monotonicity and γ-contraction properties for bounded cost-to-go functions.These properties connect approximation errors in cost-to-go functions to optimality gaps.
  • Occupancy measures: The discounted occupancy measure satisfies a balance equation interpretable through a restart process with restart probability 1 −γ.This provides intuition for how initial-state coverage enters the analysis.
  • Optimality: A policy minimizes the loss exactly when its cost-to-go equals the optimal cost-to-go ρ-almost surely.The proof uses nonnegativity and the fact that an integral vanishes only when the integrand is zero almost surely.
  • Performance difference: The performance difference lemma relates differences between cost-to-go functions to Bellman gaps encountered under future state occupancies.It is obtained by unrolling a recursion and using telescoping sums.
  • Policy gradients: The policy gradient theorem establishes continuous differentiability of the loss and supplies its gradient formula under the stated conditions.

D.2 Non-stationary policy classes: Proof of Theorem 3

Under Conditions 3 and 4, separability across time periods lets the proof propagate optimality backward from the terminal state. Consequently, every stationary point of the policy-gradient objective is globally optimal when the policy class contains an optimal policy.

  • Theorem 3: Theorem 3 states that every stationary point θ of ℓ has the optimal objective value when Conditions 3–4 hold and ΠΘ contains an optimal policy.Thus, the non-convex objective has no suboptimal stationary points under these assumptions.
  • Decomposition: Because Θ factorizes across periods, stationarity of ℓ is equivalent to stationarity of each single-period weighted policy-iteration objective.The policy-gradient formula and parameter-space factorization yield this decomposition.
  • Inductive proof: Backward induction starts at the absorbing terminal state, where both Jπθ and J∗ equal zero, and then establishes equality on each preceding state set.The induction uses equivalence of almost-sure statements under ρ and the discounted occupancy measure.
  • Inductive proof: Condition 4 transfers optimality from the full weighted objective to each period-specific objective because the latter inherits the separability structure.The induction identifies each θh as a stationary point of the objective weighted by J∗, which has no suboptimal stationary points by assumption.
  • Conclusion: The proof concludes Jπθ(s)=J∗(s) almost surely for every period, and Lemma 1 then implies that θ minimizes ℓ.The optimal-policy containment assumption supplies a parameter attaining J∗ at each relevant state.

E.4 LQ control

The LQ-control analysis establishes the Bellman-operator properties, stability characterization, smoothness, and stationary-point optimality needed for global policy-gradient guarantees. Stable linear policies have finite objectives, and within that class stationarity is equivalent to optimality.

  • Bellman operators: On quadratic cost-to-go functions, Bellman operators preserve quadratic structure, are monotone, and characterize optimality through J=TJ if and only if J=J∗.These properties support the later Bellman-error and performance-difference arguments.
  • Stability: For LQ control, ℓ(θ) is finite if and only if θ defines a stable linear policy.This identifies the effective domain ΘS for the objective.
  • Smoothness: The stable-policy domain ΘS is open, ℓ is twice continuously differentiable there, and every nonempty sublevel set is compact with bounded Hessian.Thus, smoothness is controlled on each objective sublevel set.
  • Stationary points: Any stable linear policy is stationary exactly when its value function equals the optimal value function.For a suboptimal stable policy, the policy-iteration direction produces a strictly negative directional derivative.
  • Stationary points: A suboptimal policy has a nonzero positive-semidefinite quadratic Bellman error, whose expectation under the positive-definite initial-state covariance is strictly positive.This positivity makes the directional derivative negative and rules out stationarity.

E.5 Optimal Stopping

For optimal stopping, threshold policies satisfy the structural conditions needed for policy-gradient analysis. The weighted policy-iteration objective has no suboptimal stationary points, with stronger gradient-dominance and smoothness results available under distributional regularity.

  • Setup: The optimal stopping model assumes continuous offer densities qx with support (ymin, ymax), positive ymin, and no initially terminal instances.These are part of the model’s stated regularity and initialization assumptions.
  • Structural conditions: Threshold policies are closed under policy improvement because each update remains a threshold policy with an updated context-specific threshold.The update uses the continuation value and respects the feasible threshold interval.
  • Stationary points: The weighted policy-iteration objective has no suboptimal stationary points for every policy in the class.This is stated as Condition 2.A and is later used for the optimal-stopping analysis.
  • Concentrability: Choosing the stationary distribution of the never-stop policy as ρ gives concentrability coefficient κρ≤1.The proof establishes contraction in the corresponding L1 norm and then applies Theorem 4.
  • Rates and smoothness: The gradient-dominance constant is β=maxx∈X,y∈Y qx(y)/minx∈X,y∈Y qx(y), and the objective has a bounded Hessian over Θ.The gradient guarantee depends on the uniformity of the offer distribution.
  • Inventory control: For finite-horizon inventory control, the weighted policy-iteration objective also has no suboptimal stationary points.Convexity of the target-inventory cost function rules out stationary points at suboptimal base-stock levels.

E.7 Linear MDPs: proof of Lemma 12

The linear-MDP proof uses a differentiable, strongly convex auxiliary function whose unique minimizer defines the relevant comparison point. Its gradient provides a strict directional-improvement relation away from that minimizer.

  • Auxiliary optimization: The auxiliary function h is differentiable and has a unique minimizer θ0.Strict convexity of the underlying function H supports uniqueness.
  • Auxiliary optimization: The relation (θ0−θ)⊤∇h(θ)=−∥θ0−θ∥2 is strictly negative whenever θ differs from θ0.This supplies a quantitative descent direction toward the unique minimizer.
  • Proof technique: The proof derives the needed expression for the optimizer map x∗(θ) by implicitly differentiating its first-order condition.The resulting derivative formula is obtained from θ+λ∇H(x∗(θ))=0.
Loading 1906.01786v3…