PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Global Convergence Rates of Softmax Policy Gradient Methods

Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, Dale Schuurmans

arXiv:2005.06392v3cs.LGstat.ML

TL;DR

The paper studies unresolved global convergence-rate questions for true-gradient softmax policy gradient in the tabular setting, including whether entropy regularization provides a rigorous optimization advantage. It analyzes softmax and entropy-regularized updates using Łojasiewicz-type arguments and lower bounds, finding O(1/t) convergence without regularization versus linear O(e^-c·t) convergence with it. The rate separation is explained through non-uniform Łojasiewicz degree.

  • Problem

    Prior work established asymptotic softmax policy-gradient convergence but no rate, while the entropy-regularized rate and the theoretical basis for entropy’s empirical benefit remained open.

  • Method

    The paper combines non-uniform Łojasiewicz inequalities, optimal-action probability bounds, convergence lower bounds, and analysis of entropy-regularized gradient updates.

  • Results

    O(1/t) convergence holds for true-gradient softmax policy gradient, whereas entropy regularization yields linear O(e^-c·t) convergence toward the softmax optimal policy.

  • Takeaways & Limitations

    Entropy regularization improves policy optimization convergence rates even with the true gradient, with the separation explained by non-uniform Łojasiewicz degree.

  • Takeaways & Limitations

    The analysis is conducted in the tabular setting, and some arguments involve dependence on initialization or assumptions about optimal-action probabilities.

Abstract

from arXiv · show

We make three contributions toward better understanding policy gradient methods in the tabular setting. First, we show that with the true gradient, policy gradient with a softmax parametrization converges at a $O(1/t)$ rate, with constants depending on the problem and initialization. This result significantly expands the recent asymptotic convergence results. The analysis relies on two findings: that the softmax policy gradient satisfies a Łojasiewicz inequality, and the minimum probability of an optimal action during optimization can be bounded in terms of its initial value. Second, we analyze entropy regularized policy gradient and show that it enjoys a significantly faster linear convergence rate $O(e^{-c \cdot t})$ toward softmax optimal policy $(c > 0)$. This result resolves an open question in the recent literature. Finally, combining the above two results and additional new $Ω(1/t)$ lower bound results, we explain how entropy regularization improves policy optimization, even with the true gradient, from the perspective of convergence rate. The separation of rates is further explained using the notion of non-uniform Łojasiewicz degree. These results provide a theoretical understanding of the impact of entropy and corroborate existing empirical studies.

1. Introduction

The paper addresses unresolved convergence-rate questions for softmax policy gradient methods in the tabular setting, including whether entropy regularization yields a rigorous optimization advantage. It establishes O(1/t) convergence without regularization and linear convergence with entropy regularization, explaining the separation through non-uniform Łojasiewicz degree.

  • Open questions: The paper asks for convergence rates of softmax policy gradient, entropy-regularized softmax policy gradient, and the optimization effect of entropy regularization.Previous work established asymptotic convergence for softmax policy gradient but gave no rate, while the entropy-regularized rate was an open question.
  • Main contributions: O(1/t) convergence holds for true-gradient softmax policy gradient, with constants depending on the problem and initialization.The proof uses a non-uniform Łojasiewicz-type inequality and bounds the minimum optimal-action probability using its initial value.
  • Main contributions: O(e^-t) linear convergence holds for entropy-regularized policy gradient toward the softmax optimal policy, faster than the unregularized rate.The analysis relates entropy-regularized updates to a contraction operator whose factor depends on the current policy.
  • Main contributions: An Ω(1/t) lower bound shows that the unregularized O(1/t) upper bound is unimprovable apart from constant factors.This establishes a rate separation between softmax policy gradient without regularization and the entropy-regularized method.
  • Main contributions: The non-uniform Łojasiewicz degree is nonpositive without regularization and equals 1/2 for maximum-entropy reward with regularization.The change in degree explains why the corresponding convergence rates differ.

2. Notations and Settings

This section establishes notation for finite tabular Markov decision processes, policies, values, advantages, rewards, and softmax parameterizations. It also introduces the Jacobian matrix central to the softmax analysis and recalls smoothness.

  • MDP setting: A finite MDP consists of finite state and action spaces, transitions, rewards, and a discount factor.The paper assumes one-step rewards lie in [0, 1].
  • MDP setting: The value of a policy is defined over states and can be averaged under an initial-state distribution.The notation includes V^π(ρ) and the optimal value V^*(ρ).
  • MDP setting: The advantage function is A^π(s, a) = Q^π(s, a) − V^π(s), and the paper also defines the policy’s discounted state distribution.These quantities support the policy-gradient formulation.
  • Softmax parametrization: The softmax transform converts state-action logits into probability distributions over actions.For each state, π_θ(·|s) is obtained by applying softmax to θ(s, ·).
  • Softmax parametrization: The H matrix H(π) = diag(π) − ππ^⊤ is the Jacobian of the softmax map from logits to the simplex.This matrix plays a central role in the paper’s analysis.
  • Analytical preliminaries: Smoothness is recalled as a property of functions defined on a parameter space with respect to the ℓ2 norm.The paper uses the standard convex-analysis definition.

3. Policy Gradient

The paper analyzes softmax policy gradient in tabular bandits and MDPs, establishing global convergence rates through smoothness, Łojasiewicz inequalities, and bounds on optimal-action probabilities. It also characterizes initialization effects and stationary-point failures when some states have zero sampling probability.

  • Policy Gradient Setup: Policy search parametrizes policies with finite-dimensional vectors and updates those parameters incrementally.The section focuses on softmax logits in the tabular setting.
  • Policy Gradient Setup: The softmax expected-reward objective can be non-concave in the parameter vector, so smoothness alone does not ensure convergence to a global optimum.Łojasiewicz inequalities provide gradient dominance that prevents vanishing gradients before reaching a maximum.
  • Convergence Rate: The analysis uses a non-uniform Łojasiewicz inequality whose constant depends on optimal-action probability, plus a positive lower bound on that probability during optimization.The lower bound is controlled by initialization; after some time, the optimal-action probability is increasing.
  • Convergence Rate: Uniform initialization gives an optimal-action probability lower bound of 1/K, while a matching Ω(1/t) lower bound makes the O(1/t) rate unimprovable up to constants.The general rate uses η = 2/5; the uniform-initialization theorem strengthens the dependence on the probability bound.
  • Scope and Failure Cases: If the initial state distribution assigns zero probability to a state, gradient ascent can converge to an attracting stationary point whose policy is not optimal.The construction uses state-wise bandit problems with a unique optimal action in each state.
  • Convergence Rate: O(1/t) value convergence holds for softmax policy gradient in bandits and MDPs, with constants depending on the problem and initialization.For MDPs, the result is presented as the first convergence-rate result for softmax policy gradient.

4. Entropy Regularized Policy Gradient

Entropy-regularized softmax policy gradient converges linearly toward a temperature-dependent softmax optimum, substantially faster than unregularized policy gradient. The analysis uses contraction, smoothness, Łojasiewicz inequalities, and lower bounds on action probabilities, while addressing regularization bias.

  • Bandit case: Entropy regularization changes the target to the softmax optimum π*_τ, with bias disappearing as τ → 0.For fixed τ > 0, the bandit optimum is π*_τ := softmax(r/τ), rather than the unregularized optimum.
  • Bandit case: The update behaves like a parameter-dependent contraction, with the contraction factor depending on the current policy.This contraction perspective explains why the regularized method can achieve a faster rate than the O(1/t) analysis obtained by the direct approach.
  • General MDPs: Uniformly positive action probabilities support the linear-rate proof in both bandits and general MDPs.The bandit result gives min_a π_θt(a) ≥ c, while the general-MDP result gives inf_t≥1 min_s,a π_θt(a|s) > 0.
  • General MDPs: The entropy-regularized objective is smooth and satisfies a non-uniform Łojasiewicz inequality whose sub-optimality gap appears under a square root.The smoothness constant is (4 + 8 log A)/(1 − γ)^3, and the stronger gradient signal supports exponential convergence.
  • General MDPs: O(e^-t) convergence holds for entropy-regularized softmax policy gradient toward the softmax optimal policy.The general-MDP theorem uses a stepsize depending on γ, τ, and the number of actions, with an exponential factor e^-C(t-1).
  • Controlling the bias: A two-stage method first uses entropy regularization and then removes it to combine fast initialization with optimization of the unregularized objective.The first phase requires O(e^(1/τ) · log((τ+1)/Δ)) iterations, after which unregularized updates apply.

5. Does Entropy Regularization Really Help?

The paper establishes that unregularized softmax policy gradient cannot improve beyond an Ω(1/t) lower bound, then explains the entropy advantage through non-uniform Łojasiewicz degree. Entropy raises the degree to 1/2, while the unregularized expected-reward objective has degree zero.

  • Interpretation: The paper interprets entropy regularization as an optimization aid, while noting that its exploration is not sensitive to epistemic uncertainty.The authors distinguish this optimization explanation from the more common exploration-based account.
  • Lower bounds: Ω(1/t) lower bounds hold for softmax policy gradient in bandits and general MDPs, making the O(1/t) upper rate tight up to constants.The general-MDP lower bound applies for sufficiently large t and learning rates η_t ∈ (0, 1].
  • Non-uniform Łojasiewicz degree: A larger Łojasiewicz degree is associated with faster convergence rates for methods relying on gradient information.The paper extends this optimization perspective to the non-uniform degree used in its analysis.
  • Non-uniform Łojasiewicz degree: The unregularized expected-reward objective has non-uniform Łojasiewicz degree zero.The associated constant is C(θ) = π_θ(a*), and the paper notes that this result alone does not rule out faster rates from other techniques.
  • Non-uniform Łojasiewicz degree: Entropy regularization gives the expected-reward objective a non-uniform Łojasiewicz degree of at least 1/2.The paper connects this higher degree to the faster convergence rate of the entropy-regularized method.

6. Conclusions and Future Work

The paper concludes that tabular softmax policy gradient has a Θ(1/t) rate without entropy and a linear rate with entropy regularization. Its gradient analysis builds on the policy gradient theorem and softmax structure.

  • Conclusions: Without entropy regularization, softmax policy gradient achieves a Θ(1/t) rate, with dependence on initial parameters.The paper describes this rate as faster than previously obtained but highlights the unpleasant initialization dependence.
  • Conclusions: With entropy regularization, the convergence rate becomes linear, with the exponent constant influenced by initialization.The regularized method converges toward the entropy-regularized optimum rather than directly to the unregularized optimum.
  • Gradient analysis: The softmax policy-gradient derivative is proportional to discounted state visitation, action probability, and the policy advantage.The tabular expression uses d^πθ_μ(s), π_θ(a|s), and A^πθ(s,a), scaled by 1/(1 − γ).
  • Gradient analysis: The entropy-regularized gradient has the same structural form with a soft advantage function replacing the ordinary advantage.This is the gradient representation used for the entropy-regularized objective.

A.1.2. PROOFS FOR SOFTMAX PARAMETRIZATION IN BANDITS

The bandit proof develops smoothness and non-uniform Łojasiewicz tools, establishes a positive lower bound on the optimal-action probability, and derives convergence bounds under arbitrary and uniform initialization.

  • Proof ingredients: The bandit expected-reward objective can be non-concave in the softmax parameters.This motivates using gradient-dominance and smoothness arguments rather than concavity alone.
  • Proof ingredients: A non-uniform Łojasiewicz inequality relates the gradient to policy sub-optimality for softmax bandits.The analysis assumes a unique maximizing action for the main subsequent results, while also stating a multiple-optima version.
  • Optimal-action probability: The optimal-action probability remains bounded away from zero under the update with η = 2/5.The lower bound depends on the reward problem and initialization, but not on time.
  • Optimal-action probability: After a finite time, the optimal-action probability is increasing; under uniform initialization, it is increasing from the first iteration.This yields π_θt(a*) ≥ 1/K for all t under uniform initialization.
  • Convergence bounds: Uniform initialization gives a bound of 5K^2/t on reward sub-optimality.The theorem uses η = 2/5 and π_θ1(a) = 1/K for every action.

A.1.3. PROOFS FOR SOFTMAX PARAMETRIZATION IN MDPS

The softmax-MDP analysis establishes smoothness, a positive lower bound on optimal-action probabilities, and the resulting convergence machinery for policy-gradient updates.

  • Smoothness: 8/(1 −γ)^3-smoothness bounds the value objective V^πθ(ρ) used in the softmax-MDP analysis.The same smoothness holds for each state value and their expectation under ρ.
  • Optimal-action probabilities: c := inf_s∈S,t≥1 π_θt(a*(s)|s) > 0 ensures optimal actions retain uniformly positive probability throughout optimization.The proof reaches a region where optimal-action probabilities are nondecreasing and remains there after subsequent gradient updates.
  • Rate theorem: The softmax-MDP theorem uses η = (1 −γ)^3/8 together with the positive constant c from the optimal-action probability lemma.These ingredients support the stated global convergence-rate theorem for Algorithm 1.
  • Optimal-action probabilities: The lower bound reduces the minimum optimal-action probability over all iterations to a finite initial segment ending at t0.Specifically, inf_s,t π_θt(a*(s)|s) = min_1≤t≤t0 min_s π_θt(a*(s)|s).
  • Gradient comparison: The proof uses gradient components proportional to π_θt(a|s)[Q^πθt(s,a) − V^πθt(s)] to compare optimal and nonoptimal actions.The comparison is combined with the positive optimal value gap Δ*(s) and update monotonicity.

A.2.3. PROOFS FOR MDPS AND ENTROPY REGULARIZATION

The entropy-regularized MDP proof establishes smoothness and interior convergence, then identifies the limit as the softmax-optimal policy and derives a linear rate.

  • Smoothness: (4 + 8 log A)/(1 −γ)^3-smoothness controls the entropy term H(ρ, πθ) in the regularized objective.The statewise entropy and its expectation under ρ share this smoothness constant.
  • Interior convergence: Entropy regularization keeps every action probability uniformly positive: c := inf_t≥1 min_s,a π_θt(a|s) > 0.The argument uses monotone improvement of the augmented value and rules out convergence of any action probability to zero.
  • Limit characterization: The limiting policy lies in the interior of the probability simplex, and its zero gradient identifies it as the softmax-optimal policy π*.At the limit, the gradient vanishes and the entropy-regularized optimality characterization applies.
  • Linear convergence: η = (1 −γ)^3/(8 + τ(4 + 8 log A)) is the theorem’s prescribed step size for entropy-regularized softmax policy gradient.The resulting rate statement holds for all t ≥ 1 with a constant C > 0.
  • Linear convergence: O(e^{-C(t−1)}) bounds the regularized soft sub-optimality for all t ≥ 1.The bound also includes the factor (1 + τ log A)/(1 −γ)^2.

A.2.4. PROOFS FOR TWO-STAGE AND DECAYING ENTROPY REGULARIZATION

The two-stage and decaying-regularization proofs analyze how entropy can first accelerate optimization and then be reduced while retaining quantitative convergence guarantees.

  • Two-stage regularization: t1 ∈ O(e^{1/τ} · log((τ+1)/(τ∆))) iterations suffice for the regularized first stage in the two-stage procedure.The procedure then turns off regularization and applies Update 1 for t2 additional iterations.
  • Two-stage regularization: The two-stage method switches from Update 2 to Update 1 after the regularized stage, with t = t1 + t2 and C ∈ [1/K, 1).The supplied theorem passages state the stage transition and parameter range for C.
  • Decaying entropy regularization: τ_t = α·∆/log t defines the decaying entropy schedule for t ≥ 2, with η_t = 1/τ_t.The analysis separates the schedule into a decaying part and a tracking part.
  • Lower bounds: Theorem 9 establishes an Ω(1/t) lower bound for one-state softmax policy-gradient optimization with η_t ∈ (0, 1].The lower bound is derived for rewards r ∈ [0,1]^K and sufficiently large t.
  • Lower bounds: Theorem 10 extends the Ω(1/t) lower bound to arbitrary MDPs under Algorithm 1 with η_t ∈ (0, 1].The extension follows because one-state MDPs are special cases of general MDPs.

A.3.3. PROOFS FOR THE NON-UNIFORM ŁOJASIEWICZ DEGREE

The non-uniform Łojasiewicz-degree analysis distinguishes unregularized and entropy-regularized objectives through different relationships between gradient norm and sub-optimality.

  • Unregularized objective: 0 is the non-uniform Łojasiewicz degree of θ ↦ E_a∼πθ[r(a)] when C(θ) = πθ(a*).The proposition states that no positive degree is possible for the unregularized expected-reward map.
  • Unregularized objective: The unregularized degree-zero result follows from a small-ϵ example with πθ = (1 − 3ϵ, 2ϵ, ϵ)^⊤ and rewards (0.6, 0.4, 0.2)^⊤.The example contradicts any assumed positive degree as ϵ becomes small.
  • Entropy-regularized objective: 1/2 is the Łojasiewicz degree of θ ↦ E_a∼πθ[r(a) − τ log πθ(a)] under entropy regularization.The associated constant depends on τ and min_a πθ(a).
  • Rate implications: The entropy-regularized degree of 1/2 is sufficient for the linear O(e^{-t}) convergence rate stated in the paper.The paper connects the changed degree to the improved convergence-rate relationship.

B. Miscellaneous Extra Supporting Results

The supporting results establish spectral and smoothness properties of the softmax policy-gradient analysis, together with performance-difference and Łojasiewicz tools. These lemmas connect policy probabilities, value gaps, and update behavior.

  • The ascent lemma applies to smooth functions and underpins improvement guarantees for gradient updates.
  • Performance-difference lemmas relate value differences between policies to their action-value and advantage quantities.
  • The matrix H(π) = diag(π) − ππ⊤ has a zero eigenvalue and non-negative eigenvalues.
  • The spectrum of H(π) is bounded by ordered policy probabilities, linking its eigenvalues to the minimum action probability.
  • Softmax-logit inequalities and the reversed Łojasiewicz result connect parameter changes and policy probabilities to optimal value gaps.

C. Sub-optimality Guarantees for Other Entropy-Based RL Methods

The paper derives sub-optimality guarantees for entropy-based RL methods by connecting their update objectives and consistency violations to soft performance measures. These connections cover SAC's soft policy improvement and PCL's path consistency.

  • Soft policy improvement: Small soft policy improvement implies small sub-optimality for the entropy-regularized policy update used by SAC.
  • Path inconsistency: Soft optimal policies satisfy the consistency conditions, while the paper relates violations during learning to sub-optimality.
  • Path inconsistency: Path inconsistency measures how a learned policy violates the soft consistency conditions during learning.
  • Path inconsistency: The path inconsistency objective used in PCL guarantees small sub-optimality when minimized.

D. Simulation Results

Simulations support the paper's convergence-rate claims in randomly initialized one-state MDPs and illustrate the practical effect of entropy regularization. The experiments show inverse-time behavior without regularization and faster behavior with entropy.

  • Softmax policy gradient: δ_t = C′/t is supported by softmax policy-gradient simulations, whose log-log slope approaches −1.
  • Entropy-regularized policy gradient: O(e^{-c · t}) behavior is supported by entropy-regularized simulations, where log soft sub-optimality approaches a straight line.
  • Entropy-regularized policy gradient: The minimum action probability approaches constant values during entropy-regularized optimization, verifying the corresponding lemma.
  • Bad initializations: 8 × 10^6 iterations are required around a sub-optimal corner under a bad softmax initialization, whereas entropy regularization converges significantly faster.
  • Decaying entropy regularization: O(1/t^{1/α}) is the partial rate in Theorem 8 for decaying temperature τ_t = α·Δ log t.
Loading 2005.06392v3…