Beyond Softmax and Entropy: Convergence Rates of Policy Gradients with f-SoftArgmax Parameterization & Coupled Regularization

Policy gradient methods are known to be highly sensitive to the choice of policy parameterization. In particular, the widely used softmax parameterization can induce ill-conditioned optimization landscapes and lead to exponentially slow convergence. Although this can be mitigated by preconditioning, this solution is often computationally expensive. Instead, we propose replacing the softmax with an alternative family of policy parameterizations based on the generalized $f$-$\textit{softargmax}$. We further advocate coupling this parameterization with a regularizer induced by the same $f$-divergence, which improves the optimization landscape and ensures that the resulting regularized objective satisfies a Polyak--Łojasiewicz inequality. Leveraging this structure, we establish the $\textit{first explicit non-asymptotic last-iterate convergence guarantees}$ for stochastic policy gradient methods for finite MDPs $\textit{without any form of preconditioning}$. We also derive sample-complexity bounds for the unregularized problem and show that $f$-PG, with Tsallis divergences achieves $\textit{polynomial sample complexity}$ in contrast to the exponential complexity incurred by the standard softmax parameterization.