Research map / Optimization / Nonconvex and smooth optimization

Global linear convergence of entropy-regularized softmax policy gradient beyond tabular MDPs

NeurIPS 2026 · Optimization › Nonconvex and smooth optimization · approach: Coordinate and Adam convergence analysis · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows global linear convergence of the entropy-regularized softmax policy gradient flow with log-linear policies in continuous state/action MDPs, via a non-uniform PL inequality and radial unboundedness of the KL regularizer under full-affine-span or simplex features.

Problem

Global convergence of policy gradient for entropy-regularized infinite-horizon MDPs with continuous state and action spaces using log-linear softmax policies with linear function approximation; prior guarantees are essentially tabular.

Approach

Establishes a non-uniform Polyak-Łojasiewicz inequality under Q-realizability and uses the KL divergence to the reference measure as a Lyapunov function (radially unbounded under feature conditions), so log-densities stay bounded and the FIM smallest eigenvalue is bounded below along the gradient flow, yielding O(e^{-Ct}) suboptimality decay.

Key results

• Non-uniform PL inequality holds for log-linear softmax policies under Q-realizability with constant C_R(theta) depending on the FIM smallest eigenvalue.
• Under full affine span features, the KL regularizer is radially unbounded and sup_t C_R(theta_t) is bounded, giving V(theta_t)-V* <= exp(-t/C_theta0) (V(theta_0)-V*).
• For simplex features, radial unboundedness holds in the subspace orthogonal to the all-ones vector, yielding the same linear rate.

Surprising findings

• Hat (P1 finite element) features on simplex fail radial unboundedness of KL when the maximizer set has positive measure, with KL converging to log 3 along a diverging direction.

Limitations

• Analysis is for continuous-time gradient flow with exact evaluations and Q-realizability assumed.
• Requires maximizer-set measure-zero assumptions on features and a positive definite FIM at initialization.

Experimental setup

Metrics: suboptimality of regularized value

Baselines: tabular softmax policy gradient natural policy gradient with log-linear policies

Builds on: Mei et al. softmax policy gradient global convergence Lan policy mirror descent Kerimkulov fisher-rao flow entropy regularized MDP

Closest papers by meaning

• Beyond Stationarity: Convergence Analysis of Stochastic Softmax Policy Gradient Methods (ICLR 2024 · similarity 0.88)
• Structure Matters: Dynamic Policy Gradient (NeurIPS 2025 · similarity 0.88)
• Accelerated Policy Gradient for s-rectangular Robust MDPs with Large State Spaces (ICML 2024 · similarity 0.87)
• Deterministic Policy Gradient Primal-Dual Methods for Continuous-Space Constrained MDPs (AAAI 2025 · similarity 0.87)
• Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs (NeurIPS 2026 · similarity 0.86)
• On the Convergence of Single-Timescale Actor-Critic (NeurIPS 2025 · similarity 0.86)