# Rethinking the Global Convergence of Softmax Policy Gradient with Linear Function Approximation: The Case of Multi-Armed Bandits

arXiv: https://arxiv.org/abs/2505.03155 · HTML: https://mlsanity.com/paper/2505.03155/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 May 2025.

## Built on by (most cited first, 4 of 4)

- [Why GRPO Needs Normalization: A Local-Curvature Perspective on Adaptive Gradients](https://mlsanity.com/paper/2601.23135/) (2026)
- [Convergence of an actor-critic gradient flow for entropy regularised MDPs in general spaces](https://mlsanity.com/paper/2510.14898/) (2025)
- [When Errors Can Be Beneficial: A Categorization of Imperfect Rewards for Policy Gradient](https://mlsanity.com/paper/2604.25872/) (2026)
- [Global linear convergence of entropy-regularized softmax policy gradient beyond tabular MDPs](https://mlsanity.com/paper/2605.24939/) (2026)

## Abstract (arXiv)

Policy gradient (PG) methods have played an essential role in the empirical successes of reinforcement learning. In order to handle large state-action spaces, PG methods are typically used with function approximation. In this setting, the approximation error in modeling problem-dependent quantities is a key notion for characterizing the global convergence of PG methods. We study Softmax PG with linear function approximation (referred to as textttLin-SPG) and demonstrate that the approximation error is irrelevant to the algorithm's global convergence even in the bandit setting. Consequently, we rethink the effect of approximation error in the standard stochastic multi-armed bandit problem. We first identify the conditions on the policy feature representation that can guarantee the asymptotic global convergence of textttLin-SPG. Under these feature conditions, we further prove that T iterations of textttLin-SPG with a problem-specific learning rate result in an O(1/T) convergence to the optimal policy. Moreover, we prove that textttLin-SPG with an arbitrary constant learning rate can ensure asymptotic convergence to the optimal policy.