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

Reinforcement learning (RL) has evolved from basic tabular methods to complex continuous control algorithms, driven by applications in robotics, autonomous vehicles, and AI. Early theoretical work, such as Sutton et al. (1999), established policy gradient methods for finite MDPs, but their convergence properties in continuous spaces remained less understood. Recent advances like entropy-regularized RL (Haarnoja et al., 2017; 2018) improved exploration and stability, with softmax policies becoming standard. However, most convergence guarantees were limited to finite or linear models, leaving a gap for high-dimensional, nonlinear environments. The challenge lies in analyzing the non-convex landscape and geometric degeneracies that arise in continuous settings, especially with function approximation. This paper builds on prior work (Agarwal et al., 2020; Mei et al., 2020), extending the theoretical framework to general continuous spaces by integrating geometric analysis of feature spaces and Lyapunov methods, thus addressing a critical gap in RL theory.

The core problem is establishing global convergence guarantees for policy gradient methods in continuous state-action spaces under entropy regularization. Existing results are mostly confined to finite or linear models, with limited understanding of how geometric properties of feature representations influence convergence. The main bottleneck is ensuring the positive definiteness of matrices like Fisher information and covariance matrices along the gradient flow, which is crucial for exponential convergence. Moreover, the non-convexity of the objective and potential degeneracy of the regularizer pose significant analytical challenges. Addressing these issues is vital for deploying RL algorithms in real-world, high-dimensional environments where function approximation and complex feature spaces are unavoidable.

The key innovations include: 1) establishing a non-uniform PŁ inequality tailored for continuous spaces, which relates suboptimality to gradient norms with a state-dependent constant; 2) analyzing the geometric structure of feature spaces—full affine span and simplex-valued—to prove the unboundedness of the regularizer and spectral bounds of key matrices; 3) applying Lyapunov function techniques to systematically derive exponential convergence rates. These advances overcome the limitations of prior tabular analyses, providing a comprehensive theoretical foundation for policy gradient convergence in high-dimensional, nonlinear environments. The approach uniquely combines spectral matrix bounds with geometric feature analysis, enabling rigorous guarantees in complex settings.

• �� Model policies as log-linear softmax functions with linear feature approximation, parameterized by \( heta\). • Under Qπτ-realizability, derive a non-uniform PŁ inequality linking suboptimality to the gradient norm with a state-dependent constant. • Analyze the spectral properties of Fisher information matrices and feature covariance matrices under two regimes: full affine span and simplex-valued features. • Prove the regularizer’s radial unboundedness in these regimes, ensuring the eigenvalues of key matrices stay bounded away from zero along the gradient flow. • Use Lyapunov functions based on the value function to establish exponential decay of suboptimality. • Demonstrate that under geometric conditions, the constant in the PŁ inequality can be uniformly bounded, guaranteeing linear convergence.

Simulations in synthetic continuous environments validate the theoretical exponential convergence. Different feature bases, such as Fourier and Bernstein polynomials, are tested to verify the spectral bounds and regularizer unboundedness. The experiments measure the suboptimality gap over time, confirming the predicted exponential decay rate. Sensitivity analyses explore the impact of feature choice and initial conditions on convergence speed. Results show that when geometric assumptions are satisfied, the policy’s suboptimality reduces by orders of magnitude within hundreds of iterations, aligning with theoretical predictions. These experiments demonstrate the practical applicability of the theory to high-dimensional, nonlinear RL problems.

The main result proves that, under Qπτ-realizability and geometric feature conditions, the policy gradient flow converges exponentially with rate \(O(e^{-Ct})\). The spectral analysis guarantees the Fisher information matrix’s smallest eigenvalue remains bounded below, ensuring the positive definiteness necessary for exponential convergence. Numerical experiments confirm the theoretical rate, with suboptimality decreasing by over 90% within a few hundred steps. The analysis applies to both full affine span and simplex-valued features, broadening the scope of convergence guarantees in continuous RL. These findings significantly extend prior tabular results, providing a rigorous foundation for high-dimensional policy optimization.

The theoretical framework applies directly to continuous control tasks such as robotic manipulation, autonomous driving, and industrial automation. By ensuring exponential convergence under geometric feature conditions, it enables designing more stable and efficient RL algorithms for real-world applications. The insights into feature space geometry guide feature engineering and basis selection, improving sample efficiency and robustness. Combining this theory with deep neural network approximations could lead to scalable, provably convergent RL systems capable of handling complex, high-dimensional environments, accelerating deployment in industry and research.

The analysis assumes Qπτ-realizability and specific geometric conditions on features, which may not always hold in practice. Exact evaluation assumptions limit direct applicability to noisy, real-world data. The spectral bounds involve computationally intensive matrix analysis, challenging scalability. The framework does not explicitly address model errors, partial observability, or stochasticity, which are common in real environments. Future work should focus on relaxing assumptions, extending to approximate and deep RL, and validating in real-world scenarios to improve robustness and practicality.