Source-linked AI summary
Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization
Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, Yuejie Chi
TL;DR
The paper addresses limited non-asymptotic theory for entropy-regularized NPG, which is used to encourage exploration in policy optimization. It analyzes softmax NPG in tabular discounted MDPs and establishes linear, locally super-linear, and approximate-evaluation-stable convergence. The guarantees concern the regularized MDP and rely on softmax parameterization.
Problem
Non-asymptotic theoretical understanding of policy-gradient methods remains limited, despite entropy regularization being widely used to encourage exploration and improve convergence.
Method
The paper analyzes entropy-regularized NPG with softmax parameterization in tabular discounted MDPs, connecting its update to soft policy iteration and trust region policy optimization.
Results
The method achieves linear convergence with exact evaluation, remains stable under approximate soft Q-functions up to an error floor, and becomes super-linear near the regularized optimum.
Takeaways & Limitations
The results provide non-asymptotic convergence guarantees that clarify the supported role of entropy regularization in fast NPG convergence across a wide range of learning rates.
Takeaways & Limitations
The analysis is devoted to softmax parameterization and does not immediately extend to other parameterization schemes.
Abstract
from arXiv · showhide
Natural policy gradient (NPG) methods are among the most widely used policy optimization algorithms in contemporary reinforcement learning. This class of methods is often applied in conjunction with entropy regularization -- an algorithmic scheme that encourages exploration -- and is closely related to soft policy iteration and trust region policy optimization. Despite the empirical success, the theoretical underpinnings for NPG methods remain limited even for the tabular setting. This paper develops $\textit{non-asymptotic}$ convergence guarantees for entropy-regularized NPG methods under softmax parameterization, focusing on discounted Markov decision processes (MDPs). Assuming access to exact policy evaluation, we demonstrate that the algorithm converges linearly -- or even quadratically once it enters a local region around the optimal policy -- when computing optimal value functions of the regularized MDP. Moreover, the algorithm is provably stable vis-à-vis inexactness of policy evaluation. Our convergence results accommodate a wide range of learning rates, and shed light upon the role of entropy regularization in enabling fast convergence.
1 Introduction
The paper studies entropy-regularized NPG with softmax parameterization in tabular discounted MDPs, addressing limited non-asymptotic theory for policy-gradient methods. It establishes fast convergence guarantees, including linear convergence, local super-linear convergence, and stability under approximate evaluation.
- Background and motivation: NPG preconditions policy-gradient directions with Fisher information matrices, forming a quasi-second-order optimization method intended to improve convergence.NPG is studied alongside entropy regularization, soft policy iteration, and trust region policy optimization.
- Background and motivation: Entropy regularization penalizes insufficiently stochastic policies and is used to encourage exploration and avoid undesirable flat regions.Prior empirical work suggested that regularization smooths the optimization landscape and permits larger learning rates, but theoretical support remained limited.
- This paper: The paper develops non-asymptotic convergence guarantees for entropy-regularized NPG under softmax parameterization in tabular discounted MDPs.The analysis initially assumes exact policy evaluation and presents the work as a step toward more complex settings.
- This paper: With η = (1−γ)/τ, NPG coincides with soft policy iteration and has contraction rate γ independent of τ; in a small local region, convergence becomes super-linear.The paper contrasts its O(log(1/ε)) regularized-NPG complexity with O(1/ε) for prior unregularized softmax NPG theory.
- This paper: Exact entropy-regularized NPG converges linearly for any learning rate 0 < η ≤ (1−γ)/τ when optimizing the regularized MDP.The iteration complexity has a near dimension-free feature and applies across a wide range of learning rates, including small ones.
- This paper: Approximate entropy-regularized NPG retains linear convergence before reaching an error floor that scales linearly with entrywise soft Q-function estimation error.This stability result supports future finite-sample analyses.
2 Model and algorithms
The paper studies entropy-regularized policy optimization in discounted MDPs using softmax policies and natural policy gradient updates. Its framework connects the update to soft policy iteration and trust region methods, with linear convergence in the bandit example and faster convergence under a special learning rate.
- Problem settings: The setting is a γ-discounted infinite-horizon MDP with finite state and action spaces, transition kernel P, bounded rewards, and randomized policies.A policy specifies the probability of selecting each action in each state.
- Softmax parameterization: Softmax parameterization maps logic values θ to policies in the probability simplex through πθ(a|s) proportional to exp(θ(s,a)).The paper treats policies and their parameter vectors as interchangeable when context makes the distinction clear.
- Entropy-regularized value maximization: Entropy regularization adds a policy-dependent term −τ log π(a|s) to the reward, discouraging insufficiently stochastic policies and promoting exploration.The regularization parameter satisfies τ ≥ 0, and the resulting regularized or soft value and Q-functions are used throughout.
- Optimal policies and stationary distributions: An optimal regularized policy can also be nearly optimal for the unregularized value when τ is sufficiently small.The paper states this relationship for all initial distributions ρ.
- NPG methods with entropy regularization: The entropy-regularized NPG update has a simple policy-space form under softmax parameterization, is invariant to the initial distribution ρ, and is related to TRPO and soft policy iteration.NPG uses a preconditioned gradient direction associated with controlling policy changes through KL divergence.
- A warm-up example: the bandit case: In the single-state bandit case, entropy-regularized NPG converges linearly to the optimal randomized policy, and η = 1/τ yields convergence in one iteration.The one-step choice corresponds to the soft policy iteration update and motivates its role in the general theory.
3 Main results
The paper establishes non-asymptotic convergence guarantees for entropy-regularized NPG in tabular discounted MDPs, including linear convergence, local quadratic convergence, and robustness to approximate evaluation.
- Exact entropy-regularized NPG: For any learning rate 0 < η ≤ (1−γ)/τ, exact entropy-regularized NPG converges linearly to the optimal regularized solution.The theorem is non-asymptotic, contains no hidden constants, and covers the full admissible learning-rate range.
- Exact entropy-regularized NPG: The iteration complexity is nearly dimension-free, with only a weak dependence on MDP dimensions through log C1.For fixed admissible η, complexity scales inversely with τ, while larger τ moves the target farther from the original MDP.
- Exact entropy-regularized NPG: Entropy regularization makes the optimal policy unique, enabling direct analysis of policy convergence through log policies.The same theorem also implies linear convergence of the soft value functions.
- Soft policy iteration: The SPI choice η = (1−γ)/τ achieves the best guarantee, with iteration complexity proportional to the effective horizon 1/(1−γ) up to logarithmic factors.Its contraction rate is γ and is independent of τ, recovering the iteration-complexity dependence of policy iteration.
- Scope and limitations: The guarantees target the optimal regularized MDP, so sufficiently small τ is required when the goal is an ε-optimal policy for the original MDP.The regularization approximation error can dominate optimization error, and the sample-complexity analysis remains crude with minimax optimality open.
- Approximate entropy-regularized NPG: With approximate soft Q-functions, NPG remains linearly convergent until reaching an error floor that scales linearly with the entrywise estimation error.The approximate-update theorem allows both model-based and model-free value-function estimators satisfying the stated entrywise bound.
- Quadratic convergence: In the high-accuracy regime, exact regularized NPG exhibits faster-than-linear, quadratic convergence to the soft value function.The result applies across optimization accuracies and all choices of the regularization parameter τ, but concerns the regularized objective.
4 Analysis
The analysis establishes monotonic improvement and contraction properties for entropy-regularized NPG, then uses linear-system arguments to prove convergence with exact or inexact policy evaluation.
- Performance improvement and monotonicity: For 0 < η ≤ (1 − γ)/τ, each entropy-regularized NPG iteration improves the soft value function and yields pointwise monotonicity.The improvement is quantified through the KL divergence between successive policies.
- A key contraction operator: the soft Bellman optimality operator: The soft Bellman optimality operator Tτ reduces to the ordinary operator T when τ = 0, has Q⋆τ as a fixed point, and is a γ-contraction.These properties support soft Q-value iteration with contraction rate γ.
- The SPI case: Soft policy iteration therefore converges linearly in the ℓ∞ norm toward the optimal soft Q-function.The proof combines the fixed-point and contraction properties of Tτ.
- General learning rates: For general learning rates, the error dynamics are represented by a nonnegative linear system whose spectral properties determine the contraction rate.An auxiliary sequence and a Lyapunov-like quantity control the coupled error terms.
- Approximate entropy-regularized NPG: With inexact policy evaluation, a performance-difference bound quantifies the impact of approximation error, and a related linear system tracks the resulting update errors.The approximate analysis relaxes the exact monotonicity result and controls how far soft Q-function estimates depart from monotonicity.
5 Discussions
The discussion identifies extensions beyond the paper’s current theoretical scope, including inexact gradients, sample-based evaluation, function approximation, and alternative parameterizations.
- Future directions: The framework could be extended to policy gradient methods with inexact policy gradients.The paper presents this as a direction for improving existing theory.
- Future directions: Finite-sample analysis remains open when value functions are estimated from rollout trajectories or by bootstrapping.The discussion specifically points to sample complexity for entropy-regularized NPG methods.
- Future directions: The current work is limited to tabular settings, leaving entropy-regularized NPG with function approximation for future study.The paper describes this extension as fundamentally important.
- Future directions: The paper is devoted to softmax parameterization, so other parameterization schemes remain outside its analysis.Examples mentioned include vanilla, log-linear, and neural softmax parameterizations.
A.1 Derivation of entropy-regularized NPG methods
The derivation expresses regularized policy gradients through the entropy-regularized advantage function and shows how natural-gradient updates simplify under softmax parameterization.
- Advantage function: The entropy-regularized advantage function measures the gain from taking action a instead of following policy π in state s.It enters the fundamental policy-gradient relation used throughout the derivation.
- Policy-gradient derivation: Under softmax parameterization, the gradient of the regularized value function is expressed using discounted state visitation, action probabilities, and the regularized advantage.The resulting natural-gradient search direction is invariant to the choice of state-distribution ρ.
- Policy-space update: The regularized NPG update becomes a policy-space update because the softmax representation and natural-gradient relation remove action-independent terms.This establishes equivalence between the parameter-space and policy-space update rules.
- Softmax properties: The softmax transform and its log-policy properties provide Lipschitz bounds used to control differences between policies.These bounds are derived through elementary gradient and mean-value arguments.
B Proof for the bandit case (Proposition 1)
The bandit-case proof introduces an auxiliary sequence that represents the iterated policy and supports the convergence result in Proposition 1.
- Auxiliary sequence: An auxiliary sequence ξ(t) is defined recursively to analyze the bandit-case policy updates.The construction is used to relate the sequence directly to the iterated policy.
- Policy representation: The iterated policy is proportional to ξ(t), allowing the policy sequence to be analyzed through the auxiliary recursion.The normalization converts the auxiliary vector into the policy distribution.
- Proposition 1: Properties of the auxiliary sequence, combined with the policy relation, complete the proof of Proposition 1.The argument uses the softmax bounds and the form of the optimal policy.
C.1 Proof of Lemma 1
The proof derives entropy-regularized policy and value-function identities, then combines Jensen-based bounds, monotonicity, and recursive expansions to establish the lemma’s claims.
- Regularized policy identity: Jensen’s inequality yields equality when π(·|s) ∝ exp(Q(s, ·)/τ), identifying the softmax policy associated with the soft Q-function.This equality condition directly supports the subsequent regularized policy expression.
- Operator bounds: The proof bounds operator differences using the Lipschitz property and establishes the resulting inequality for every state-action pair.The argument applies the Lipschitz property to the soft Bellman operator and concludes the bound uniformly over S × A.
- Recursive control: Recursive substitution and monotonicity control the terms in the value-function expansion, leading to the claimed bound for all (s, a) ∈ S × A.The proof separately bounds the terms, then combines them with the recursive construction.
- Auxiliary updates: The regularized update is analyzed through an auxiliary exact-update policy sequence, separating one-step perfect updates from inexact evaluation.The exact-update sequence is constructed from the current policy rather than from its previous auxiliary iterate.
- Conditions and simplification: The analysis allows step sizes satisfying 0 < η ≤ (1 − γ)/τ and uses the state-only normalization term Z(t)(s) to simplify action-dependent expressions.Because Z(t)(s) does not depend on the action, it can be rearranged or canceled in several identities.
C.6 Proof of Lemma 6
The lemma extends policy-gradient identities to entropy-regularized value functions under softmax parameterization and characterizes the Fisher-preconditioned gradient through a least-squares representation.
- Regularized policy gradient: The entropy-regularized policy-gradient derivation treats the regularized value as an unregularized value with modified rewards r(s, a) − τ log πθ(a|s).Recursive differentiation then aggregates state-action terms into the regularized advantage.
- Softmax identities: Under softmax parameterization, the gradient derivation uses the regularized advantage and the identity that action-weighted advantages sum to zero.The zero-sum identity supports the final simplification of the gradient expression.
- Natural-gradient characterization: The Fisher-preconditioned gradient is characterized as the solution to a least-squares problem involving the regularized policy-gradient quantities.The proof obtains this representation from the Fisher information matrix definition and the softmax derivative calculation.
- Statewise decomposition: The Fisher-based objective can be rewritten using a state-dependent quantity c(s), yielding a statewise expression involving the regularized advantage.The quantity c(s) is defined as an action-probability-weighted sum and is independent of the action.
D Convergence guarantees for CPI-style policy updates
This section analyzes CPI-style policy updates as conservative mixtures with the SPI-improved policy and proves their performance improvement and linear convergence properties.
- Update rule: The CPI-style update uses a parameter β ∈ (0, 1] to control the conservatism of policy updates.The convergence theorem applies to every β in this interval.
- Convergence guarantee: Theorem 4 establishes linear convergence for CPI-style updates for any 0 < β ≤ 1.The theorem states the convergence guarantee for the update rule introduced in the section.
- Performance improvement: Lemma 7 gives a performance-improvement guarantee for the CPI-style update for any distribution ρ and β ∈ (0, 1].Its proof uses the update rule, convexity of KL divergence, and Jensen’s inequality.
- Proof strategy: The proof derives the improvement relation by expanding the regularized value function, applying the CPI update, and recursively using the resulting equality.The analysis also subtracts and adds a KL-divergence term to control the update’s effect.
E Proof for approximate entropy-regularized NPG (Theorem 2)
The proof of approximate entropy-regularized NPG reduces policy-evaluation error to a linear system, then analyzes its spectrum to extract convergence guarantees.
- Proof structure: The proof first establishes the linear system in (58) and then extracts the convergence rate from that system.These are the two explicit steps organizing the proof.
- Error control: The analysis controls approximation errors using the triangle inequality, the assumed error bound, and the relation α = 1 − ητ.Taking the maximum over state-action pairs produces the uniform bound used in the recursion.
- Spectral analysis: The matrix B has eigenvalues λ1 = 1 − ητ, λ2 = α, and λ3 = 0.These eigenvalues are used to analyze the recursion governing the approximate-update error.
- Recursion bound: The recursion is combined with the non-negativity of B and the eigenvector structure to bound the first two entries of the iterate vector.The term involving v2 is dropped because its first two entries are non-positive.
- Policy-level conclusion: The resulting bounds are transferred from the auxiliary vector to log policies using the relation between π(t) and bξ(t), together with property (66).This connects the linear-system analysis back to policy-level quantities.
F Proof for local quadratic convergence (Theorem 3)
The proof derives bounds needed for local quadratic convergence by controlling visitation distributions, transition-matrix expressions, and policy-log gaps under stated conditions. These bounds are combined through the SPI update and change-of-distributions arguments to establish the claimed result.
- Visitation-probability control: Condition (30) bounds differences between discounted state-visitation probabilities using the policy’s sub-optimality gap with respect to the log policy.The corresponding lemma provides this control for policies satisfying the condition.
- Bound propagation: The SPI update rule and successive inequalities combine with Lemma 8 to produce the intermediate bound required by the proof.The derivation repeatedly uses change-of-distributions arguments before substitution into the target expression.
- Transition-matrix representation: For any policy, the induced state transition matrix Pπ is introduced to express policy-dependent state dynamics in matrix form.This representation supports the subsequent derivation of the claimed bound.
- Local condition: The proof uses ∥log π⋆−log π∥∞≤1 and an elementary logarithmic inequality to control policy differences.This assumption is used in one of the intermediate inequalities.